Edvard's blog

Educational Codeforces Round 14
By Edvard, history, 8 years ago, translation, In English

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.

  • Vote: I like it
  • +224
  • Vote: I do not like it

Comments Comments (109)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like it

"TAK" and "NIE". So fun)

→ Reply
»
8 years ago, # |
  Vote: I like it +54 Vote: I do not like it

Codeforces website is very slow during the contest :/

→ Reply
»
8 years ago, # |
  Vote: I like it +51 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I am still loading problem A.

→ Reply
»
8 years ago, # |
  Vote: I like it +134 Vote: I do not like it

me reading problem A (before revision)

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve E?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    I Have solved it with Matrix exponentiation.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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)

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      It does not fit with the given sample

      → Reply
»
8 years ago, # |
  Vote: I like it -13 Vote: I do not like it

Why am I getting a TLE in the Problem D?

My code

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    TRUST SCANF AND PRINTF!

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +7 Vote: I do not like it

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

E: 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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    Why am I getting a TLE in the Problem D?

    My code

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

I always get one WA for that!

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    use __builtin_popcountll() for long long type

    → Reply
»
8 years ago, # |
  Vote: I like it +31 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Can someone explain problem e in more details??

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          but 1 isn't a multiple of 3

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

            → Reply
»
8 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +18 Vote: I do not like it

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??

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In C, could be there multiple answers?

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the answer should be in the form of x = a·10b where 1 ≤ a < 10 so 323345E - 3 is wrong because 323345 ≥ 10

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is unexpected verdict in hack 240056 (problem F) caused by load issues (too many B hacks) or something else?

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

Edit : I understood the solution.

→ Reply
»
8 years ago, # |
  Vote: I like it +35 Vote: I do not like it


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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.net/contest/691/submission/19096778 — scanf version, 1200ms

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

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

→ Reply
»
8 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

That moment when you hacked yourself :D

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

Edit:got it.
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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)

→ Reply
»
8 years ago, # |
  Vote: I like it +34 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +13 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +4 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        Was judge_chutiya_hai already taken or did you make a typo?

        → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      We will increase hacks phase duration until tomorrow.

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
8 years ago, # |
← Rev. 4   Vote: I like it +39 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

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

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Hacks for the problem D will be rejudged soon.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Please update us when they're rejudged

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

+112 hack... Awesome

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem B: Can any one please tell me why I'm getting error in test 14 http://codeforces.net/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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
8 years ago, # |
  Vote: I like it +26 Vote: I do not like it

For Problem D, my submission http://codeforces.net/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?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It was rejudged, you got OK.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am still hacked in the virtual participation submission.

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.net/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?

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Where is editorial for this contest ?

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    → Reply