Educational Codeforces Round 26
By awoo, history, 7 years ago, translation, In English

Hello Codeforces!

On August 3, 18:05 MSK Educational Codeforces Round 26 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

The round will be unrated for all users and will be held on extented ACM ICPC rules. After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were prepared by Ivan BledDest Androsov, Alexey Perforator Ripinen, Mike MikeMirzayanov Mirzayanov and me.

Good luck to all participants!

Don’t miss your chance to be a part of this leader board in the next ACM-ICPC World Finals by reserving your spot in the 2nd Hello Barcelona Programming Bootcamp in collaboration with Moscow Workshops ACM ICPC.

Check out the winning statics of Universities that participated in this special training — World Finals 2017 Results.

8 out of 12 prize-winners of the World Finals 2017 participated in Moscow Workshops ACM-ICPC!

Take a look back on our previous "Hello Barcelona ACM-ICPC Bootcamp, in collaboration with Moscow Workshops ACM-ICPC". Students and coaches from all over the globe gathered at our campus to learn from and work with the world’s top programmers, soak in the Barcelona sun, and share in the comradery built within the programming community. Harbour.Space University is looking forward to hosting again, this time at the beautiful and technologically mind bending Media-TIC building.

UPD: Editorial is available

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 dotorya 7 174
2 LHiC 7 212
3 uwi 7 244
4 Belonogov 7 289
5 MrDindows 7 297

Congratulations to the best hackers:

Rank Competitor Hack Count
1 uwi 325:-19
2 halyavin 323:-30
3 andreumat 53:-1
4 CurtizJ 45:-2
5 naksh9619_ 36:-5

1361 successful hacks and 513 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A marcoskwkm 0:01
B dotorya 0:05
C irkstepanov 0:07
D fatego 0:11
E dotorya 0:19
F snuke 0:36
G fatego 0:45

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

Comments Comments (62)
| Write comment?
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

delayed by 10 minutes

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

    I thought no one has noticed the delay because until 4 min ago there is no comment but it was delayed 10 min before original starting time

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

      maybe they focus on the problems not announcement :)

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

Hi first thx for preparing the contest But Why So delay?!

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

20 minutes penalty for wrong submit is too much for 2-hours contest, don't you think? What about decreasing this value for educational rounds?

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

    Well, mostly I can agree with you, 20 minute penalty for any little bug, is a bit too huge, but on the other hand, it's EDUCATIONAL round, so scores doesn't really matter. Here the only goal is to improve, not to compete with others.

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

How to solve E?

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

I have known how to solve E,but it's too late!

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

How to solve D, I think it's dp but I can't find it. :'(

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

    You can notice that the roundness is equal min(v1, v2) where v1 = number of 5 in a number, and v2 is number of 2 in a number. So just do dp[size_of_subset][number_of_5] = max_number_of_2.

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

    First: the number of trailing 0's is the minimum number of 2-factors or 5-factors.
    So now we just have to pick a subset to maximize this minimum. I solved it via a knapsack with 2 states, the number of element in the subset, and the number of 5-factors.

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

    dp[i][j][L] = max number of 2 when choosing j numbers from the first i numbers, with a total of L 5's. L won't be larger than 5000 (5^26>10^18).

    By the way, that's 200*200*5000=2*10^8 operations, why it works so fast(under 200ms)?

    29170931

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

      Is it because they haven't included stronger test cases yet?

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

        Any test with n = k = 200(test #21) should be the slowest for my code.

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

          so have you figured out why is it so fast?

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

            Why it should be slower? It's absolutely normal time for such amount of simple operations.

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

    UPD: The following is wrong. The solution is an N^3 DP.

    I just tried the problem, did the following DP.

    The first observation is that, for any point, the total number of zeroes = min(number of twos, number of fives).

    Let twos[i] = number of twos in the number at the ith index, fives[i] = number of fives in the number at the ith index.

    Declare dp[i][j] as a pair, dp[i][j].f = number of twos in our set, dp[i][j].s = number of fives in our set.

    dp[i][j] = best subset we can make until index i with j numbers in our subset.

    If min(dp[i — 1][j].f, dp[i — 1][j].s) > min(dp[i — 1][j — 1].f + twos[i], dp[i — 1][j — 1].s + fives[i]), dp[i][j] = dp[i-1][j].

    Else, dp[i][j].f = dp[i — 1][j — 1].f + twos[i], dp[i][j].s = dp[i — 1][j — 1].s + fives[i].

    Answer is min(dp[N][K].f, dp[N][K].s). Complexity is O(N^2).

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

      Hacked you with this case: 

      3 2
1024 1000 9765625
      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Nice! Sorry for the confusion, my solution got accepted on the normal tests so thought I was good. Guess I'll go with the N^3 DP. Initial logic is flawed on cases with separate twos and fives :D. Edited my comment. Thanks!

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

      It can't work because you cannot count dp with only those informations. You don't know what is best pair. Maybe optimal solution is take one number power of two and next one power of 5.

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

How to solve D?

I did DP[i][k][s] — a maximal number of 2 in prefix [1..i] when we take k numbers and product of those numbers has s factors equal 5.

1 <= i,k <= n , 0 <= s <= 5000

It was too slow.

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

    i did the same and my solution works under 100ms.

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

    It wasn't too slow, you got mle, so you just needed to keep the only last layer of dp.

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

    OK, I had a bug.

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

is solution for D Dp state reduction?

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

Problem E is so interesting and I think it's original problem, it would be better if it was used in rated contest (if it's indeed original)

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

    very nice problem indeed...I couldn't solve it during the contest..any hints???

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

      notice that gcd(a , b) always increases in this process , so for a particular value of b , find the max b' < b where gcd(a , b') > gcd(a, b) , this can be done in O(P) time where P is the number of distinct prime factors of a , and since number of distinct gcds are , total complexity is

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

        A better bound than on the number of iterations is as in ever step gcd gets multiplied by some integer >= 2.

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

    I was thinking is the max number in array A^j is sum A[i]*binomial(j+n-i, n-i)? How to calculate binomials fast enought?

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

I was enjoying this contest. Short description and interesting problems. :)

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

Hey, Can anyone tell me why my code failed in Test #15 of Problem B. Here's a link : My Solution

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

Hints for F?

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

    I think brute-force can solve F, for the answer won't be too large if n>3 (after removing leading zeros). When n=2 or n=3, we can use binary search. However, the overflow problem troubled me a lot, so I didn't complete this method during the contest :(

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

      We can do binary search every time if we succeed to calculate binomial coefficients :D

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

      How exactly the binary search part works?

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

        Max number is rightmost. It is just sum of elements using binomial coefficients. It comes from pascals triangle property what A[i, j]=A[i-1, j]+A[i, j-1].

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

        When n = 3 and arr = [a, b, c], on m-th iteration we have third number in array equal to , so we can use binary search to find first m, for which this value is  ≥ k.

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

3 100 BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRG why answer is no for this test case??

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

    It has G in a row of R.

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

    there's a 'G' at the end of the last row...because of that there are not three stripes of different colors to make a valid flag

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

Can D be solved faster than O(Cn^3), where C is log5(1e18)?

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

Do red coders use some kind of script for hacking or something?

One refresh in my status page shows 2-3 hacks by halyavin

(please tell me your secret :v )

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

    Only 2-3? Sometimes before I saw uwi had +55 hacks .. Just after 1 minute I refreshed page and saw +77 :| Now it is +124+ \m/

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

      you can't say only 2-3 :v your rate is (77-55)/60s which is less than (2)/2s So I am ahead of you in observing this phenomenon 8-)

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

When do we get editorials for this contest ?

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

what is hack test for D except this one :

3 2

4 10 25

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

If our code is hacked then can we see the hack case? If so how?

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

    During hacking time, only hackers know the case. I think it is good to send message to the hacker.

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

      Ohh ok alright. I'll do that. Thanks!

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

      Also can you please tell me that if I submit a solution now does it run on stronger test cases or the pretests from the edu round?

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

        Sorry I'm not sure. Let's check in this round.

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

        i guess on stronger tests but still people can hack you:)

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

        They add all succesful hacks' cases to system tests in practice.

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

Auto comment: topic has been updated by awoo (previous revision, new revision, compare).

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

Why are they showing rating change on the right hand side??????!!!!!! its so sad that we cant get that!! its like they are teasing us!

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

    I don't see any rating, i think you have some rating predictor extension installed.

    → Reply