No, it will be unrated. :( UPD 2: Codeforces Round #347 will be unrated.

You've jinxed it...

NO! Why contest is unrated? We waited a lots of time and finally unrated?

Fixed, thanks. It is better to write about such mistakes through a private message.

Exactly! I'm going to send the problems to everyone I know ohwait pretty much none of them compete these days

Tourist!

Just when I thought "finally a rated contest"

Another month for a rated Codeforces Round I guess?

So, everyone can participate in the round except for you :3

Are you trolling? I hope you are...

Well D was truely what you call a brilliant problem, try reversing the queries (like in problem Parking Lot (480E)) it will be really easier, since everybody may not want to see the solution see it at previous edit.
EDIT: Oh !! i just noticed that you guys that didn't participate onsite (well i did) could be lying that you saw the problems :OOOOOOO !!!! >_< !!

So, Finally my dream of getting a better rating than tourist came true :D

As tourist's rating can get very high they count it modulo something, lol. I think the actual problem is rating overflow.

I think it probably is an overflow haha

Stay calm my friend :v

Now it's not :(

You have just greatly complicate the life of Codeforces and generally behave like assholes. It sometimes happens that something goes wrong. Making onsite events — a very complex activity. Codeforces team worked ~32 hours with 4 hours sleep break to make CROC Final, and we really wanted to make it not only for 44 participants but for all community. Most organizers do not make such events like: parallel rounds of onsites but Codeforces hold them many times. It is difficult and requires huge effort, but we did it to give the contests for community.

Why do you do like that,people aren't competing for rating,they are competing because they want to solve the problems by themselves and see their level,just be honest with you and don't look at the problems/solutions.Respect at least the people who give you opportunity to compete with others in a contest.

Codeforces rule #1: Don't upset mike.

What was in this comment?

It seems now we have to do the round unrated. It is really pitty. It was my mistake that I accidentally opened the solutions for 15 minutes. I upset the behavior of some of the participants who did not give opportunities to others to fully take part in the round. I involved in programming contests for 15 years and I'm sure that this community rests on mutual respect and honesty. Yesterday it was impossible for us to run round in the same time or just after the Finals.

You can change constraints a bit, for example: from n = 100 000 to n = 200 000. If somebody submits a solution with old constraints — ban it! :D

Nice Idea!!!!!

Generally speaking, the problems in an Educational Codeforces round are some of the more "classical" problems unfit for a regular contest. In any case, it would not be a good idea anyway, changing all the problems last-minute.

maybe we can make the Educational round rated, it would be sad to wait for another two weeks to participate in a rated round :(

I think this may be a good idea. If necessary they may delay the round. After all, it has been a long time since a rated contest .

please look at the end of the post !

It's unrated as is stated in UPD2.

see UPD2

If I asked you to go and kill yourself, will you post an image for my request saying "that was the reason why I killed myself", then go kill yourself?

Electricity in Syria is not always on. I usually save my laptop's battery for CF contests, but today I had to waste it on silly arguments here (after which I turned out to be a bad guy who forced CF team's decision to make the round unrated). I wish one could participate from his smartphone

All hail tweety our saviour/ martyr (because some of his upvoted comments were deleted).

On a more serious note, I totally agree with you. I was going to participate blindly if it wasn't for tweety, and I would've probably lost a lot of my points because I didn't know that the solutions were leaked.

Let's all remind ourselves that it wasn't tweety who leaked the solutions. He was the one to draw attention to the fact, refusing to stand by while a few individuals took advantage of the situation.

The organizers might not like him for that, but it is something very common to have a scapegoat around for your screw ups and what better scapegoat than the one who drew attention to their mistakes in the first place.

You ruined my world :D

Answer is Impossible, right?

Thanks, I was afraid of being in first hundred in unrated round:D

P.S. Hmmmmpphhh.... I still in first hundred:D

I think that the one who accidentally left the solutions open to the public should make a rated contest soon.

So do I, I didn't realize IAP'00 is a valid abbreviation until got hacked T.T

ok i solved the same problem as yours only now i found out my mistake :))

Here's a sub-problem:

you are given at most 200000 "selected" 20-bit numbers. For each possible 20-bit number and each number k, find how many selected 20-bit numbers differ from this number in exactly k bits. This is done using DP.

You can compute freq[x] = number of times the bitmask x appears Also, compute cost[x] = min of (number of 1s, number of 0s).

You want to compute minimum over all j of the sum freq[j^x] * cost[x] (i.e. we flipped the rows according of to the bitmask of j).

You can compute sum freq[j^x] * cost[x] for all j in n*2^n time using a variant of fft. (You can see the editorial here: https://www.hackerrank.com/contests/back2school14/challenges/xor-subsequence for code).

An approach slightly different from the one described by Petr (might be easier to come up with, but is much slower): let's iterate over the first 13 bits. If the first 13 bits are fixed, each number becomes pair (distance on the first 13 bits, last 7 bits) — there are only 2⁷·14 such numbers. So, with this we can iterate over the last 7 bits and solve the task with brute force. The number of operations is 2¹³·(100000 + 2⁷·(2⁷·14)), which is small enough.

Obvious but slow solution: fix a mask of rows that we're going to flip. Now, for each column we can achieve min(ones(column[i] ^ rows_mask), n - ones(column[i] ^ rows_mask)) ones (^ is XOR operator, ones(X) is the number of bits equal to 1). Compute the sum of these values for all columns and find a minimum over all row masks. The complexity is O(2ⁿ·m).

Optimization: Split the rows into two groups of sizes A and B. Iterate over all masks of rows from group A and let's assume it's fixed now (and equal to X). For each column compute how many bits are equal to 1 in XOR of X and that column (let it be C[i]) and also let R[i] be a mask of remaining B rows for that column. Let's compute how many columns have the same values of C[i] and R[i] for all pairs of (C, R) (the number of these pairs is A·2^B). Now, let's fix the mask of rows from group B (let it be Y) and iterate over all pairs of (C, R), each group will contribute min(ones(Y ^ R) + C, n - (ones(Y ^ R) + C)) * cnt(C, R) to the overall sum. Notice that we actually don't need to iterate over all pairs (C, R) as it's enough to compute prefix sums for all C for a fixed R and then we can compute the minimum in O(1) using them. The complexity is O(2^A·(N + 2^2B + 2^B·A)) assuming that ones(X) works in O(1). To choose A and B properly I just used a simple for loop that tried all possible pairs, although one could easily find it on paper (e.g. for the max test the optimal values are A=12 ans B=8).

UPD: ilyakor has already mentioned this approach without prefix sums

Although due to mis-understanding the constraints of the problem, my code failed the system testing, but my code passed pretests and your's gave TLE on pretest 1 because your preprocesing loop, the one filling the map, runs for ~(2*10^5) times. Mine runs exactly half of it.

just make every integer 1,then make one integer bigger if it makes ans more closer to n,until it can't be bigger or equality holds and do the next integer

Fortunately, I overslept.

If I'm not mistaking, problem C from div2 has only 3 pretests (and you know 2 of them from statement). It means that contestants should not rely on pretests :D

We have string representing our "short year" (call it S). Let's denote ans(S) that calculate answer. Fact: if we have suffixes of S S1 ans S2; |S1| < |S2| then ans(S1) < ans (S2). So we can build answer suffix by suffix. Assume we built answer for suffix Si (|Si| = i; ans(Si) = Ai). So A(i + 1) > A(i). A(i + 1) % 10^(i + 1) must be equal to S(i + 1) % 10^(i + 1) and A(i + 1) must be minimal. We can represent A(i) as k * 10^(i + 1) + r (0 <= r < 10^(i + 1)). Now we have 2 cases:
1) S(i + 1) % 10^(i + 1) > r. Then A(i + 1) = k * 10^(i + 1) + S(i + 1) % 10^(i + 1). Easy to see that A(i + 1) correct answer.
2) S(i + 1) % 10^(i + 1) <= r. Then A(i + 1) = (k + 1) * 10^(i + 1) + S(i + 1) % 10^(i + 1).
Now if we assume A(0) = 1988, then A(|S|) = ans(S).

Example. S = "015".
A(0) = 1988 = 198 * 10 + 8. S1 = 5. 5 <= 8 => A(1) = 199 * 10 + 5 = 1995.
A(1) = 1995 = 19 * 100 + 95. S2 = 15. 15 <= 95 => A(2) = 20 * 100 + 15 = 2015.
A(2) = 2015 = 2 * 1000 + 15. S3 = 15. 15 <= 15 => A(3) = 3 * 1000 + 15 = 3015.
So answer for S = "015" is 3015.

You want to know what number chose that suffix. Simple observation from that is that each suffix of the suffix (except itself) was chosen before.(otherwise there was at least one smaller than itself,and it wouldn't choose it).

Now this is how I find the number. Let's take 3098 for example. You can also see that one which chose 8 is before the one who chose 98. Now the greedy approach is simple.Calculate who took the suffix with length 1,call it VAL. Calculate who took the suffix with length 2 and it's >VAL,... and so on. If you want to find the number which has the suffix p,the number looks like prefix+p (0<=pref<=inf).

In my solution I just binary searched prefix,and took the prefix which gave the smallest number > VAL. I saw other people just brute-force to find prefix(even if for prefixes of length 1 and 2 it takes some hundred steps,for other lengths is seems like it takes maximum 10).

Hope I helped you understand the greedy approach.

Example: IAO'1999 => from right to left: 9 => 1989 | 99 => 1999 | 999 => 2999 | 1999 => 11999

well , we have two options for the final color (1 — red , 2 — blue )

suppose we want to color the graph with red

for each component this is the algorithm :

suppose we have a vertex v in this component .

again we have two options : change the color of all edges adjacent to vertex v , or don't do anything with v .

when you choose this option , you can run a dfs from this vertex , and you will know for each vertex of this component , what you should do with it ... (change it or not)

after that , you know what to do with the vertices of that component :D ( while running dfs , if you changed one vertex , you can mark it in a bool array or sth ..)

now you can easily know , what would be the color of the edges of this component ... (by using the information of each initial edge and the bool array we used) .

if all of them were equal to the final color (here it is red) , add the changed vertices to a list.

now , after you tested the 2 options for each component , if just one of them worked , just add it the the list of vertices for the final color which should be changed .

if both of them worked , add the one with the minimum number of vertices

and if none of them worked , sadly we can't color all of the edges with this especial color ( which was red here)

now do the same thing for the blue color

if you had 2 final list , print the one with minimum vertices

if you had only 1 list , just print it

if you hadn't any , print -1 :D

Why? I don't understand. Problem A of purple someone will fall anyway, but now you have 100 additional points.

This is what I did and the tests passed. I guess you didn't apply the idea for each connected component.

though this problem is quite similar to 228 E.