On July 28th and 30th, EJOI tours will take place — a personal programming competition for juniors, taking place according to the rules of the international schoolchildren's competition in informatics.

EJOI is made up of the most interesting and complex tasks that were proposed by a large team of our authors, therefore, not wanting to deprive you of the opportunity to break your head over the problems of the full problem of the network together with the contest participants, we are going to run a rating round of Codeforces, based on the tasks of both rounds of the Olympiad.

In this regard, we ask all members of the community who are going to participate in the competition, show respect for themselves and other participants of the competition and not try to cheat in any way, in particular, clarifying the tasks of the participants in the competition in Innopolis. If you learned any of the tasks of EJOI (by participating in it personally, from someone from the participants or in some other way), please do not write a round. We ask the participants of the Olympiad to refrain from public discussion of the tasks. Any violation of the rules above will be an excuse for disqualification.

The round will be held on Monday, July 30, 2018 at 11:05 and will last 2.5 hours. In each division, six tasks will be proposed.

Sorry, it is translated now.

Thanks, fixed.

isaf27 is also among the names of the last round

5th Century of Codeforces round, not Codeforces Contest. :)

As educational rounds are also Codeforces Contest but not Codeforces round. :)

ez katka round

Registered.

Young man. Are you eager for force?

(Please downvote this comment)

i am not in !!

DELETED

HAHA!You are so funny.

Yeah,it is so tiring to take part in contests at midnight,especially when you need to go to school tomorrow

but tomorrow's div 3 will start at night again ...

3 AM here in Colombia :)

If u can, why not?

Well, I just did this in Round #469 which has the same beginning time ┑(￣ _ ￣)┍

Херня какая-то

I think that the main purpose of the contest is to solve interesting tasks, not to earn ratings. We will try to do everything to fight with cheaters, but I don't think that cheaters can ruin the contest. Just enjoy the tasks!

The onsite contestants were asked to don't disclose the problems.

Anyway, there are ways to cheat in codeforces rounds even without onsite competition present. So we hope, that most people on codeforces just simply don't cheat.

I really like the tone of this comment, "Do this, do that, it should be". Should we also buy you a Ferrari and a nice house?

I think this team of experienced contest authors together with Mike can figure something out, don't you think?

I think that first 2 or 3 problems won't be from the EJOI, because A, B and sometimes C are very easy and I think there aren't that easy problems on EJOI. Please correct me if I am wrong.

downvote for sguu

me too,hhhh!

Полагаю, чтобы начать вместе с основным ивентом

Возможно, удобно для школьников и студентов, у которых сейчас каникулы.

Better than long submission queues during the round.

That's better than 1 hour delay,isn't it?

Ten minutes for dinner:(

same here, I just want to participate to contest until end of my lunch time, which means 55 minute of the contest. Now they decreased it to 45 minutes by delaying it :(

It may be caused because I registered in the 10 minutes delay time.

Same in div1...

Represent each row and column as a node, and connect a row and column if cell (x,y) exists. Answer is number of connected components minus one.

Make a bipartite graph (the left side of the graph is for r_i and the right side is for c_i, edge (r_i, c_i) exists if we have element (r_i, c_i)), then count the number of connected component.

This solution works because if you will be able to make element (r_i, c_i) if you can reach node c_i from node r_i.

DSU on rows and columns. When you're given a cell, you merge the x and y coordinates. The answer is the number of components in total — 1.

Yeah, so sliding window will work.

Note that when you're doing a proof you may get stuck at one point while trying to induce a contradiction, but you should also pay attention to whether the y's form a contiguous subarray as well.

If you assume that neither the x's nor the y's make a contiguous subarray, you should be able to easily induce a contradiction of the minimality.

Yes, because you can make the x's contiguous without affecting difference between the highest and lowest y (can even decrease it), resulting in difference between the highest and lowest x being decreased (or not changed at least).

I think 2. Update: I don't know.

Please, explain what is d[i][j][0] and d[i][j][1] in your solution (we are not telepaths)

Finally, mistake found — a stupid one I must say.

i64 dp[5001][2500][2]; (It should be 2501 for the second dimension).

Like, I've neglected Carrays for a very long time (only using it today since nested vectors didn't suit in 1s TL), and then this happened...

Still thanks for all the support! rembocoder Tutis ouuan

And how beautiful when it is going to be a great rise.

Have been monitoring your progress, and I can only say congrats! ;)

Codeforces's progress proves the revolution successful and makes itself better!^_^

Maybe I won't be able to? The rating change hasn't been shown yet.

D1 B+ were from EJOI

Cheer up T_T..

It seems that you would have won this round if this didn't happen. So sorry.

But still, congratulations on becoming nutella :)

Ehm, I spent some 20min going in wrong directions on E, then wasted a lot of time on D. About an hour after the contest, I decided to revisit E and figured out I can take Euler cycles in about a minute... and the rest is straightforward.

How was your greedy, exactly?

Also, please keep in mind that the commands with string are linear in time complexity, in case you implemented them directly on your solution.

Yeah, I also did not understand why does not it work to just break an "ab" in one string and a "ba" in another. Though I just saw the number of OKs and the number of WAs and decided not to think further =/

For a test like:

ababa
b

It's better to make the number of cuts in the two strings more equal. For example, we balance them on the very first move:

ab|aba  -->  aba         ab|a  -->  aa           |aa   -->  aaa
|b           abb  ;      a|bb       abbb  ;      a|bbb      bbb

Let's present a table as bipartite graph. N vertices for rows and M for columns. Then an element means an edge in this graph. If we have a path of three edges, we can connect the ends of this path with an edge. This means that if we have a longer path a_1, a_2, a_3, ..., a_k, we can at first connect a_1 and a_4, so the path becomes shorter, and so afterwards we can connect a_1 and a_k. So if two vertices are connected, then we can draw an edge between them already. Thus we only need to buy edges to make all the graph connected, so the answer is the number of components — 1.

I approached it with greedy solution — minimize one dimension of the desired rectangle as much as possible.

To achieve that, we will sort 2 * n coordinates, and choose n consecutive coordinates in the new sorted array to be coordinates of the same dimension (either x or y, doesn't really matter). Technically, we'll keep a sliding window and try all possible n-length consecutive subarrays.

last submission will count

your first solution will not be judged. It will get skipped

hmm, I think it should be 6 for this case.

you should join codeforces team

My answer also has 6 actions.

When a solution considers a number of cases, there can be quite a few of them (mine, for example, has a total of 18 calls to the main solution function, just to be sure). So, if one of X such cases is solved incorrectly, informally, it is X times harder to catch it with tests. So it is understandable if something like that slipped through.

Nice.

I guess I'll just repeat Jatin.

Get a life.

Consider all substrings ab and ba: the switch positions where the two consecutive letters are not equal. Note that each cut can remove at most one switch position. Now, if we cut ...a|b... in one string and ...b|a... in the other, and swap the prefixes, we remove two switch positions simultaneously. However, one swap can remove no more than two of them, one from s and one from t.

What's left to do when, for example, s has no switch positions and t has X > 0 of them? We can remove one switch position from t with one swap. But we can do better: cut the string t so that approximately half of these positions go into s. Then we can again remove two switch positions per swap, which is twice as fast.

In fact, we can start by counting the number of switch positions in s and in t (let them be X > Y), and if they are not equal, make the first cut so that (X - Y) / 2 of them go from s into t, making their count approximately equal. After that, proceed with the greedy solution which removes one switch position from s and one from t in each swap.

What's left is to consider which string will turn into aaa...a and which into bbb...b, and formalizing the "approximately equal" above. We can just solve for a few  ± 1 cases and take the minimum to be sure.

Don't. Solve E instead.

Seriously, if it looks simple and there are few correct submissions, maybe the next problem will be more doable — or if it isn't, at least it won't give you a headache.