Автор arsijo, 5 лет назад, По-русски

Добрый день!

В 06.10.2019 18:05 (Московское время) состоится Отборочный Раунд 1 олимпиады для школьников Технокубок 2020. Раунд будет длиться два часа, участникам будут предложены 7 задач. По его результатам лучшие участники (но не более 45% от общего числа участников раунда) будут приглашены на финальный этап в Москву. Для регистрации на раунд и участия перейдите по ссылке. Не забудьте заранее зарегистрироваться на раунд! Для опоздавших будет открыта дополнительная регистрация.

Зарегистрироваться на Отборочный Раунд 1 →
Соревнование открыто для всех в виде отдельных раундов для первого и второго дивизионов.
Для всех участников всех трех редакций этого соревнования будет пересчитан рейтинг.

Параллельно с Отборочным Раундом будут проведены открытые рейтинговые раунды для обоих дивизионов, в них могут принять участие все желающие.

Напомним, что согласно правилам раундов Codeforces во время соревнования ваши решения будут тестироваться только на претестах (предварительном и неполном наборе тестов), а системное тестирование состоится после окончания раунда. Обратите внимание, что претесты не покрывают все возможные случаи входных данных, поэтому тщательно тестируйте свои программы! После прохождения претестов у вас будет возможность заблокировать решение, тем самым получив привилегию искать ошибки и взламывать чужие решения, но отказавшись от возможности перепослать ваше решение при каких-либо обстоятельствах (например, даже если вы найдете ошибку или вас взломают). Со временем задачи падают в стоимости. После системного тестирования учитываются только полные решения. Подробнее про правила соревнований можно прочитать по ссылкам:

Регистрация на олимпиаду Технокубок еще открыта. Победителей и призеров олимпиады ждут значительные квоты при поступлении в престижные технические вузы России и ценные призы! Если вы — школьник 8-11 классов и пока не зарегистрировались на Технокубок, то самое время сделать это:

Зарегистрироваться на олимпиаду →
После регистрации на олимпиаду не забудьте зарегистрироваться на Отборочный Раунд!

В финал соревнования будут приглашены лучшие участники каждого из отборочных раундов (но не более 45% от общего числа участников раунда).

Авторы отборочного раунда — BledDest, MikeMirzayanov, Neon, awoo, Roms, adedalic и я. Кроме того, хочу выразить благодарность тестерам, без помощи которых этот раунд не состоялся бы: KAN, chemthan, gisp_zjz, Kallaseldor, Jeffrey, danya.smelskiy, Juve45!

Для тех, кто впервые на Codeforces: в таблице ниже вы можете найти примеры решений на всех поддерживаемых языках:

Группа языков Языки программирования / компиляторы Примеры
C GNU C, GNU C11 10903473, 17029870
C++ GNU C++, GNU C++11, GNU C++14, GNU C++17, MS C++, etc. 23794425, 5456501
C# Mono C#, MS C# 3195513, 3794163
D D 5482410, 2060057
Go Go 7114082, 21366098
Haskell Haskell 455333, 1668418
Java Java 8 25491359, 23678167
JavaScript V8 35963909, 35681818
Kotlin Kotlin 25779271, 25204556
OCaml OCaml 6157159, 1281252
Pascal Delphi, FPC, Pascal.NET 1275798, 1259434
Perl Perl 2519448, 1277556
PHP PHP 413942, 35875300
Python Python 2, Python 3, PyPy2, PyPy3 35883730 (Py2), 36179112 (Py3)
Ruby Ruby 1837970, 1289551
Rust Rust 25180002, 35652442
Scala Scala 35847980, 2456025

Удачи!

UPD.

Раунд нерейтинговый! После окончания системного тестирования мы объявим сколько человек будут приглашены на финал Технокубка 2020 из этого раунда. Кроме этого, будет проведен четвертый раунд.

Разбор.

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

»
5 лет назад, # |
  Проголосовать: нравится -40 Проголосовать: не нравится

gisp_zjz Liu HongYang niubi

»
5 лет назад, # |
  Проголосовать: нравится -65 Проголосовать: не нравится

Why arsijo?

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

Oh,come on. Let's enjoy this contest!

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

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

A worth-joining contest to end my boring week incredibly <3 <3

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

Hope that we are not going to be punished with long queues

Just for not thanking MikeMirzayanov for this awesome platform. XD

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

Let's hope for clear problem statements

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

я не могу зарегестрироваться на отборочный этап мне пишет ""Извините, только официальные участники чемпионата Технокубок могут принять участие в этом раунде. Если вы школьник 8-11 класса, то для участия зарегистрируйтесь на чемпионат по ссылке https://technocup.mail.ru/" ,что мне делать проблема не уходит

»
5 лет назад, # |
  Проголосовать: нравится -121 Проголосовать: не нравится

Kindly, after the contest, up-vote this comment if the contest was good, down-vote if it was bad, do not vote if it was mediocre.

»
5 лет назад, # |
  Проголосовать: нравится -27 Проголосовать: не нравится

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

.

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

It's going to be my first div.1 contest, so excited for that!

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

what is rule of contest? ICPC or Codeforces?

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

hope arsijo remember the contest he last conducted which was a heck

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

What will be the Scoring Distribution, no of problems etc ?

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

Time to go IM

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

"All you bug are belong to me" — or how to open problems?

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

"Independent" QueryForces!

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

*Me after solving A, B and C

"Let's go to comment section"

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

i guess its an unrated contest because of long queue and not being able to access cf

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

I am not able to submit for last 15 minutes!!

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

Codeforces и unrated братья на века!

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

[DELETED]

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

Go To Hell DDOS Attacker (The Problems Were really nice )

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

Unfortunately, we had a DDOS attack during the round. Codeforces did not work for a few hours. Obviously, the round will be unrated. Also, there will be an additional Technocup Elimination Round.

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

SUCH A SHAME

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

    О да, если би все било нормально я б тоже мастером стал

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

Seems like Codeforces is working again <3

This DDoS attack is such a shame, because the contest was quite nice in my opinion. Do we have any idea why would someone do that? (Or if it was a DDoS and not some other issue)

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

"Nice round"

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

I was doing so well in this contest! :( So angry at the ddos attacker. Hopefully the next round is soon.

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

I would like to submit it quickly. Korea is dawn, but I can't sleep because I wonder the answer is correct. :X

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

F*ck you ddos attacker btw How you solve div2- C ?

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

    Binary search, I guess

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

      Can you please explain ? :)

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

        Basically you binary search for the minimum length you can get

        And to test if a length is ok

        You place the maximum ticket prices at positions where both programs occur i.e. positions divisible by both a and b then the next batch of maximum ticket prices go to positions divisible by a if max(x,y) equals x or b if max(x,y) equals y and the last batch of maximum ticket prices go to positions divisible by a if min(x,y) equals x or b if min(x,y) equals y

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

        Binary search on the number of tickets you will use. You can easily see that if the problem is solvable with k tickets, then it must also be solvable with k+1, and if it is unsolvable with k, it will still be unsolvable with k-1.

        To check if the problem is solvable for a given K, you have to use the k/lcm(a,b) most expensive tickets on the lcm(a,b) positions, the next most expensive ones will be used for the remaining a and b positions (if x > y use the a positions first, else use the b positions first). This guarantees a maximal value to help the environment.

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

        you can use binary search. first sort the array the then we assume that we need to sold mid ticket and for valid mid we use binary search and in check function u can implement that if we sold the mid number of ticket than profit is more than we reduce right by mid-1 otherwise we increase left by mid+1. At last our answer is mid. you can see the my solution https://mirror.codeforces.com/contest/1241/submission/62071599

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

      NO.. It's greedy

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

      I solved it with greedy we need to maximize sum we first take maximum values for (x + y) after that we take values to maximum of x and y and then to minimum of x and y

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

      btw i solve it with Greedy and my solution complexity is O(N)

      so for my solution i put the 3 possibility of discount into a vector in order to ignore i-th index which has no discount:

      1. x+y

      2. max(x,y)

      3. min(x,y)

      and then i sort the ticket price descending.

      for each iteration i mark where's the ticket price goes (3 possibility of discount) by putting it into queue.

      if at i-th iteration the discount is min(x,y) just add the value and put the index into a queue.

      if at i-th iteration the discount is max(x,y) we move the ticket price at min(x,y)'s queue to max(x,y)'s queue and put the current ticket price in min(x,y)'s queue since the current ticket price is lower than previous ticket price (sort descending)

      if at i-th iteration the discount is x+y we move max(x,y) to x+y and min(x,y) to max(x,y) and current to min(x,y)

      example:

      ticket price : 300 200 100 100

      discount : 1 1 2 3

      and here's how the ticket price move for each iteration

      • 300
      • 300 200
      • 100 200 300
      • 100 100 200 300

      source code: https://mirror.codeforces.com/contest/1241/submission/62074247

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

    Suppose x > y, and the number of tickets sold (call it L) is known in advance, and we just want to know what the optimal profit will be. Let lcm be the least common multiple of a and b.

    Then the best strategy would be to place your most expensive tickets on multiples of lcm (since this gets you (x+y)%). You can compute how many of those there are in constant time (there are L/lcm of them), and you can use a cumulative sum array to compute the total value of all the tickets in that range (sort the tickets by descending price and sum from 0 to L/lcm). Similarly, place your next most expensive tickets on multiples of a (there are L/a - L/lcm of them), and your least valuable tickets on multiples of b (there are L/b - L/lcm of them), and use the cumulative sum array to get the profit. After you have these quantities, you can compute the total price and compare it to K to see if it satisfies the problem requirements.

    Now you want to know the minimum L. You can binary search for L, or (since the bounds are low) just do linear search. If you didn't implement the previous paragraph in O(1), you probably need binary search for this part.

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

      After putting the maximum priced tickets for x+y shpouldn't we consider a and b along with x and y too? Suppose a is very small so its frequency will be more so won't the optimal way would be to use x because of that even if y>x ?

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

    I had a pretty stupid solution. First sorted the list then used 3 queues for type a and b and both. for each length the sum is updated in O(1) with at most 3 push/pops. 62028584

»
5 лет назад, # |
  Проголосовать: нравится -9 Проголосовать: не нравится

 I submited 4 times. -150 points and get last time @@??? why

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

How to solve div2-D?

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

    I submitted bottom-up DP. We can show that any element will be moved at most 1 time. So there is exactly 3 options. We either move it to the beggining, move it to the end, or don't touch it. So it's DP[N][3], with DP[i] = minimum amount of turns to sort the first i elements, and [0..2] to denote those 3 options.

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

      Thanks. Nice solution!

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

      can u please explain why dp[i][1]=i in both cases. and why dp[i][2] is same in both cases

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

        Let's say [1] means move ith element to the left and [2] to the right. If we move ith element to the left, then it will become leftmost element in our array. In that case, the only possible way to sort the first i elements (considering we won't move ith element anymore) is to move the first i — 1 elements to the left, using exactly i turns. And if we move ith element to the right, then we don't care about how we sort the first i — 1 elements, because ith will become the rightmost element, thus it will be the same in both cases.

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

Unlucky arsijo... Why problem occurs (!) always in his round?

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

why the blog doesn't thank MikeMirzayanov to the platform codeforces, maybe this is the issue xD

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

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

the statement of the problem Cdiv2 could be shorter . :)

i know you probably worked on the statements and you may have a purpose .

it was just an advice to shorten the statements as much as you can. :)

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

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

    We need a version of this pic with Mike + CF coordinators. Not just cut+paste in Paint, but some decent work.

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

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

Looks like a few people do not see some of their submissions. We are investigating the issue.

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

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

Hope upcoming educational will have nice problems as well!:)

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

Problem D is very similar to one task from CSAcademy (the only difference is that the given array was a permutation in CSA, but is doesn't really change the solution).

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

It feels like every rounds kinda DDoS attack, but this time bigger.

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

In div 1 F, are these random solutions hackable? 62022214 62023134

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

I Was enjoying this round so much that I was reloading every now and then to see the problem getting resolved and never lost hope! Hard Luck arsijo!!

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

arsijo in your last 2 round, you forgot to thank MikeMirzayanov for platform and polygon. then both of this rounds became unrated !

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

How to solve div1-D?

»
5 лет назад, # |
  Проголосовать: нравится -19 Проголосовать: не нравится

arsijo's rounds are always unated!

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

is the div2 unrated?

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

Why are submissions and testcases kept hidden??....Or is this something, only I am facing??

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

It's probably the most upvoted unrated round.

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

Can someone someone explain problem E (definition of K coloring)?