Hello, Codeforces!

Educational Codeforces Round 14 will take place on 13 July 2016 at 19:00 MSK for the first and the second divisions.

<I already have a long list of problems, so don't be upset if your problems wasn't used yet>

The round will be unrated for all users and it will be held with extented ACM ICPC rules. You will have two hours to solve six problems. After that you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

If you have ideas for some problems or maybe already prepared problems that you can't use in rounds or official competitions, you can write to me.

It seems that it is harder to invent interesting simple problems (like A and B) than difficult ones. So don't be afraid to suggest interesting simple or very simple tasks (of course the difficult tasks are also needed). Please send only the problems for which you know the solution with clear statement (the story is not required). And also please add one or two samples to make the problem statement more clear.

Thanks a lot to them and all others who are sending the problems! The number of unused problems are increasing. If I didn't miss anything I already replied to all who sent me the problems at least 5-6 days ago. Please be patient if your problem was not used a long while.

</I already have a long list of problems, so don't be upset if your problems wasn't used yet>

The problemset was suggested by Codeforces users. The problem А was suggested and prepared by user Arthur Jaworski KingArthur. The problem B was suggested by Nikita Melnikov nickmeller. The problem C was suggested by user I_Had_A_Great_Time. The problem D and E was suggested by Zi Song Yeoh zscoder (he is on IMO now, so good luck to him). The problem F was suggested Michael Kirsche mkirsche.

As I said the problem A is prepared by Arthur Jaworski KingArthur. All other problems was prepared by me (Edvard Davtyan). Thanks to Tatiana Semyonova Tatiana_S for checking the English statements. The problems was tested by users suggested them, respectively: Arthur Jaworski KingArthur, Nikita Melnikov nickmeller, user I_Had_A_Great_Time and Michael Kirsche mkirsche. Thanks a lot to all of them!

I hope you will enjoy the problems! I think the problemset is balanced and not difficult.

Good luck and have fun!

UPD 1: All the hacks for the problem D will be rejudged.

UPD 2: Hack phase will be extended until tomorrow.

UPD 3: Sorry for the problems in the problem D. The solutions that got WA3 were rejudged. The problem is OK now.

UPD 4: The contest is finished. All the solutions were judged on the full testsets. The editorial will be published soon.

UPD 5: The editorial is published.

I think I can solve with one or more problems in this test,good luck!

Wish you good luck

"TAK" and "NIE". So fun)

Codeforces website is very slow during the contest :/

Problem statement is not very clear. :( Also the website is so slow.

The english statements were not very clear in this contest :(

please check problem statement(english) before contest more than once. :(

The statement for problem A (in english) is horrible.

P.S.: I had to use google translate on the russian statement in order to understand the problem.

Half of round time could not connect. 'The connection has timed out'.

I am still loading problem A.

me reading problem A (before revision)

you sir, made my day :D

How can O(N^3 * Log(K) ) TLE in problem E?

My solution took 1.3/3 seconds. I am using statically allocated matrices. I guess maybe with vectors it may TL..

I've seen AC solutions with vectors.

Java with arrays TLE.

Java matrix exponentiation somehow passed by a hair: 19090004 (Never mind, that got hacked)

Edit: This one passes with plenty of time to spare: 19096055

Operation % works very long, you can use O(N^2) operations % instead O(N^3) in matrix multiplication.

You can see function mul in my code for details: http://codeforces.com/contest/691/submission/19082266

ignoreon what situations is this trick valid and yeah please explain MOD2?

MOD2 could be any multiple of MOD,

Thanks, cool idea!

How to solve E?

I Have solved it with Matrix exponentiation.

It looks like DP, but

`k`

is too big. So, you may use matrix exponentiation. Let's create matrix`A[N][1]`

, every`A[i][0] = 1`

. Then let's create matrix`B[N][N]`

. For every`i`

and`j`

:`B[i][j] = 1`

if the number of ones in the binary representation of the number`(a[i] xor a[j])`

is a multiple of 3, else`B[i][j] = 0`

. So, answer is any element of matrix`C = binpow(B, k - 1) * A`

. Complexity`O(N * N * N * logK)`

Any element of matrix C??Does all element will be same?

It does not fit with the given sample

I can implement this solution, but I am not sure I am able to justify why it is considered correct or how I can possibly consider such solution in the future. I would appreciate it if you can help.

Why am I getting a TLE in the Problem D?

My code

TRUST SCANF AND PRINTF!

The main idea of your code is okay, but it has been implemented very inefficiently. First of all, when number of input >= 5*10^5, it is better to use scanf instead of cin. Also, you could improve your dfs function. It is better to check whether a node has been visited within the loop-this way, unnecessary function calls can be avoided. A lot more optimizations can be done; and I haven't looked at the code more deeply, but I think the logic is okay(as far as I have seen; apologies if I am mistaken).

This way means?

D: UnionFind to find connected groups, sort each group separately

E: Let matrix , then the answer is sum of the elements of

M^{ K - 1}. You can think of it as counting "paths" (sequences) in a graph with adjacency matrixM.F: Compress and sort the array. Then we can enumerate all products of pairs which are not greater than

max(p) and save counts for each product. There are at mostmax(p)log(max(p)) such products: (max(p) / 1 +max(p) / 2 +max(p) / 3 + ...). Then we need to count all products which are greater thanmax(p), using Fenwick Tree or partial sums (e.g. for each indexiwe find position wherea_{ i}*a_{ j}>max(p) and then sum all counts on suffix starting fromj). The latter count will always be added to the answer. Then to compute the answers we need to compute suffix sums on the array of counts per product. Special care needed for repeated elements.Why am I getting a TLE in the Problem D?

My code

Hi! Why (ai xor aj)%3=0 is same as the number of bits in ai xor aj are a multiple of 3?

Shouldn't the answer of problem E test 4 be 63? My program found 63 valid combinations...

http://pastebin.com/HHDqbZ6s

Typo: Generated 62

UPD: Oh crap, I misread the statement. It's about the NUMBER OF BITS... Now I see.

Someone else tried to solve D using random selection of pairs for swapping? It was a funny idea but wrong, of course. :)

Why didn't they use a template type of definition to create __builtin_popcount() ?

I always get one WA for that!

This is intrinsic stuff, you can do a template version yourself :)

Hah! Kept getting Wrong answer on test 7 due to this

use __builtin_popcountll() for long long type

I did it sir but after One time wasting WA :P

I liked almost all the problems — I didn't have time to read F, as I spent too much time on C, which I didn't like.

Can someone explain problem e in more details??

This is actually a graph problem. Vertices are the elements of a, and edges between them are present if number of 1-bits in their XOR is divisible by 3. The task is to find number of valid paths of length k.

What you need to know is that if you multiply adjacency matrix of this graph k times by itself, you will get matrix that contains info about number of ways to get from one vertex to another in k hops (better explained here). After you get that matrix (this can be done in O(n^3*log k) via binary powering) you just need to sum up the values of the nodes and this sum will be the answer.

I think, He said to explain the problem not solution.

I also didn't get it, if a={1,1} and k=1 how is the answer 2? anyone explain please

The sequence will be of just one element. You can pick either the first one or the second one. Hence, the answer is 2, and it doesn't matter whether they are equal or not.

You should count the number of different valid index sequences, not sequences of their values.

but 1 isn't a multiple of 3

Question asks for xor b/w consecutive elements to have no of 1's in them as multiple of three.

Thanks a lot for such an interesting round, Edvard! And many thanks to authors for the efforts, it was definitely worth it!

Bonus for problem D: calculate the minimum number of swaps to achieve the maximum lexicographically permutation

Other variant for problem D: given two permutations and the allowed swaps, it is possible to obtain one from the other by making a sequence of allowed swaps?

Problem D: So, one swap step can be used any number of times!!! Didn't realize that. Anyways, how to solve this when each swap step can be used at most once??

When you found a connected group (with dfs or union-find), you have to put maximum element from that group to the first place and you can do it in only one way, e.g. if the group is 5 3 1 8 7 2 4 then you first put 8 to firstposition, and you have used all swaps between 5 and 8, so you repeat the idea on the rest, e.g. put 7, then put 4: 8 5 3 1 | 7 | 4 | 2.

EDIT: I've realized that the connected components are not necessarily chains. There even may be loops and therefore multiple paths from the largest element to the smallest position. It is not clear how to choose optimally.

In problem B, How is the answer for "opo" is NIE when the answer for "oHo" is TAK?? :/

The symmetric string is "oqo", which is not the same as "opo".

s-palindrome is a string that can be mirrored. For example, oqpo — is TAK (q and p are mirrored to each other).

Thanks a lot :)

can anyone explain statement or sample cases of problem E?

In C, could be there multiple answers?

E.g, 323.345 can be presented as 3.23345E2 and 323345E-3

323345E-3 is incorrect, there must only be 1 number to the left of the decimal point.

the answer should be in the form of

x=a·10^{ b}where 1 ≤a< 10 so 323345E- 3 is wrong because 323345 ≥ 10Is unexpected verdict in hack 240056 (problem F) caused by load issues (too many B hacks) or something else?

How to solve D? Naive dfs will time out,so how to compute efficiently?

Edit : I understood the solution.

https://en.wikipedia.org/wiki/Mirror_image

Nice, thank you very much :P

BTW this is the first problem I see that requires checking for mirror reflections and doesn't clarify what is the reflection of each character. In my opinion doing things like not clarifying makes problems really annoying. Afterall this contest is "educational", it should not annoy us by wasting our time checking if there's a reflection for each of 52 characters

I was hacked because i thought that i can be reflected to it self i.e string : iii does conut as s-palindrome but it turned out it shouldn't

It should teach you that such problems exist. I encountered a reversible stepladder and rotatable calculator-style digits.

Was getting TLE on F until I put cin.tie(0) into code.

Then changed everything to scanf and it worked twice faster.

http://codeforces.com/contest/691/submission/19096778 — scanf version, 1200ms

http://codeforces.com/contest/691/submission/19096765 — cin version, 2324ms

So the answer is just to drop cin/cout and switch to scanf?

The problem statements were really ambiguous. Even if we ignore the mistake in English statement A that was wrong for whole 10 mins, and made the problem unsolvable for English reading coders, why did you feel the need to include: "but not necessarily it should be the last one". It adds no clarification or help to the problem, and only confuses the competitors.

And for problem B, you should've specified that we should use the pictured alphabet to determine what the mirror images of certain characters are. Since it really depends on the font we use. For example: the letter l in some fonts mirrors it self, but here it doesn't, the same happens with the letter i.

I agree. The sentence "but not necessarily it should be the last one" made me think I was not understanding the problem as I could not see which kind of information was this sentence adding.

Hi, I want to join to these series rounds.

Why does it named "Educationl"?

Is there any plan for these rounds (e.g any discipline for problems and including subjects for a round)?

Is there any program of study the subjects?

Does it need to solve all the problems in previous rounds to join these series or not?

Here

That moment when you hacked yourself :D

Can someone please explain Problem Dthat how to model it into a graph. Thanks.

At first you notice that every position is node of our graph and swaps are our edges. Solution of this problem is to find connected components and then sort their elements. For every component we know values of initial permutation. Because we want maximum permutation, the highest value of component must be leftmost (of possible positions that are in current component). If we look at first example, we get 3 components. 1(1) — 4(4) — 7(7) 2(2) — 5(5) — 8(8) 3(3) — 6(6) — 9(9) () — value In first component the highest value is 7, so 7 should be at position 1, then second highest value is 4, so it is on position 4 and 1 is at position 7.

You actually don't even need to model graph, all you have to do is use DSU.

I hope this will help you.

A, B, C were "stringy" problems, here you can see some of mine solutions using regexes with Perl: A — 19090971, B — 19095540, C — 19089637 (or 19096070)

What's going on with D? Is it checker/validator bug somebody found? :)

Yes. Unfortunately, someone else is figured it out too and unlike me, he/she is exploiting the bug instead of avoiding it.

^ So u are saying u got >100 valid hacks.

I can't be 100% sure because of the buggy checker. All these solutions failed on my computer (or were close to time limit) at least.

Was judge_chutiya_hai already taken or did you make a typo?

Unfortunately, this behavior blocks challenging submissions on the real bugs in this problem :( .

We will increase hacks phase duration until tomorrow.

The hacks for the problem D will be rejudged soon. Testing during the contest was correct.

For problem D, I have tried hacking my submission with such test

3 1

1 3 2

1 2

My output is

2 1 3

while the answer given by std is actually the same.

Obviously the correct answer is

3 1 2

so there must be sth wrong with std.

I think you are right. I have never seen so many rednames are hacked.

What is the hack for problem D otheer than this?I am hacked.

Looks like you made exactly the same mistake as the author solution. No one can hack you until rejudge :).

I do not get you?

Hacks for the problem D will be rejudged soon.

Please update us when they're rejudged

+112 hack... Awesome

Can someone explain problem A to me in english? I can't understand the description

Every citizen should wear a jacket with exactly one unbuttoned stud (no matter what it's in order, first, last, etc.) except in the case when a stud on the jacket is alone, then it must be buttoned. So you have

nstuds and its statements (0 — unbuttoned, 1 — buttoned). Print "YES", if jacket buttoned right, or "NO" if didn't.Problem B: Can any one please tell me why I'm getting error in test 14 http://codeforces.com/contest/691/submission/19109528 since the test case is not fully displayed and can't see it to correct or even trace the answer thanks, Emad

In your mirror function if left == 'w' you are returning true if right == 'W' ( Capital). Here right should be 'w'.

For Problem D, my submission http://codeforces.com/contest/691/submission/19110524 failed on test case 3, it shows the answer for case 3 is "1 2", however I found a lot of other's submission that the answer for case 3 is "2 1". So my question is which is correct?

From what I understood, it should be "2 1".

Same problem :(

Your submission was rejudged. It's Ok now.

Your submissions were rejudged. They are OK now.

Will submissions for problem D for virtual participation be re-judged? because I still have this invalid hack.

It was rejudged, you got OK.

Only submissions are rejudged, right? Hacks are still shown with "Ignored" status.

I am still hacked in the virtual participation submission.

I see that final testing is complete but challenges are still not rejudged (have "ignored" status). Some wrong solutions are passed as a result. See http://codeforces.com/contest/691/submission/19091023 and its challenge 240335 for example. This solution doesn't use path compression and so needs O(n^2) time on average (in the set construction phase) on my test in the challenge. If you are not going to rejudge these challenges, could you please add tests from them?

I can't do rejudges myself. I will add the test to the testset. And discuss possibility to rejudge the challenges.

The rejudge ability is badly needed in Education Rounds. Is it only MikeMirzayanov who can add it?

Where is editorial for this contest ?

OP said it'll be posted soon, just wait!

The runtime for problem E is not realistic at all. I have got TLE on test case 12 and tried it on my PC and it worked in less than 700 ms. I think something wrong is going on.

Try reducing the number of times you compute modulo. http://codeforces.com/blog/entry/46009?#comment-304869

hi, I don't understand the problem D, principally this part: "p is lexicographically smaller than the q if a number 1 ≤ i ≤ n exists, so pk = qk for 1 ≤ k < i and pi < qi"(the core of the problem :) ). Could you please, explain me this. thanks

Let p and q be 2 different permutations. Permutation p is lexicographically smaller than q if the first element that they differ at, is smaller in p than q.

thanks

When is round 15?