The greedy algorithm I use is a little bit more complicated but you can catch what I mean more easily.

The algorithm goes as follows:

1.binary search part. Use binary search to find how much lecture notes you can read In the two days.

1. greedy part for the checking function of binary search. Iterate through each note from x to 1. For note i, If you can put it in the day which has fewer hours to spend, It's always better. So we just iterate through. If we find a note that we can't put it in any of the days, we try a smaller amount.

2. To get the answer uses the same algorithm as the checking part. Just iterate from x to 1, and put the note in the day which has fewer hours to spend. If you didn't get this, I may post my code:44658856

Wait please, they're gonna be translated

There are two possibilities:

1. All lecture notes are in the first day, this case is trivial.

2. When we tried to put the x-th lecture note into the first day, there was only w free hours. Let's put the lecture w instead then. Now the first day is full, and since a + b is at least x(x + 1) / 2, the second day is long enough to read the remaining notes.

I'm not a native English speaker, sorry for my poor explanation.

It's easy to find that if we get the first two items of the series t, we will be able to determinate whether it's possible to build a t meets the conditions.

Then we will try every possibilities for t₁ and t₂, we will be able to find the relationships between t and a, b.

Finally we try every possibilities for the first two items (not so much, though), and find if it is possible to meet every a_i and b_i (we have one item of t_i, and it's easy to determinate whether it's OK for the other items).

My solution using DP is described as following: Let dp[i][j][0] standing for the possibility of i-th number of t is j, and dp[i][j][1] means which number is the number before i-th number of j, we can easily iterate k from 0 to 3 for the last number of t, and we can get:

Specially, we have dp[1][0][0] = dp[1][1][0] = dp[1][2][0] = dp[1][3][0] = 1.

Then we can judge if dp[n][·][0] is 1, for YES or NO, and if the answer is YES, use dp[n][·][1] with a stack to print t.

Just use simple depth-first-search. The hint means(I think) that you when you brute force the problem, you will not get a TLE.

There is some interesting observation.

there exist at most one value of t(i) for specific value of t(i+1),a(i),b(i).

formally, if there exist t(i) such that t(i) | t(i+1) == a(i) and t(i)&t(i+1)==b(i) then t(i) can be one of the {0,1,2,3}. it means that the equations t(i) | t(i+1) == a(i), t(i) & t(i+1) == b(i) has exactly one solution of t(i) if we know the value of t(i+1),a(i),b(i) or doesn't exist.

you can see this fact using my below code. just run the code and you will see that observation. ~~~~~

include<bits/stdc++.h>

using namespace std;

int main(){ for(int i = 0;i<=3;i++){ // values of a(i)

for(int j = 0;j<=3;j++){ // values of b(i)

        for(int k = 0;k<=3;k++){ // values of t(i+1)

            cout << i << " " << j << " " << k << " -> ";

            for(int l = 0;l<=3;l++){ // possible values of t(i) 
                if((k & l )== j && ((k|l) == i)){
                    cout << l << " ";
                }
            }
            cout << endl;
        }
    }
}
return 0;

} ~~~~~

now simply take t(n) as 0,1,2,3 one by one and find t(n-1),t(n-2),t(n-3)... if there exist sequence for some t(n) then print it otherwise change the value of t(n)..

see this for full code (c++)

sorry for my bad english. Please,right me if i'm wrong.

I'm not a native English speaker, sorry for my poor explanation.

There is something interesting about Bitwise operation:a^b=(a|b)-(a&b).

So let c[i]=a[i]-b[i],then just let t[1]=0~4 ,and calculate the others t by array c.After this,just judge the array t if or not satisfy the conditions

i agree

I used something bfs-liked instead , I have the list of last-minimum block at that length then(For each row there can only be at most 1 element so this list will never exceed n) name A.

Considering this example

bcc
caa
ggg

We know that the first character must be 'b' , second character must be 'c' , BUT WE DO NOT KNOW IF THE 'c' IS FROM (1,2) or (2,1) , so after we append 'c' to answer our A must contain both (1,2) and (2,1) for future use.

For the next length each block in A can generate 2 more blocks. For the sake of simplicity i used std::set name B to store it to get rid of duplicate blocks and auto sort for me.Then the next character of the answer is value of the first block in the set(set sorted for me). So I get all the blocks from B which has the value equal to the minimum block back into A and repeat until we reached the answer's length.

This way I do not need to store all the string length but only 1 letter for each block in list A. So the total memory used for this step never exceeds O(n) I guess...

Sorry for my bad English

it can be but it won't increase the count of lectures. ex: a = 9, b = 12 output: 2 3 6 4 1 2 4 5 but for a = 10 and b = 12 output: 2 3 7 4 1 2 4 5 OR 2 3 6 4 1 2 4 5 here the sum of lecture notes is exactly a+b but it doesn't affect the count.

You can run bruteforce

If you have >= 8, you can get rid of a 1 in any position.

eg:

A)

0 0 0 1 0 0 0 0

Can be done with:

1 0 1 0 1 0 0 0
0 0 1 0 1 0 1 0 
1 0 0 1 0 0 1 0

B)

0 0 1 0 0 0 0 0 

Can be done with:

0 0 1 1 1 0 0 0

thus creating 2 instances of (A)

C)

0 1 0 0 0 0 0 0

Can be done with:

0 1 0 0 1 0 0 1
0 0 0 0 1 1 1 0
0 0 0 0 0 1 1 1

Similarly, D)

1 0 0 0 0 0 0 0

Can be done with:

1 0 0 1 0 0 1 0
0 0 0 1 1 1 0 0
0 0 0 0 1 1 1 0

Ones on the right hand side are of course symmetrical

for(i=max(a,b);i>=0;i--) { if(((i*(i+1))/2)<=a+b) break; } this part gives TLE; reduce this through binary_search or directly use quadratic formula;

LOL fmqjpt we just learned this stuff

long is 32-bit on Codeforces but 64-bit on Ideone. Use long long instead.

As a contestant you don't have to prove anything, but as the editorialist, I felt responsible for doing this.

Even for 5 5 1 the answer is already 20 > 17 as the number of border cells

It's possible (the solutions won't be rejudged, though). Moreover, if you happen to mean all AC submissions of Div2.E and during the contest, then more tests have already been added.