### Edvard's blog

By Edvard, history, 6 years ago, translation,

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 blowUpTheStonySilence. 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 blowUpTheStonySilence 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.

• +224

 » 6 years ago, # | ← Rev. 2 →   0 I think I can solve with one or more problems in this test,good luck!
•  » » 6 years ago, # ^ |   0 Wish you good luck
 » 6 years ago, # |   +9 "TAK" and "NIE". So fun)
 » 6 years ago, # |   +54 Codeforces website is very slow during the contest :/
 » 6 years ago, # |   +51 Problem statement is not very clear. :( Also the website is so slow.
 » 6 years ago, # |   +8 The english statements were not very clear in this contest :(
 » 6 years ago, # |   +9 please check problem statement(english) before contest more than once. :(
 » 6 years ago, # | ← Rev. 3 →   +8 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.
 » 6 years ago, # |   +14 Half of round time could not connect. 'The connection has timed out'.
 » 6 years ago, # |   +9 I am still loading problem A.
 » 6 years ago, # |   +134 me reading problem A (before revision)
•  » » 6 years ago, # ^ |   +1 you sir, made my day :D
 » 6 years ago, # |   0 How can O(N^3 * Log(K) ) TLE in problem E?
•  » » 6 years ago, # ^ |   0 My solution took 1.3/3 seconds. I am using statically allocated matrices. I guess maybe with vectors it may TL..
•  » » » 6 years ago, # ^ |   0 I've seen AC solutions with vectors.Java with arrays TLE.
•  » » » » 6 years ago, # ^ | ← Rev. 4 →   0 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
•  » » » 6 years ago, # ^ |   +17 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
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 ignore
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 on what situations is this trick valid and yeah please explain MOD2?
•  » » » » » 6 years ago, # ^ |   0 MOD2 could be any multiple of MOD,
•  » » » » 6 years ago, # ^ |   +5 Thanks, cool idea!
 » 6 years ago, # |   +3 How to solve E?
•  » » 6 years ago, # ^ |   -9 I Have solved it with Matrix exponentiation.
•  » » 6 years ago, # ^ |   +9 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)
•  » » » 6 years ago, # ^ |   0 Any element of matrix C??Does all element will be same?It does not fit with the given sample
•  » » » 6 years ago, # ^ |   0 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.
 » 6 years ago, # |   -13 Why am I getting a TLE in the Problem D? My code
•  » » 6 years ago, # ^ |   +8 TRUST SCANF AND PRINTF!
•  » » 6 years ago, # ^ |   0 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).
•  » » » 6 years ago, # ^ |   0 This way means?
 » 6 years ago, # | ← Rev. 3 →   +7 D: UnionFind to find connected groups, sort each group separatelyE: Let matrix , then the answer is sum of the elements of MK - 1. You can think of it as counting "paths" (sequences) in a graph with adjacency matrix M.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 most max(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 than max(p), using Fenwick Tree or partial sums (e.g. for each index i we find position where ai * aj > max(p) and then sum all counts on suffix starting from j). 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.
•  » » 6 years ago, # ^ |   -18 Why am I getting a TLE in the Problem D? My code
•  » » 6 years ago, # ^ |   0 Hi! Why (ai xor aj)%3=0 is same as the number of bits in ai xor aj are a multiple of 3?
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 Shouldn't the answer of problem E test 4 be 63? My program found 63 valid combinations...http://pastebin.com/HHDqbZ6sTypo: Generated 62UPD: Oh crap, I misread the statement. It's about the NUMBER OF BITS... Now I see.
 » 6 years ago, # | ← Rev. 2 →   0 Someone else tried to solve D using random selection of pairs for swapping? It was a funny idea but wrong, of course. :)
 » 6 years ago, # |   +3 Why didn't they use a template type of definition to create __builtin_popcount() ? I always get one WA for that!
•  » » 6 years ago, # ^ |   +3 This is intrinsic stuff, you can do a template version yourself :)
•  » » 6 years ago, # ^ |   0 Hah! Kept getting Wrong answer on test 7 due to this
•  » » 6 years ago, # ^ |   +4 use __builtin_popcountll() for long long type
•  » » » 6 years ago, # ^ |   0 I did it sir but after One time wasting WA :P
 » 6 years ago, # |   +31 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.
 » 6 years ago, # |   +5 Can someone explain problem e in more details??
•  » » 6 years ago, # ^ |   +5 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.
•  » » » 6 years ago, # ^ | ← Rev. 3 →   0 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
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 6 years ago, # ^ |   0 but 1 isn't a multiple of 3
•  » » » » » » 6 years ago, # ^ |   0 Question asks for xor b/w consecutive elements to have no of 1's in them as multiple of three.
 » 6 years ago, # |   +12 Thanks a lot for such an interesting round, Edvard! And many thanks to authors for the efforts, it was definitely worth it!
 » 6 years ago, # |   +8 Bonus for problem D: calculate the minimum number of swaps to achieve the maximum lexicographically permutation
•  » » 6 years ago, # ^ |   0 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?
 » 6 years ago, # | ← Rev. 2 →   +18 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??
•  » » 6 years ago, # ^ | ← Rev. 2 →   +6 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.
 » 6 years ago, # |   0 In problem B, How is the answer for "opo" is NIE when the answer for "oHo" is TAK?? :/
•  » » 6 years ago, # ^ |   0 The symmetric string is "oqo", which is not the same as "opo".
•  » » 6 years ago, # ^ |   0 s-palindrome is a string that can be mirrored. For example, oqpo — is TAK (q and p are mirrored to each other).
•  » » 6 years ago, # ^ |   0 Thanks a lot :)
 » 6 years ago, # |   0 can anyone explain statement or sample cases of problem E?
 » 6 years ago, # |   0 In C, could be there multiple answers? E.g, 323.345 can be presented as 3.23345E2 and 323345E-3
•  » » 6 years ago, # ^ |   0 323345E-3 is incorrect, there must only be 1 number to the left of the decimal point.
•  » » 6 years ago, # ^ |   0 the answer should be in the form of x = a·10b where 1 ≤ a < 10 so 323345E - 3 is wrong because 323345 ≥ 10
 » 6 years ago, # |   0 Is unexpected verdict in hack 240056 (problem F) caused by load issues (too many B hacks) or something else?
 » 6 years ago, # | ← Rev. 3 →   0 How to solve D? Naive dfs will time out,so how to compute efficiently?Edit : I understood the solution.
 » 6 years ago, # |   +35 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
•  » » 6 years ago, # ^ |   0 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
•  » » 6 years ago, # ^ |   0 It should teach you that such problems exist. I encountered a reversible stepladder and rotatable calculator-style digits.
 » 6 years ago, # | ← Rev. 2 →   0 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, 1200mshttp://codeforces.com/contest/691/submission/19096765 — cin version, 2324msSo the answer is just to drop cin/cout and switch to scanf?
 » 6 years ago, # |   +17 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.
•  » » 6 years ago, # ^ |   0 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.
 » 6 years ago, # |   0 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?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0
 » 6 years ago, # |   +5 That moment when you hacked yourself :D
 » 6 years ago, # | ← Rev. 3 →   0 Can someone please explain Problem Dthat how to model it into a graph. Thanks. Edit:got it. 
•  » » 6 years ago, # ^ |   0 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.
 » 6 years ago, # |   +20 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)
 » 6 years ago, # |   +34 What's going on with D? Is it checker/validator bug somebody found? :)
•  » » 6 years ago, # ^ |   +6 Yes. Unfortunately, someone else is figured it out too and unlike me, he/she is exploiting the bug instead of avoiding it.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +13 ^ So u are saying u got >100 valid hacks.
•  » » » » 6 years ago, # ^ |   +4 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.
•  » » » » 6 years ago, # ^ |   +15 Was judge_chutiya_hai already taken or did you make a typo?
•  » » 6 years ago, # ^ |   0 Unfortunately, this behavior blocks challenging submissions on the real bugs in this problem :( .
•  » » » 6 years ago, # ^ |   0 We will increase hacks phase duration until tomorrow.
•  » » 6 years ago, # ^ |   0 The hacks for the problem D will be rejudged soon. Testing during the contest was correct.
 » 6 years ago, # | ← Rev. 4 →   +39 For problem D, I have tried hacking my submission with such test3 11 3 21 2My output is2 1 3while the answer given by std is actually the same.Obviously the correct answer is3 1 2so there must be sth wrong with std.
•  » » 6 years ago, # ^ |   +10 I think you are right. I have never seen so many rednames are hacked.
•  » » 6 years ago, # ^ |   0 What is the hack for problem D otheer than this?I am hacked.
•  » » 6 years ago, # ^ |   +14 Looks like you made exactly the same mistake as the author solution. No one can hack you until rejudge :).
•  » » » 6 years ago, # ^ |   0 I do not get you?
•  » » 6 years ago, # ^ |   +7 Hacks for the problem D will be rejudged soon.
•  » » » 6 years ago, # ^ |   +5 Please update us when they're rejudged
 » 6 years ago, # |   0 +112 hack... Awesome
 » 6 years ago, # |   0 Can someone explain problem A to me in english? I can't understand the description
•  » » 6 years ago, # ^ |   +4 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 n studs and its statements (0 — unbuttoned, 1 — buttoned). Print "YES", if jacket buttoned right, or "NO" if didn't.
 » 6 years ago, # |   0 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
•  » » 6 years ago, # ^ |   0 In your mirror function if left == 'w' you are returning true if right == 'W' ( Capital). Here right should be 'w'.
 » 6 years ago, # |   +26 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?
•  » » 6 years ago, # ^ |   0 From what I understood, it should be "2 1".
•  » » 6 years ago, # ^ |   0 Same problem :(
•  » » » 6 years ago, # ^ |   +3 Your submission was rejudged. It's Ok now.
•  » » 6 years ago, # ^ |   0 Your submissions were rejudged. They are OK now.
 » 6 years ago, # |   0 Will submissions for problem D for virtual participation be re-judged? because I still have this invalid hack.
•  » » 6 years ago, # ^ |   0 It was rejudged, you got OK.
•  » » » 6 years ago, # ^ |   0 Only submissions are rejudged, right? Hacks are still shown with "Ignored" status.
•  » » » 6 years ago, # ^ |   0 I am still hacked in the virtual participation submission.
•  » » » 6 years ago, # ^ |   0 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?
•  » » » » 6 years ago, # ^ |   0 I can't do rejudges myself. I will add the test to the testset. And discuss possibility to rejudge the challenges.
•  » » » » » 6 years ago, # ^ |   0 The rejudge ability is badly needed in Education Rounds. Is it only MikeMirzayanov who can add it?
 » 6 years ago, # |   0 Where is editorial for this contest ?
•  » » 6 years ago, # ^ |   0 OP said it'll be posted soon, just wait!
 » 6 years ago, # |   0 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.
•  » » 6 years ago, # ^ |   +5 Try reducing the number of times you compute modulo. http://codeforces.com/blog/entry/46009?#comment-304869
 » 6 years ago, # | ← Rev. 2 →   0 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
•  » » 6 years ago, # ^ |   +8 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.
•  » » » 6 years ago, # ^ |   0 thanks
 » 6 years ago, # |   0 When is round 15?