Would you prefer a full queue?

Unfortunately, the contest interface does not support taking the maximum score of all submissions. This was mentioned in the competition rules quite some time ago.

Regarding the 5 minute rule, we were very worried that a very long queue might be created in the grader. The submission time restrictions were smaller for the on-site competition (1 minute for only one task), but we expected a large amount of participants and submissions for the online version.

It seems the grader performed better than we expected. We are sorry for the inconveniences.

Deleted.

How to get some points?

Oh, please next time say it's not working, firstly.

Reyna found one stupidity in solution above. Can I upsolve somehow?

Why it's important to add testID? If we get all binom(12, 6) possible tests in N = 6, this will surely fail, as we'll answer all tests anyway, even after transforming the sequence.

It sounds like you change "failing for sure" to "failing with some probability". If this hack makes sense at all, I think the probability of failing isn't negligible. Otherwise your reasoning "why it's important" doesn't make sense.

I don't like that you care about xor of numbers. For me, looking for the sum modulo 2n + 1 sounds better. Giving some info for xor should be harder because there are more possible values. Am I right or not?

I'm not describing my solution simply because I don't know any nice solution for small n. (I could solve n ≥ 12 only.)

Hello! I am the author and problem setter of task Trick.

There is a clean and deterministic linear-time solution. After the second competition day, there will be a short session with the contestants where all task solutions will be presented. I will publish the solution for this task after the official session.

First, find a way to split the vertices into two disjoint sets such that the (new) edge is surely between them, in O(lgn) time. You may want to use the disjoint set data structure for this task (since you have to be sure that whenever you add a node, you also have to add the entirety of its component, coupled with a somewhat obscure trick — using the binary representation of the vertices to find the given split. This might sound slightly off — it sure did for me, but I found no other way to solve this part. Then, implement two binary searches on the sets, narrowing down the possibilities until only two nodes remain. Those nodes are, of course, the answer. The key idea is to test which of the halves contains the edge, which can be done with only one call to the grader query function. This particular solution, given a clean implementation for the first part, has an upper bound of 3 * n * lg(n) calls to query. I could gladly give more details if you wanted to, but you asked for just a hint.

Best of luck, and have fun!

http://cni.nt.edu.ro:8080

That will take maybe an hour. The contest barely ended.

Probably they used the formula or something.

B. dp[len][cnt] — we divided first len tests into cnt subtasks.

dp[len][cnt] = MIN of {dp[pos][cnt - 1] + (s[len] - s[pos]) * cnt_of_full_rows(pos + 1, len)}

Notice that cnt_of_full_rows(l, r) <= cnt_of_rull_rows(l + 1, r).
Using this fact, let's fix cnt_of_full_rows (only 50 unique values) and call it x.
Then, we can a find a segment [l, r] such that cnt_of_rull_rows(i, len) = x for all i in [l, r]. (this will be always a segment because cnt_of_rull_rows is non-decreasing).

Now, our DP became easier

dp[len][cnt] = MIN of {dp[pos][cnt - 1] + (s[len] - s[pos]) * x}

which can be written like this

dp[len][cnt] = MIN of {dp[pos][cnt - 1] - s[pos] * x} + s[len] * x

Wow, this is line equation. :)
Notice that x <= 50 and pre-calc line equation value for each x and line i in res[x][i].
Now, we need to find minimum on segment, which can be done with segment tree.

Total it is O(TN^2logT)
My code

A: This is what I had at these weird wrong n ≤ 10⁶ and TL=0.1s bounds. It worked locally in 0.09s, so it'd be a close call...

Checking if the whole word is okay is easy — just greedily maintain a stack and when seeing consecutive letters, try to pair them with the top of the stack. If they do, they both disappear; in the opposite case we must push it on the stack. Using that, we make an easy O(n²) algo.

However, we can tell something stronger — find all substrings which are correct under the task requirements. I'm not showing this, but just look what the stack looks like between all characters (also, before the first character and the last character). I say that a substring is correct iff the stack contents before and after reading it were the same (it's quite easy to prove).

Okay, so let's find all the equivalence relation classes between the points in time (equality holds when in two points of time the contents of stack were the same). It's easily doable with a trie, however under the limits above it was either too slow (O(n|Σ|)) or took too much memory (O(n) time, but ~400 megs of RAM). Hash-tables in nodes made probably no sense as they would be slow, too. What I did what some string hashing with a self-written hash-table, which gave me expected O(n) time and O(n) memory.

Now let's become greedy again. Write a recursive function which tries to place the first pair of parentheses (the one in which the opening bracket is on the beginning of the word). You can prove that the matching closing parenthesis should be placed as far as possible — that is, its contents should begin with some stack state α and should end with the same state α and the terminating α should be the last possible one. It can be done with some binsearching. When we place the brackets, we fire up recursively: between the brackets, and then to the right of brackets. We see that it's and might be too slow (you see the limits, right?)

However, notice that the order in which we process the recursive calls does not matter. In fact, we can process them from right to left using some sweeping. For each state α we maintain the furthest possible occurence of α in the word. When we cut off the letters of the word, we find (in constant time) what state we just cut off and what's the second furthest possible occurence of it. When we process a 'recursive call', we do it in constant time (no binary search needed) and then put the recursive calls into the structure holding them. As a call is a subinterval of [0, N], we can hold them in a table. Putting a call is thus also O(1). So... overall, we get O(n) expected running time.

Then I submitted it, saw 0.008s on final tests. Aaaand mere minutes later got announced that n ≤ 10⁵. Eh.

Oh my god. I finally understand why the first problem was failing for me. I've spent the whole first day debugging because my "bruteforce" solution for the first problem was getting 0 points for the easy subtask and I was seriously confused. It was very straight forward but it was still failing for some reason and I couldn't focus on anything else.

Now I can rest in peace thanks to you.

MLC!

Hi, i am the author of problem Popeala. I don't know why the solution for another problem was uploaded. I will post the official solution which was supposed to be there (and sorry for the late response :) ):

D[t][g] = the minimum cost we can obtain if we take the first t test cases and put them in g groups.

D[t][g] = min(d[k][g – 1] + group_cost(k + 1, t)), where k is the last test of the previous group and group_cost(x, y) is the total score the participants will obtain on tests x-y if we group them.

The complexity is O(T * T * S) but it is too big for 100 points. Let’s assume that we are at test t. Let’s keep for each of the N participants the most recent test he failed and denote it with last. For contestant x, last[x] = max(k), k <= t and x failed test k.

Using those N values, we will divide our tests in N + 1 groups. Group 1 consists of all test cases from the most recent last[x] until t (basically, no one fails any tests in this group). Group 2 consists of all test cases from the second most recent last until the most recent last (only one participant fails the groups), etc. Let’s denote for each group x: best[x] = k, where k is the best option we can select for our dynamic programing with the restriction that k to be a test from group x. Formally: d[k][g – 1] + group_cost(k + 1, t) is minimal for all k from group x. If we know for each group this best, we will have to check only O(N) different possibilities ( since there are only N groups) and take the best option.

Let’s assume that we solved D[t][g], formed all the groups and computed each best[x]. Let’s see what happens when we go to test t + 1. Assume initially that all participants pass this test. One of the key observations is that the "best" values does not change (all options increase with the same value in the same group), so we just have to recheck all the N + 1 possibilities. Now let’s assume that contestant x fails test t + 1. The main modification is that last[x] becomes t + 1, so the groups change their configuration:

1) The previous last[x] was dividing 2 groups which now have merged into one. To compute the new best of this new group it is enough to just compare the two old options and take the best one.

2) All the options from the previous last to the new one change their value in the recursion. Unfortunately, it is necessary to loop throw all of them again since they changed drastically. Fortunately, we can do that brute force and the complexity will not change (because a passed test will be recomputed only once between 2 consecutive failed tests) The final complexity is O(T * S * N).