vector<vector<int64_t>> sequence = {
  {1,1,1,1,1,1,1,1,1,1,1,1},
  {1,0,2,0,4,0,8,0,16,0,32,0},
  {1,2,6,14,37,92,236,596,1517,3846,9770,24794}, // next is 62953
  {1,0,14,0,154,0,1696,0,18684,0,205832,0}, // next is 2267544
};

The solution is a linear recurrence. Output is multiplied by 2.

Edited by author 16.01.2020 16:32

I wrote a stupid solution and got wa32. Help please!

In my case this test may help you

16 19
1 2
2 3
3 4
4 5
5 1
1 6
6 7
7 8
8 9
9 10
10 6
5 11
11 12
12 13
13 4
3 14
14 15
15 16
16 2

The sequence of contraction affects the solution if you do not repeat the process after release the blossom.

if you contract (6,7,8,9,10), (4,5,11,12,13), (2,3,14,15,16) first
   you get maximum matching.
but if you contract (1,2,3,4,5) first and don't repeat the process after release it
   you don't get to the maximum.

Hope this helps.

Edited by author 13.01.2020 19:23

Edited by author 13.01.2020 19:23

import java.util.*;
public class LuckyNumber{
 public static void main(String args[]){
Scanner in = new Scanner(System.in);
int x = in.nextInt();
 int a1,a2,a3,b1,b2,b3;
a1 = x/100000; a2 = (x/10000)%10; a3 = (x/1000)%10;
b1 = (x/100)%10; b2 = (x/10)%10; b3 = x%10;
     if((a1+a2+a3) == (b1+b2+b3)) System.out.println("Lucky Number");
 else if(a1+a2+a3-(b1+b2+b3)>1 ||(b1+b2+b3)-(a1+a2+a3)>1) {
     System.out.println("prostoi bilet");
 }
else System.out.println("Lucky Number budet sleduwii ili prediduwi bilet");
     }
        }

Input:
2
2 1 2
2 1 2
My output: YES
Answer: NO

Rejudge pls!

On #1 test my program output:
4
4 5 1 6
with code: cout<<4<<endl<<4<<" "<<5<<" "<<1<<" "<<6
but get wrong answer. Why?

What is 5 test ?

if test 50000 300 300
My solution takes about 1.9 seconds (time library). the test fails.

almost all the time spent on summarizing lists:

"ncalls  tottime  percall  cumtime  percall filename:lineno(function)"
"99402    1.773    0.000    1.773    0.000  {built-in method builtins.sum}"

Maybe there is a way to more quickly summarize than the built-in function "sum"?

Edited by author 12.12.2019 15:42

Edited by author 12.12.2019 15:42

Edited by author 12.12.2019 15:42

What is WA11?
P.S. subfactorial func is correct
P.P.S. Admins, is it possible there are some bugs here?

Edited by author 29.02.2016 01:26

How can i fix WA18? Im solving using greedy algo

50

39
1 33 11 22 44 4 28 14 42 21 7 35 5 25 50 10 20 40 8 32 16 48 24 12 36 18 6 30 15 45 9 27 3 39 13 26 2 34 17


21

17
1 16 8 4 20 10 5 15 3 9 18 6 12 2 14 7 21

Can you guys share your approach ( and proof if possible ) because mine, though AC, is not very certain. I rely on greedy approach which output pairs with maximum number and minimum number.

Use sort and find min and max after output each pair.
Quite slow, 0.14s :)

What is test 20?

Try this test:
5
2 10
2 4
3 4
6 9
7 8
11
1
2
3
4
5
6
7
8
9
10
11

Answer:
-1
2
3
3
1
4
5
5
4
1
-1

#include <iostream>

using namespace std;
long long maxi,sum=1,sum1=1,n,a,b,i,v[100000],v1[100000];
int main()
{
    cin>>n>>a>>b;
    if(a>b)
        maxi=a;
    else
        maxi=b;
    v[maxi]=1;
    v1[maxi]=1;
    for(i=maxi+1;i<n+maxi;i++)
    {
        v[i]=sum1;
        v1[i]=sum;
        sum=sum+v[i]-v[i-a];
        sum1=sum1+v1[i]-v1[i-b];
    }
    cout<<sum+sum1;

    return 0;
}

What's this test??
My code:
#include <string>
#include <algorithm>
#include <iostream>
#define N 2222
#define MOD 1000000007ll

using namespace std;

long long f[N][N],d[N][N];
int n,m;
string s1,s2;

void init(){
    getline(cin,s1);
    getline(cin,s2);
    n=s1.length(),m=s2.length();
}

int main(){
    init();
    for (int i=0;i<=n;i++) d[i][0]=i;
    for (int i=0;i<=m;i++) d[0][i]=i;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            if (s1[i-1]==s2[j-1]) d[i][j]=d[i-1][j-1]+1;
            else d[i][j]=min(d[i-1][j],d[i][j-1])+1;
    for (int i=0;i<=n;i++) f[i][0]=1;
    for (int i=0;i<=m;i++) f[0][i]=1;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++){
            if (d[i][j]==i || d[i][j]==j) f[i][j]=1;
            else{
                if (s1[i-1]==s2[j-1]) f[i][j]=f[i-1][j-1];
                else f[i][j]=f[i-1][j]+f[i][j-1];
            }
            f[i][j]%=MOD;
        }
    cout<<f[n][m]<<endl;
}