Edvard's blog

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

Hello, Codeforces!

Today is the first day of the spring and it's great!

Educational Codeforces Round 9 will take place on 01 march 2016 at 18:00 MSK for the first and the second divisions. You can read about educational rounds here and here. I should again notice the high density of contests and championships.

<This time it wasn't changed>

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.

</This time it wasn't changed>

The problemset again was totally suggested by Codeforces users. The problem А again was suggested by user unprost (be ready to see a long problem statement). The problem D suggested by Denis Bezrukov pitfall. Alexey Chesnokov CleRIC sent the problem E a long ago. The problems B, C and F was suggested by Lewin Gan Lewin.

Thanks a lot to them and all others who are sending the problems or just ideas of the problems!

The problems was prepared by me (Edvard Davtyan). Thanks to Maria Belova Delinur for checking the English statements. The problems was tested by the same users who suggested them: unprost, Alexey Chesnokov CleRIC and Lewin Gan Lewin. Thanks a lot to all of them!

I hope you will enjoy the problems!

Good luck and have fun!

UPD1: The first part of the contest is finished. You can hack solutions.

UPD2: There are some technical problems. The phase of open hacks will be opened later (several hours).

UPD3: Editorial is ready.

UPD4: The contest is finished. We will start system testing in a few minutes.

UPD5: TOP3 of hackers:

P_Nyagolov — 31 hacks

khadaev — 27 hacks

halyavin — 23 hacks

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

Comments Comments (75)
| Write comment?
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Thank you:)

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

Hello spring and hello another amazing editorial. Good luck to everyone

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

On one hand i also want to prepare some problems but on the other hand i don't want to miss any CF round...

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

I think it would be better if it was rated ^_^

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

    There'd be no difference between regular cf round and educational round if it was rated .

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

I'm running in the the contest and I don't know from which files to take the input and write the output at problem F because input.txt and output.txt don't work for me. I know the code is good because with cin and cout it ran until test 8 I think where I got th time limit exceeded. Please help me.

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

    How would you pass 7 tests with reading from a wrong file? And how does passing 7 tests mean that your code is "good"? Read from the stdin, not from a file. Your program is too slow apparently.

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

      I passed test 7 reading with cin. And i tried to read with fstream.

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

        It's guaranteed that printf() and scanf() are fast enough in C++. And note that maybe your algorithm is too slow.

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

          Of course my algorith is too slow without scanf and printf and this is the point. It doesn't work when i try to read from input.txt

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

can E be solved without FFT?

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

    I don't think so.

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

      aha, then it should be harder than F if the intended solution for F is bitset, IMHO.

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

        Of course it is not intended solution. I'm sorry for that, but I can't increase the size of input, it is already about 67MB. The right solution has complexity O(n2logn).

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

          It's also possible to get O(n^2)

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

            Wow, that's nice! You can sort all edges in O(n2). I didn't notice it during the contest.

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

            Could you explain it?

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

          Are you sure? The input size is O(n2).

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

            Yes. As you can see aij < 109 not aij ≤ 109. It is by the reason of large input size.

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

              I meant that your complexity can't be O(nlog2(n)) because it's smaller than the input size. Maybe you meant O(n2log(n))?

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

      There seems to be bfs solution (let ): let's look for possible sums of k elements, we can get them by starting with k·a0 and trying to find sums, rechable from this by not more than k replacements of a0 with some ai. Basically, there is a graph with vertices and edges from each.

      It is even possible to optimize this solution with bit operations, because all edges are to vertices with sum different from current not more than by an, so we can use some bit manipulation to find edges to yet not visited vertices in , which amortizes to , where w is amount of bits in processor word, i.e. w = 64.

      I hope explanation is relatively clear, you can look in my code (and try to hack it, I was too lasy to implement above optimisation after seeing that code works reasonably fast without it).

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

      Has anyone solved E with just FFT on complex? I get TL6 even with some optimizations.

      UPD: I did it, 4991 ms :)

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

        You can raise polynomial P to the k-th power just by raising every value of FFT(P) to the k-th power.

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

          But if we raise double in 1000th power, there may be problems with precision?

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

          I think you can't do that with doubles (too high degree k). But my third solution do that with NTT. Of course it works faster, but it is not correct of course. To make it correct we should get several random primes.

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

        You do all FFTs on arrays of size 106. That's O(k·maxa·log(k·maxa)·log(k)). If you do FFT on arrays of size equal to the degree of polynoms then complexity will be O(maxa·log(maxa) + 2maxa·log(2maxa) + ... + k·maxa·log(k·maxa)) = O(k·maxa·log(k·maxa))

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

    This solution seems to work without FFT: http://codeforces.net/contest/632/submission/16447568

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

I still cannot hack solutions. What is going on? Can anyone hack now?

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

UPD1: The first part of the contest is finished. You can hack solutions.

How? :P Why doesn't the hacking phase start immediately after the contest is finished?

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

cannot hack

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

I can't hack solutions.

is someone facing the same problem ?

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

where can I see editorial to these problems?

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

    Contest is not over yet. Usually the editorial is published as soon as the hacking phase finishes.

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

Oh, silly me, I thought in 632B - Alice, Bob, Two Teams Bob could take any segment...

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

F: We can prove that if matrix is MAGIC, after removing all values which are maximum among the matrix elements, the remaining part of matrix is collection of MAGIC matrices.

Then we can solve this problem by solving smaller problems recursively. The naive implementation of this idea took O(N^3) times, but good implementation make this algorithm O(N^2 log N).

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

    If you do it in reverse order, starting with empty graph and adding edges in increasing order, then it'll work in O(n2).

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

      Oh, your solution is much easier to implement. (But it requires O(N^2 log N) time since we sort the elements, I think.)

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

        Yes. But edges can be sorted in O(n2) if you notice that in magic matrix there are only O(n) different values. So it's not hard to improve it to O(n2).

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

Can someone explain why am i getting runtime error in the 8th pretest of the 3rd question?
Here is the code.

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

    comparison function should return false when both elements should be considered the same

    now your function returns true so it breaks the sort function. To fix that just change <= to <

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

      Don't read this comment

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

        Ignore the usual comparator, you are defining a new one. The function should work exactly as operator <. Can you say that A<B and B<A are both possible at the same time?

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

          I get you now :)

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

            I am telling you that sort uses < operator, not <= and in rivudas' case it happens that A<B and B<A at the same time ( a=xyz and b=xyzxyzxyz ) :)

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

            It's because the sort function assumes that when your comparison function returns false, if and only if a is strictly less than b. (In other words, a must be placed before b.)

            Let's say a = xyz and b = xyzxyz just as you said, the sort function tries cmp(a, b) and got true. That means a should be before b. But then if for some reason it calls the reflexive cmp(b, a) (or transitive like cmp(b, c) cmp(c, a)) and it got true again, there would be a contradiction, thus the runtime error.

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

              Don't read

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

                Work sometimes doesn't mean work always. You cannot prove correctness by giving examples.

                And to be more specific why you case might work, STL sort is based on intro sort which uses different sorting algorithms depending on the contents and the size of the array. I made your example fail simply by increasing the size of the array.

                http://ideone.com/CQt5jE

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

I've got an off-topic question : how do you suggest new problems ? I mean, to whom do you have to send them ? To GlebsHP?

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

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

    you can write to Edvard :D

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

    Oh sorry, I didn't read that well. Thank you ! :)

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

Edvard, do you know approximately when the hacking phase will be open?

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

    It is already opened. Sorry for late answer.

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

"UPD2: There are some technical problems. The phase of open hacks will be opened later (several hours)."

NourAlhadi when i decided to learn hacking :3 :3

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

How to solve problem E ?

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

I found someone with amazing short (compare to other which use FFT) code to E:

http://codeforces.net/contest/632/submission/16452555

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

Problem C. C++ solutions using bool comp(string& a,string& b){ return a+b<b+a;} seems ~2-3 times slower than solutions using the same in dynamic languages: Python, Perl. That's interesting.

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

Hi, I want to know some idea about how to solve problem D :)

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

    I solved it this way:

    Remap all values from array co counts arr, where index is a value and value is a count of times the value presented in input. Only use numbers <= M (numbers > M won't be in any possible solution).

    Cycle from M to 1. This way we pick our L for test.

    Factorize our L in prime factors (using e.g. Eratosthenes sieve). From factorization generate all possible distinct delimiters (including non-prime ones, e.g. for 30 it would be 30, 15, 10, 6, 5, 3, 2, 1). Get sum of counts[delimiter].

    Pick the best sum.

    Can't say what exactly complexity this solution is, but something around O(500 * M), where 500 is max possible distinct delimiters of any number (it is somehow defendant on M too, 500 is my estimation for max value of 10^6).

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

      It's actually less, maximum of divisors between 1 and 1 000 000 is actually only 240. 240·M is still very risky for 2 seconds, but the actual sum of delimiters is almost half that, , where σ0(x) is the divisor function.

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

        And ln(1000000)*1000000=13815510... Coincidence? I think not.

        PS The reason behind this is that harmonic series diverge as ln(n).

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

      I think I understand. It's somewhat easy I failed to think that because i misread the problem, thinking it was asking for a contiguous sub-sequence

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

        acc!!! I don't even needed to calculate the primes :) I used some kind of dynamic programming

        16463867

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

can anyone show some ideas about E? I see the post above mentioned FFT, I searched it but still no idea...

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

What is "Unexpected verdict"? Hack #217732.

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

    Another solution got "Unexpected verdict" on the same test (Hack #217738). So I guess one of incorrect author solutions was marked as correct by mistake.

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

      Yes. You are right. You hacked my third solution with one (not random) module and binary exponentiation of DFT (not polynomials). Module is 998244353.

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

DP solution for problem E is awesome. I wonder how people think this way in contest time.

Can anyone one please give some problem link that is solvable using this technique.

→ Reply