Автор PikMike, история, 12 месяцев назад, По-русски,

Привет, Codeforces!

3 августа в 18:05 по Москве начнётся Educational Codeforces Round 26.

Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.

Раунд будет нерейтинговый. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. После окончания раунда будет период времени длительностью в один день, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.

Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.

Задачи вместе со мной придумывали и готовили Иван BledDest Андросов, Алексей Perforator Рипинен и Михаил MikeMirzayanov Мирзаянов.

Удачи в раунде! Успешных решений!

Не упустите возможность попасть в список победителей финала ACM-ICPC, зарезервируйте себе место во втором Hello Barcelona Programming Bootcamp (в сотрудничестве с Moscow Workshops ACM-ICPC)!

Посмотрите на статистику достижений участников этих сборов на прошедшем финале — World Finals 2017 Results.

8 из 12 призёров финала 2017 года принимали участие в Moscow Workshops ACM-ICPC!

Вспомните, как проходили первые сборы "Hello Barcelona ACM-ICPC Bootcamp (в сотрудничестве с Moscow Workshops ACM-ICPC)". Студенты и тренеры со всего мира собрались там, чтобы учиться у ведущих программистов мира и работать с ними, наслаждаться солнцем Барселоны и стать частью дружного сообщества программистов. Harbour.Space University снова рады приветствовать всех на сборах, на этот раз в красивой и высокотехнологичной постройке Media-TIC.

UPD: Разбор доступен по ссылке

Поздравляем победителей:

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

Поздравляем лучших взломщиков:

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

Было сделано 1361 успешных и 513 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

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

 
 
 
 
  • Проголосовать: нравится  
  • +104
  • Проголосовать: не нравится  

»
12 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

All the best everyone, my target will be to atleast solve 3 out 7 problems, hope I reach my target :)

»
12 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

delayed by 10 minutes

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Здравствуйте. Не подскажите, будут ли отсортированы задачи по сложности?

  • »
    »
    12 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    Мы постарались расставить их по сложности, однако не гарантируем корректность расстановки.

»
12 месяцев назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

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?

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    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.

»
12 месяцев назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

How to solve E?

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
12 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    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.

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

  • »
    »
    12 месяцев назад, # ^ |
    Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

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

    • »
      »
      »
      12 месяцев назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      Hacked you with this case:

      3 2
      1024 1000 9765625
      
      • »
        »
        »
        »
        12 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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!

    • »
      »
      »
      12 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
12 месяцев назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

is solution for D Dp state reduction?

»
12 месяцев назад, # |
Rev. 2   Проголосовать: нравится +9 Проголосовать: не нравится

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)

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      12 месяцев назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        12 месяцев назад, # ^ |
          Проголосовать: нравится +20 Проголосовать: не нравится

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

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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?

»
12 месяцев назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hints for F?

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 :(

    • »
      »
      »
      12 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      12 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How exactly the binary search part works?

      • »
        »
        »
        »
        12 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        12 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    It has G in a row of R.

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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

»
12 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
12 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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 )

»
12 месяцев назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

When do we get editorials for this contest ?

»
12 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

what is hack test for D except this one :

3 2

4 10 25

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

    • »
      »
      »
      12 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      12 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      • »
        »
        »
        »
        12 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        12 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        12 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
12 месяцев назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

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!

»
12 месяцев назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

I might want to thank you for the exertion you have made in composing this article. You have share wonderful post which might be share with my friends. $1 Hosting is the hosting website where you can get hosting plans with discount & deals.

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

When would Solution of this problem be provided?

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
11 месяцев назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Nice to share the education codeforrce!

If you are looking for holiday packages services then visit www.vistara.tours