Блог пользователя KAN

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

Добрый день!

В воскресенье, 21-го октября в 11:05 по московскому времени состоится Отборочный Раунд 2 олимпиады для школьников Технокубок 2019. Раунд будет длиться два часа, участникам будут предложены 6 задач. По его результатам лучшие участники (но не более 45% от общего числа участников раунда) будут приглашены на финальный этап в Москву. Для регистрации на раунд и участия перейдите по ссылке. Не забудьте заранее зарегистрироваться на раунд! Для опоздавших будет открыта дополнительная регистрация (с 11:15 до 13:05).

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

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

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

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

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

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

Авторы задач — Александр Kostroma Останин, Александр Golovanov399 Голованов, Артем komendart Комендантян, Денис Denisson Шпаковский и Дарья Dashk0 Колодзей.

Для тех, кто впервые на 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

Удачи!

Раунд завершен, поздравляем победителей!

Технокубок 2019 - Отборочный Раунд 2

  1. Holidin
  2. receed
  3. Sonechko
  4. radoslav11
  5. scanhex

Codeforces Round 517 (Div. 1, основан на Отборочном раунде 2 Технокубка 2019)

  1. Radewoosh
  2. ainta
  3. 300iq
  4. TLE
  5. RAVEman

Codeforces Round 517 (Div. 2, основан на Отборочном раунде 2 Технокубка 2019)

  1. cz_yixuanxu
  2. orbitingfIea
  3. I_Love_Irelia
  4. djq_fpc
  5. buaads

Опубликован разбор.

UPD: Лучшие 200 участников отборочного этапа Технокубка приглашаются в Финал олимпиады. Поздравляем победителей!

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

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

CF rounds on weekends are the most fun.

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

Perfect time for Chinese users!

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

..

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

This weekend,

It's not a weekend in most Arabic countries XD

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

How many problems? When do we know the score distribution?

PD: Just a joke: Where is thanks to Mike and Polygon and ITMO??

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

Исправьте пожалуйста ошибку, сегодня же будет 2 отборочный раунд

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

Elimination round(not CF) will be rated or no?

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

A really good time for Chinese users :).

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

very less participation :(

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

Delayed by 5min!

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

delay :(

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

Score distribution?

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

I love contests at 3 am :)

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

I am not able to submit code, getting error "you have submitted exactly the same code before". Please someone look into this matter. I have not done any submission in that problem.

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

div2D was dp or bfs?

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

    Both of them :)

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

    I spent so much time on this problem and didn't manage to do it in the end, is there a way to compute for each i, j the lexicographically smallest path from i, j to n, n?

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

      I did it with dynamic programming. For each field you just need to know if you want to go right or down. So create a table int dp[2001][2001] with 3 possible values: 0 — go down; 1 — do right; 2 — it doesn't matter (both going down and right will produce same string). We fill entries of dp from n, n to 1, 1 (backward). how to fill this array? For boundary entries (i = n and j = n) it is obvious, for others dp[i][j] = fillDp(i + 1, j, i, j + 1);

      //(x, y) - pointer which is lower, (b, a) - pointer which is to the right
      int fillDp(int y, int x, int b, int a) {
          if (arr[y][x] < arr[b][a]) return 0; //you can only go down
          if (arr[y][x] > arr[b][a]) return 1; //only right
          if (b == y && a == x) return 2; //doesn't really matter which way
          //if letters are the same and we check different fields
          //we either move according to dp or (if dp == 2) we move pointers closer to each other
          if (dp[y][x] == 0) y++;
          else x++;
          if (dp[b][a] == 1) a++;
          else b++;
          return fillDp(y, x, b, a);
      

      Edit: arr = original array with letters

      Computing path is just going with pointers in dp.

      I can't actually prove it works in O(nm) but I got accepted. Here is my solution — a little more verbose: 44647952

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

What was pretest 15 in div2 C? :(

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

    Something like 147694707 63714381

    The sum m + n in this case should be 20562.

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

      It works for me, and I got pretest 15 wrong. What's special about this test case?

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

        I stress-tested my WA on pretest 15 with the solution that passed that test case to get that. I'm sorry that I don't see anything special about this test case :(.

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

    Got 6 WA in that. But, figured it out. It was because of not using long long int.

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

300iq Becomes Legendary Grandmaster!!

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

How do you solve div2B?

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

    DP by O(16n) I'm not sure it's a correct algorithm.

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

    DFS is enough.

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

      Sorry! I find a hack data to hack DFS. It is:

      100000
      3 3 3 2 3 3 3 3 2 3 3 3 3 2 3 3 3 3 2 3 ...(repeat)
      0 2 0 0 0 0 2 0 0 0 0 2 0 0 0 0 2 0 0 0 ...(repeat)
      

      answer is:

      YES
      1 2 3 0 2 1 2 3 0 2 1 2 3 0 2 1 2 3 0 2 ...(repeat)
      

      I have hacked lots of codes using DFS to solve problem B. If we add this data for judging, a lot of codes will be hacked.

      The reason why it can hack DFS is when a = 3 and b = 0, t can be 0, 1, 2, 3.

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

      Sorry for my reckless. It seems my computer is too weak to run this data. I find that DFS is right to solve this problem. Very sorry!

      Because if ti has been determined, ti + 1 will have only one value to choose. Specially, if a = 3, b = 0, t can be 0, 1, 2, 3. But if ti has been determined, we should not worry about ti + 1.

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

    Brute force the value of tn. Given ai, bi, and ti + 1, it is easy to show that there can be at most one ti that satisfies the given constraints.

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

      Yes, and ti equals ai + bi - ti + 1. Because x&y + x|y = x + y.

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

        How did you get this relation?

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

          By Binary Numbers.

          x + y = x + y — x & y + x & y = x + (y — x & y) + x & y

          Because any digit of x and that of (y — x & y) are different,

          So x + (y — x & y) = x | y

          So x + y = x | y + x & y

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

Div2F / Div1D was bfs?

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

I finished fixing div2.D and the contest is over

Now, I hope my solution is not correct ...

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

Lose to constructing.

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

How to solve div2-C , i tried bin Search but i knew it's not working good ,, any hint ?

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

    Let k be the largest integer such that 1 + 2 + ... + k <= a + b. Then it's always possible to construct an answer with n + m = k.

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

in B all a[i] and b[i] gives only two numbers except when a[i]=3 and b[i]=0 then t[i]=1 and t[i+1]=2 or t[i]=0 and t[i+1]=3 right?

I couldnt submit my last solution because I did not understand my new stupid error while debugging which is we can't write cout<<1&3; that gives an error and Idk why

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

    when you type cout << 1&3 compiler reads << as bit shifting

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

      man if my solution was right and i couldnt submit it because of that ... meh

      edit: it's wrong anyway:P

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

I slept just 3 hours to take this CF, let's see how my C fares the system tests :Dd. Already had to resubmit once during the contest

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

What was pretest 8 for div2D ?

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

How I solve Div2-C/Div2-A:

  • Write a greedy solution, get WA on test 15.

  • View submission detail and realize the checker's answer is not the same as the sample answer. Screenshot from 2018-10-21 05-32-10.png

  • Analyze the pattern and write a new solution.
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

wow, very weak pretests again

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

Full Feedback contests are the best.

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

    But remember that in most rated Codeforces round, you don't receive full feedback, especially when the pretests are weak :D.

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

    I'm of the opinion that problems which are going to have very few solves anyway almost always ought to have virtually full feedback, i.e., the systests should not have anything special (new cases, etc) that the pretests don't have, especially considering that if you fail systest you get a score of 0.

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

It seems that div2C/div1A system tests are weak. After the contest I found a bug in my code that makes it fail : for the test
7 1 it gives the following output :

3
2 3 4
1
1

which is obviously wrong. And still my solution got AC. (tmw when you think that the pretests are weak but after the systests it turns out the systests are weak too xd)

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

What is the answer to this case for C? LHiC's AC code gives NO.

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

    My AC code gives

    YES
    3
    3 5 7
    3 4 5
    1 4 7
    
  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +24 Проголосовать: не нравится
    YES
    3
    5 6 7
    1 4 7
    4 5 6
    
    

    Weak tests ¯\_(ツ)_/¯

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

    Similarly, I resubmitted because my first submit uses too many operations in the case

    100000
    0 1 0 1 0
    ...
    0 1 0 1 0
    0 0 0 1 1
    

    (line breaks added for clarity)

    But turns out my first submit would also have passed :/

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

Waiting for tutorial.

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

Waiting for my new rating... And of course waiting for tutorial....

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

Возьмут ли меня, если первые сто человек решили не меньше трех задач, 101-й решил две, а я нахожусь на 103-м месте с тремя задачами?

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

Здравствуйте, сколько человек берут в финальный раунд ?

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

The tests for div1 C seem to be so weak that some wrong codes passed.

44641451 The hack data is : 1 1 0 1 0 1 0 1 0 1 0 ...

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

    Uhhhh that is the obvious "naive" solution that I didn't bother coding because surely it wouldn't pass right?.... but it does.

    And then I didn't find a good solution during the contest :/

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

    After more thinking I realise this solution is quite solid with a small tweak. If try it twice and take the best solution, once normally and once ignoring the first 1 (and do the first 1 manually later) then it is perhaps not possible to make a counter case.

    Anyway there are like dozens of solutions and I came up with zero of them during the contest.

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

can someone plz tell me whats wrong with my code for Div2D?? 44650538

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

As I see, the problems and the score distribution in the Technocup Round and in the Div 2 version were the same. However, the scores obtained in the Technocup Round were smaller compared to the Div 2 version. For example, score 2500 is in top 40 in the Technocup, whereas in the Div 2 version, someone with 2500 is on the 200th + position. So I guess that participation in the Technocup would have helped you increase your rating more than in the Div 2 version.

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

Maybe the tests for Div1C are not strong enough

these solutions were hacked by my data.

44638710

44641451

44641456

data:

125
1 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0
1 0 1 0 1
0 1 0 1 0

Update: Oh, after posting this review, I found that cuizhuyefei has already mentioned it

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

Well, after contest, I have found a hack data to hack DFS solution in Div2.B.

We just use a form like:

100000
3 3 3 2 3 3 3 3 2 3 3 3 3 2 3 3 3 3 2 3 ...(repeat)
0 2 0 0 0 0 2 0 0 0 0 2 0 0 0 0 2 0 0 0 ...(repeat)

answer is:

YES
1 2 3 0 2 1 2 3 0 2 1 2 3 0 2 1 2 3 0 2 ...(repeat)

If you use DFS to solve this, you will get Runtime Error.

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

    If possible, please add this data to hack someone who didn't solve the question well, including me :-) . Thanks.

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

    Sorry for my reckless. It seems my computer is too weak to run this data. I find that DFS is right to solve this problem. Very sorry!

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

I faced problem in B when ai =3 and bi=0 then ti and ti+1 can take 0,1,2,3 .can anyone help?

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

    You can try to make first t( t1 ) be 0, 1, 2, 3. And the sequence will be constructed.

    We can think about this:

    If t1 has been determined, t2 will also be determined. Obviously, if ti has been determined, ti + 1 will be determined, too. For example, if ai = 3 and bi = 0, ti can take 0, 1, 2, 3. But don't forget that ti has been determined. ti will only has one value to choose, and it's easy to solve. Hope I can help you :-).

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

the rating changes is unfair. in official round if you solve just 3 problem you will get high rating changes but in Div2 round if you solve 3 problem your rating change is not as high as rating chane in official round.

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

I noticed that the announcement and editorial are not linked to the problems, can some admin do this? Thanks

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

Does anyone know if there will be a parallel open round again for the upcoming Technocup Elimination Round 3 in a few days?