There can never be too many rounds! :)

I think of contests as opportunities of improvement; you should too :)

2 rounds who ?

try 4 :v

http://mirror.codeforces.com/blog/entry/49236

Has anyone ever told you you look like Russel from Up? :)

By clicking " register now " in top right of this page/ home page ..

click Contest from the bar in the top then you will find this contest click register

You look like you might need to take a break.

Errr...That means you ARE already registered and dont need to register any more...do you need help to un-register or what? :P

Yeah, I think it's to make up for all the unrated rounds we had last month.

I hope no one

There should be a coding weak every few months or so...where we get a competition each day of the week!

(Or will it be too much? )

all the contests are rated unless it is mentioned as unrated.

hura first stop commenting from fake account

yes but not for me bro

is it?

Yes, same problem, I couldn't submit for the past 10 minutes

Second question is not accepting soln , submit link is not working for second ques, what the hell is going on

C is at an acceptable difficulty IMO, but i don't think that D is a problem that worth only 1500 points...

i wanna know how opening another account helps?

Haha, sould've just written that in the statement.

30 minutes spent after i came up with that. It is illogical to have 2 stars on a grid at the same position (and how can he see two starts at the same point?) so it was better to write it in the statement. (Me personally got the point when i realised that number of stars could be up to 10^5 and grid has 10^4 cells)

Usually in this type of statements, I see that the phrase "All thingys have distinct co-ordinates" is given in such cases. Like in problem F, you are told that there is no road that connects a city to itself. So if you see no such statement, you usually take the worst case interpretation. So from my point of view, I don't think there was anything wrong with the statement

prefix sums

I (hope I) solved it with 11 2-dimensional Fenwick trees.

For every initial s calculate 2d prefix sums of stars so we can answer queries in O(c), because for each initial star brightness we know how many were there in the given rectangle and we can easily calculate what will be the brightness at the given time for this particular brightness.

Apparently a O(n + xc(y + q)) solution passes (here x = y = 100) with a sufficiently fast language. First, keep an array of all coordinate and brightness possibilities; put each star into its appropriate array. Now, compute the prefix sums of each row/brightness combination. Given this, we can answer each query in O(yc) time: iterate over all row/brightness combinations and find the number of stars in that row with the specified brightness that is also inside the query (can be done in O(1) because you have prefix sums). I'm sure you can fill in the rest of the details.

I tried hashing but it failed on test case 5 are there anti hash cases in pretest

I tried to do so: DP[i][j][k]=DP[i][i+sz-1][k-1] && DP[j-sz+1][j][k-1] && leftside = rightside. When i figured out what my function for leftside==rightside is not right :( I think it is O(n^2log^2n)?

Find values till logn. After that answer will be zero. Complexity n*n*logn

I did something like this: you first have is_pal[i][j] = the substring from i to j is a palindrome. (is_pal[i][j] = 1 if is_pal[i + 1][j -1] = 1 and string[i] = string[j]) Now, notice that a K-pal is also a K-1 pal. So we need the maximum "degree" of a substring: 0 if it isn't a pal, 1 is it is a 1-pal, k if it is a K-pal. We will have dp[i][j] = the degree of substr from i to j. When we reach [i][j], we have to analyse its 2 halves and if [i][j] is a pal. Now notice that if [i][j] is a k > 1 pal, then it is a pal and its halves are also pals (so they are equal). If that is the case: dp[i][j] = dp[one half] + 1. Now add them to your answer. (Hope this will pass EDIT: it did pass )

For simplicity, put a | between each character, as well as at the front and the back of the string. Now all palindromes will have odd length (possibly centered at a |). A radius of a palindrome is half its length, rounded down. (For example, the radius of abcdcba is 3.)

First, find longest palindrome centered on each character. Naive O(n²) search is fine.

Now, we will compute , being the largest level of the palindrome centered at m with radius r, minus one. , since a single character is a 1-palindrome. To compute , let r' = ⌊ r / 2⌋. If the longest palindrome centered at m has radius less than r, then . Otherwise, will be equal to , and you can set . Why it works is left for the reader, or I'll explain later.

Now that you have your , we can prove that a_i is equal to the number of that is greater than or equal to i. We can find all a_i's in O(n²) time.

I used suffix arrays to be able to check in O(1) if a sequence is a palindrome. Then I just checked each sequence to see if it is a palindrome. If it is, I check whether half my sequence is a palindrome and so on. Total O(N*N*logN) it fit in 1.3 secs.

Basic insights. Every k-palindrome would be a palindrome, can be easily proved using induction. Every k-palindrome would also be a (k - 1)-palindrome.

So, we only need to find max k for every palindromic substring of S, such that it is a k-palindrome.

Here's what I did.

1. Generate prefix and suffix hashes for S, let them be HP and HS.
2. Iterate over all substrings. For substring S[i][j], check if HP[i][j] = HS[i][j], i.e. if prefix and suffix hashes are same only then the substring would be palindrome.
3. If S[i][j] is palindrome, recursively do the following.
4. If len(S[i][j]) = 1, return 1. (strings of length 1 are 1-palindrome)
5. Else L and R be left-half and right-half of the strings, as defined in the question. Check if hash(L) = hash(R), i.e. check
6. If hash(L) ≠ hash(R), return 1. (given string is just a palindrome)
7. If hash(L) = hash(R) then do step 3 for L, and return ans(L) + 1

Now, this solution wasn't passing under time-limit, so to optimize I used an unordered_map to store answer for all palindromic substring hashes that I've seen and if I see the same hash for any substring again, I just lookup answer for it in the map.

yup, looking at his submission, he just change a comment to intentionally get hacked. Though, we cant be sure if the hacker co-operated with him.

where is your solution ?

Did you sort the string????

String was only aloud to be 1e5 digits long

not for me

It pass pretests, but I really doubt it pass the full system testing :(

UPD: It passed

I got MLE ! (time complexity as well as space complexity was O(n*n*logn))

Not for me too :( I was so positive about it, since, N^2log(N) was equating to 3 * 10^8 operations and tl was 3 secs.

It did for me in 1.3 secs.

it should be having more than one star at some position

I have an idea asking for each of bit of the position but dont have enough time to code

Let answer be A and B (A<B). For each bit position, find whether the bits at that position are same or different in A and B. For highest diff position, A has 0 and B has 1. For all other positions, find the bit at that position in A. Correspondingly, you get the bit for B.

To check if the bits at position pos are same/different for A and B, put all numbers having 0 at position pos in a set and query the system. If the number of occurrences of Y is 1, then the bits at pos are different in A and B.

To find the bit at position pos for A (after you've found the highest differing bit high), put all numbers with high=0 and pos=0 in a set and count the number of Ys in it. If the number of Ys is odd, then A has 0 at position pos and 1 otherwise. Now based on the relation found earlier (bits at position pos are same/diff for A and B), you know the bit for B too.

To count the number of Ys in a set, use the following -
If size of set is even, the no of Ys is 0/2 if XOR is 0 and 1 if XOR is X^Y.
If size of set is odd, the no of Ys is 0/2 if XOR is X and 1 if XOR is Y.

You can see my code for an implementation of the same.

I was asking for each bit. Then answer for some bit must be y or x xor y and then I have numbers which have only one y. For first number I just make binary search on numbers with this bit.

For simplicity, suppose there are 1024 icicles numbered from 0 to 1023, so you can interpret them as 10-bit bitstrings.

First 10 questions: ask the icicles that has 0 on i-th position, for each i. If there are 0 or 2 of the special icicles, the XOR will be 0; otherwise, the XOR will be x^y. Also note that it's impossible for all questions to give XOR 0.

Now you know the answers to the questions. Suppose the special icicles are numbered p, q, and their XOR is r. We claim that the i-th bit of r is 1 if the i-th question gave x^y, otherwise it's 0. It's actually not difficult to prove; you can try it, or I'll expand on it later.

Now you know that there are 512 possibilities of pairs of the special icicles. Interestingly, each icicle is involved in exactly one of them. Pick one icicle from each pair arbitrarily, then binary search on them.

EDIT: Since n is not necessarily 1024 (it's impossible to be that, in fact), you need to fudge with it a little. You're still asking the same question, but now the response is either 0 or x^y (if there are an even number of icicles), or either x or y (if there are an odd number of icicles).

Let set A_i be the numbers from 1 to n that have their ith bit on. Also let F(H) function be the xorsum of set H's elements. If for some set X or then X contains only one special element. We'll calculate F(A_i) for every 0 ≤ i < 10 (this is 10 operation). Let j be the first set A_j that A_j contains a special thing. Let's do binary search in 9 steps to find it (we can do it because |A_j| < 512). So we have the index of one special thing, but remember the 10 steps we did earlier? Just invert those bits in this one to find the other special thing.

First of all, observe that there can be no k-palindromes such that 2^k > n / 2.

Let's calculate dp[k][l][r] which denotes whether [l..r] is a k-palindrome (i prefer something like bitset < N > dp[K][N]).

The basic case is k = 1. This can be obtained in O(n²) if we just launch from all possible middles of palindromes.

For k > 1 and [l..r] we just have to check several things (assuming m is the median of this segment): whether s[l..m] = s[m + 1..r] and whether dp[k - 1][l][m] and dp[k - 1][m + 1][r] are (k - 1)-palindromes (depends of parity, but the main idea remains the same). Hence you get .