There is a separate round for div1 and div2.

where is the contest "GP of Korea"?

On Sunday? :o

In many Chinese senior high schools, Saturday and Sunday are school time. ( >﹏<。)～

Они проводятся в одно и тоже время: расписание

%%%

Just go back to sleep after the contest :)

Really good time for Chinese users :)

Yes, this one killed me too

20 7
3 6
5 2
......*
.****.*
.****.*
....*.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**.**.*
**....*
*******

47

for those who used a single queue.

UPD: It seems that not everyone used a single queue failed on this test.

So the correct answer for asasas is aaasss, isn't it asasas better? First one has 8 palindrom substrings and the second one has 12.

what is the correct approach to this problem?

Deque is enough, thought

0-1 bfs

I also got RE 8.

Let dp(i) be the maximum length of a journey starting at position i.

Then, dp(i) ≥ x iff there exists such j that i + x ≥ j, dp(j) ≥ x - 1 and s[j, j + x) matches either s[i, i + x) or s[i + 1, i + x + 1).

You can get different and solutions with the following observation:

There exists an optimal journey such that these conditions hold:

1) The maximal length of a string in the journey is .

2) The difference in lengths of two consecutive strings in the journey will always be 1.

Mine didn't pass but maybe someone passed with such a solution.

My solution is . Not sure if it will pass.

I am going to assume the string to be reversed.This way the strings in a journey are going to be increasing in length.

We can prove that there always exists an optimal answer when t_i has length i. Now, let dp_i be the largest possible length, such that the last string ends at position i. Note that if we can have a valid length l ending at i, we can also have a valid length l - 1, so it makes sense to define such a dp state.

We can binary search on dp_i. For a length l, the second last string is either same as s_{i - l + 1... i - 1} or the same as s_{i - l + 2...i}. We find the rightmost such string which doesn't intersect the last string, and check if this string could be used according to the dp state.

Finding the rightmost possible second last string can be done using persistent segment tree in . Basically, we have a range on the rank in suffix array the secondlast string can belong to, and a maxmium possible rightmost index for the secondlast string as the constraints.

Not at all. It can be solved in O(nm).

Think of solution.

The time limit is too strict, possibly due to recursion and stack size.

As far as I understand you did a dfs and checked the conditions and you dont visit the same place twice. However consider this

.....

.*.**

.x.**

x is where you are initially.

lets say you can go left at most once and right at most twice.

Then if you go left and go up twice and go right twice you will mark (0,2) as visited and when you come there again from (2,1) -> (2,2) -> (1,2) -> (0,2) you wont continue since it (0,2) is visited however you went right only once and if you continued you could go right.

Probably something like 1 black and 29 white.

Yeah I was getting wrong answer on pretest 10

n = 30, jury mostly assigns colors randomly.

However there is a small twist: in all of jury tests (except for sample) if it is possible to assign a color, such that it makes impossible to separate points later jury will always do that :).

answer is just sorted s. if N_x is number of occurrences of x in s. then number of palindrome substrings because first and last letter of palindrome must be same. on the other hand this number is achieved when s is sorted.

I 100% agree. Missed that sweet tooth — one candy case for 30 minutes during contest...

Well, while I will agree that D had hard technichal part, I not very much agree with your complaints on C.

You just needed to come up with cute binarysearch-like construction and the implementation is very short. If the problem was obvious to you -- just get AC in 5 mins and move on!

For me div1C was not trivial, and had a lot of challenges, not just "implement binary search". I don't think the geometrical construction was obvious at all.

(edited) dfs won't work, because you can end up in a square with "wastefully expended left/right moves". Meaning, you could end up in the same square later with fewer left/right moves. What do you do at this point? If you reprocess the square and start doing dfs again from it, you will TLE for sure. If you don't reprocess the square, you might get WA if later on you fail to reach some square because you had wastefully expended left/right moves earlier.

edit 2: or maybe dfs will work if you can do dfs in such an order that you never wastefully expend left/right moves?

Consider you started from vertex 'X' and at some point you are at vertex 'Y'

DFS ensures that you visit every vertex only once so you won't come to vertex 'Y' again. But as the graph formed might be cyclic i.e. there can be multiple ways to reach a vertex 'Y' from 'X' and there can be a possibility that there is some shorter path to 'Y' that you'll miss.

PS: Dijkstra :)

My solution in python:

def ans():
    n = int(input())
    c = bin(n).count("1")
    ans = pow(2, c)

    print(ans)

tc = int(input())
for _ in range(tc):
    ans()

There goes my hopes of entering div1 :(

You are very welcome :)

WOW, and my solution failed!

Actually it could be O ( N ). Flash sort!

Impossible

It was a bit... unexpected to us.

We held a presolving of the moscow team olympiad, from which the problems are. And most of the teams got accepted all problems except problem corresponding to Div1F.

So I was even worrying whether our Div1D and Div1E are a bit too easy.

Just go left, straight up and down, then go right. You can visit all the free cell. 0-1 bfs can solve this problem. Because moving up and down costs 0, you should push one colomn into the queue at the same time when visiting a new cell.

Use binary search! Put x somewhere to the middle (from 1 to 999999999) and fix it (x=3, for example) and try (3,0) (save the color). Next try (3,500000000). If these two point have the same color next point you should try is (3, 750000000) if colors are different next point should be (3, 250000000). Beware of edges cases: one with all points with the same color and when another one only one color is different 44313158 (very bad code, sorry)