Codeforces Round 679 (Div.1, Div.2) and Technocup — Elimination Round 1
By Golovanov399, 4 years ago, translation, In English

Hi all!

This weekend, at Oct/25/2020 14:05 (Moscow time) we will hold Codeforces Round 679. It is based on problems of Technocup 2021 Elimination Round 1 that will be held at the same time.

Technocup is a major olympiad for Russian-speaking high-school students, so if you fall into this category, please register at Technocup 2021 website and take part in the Elimination Round.

Div. 1 and Div.2 editions are open and rated for everyone. Register and enjoy the contests!

The Elimination Round authors are AndreySergunin, Endagorion, amethyst0, and me, Golovanov399. Thanks to KAN and 300iq for their coordination. This round would also be not possible without the help of our testers: kalki411, 300iq, arjunsanjeev7, brunomont, Chocobar, iankury, low_, psevdoinsaf, JinhaiChen, and teapotd, thank you so much!

Have fun!

The Elimination Round will feature 6 problems, preliminary costs are
500 — 1000 — 1500 — 2000 — 2250 — 3000.

Div. 1 will feature 5 problems, preliminary costs are 500 — 1000 — 1250 — 2000 — 2500.

Div. 2 will feature 5 problems, preliminary costs are 500 — 1000 — 1500 — 2000 — 2250.

Добрый день!

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

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

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

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

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

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

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

Авторы отборочного раунда — AndreySergunin, Endagorion, amethyst0 и я, Golovanov399. Спасибо KAN и 300iq за координацию. Кроме того, хочу выразить благодарность тестерам, без помощи которых этот раунд не состоялся бы: kalki411, 300iq, arjunsanjeev7, brunomont, Chocobar, iankury, low_, psevdoinsaf, JinhaiChen и teapotd!

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

Удачи!

Обратите внимание, в Отборочном Раунде Технокубка будет 6 задач, предварительные стоимости:
500 — 1000 — 1500 — 2000 — 2250 — 3000.

В div. 1 будет 5 задач, предварительные стоимости: 500 — 1000 — 1250 — 2000 — 2500.

В div. 2 будет 5 задач, предварительные стоимости: 500 — 1000 — 1500 — 2000 — 2250.

Congrats to the winners!

Technocup:

  1. oleh1421
  2. usachevd0
  3. turmax
  4. Egor.Lifar
  5. sadovan

Div. 1:

  1. tourist
  2. QAQAutoMaton
  3. Rebelz
  4. Marcin_smu
  5. jijiang

Div. 2:

  1. Algorithms_with_Shayan
  2. KanbeKotori
  3. waaitg
  4. DepthFirstSearch
  5. AceKing

Editorial is available.

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

Comments Comments (198)
| Write comment?
»
4 years ago, # |
  Vote: I like it +192 Vote: I do not like it

As the author of two problems I'd like to ask you guys to read all the problems and not to rage quit if you dislike a problem too much

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

    Don't say that you authored either of problem A, B or C of this contest

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

    As the author of all other problems, I agree with this comment:D

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

    i am getting my version of "peter tingle!" :'(

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

    Dont know why but after seeing all author names I have a feeling round's gonna be hard :/

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

Is it rated?

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

As a tester, Problems are really good and interesting. Good luck!!

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

I see low_ as a tester. Congrats!!

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

As a tester, I approve this contest.

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

In before

If you don't want failed system testing, submit correct code

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

I am able to register for official contest too is it ok .

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

Which One should I register for uprating? (rating ability about 1900) Could anyone give me some suggestion

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

    Actually, you don't have much choice
    You should be able to register only for one as far as I understand

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

HALA Madrid!!!

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +17 Vote: I do not like it

Notice the unusual starting time,Golovanov399,I think this should be mentioned

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

Notice the Unusual time. GOOD LUCK :)

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

Oh my
Notice that it is based on the olympiad (kind of) for Russian students of 8-11 grades.
For some reason it is not written so explicitly in the English page. But better be prepared

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

Judging from the announcement, the official round is not rated, and the div1 and div2 versions are rated. Is my understanding correct?

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

As a tester, I just wanted to say I love this community :D and thank you KAN for reaching out and giving me this opportunity

I'm still seeing a lot of upcoming future contest :3

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

    As a non-tester, I just want to orz low_ and thank you for your contributions to the CP community :D

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

I hate problems

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

As a tester, I highly recommend writing this round.

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

An interesting thing happened. Yesterday，my rating was still 1900 + and I was able to sign up for div1. After the end of yesterday's contest, I dropped to 1800 +, which should not be able to fight div1, but I was still in the div1 queue. So do you think I should quit div1. :) (https://mirror.codeforces.com/contestRegistrants/1434)

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

    Actually this(including the opposite situations) happens quite many times.

    And it can lead to this: standings — see the forth place.

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

As a tester , problems are balanced+Cf-Level and great effort by setters . ATB.

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

Who can tell me if the problems in the 3 contests with same preliminary costs are a same problem? Thanks a lot! By the way, I tried to register for the Div.2 contest as usual, but I failed and got the information "Rating should be between 0 and 1,899 in order to register for the contest". I remembered that the Div.2 contests were for users whose ratings were between 0 and 1,999 (or 2,100) usually. Was it common for this situation?

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

    For parallel Div.1 and Div.2 contests, purples can only participate in Div.1, while purples can participate officially in Div.2 only contests.

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

Today there seems to be a very long queue. I hope it is fixed before the round.

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

I know this is not the right place to ask but I'm facing problem with codeforces. My codeforces from last night is loading in russian and every time it takes few seconds to translate the page into english but its happening every single time for every page of codeforces.

Also i'm seeing few keywords change in codeforces like "Accepted" to "Complete Solution" and "Submission" to "Attempts". Can anyone help me out? Apologies for posting it in this blog but this blog is active so I asked here.

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

    Are you sure you're not using something like Chrome's built-in Google Translate? (that would explain the delay and the system message changes) You can switch the language by clicking the UK flag in the upper right corner of any page.

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

am I the only one who reads all the comments and vote them ? codeforces comments section is really fun to me! :v

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

Could anybody tell me why the registration for Div. 2 is already closed? Is it because of some participant limit? You can still register for Div. 1...

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -19 Vote: I do not like it

I didn't expect such problems. Typing it in the middle of contest can show you my frustration level..

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

Anyone else suspicious of D being "well known" problem in China?

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

contest has made me wonder if i'm way dumber than I though I was ;-;

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

After 1396C - Monster Invaders, I decided to not read tasks with monsters/enemies and more than 3 parameters in input. It is not good for my mental health.

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

1B/2D is easier than 1A/2C.

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

    Imo 2C was easier. I didn't prove that sorting both and then choosing would be optimal, but other than that it was a straightforward DP. I was getting WA on pretest 10 on 2D.

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

I don't know why, but it seems that the contest is too friendly to Chinese OIers.

Almost half of the first 50s are Chinese OIers...

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

    Well, Div1 D was a standard ugly tree data structure problem, so nothing too unexpected happened.

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

      I solved it without ugly data structures, unless a segment tree with range updates counts, and with quite a lot of ideas going into it.

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

        Well, did you use Centroid or HLD decomposition?

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

          There exists optimal path whose one end is end of (arbitrary) diameter

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

            Well, that was unexpected... ;) Still, I believe that it was possible to squeeze straightforward solutions using HLD or Centroid decompositions. My centroid solution used too much memory, but it's basically the intended solution which solves the problem for all possible roots ;(

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

              Yeah, I can definitely understand somebody didn't notice that, because at first I thought about HLD, after a bit more thought I solved this using centroids and was coding this for a long time and it was unexpected need to take a dump that pulled my hands away from keyboard when I realized this observation and after it I threw almost all of my code to trash and rewritten it from almost a scratch :P

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

          Nope. See below.

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

            Yeah, I can agree now that the idea mentioned by Swistakk is pretty cool, but the overall implementation is still messy IMHO.

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

      Unfortunately, some of them got FST...

      Even I got 4851 ms to pass, under the condition of using fast IO (which the previous submission didn't). That was too close, is the time constraint too tight?

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

How to solve 2C?

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

what's pretest 9 in div2 C?

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

What's the hack point of Div.1B?

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

Div 2C, What was I missing, anyone please help?

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

What was pretest 9 on D2C? I noticed most solutions that failed 2C got WA on test 9. (so did I T.T)

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

How to solve Div2C/1A?

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

    I did two pointers .. Concept of minimum sliding window .. dont know if it is the intended solution

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

      I tried to do the same but got WA on 9 testcase

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

        Man atleast I passed .. wish that it passes the systest also sinnce I got fst yesterday on C :(

        → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -28 Vote: I do not like it

Div 2 D was pretty easy ! just hope that it has strong pretest.

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

why my sol for div2 D getting tle https://mirror.codeforces.com/contest/1435/submission/96683823

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

    For lower_bound on std::set, use s.lower_bound(x) rather than lower_bound(s.begin(), s.end(), x);

    The latter will give TLE since std::set. See this

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

      this is second time i am doing this fu****ng mistake ,so any idea how to avoid same mistake in future.

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

Holy shit this is the first time I solved all problems in a div2 contest DAYUM.

GOD of codeforces, please make it so I don't fail any system tests, please!!!

update: All tests passed :)

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

How to approach C?

was ternary search going to help in any way?

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

    Sorry, first I wrote the full idea and you only wanted approach, so it's spoilered now.
    Anyway, when I solved it, it kind of reminded me of the standard problem taught in DSA "merge k sorted lists".

    There are only 6 possible strings so the first thing I thought was — from each note generate all 6 options for the fret, which are the differences from each string.

    Then I said, for the hell of it, let's sort each of them (because of the median-of-medians selection algorithm).

    Now try to continue from here by yourself, you have n sorted arrays of size 6. If you want the rest, look below.

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

      oh great implementation thankyou.

      my dumb ass was thinking that the answer's graph would be something like \/ in shape and i could apply ternary search on it. i later found out that it was stricly decreasing and then strictly increasing but it also had some portion parallel to x-axis. that where it fucked up... i was clue less after that. :(

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

      I have doubt you didn't changed minimum at all ?

      why did you worked on maximum only?

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

        If the best solution has a smaller minimum, then eventually by lowering the maximum the minimum will be smaller.

        For example, if you have [8,4], [6,3] you start with the option 8,6 which gives difference of 2. Then you change 8 to 4 (minimum is now changed from 6 to 4). Now you are at option 4,6, which again is diff of 2, so you change 6 to 3 (again minimum changed from 4 to 3), and you get the best option with diff 1: 3,4.

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

          i am having a implementation problem what if there are more than one maximum equal to maximum(maximums)?

          i think this is why my new code according to you failed on test 9

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

            You are erasing the minimum element from val. You should be erasing the maximum element from val.

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

              vals is sorted in descending order.

              the the set with the bigger (maximum value) comes first in set. so i am erasing the begin because begin has the current maximum. :(

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

              Finally did it, i am sorry i didn't understand your logic at first go. now when i anaylyzed properly i found out it how it is working it a great implementation. and i surely learned something out of it.

              thankyou for being so helpful. keep up the spirit.

              submission.

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

                I was just going to say that you don't update the minimum answer — good job!

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

Thank you guys for the Div2 C really enjoyed doing it :)

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

How to solve div2 B?

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

    All elements were unique you just have to find a row and column with same first element and now you know that is the first row and column...

    elements for first row are going to be first element of columns and same for the elements of columns.

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

    Note that all the elements are different, so take first element of all the rows. All these elements must make up the first column. Search for this column in the given columns, once you find it, you know the order rows need to be placed in. Then just print the rows in the required order.

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

      Can you please help me what I did wrong? (WA on test 2)

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

        Your answer is sometimes repeating rows.

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

          Can you give me an example please?

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

          Oh! I got it. I missed some part of the problem. Sorry for disturbing you.

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

Why TL in C is too strict. My O(NlogN) gives TL on test 9. Why? Why?
link

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

    Seemes to me that 

    for(int r = 0; r < mp[val[i]].size(); r++){

    is O(logn) search at each iteration.
    I'd say that you there have O(nlogn) with huuuuge constant.

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

      Yeah, that's it but I don't have any better way to go. It's bad to see an intended solution gets rejected due to strict TL

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

        It's you who's doing too much extra job.
        For example you can do smth like

        for(int p : mp[val[i]]) {

        I pretty sure, that intended solution is a way less and O(nlogn).

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

    Most likely it is not $$$O(NlogN)$$$

    I am not sure but I think you do on each '+' linear search for next element...which makes it basically $$$(N^2logN)$$$

    Assume input like n times '+', then 1,2,3,4...

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

      In the vector $$$val$$$ I am taking each reachable elements once and in the map $$$mp$$$ I am taking from where a certain value is reachable. Which gives us total of $$$6n$$$ and map gives us $$$logn$$$. Isn't it?

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

        You iterate the lists in mp[], these lists can be huge.

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

          But, in the whole iteration, isn't it that I am counting $$$6n$$$ things? I might be wrong, I am not really good in time analysis. But, I am not getting your point

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

Today's div2 C was very similar to this: https://www.geeksforgeeks.org/find-smallest-range-containing-elements-from-k-lists/

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

Can someone give some hints for Div1 D?

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it -10 Vote: I do not like it

Man I thank authors for problem D2C .. really felt a super satisfied after solving that problem

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

Div1 ABC were selected while high on something, huh? A is a good problem but seems way harder than a typical A, B is just a basic idea and implementation (I'd swap them) and C is just some weird ugly adhoc. Call it personal preference, but that is a ragequit problemset.

At least D is very interesting. My solution is based on proving that we don't miss the best path if we pick a diameter and use one of its vertices as one end of our path. Next, we can assign a state $$$X_v$$$ to each vertex $$$v$$$ where for a stone edge $$$(u, v)$$$, $$$X_u \oplus X_v = 1$$$. That means we're dealing with 2 fixed rooted trees and queries "invert all $$$X$$$ in a subtree" and "find the deepest vertex with $$$X=0$$$", which can be done with a segment tree in $$$O(N+Q\log{N})$$$.

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

    How to prove "we don't miss the best path if we pick a diameter and use one of its vertices as one end of our path"?

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

      Prove that when the diameter has an odd number of stone paths and our best path doesn't visit this diameter, we can extend our path to the appropriate endpoint of the diameter. Then prove that when it visits the diameter, we can also improve it.

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

    Nice observation. I thought you have to use centroids and solve in O(Qlog^2N).

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

What was pretest 11 on div2 D?

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

Was C precomputation with a small dp of prefix and suffix?

.Can anyone tell that my solution will pass or not . Solution link. Code Link

Pre-thanks to the reader of the comment!

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

Why is Div1C a routine maxima finding problem?

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

Can someone please help me in 2C/1A? I formed an array of all possible ferrets I can chose by also storing the index for which I get that ferret. After that I just iterate over all possible values of ferret using two pointer. Whenever I get a condition that the current indices have all notes atleast one, I consider it and increase the lower indice by one. ANd whenever I dont comeup with such a situation, I increase the upper indice by one. Can someone please tell where did I go wrong?

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

You can copy-paste problem Div.1D from either here or here, and then add 5 new lines to adjust it to this problem. Too sad I read Div.1E first. =/

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

Seems that m2.codeforces.com had periodically been unstable during contest. Why is that?

(Had it been accessible, I would perhaps have one more problem Pretest Passed... sad story)

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

In div.2,why C C and why E E?:/

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

Problem D was way easier than C, I wasted 60-75 min on C and then started D and it took only 10 min. Even no of ac submissions say it. If D and C were interchanged D would have had 1000+ and C would have 400 and would have been reasonable.

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

    I feel it is psychologically difficult to move to the next problem skipping the current one, especially if it is WA as it may just be a corner case.

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

Learnt 2 lessons

1)If you see a problem which even IM's are struggling to get AC, skip that and move to the next problem (Iam looking at you 2C/1A)

2)If you keep on getting WA on a particular test case, instead of debugging do ctrl + A + del start from scratch

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

    Keep your lessons to yourself, you aren't helping anyone by sharing them here.

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

Bad ordering of questions. Why is D 500 points more than C?

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

Is there a DP solution for 2C, two pointer approach worked for me but I wasted too much time thinking about a dp solution.

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

Golovanov399 reporting cheating cases this and this
Even their handles are similar lol.

MikeMirzayanov please take care of this, he is ranked 4 in div2.

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

    wow nice catch. I hope it will be taken care of.

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

Waiting eagerly to see ecnerwala solving 2C/1A in his stream .

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

    Sort the 6 strings by value. Put all nodes on lowest string. Then, while possible, take the note from the biggest fret and move it one string up (which moves it some frets down). Check diff biggest fret — smallest fret for ans. Repeat.

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

      Is this exponential in the worst case?

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

        No, it is n*6, in worst case, since every note can be moved only 5 times (+1 initial run thhroug the array. So $$$O(n)$$$

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

There seems to be some issue with java platform. Problem B is giving TLE for a simple O(n*m) solution.

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

why my sol for div2 D getting tle https://mirror.codeforces.com/contest/1435/submission/96683823 please help..

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

haha )) :

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

Tired of weak pretests now. 4 FST in last 3 contests. -_-

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

If you struggle with C for 1.5 hour, maybe you should read D... The more you know

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

From now on I won't ever trust any tester saying than he approves the contest/loves the problems/finds them interesting. The same goes for "don't rage quit the contest" — today it was the best possible tactical move.

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +59 Vote: I do not like it

I wonder why tourist's submissions got skipped except the first one(which took part in the systest).... __ Just be curious, shouldn't the last submission count into the systest(instead of the first one)? Or I missed something?

→https://mirror.codeforces.com/blog/entry/84056?#comment-714979

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

I have solved only two problems in today's contest. One of them got tle in main tests. Please god let me know is it a dream?:()

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

submissions 96704396 and 96676432 are exactly the same code, but one of them passed while the other got TLE on test 17.

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

    May you rejudge submissions of D? Many of them are very close to the time limit(but we don't know that during the contest since their performance are good on pretest), and those submissions're hopefully to pass with fread or rejudging. I think it's not the intention of problem to distinguish the codes with fread and the codes without.

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

I: Nice! I finally passed Div1.D!

System Test: No, you didn't.

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

please anyone check to it

my solution is O(n) for div2B and it still shows TLE what i am doing wrong how can i further decrease time complexity people have submitted in O(n) and they are accepted ?? Help

https://mirror.codeforces.com/contest/1435/submission/96705858

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

    You are creating array of size 100001 for every tc i.e: 100001*100000 operations. The statements said that "Sum of nm over all test cases does not exceed 250000" reduce the unnecessary space to avoid TLE.

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

How to create a large number of [TLE failed system test] :

  1. Set a tough time limit.

  2. Don't put into pretests the test on which most solutions run slowest.

  3. Enjoy FSTs.

:)

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

    what are you saying this is very bad even solving in O(N) in pypy and python it is impossible to solve B div2 in O(logN) when submitting in c++ it is getting accepted this is unfaire for python coders !!

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

      Nah Jiangly and you are discussing totally different things. Python is already a very slow language and there is no reason to set additional time constraints for python users.

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

        They shouldn't have given the option to submit in python then. Just like Kotlin heroes.

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

    The author solution works 1.4s, and we added tests with highest time for our solution into pretests. Time limit is 5s, because we wanted to prevent $$$O(nlog^2(n))$$$ solutions.

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

      Well, most of the time this is OK, but here's the reminder that you'd better check if other solutions have the same complexity but larger constants. (As well for me to come up with a solution with smaller constant)

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

What the hell is this!! why so strong time constraints, is it even possible to pass Div2B in python? My Code

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

A good round! But,in fact,I don't think the order of problem A and B is correct.The statistical data also showed that problem B is easier than A.And of course,I tried to solve A for 1h,then give up to solve B,and solved it after just 7min.I'm very angry for I solve B so quickly but still got lots of penalties for B.

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

    By the way,I'm talking about the div1 round.

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

Why cin is THAT slow?

It took cin about 800ms to read just $$$4\times 10^5$$$ integers that $$$\leq 10^6$$$?

https://mirror.codeforces.com/contest/1434/submission/96673580

https://mirror.codeforces.com/contest/1434/submission/96703647

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

    Have you tried ios_base::sync_with_stdio(false); cin.tie(nullptr);?

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

    its funny, you are a red coder. and you are asking us about cin and scanf?

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

      Maybe because cin is very fast in some other online judge like zhengruioi .

      It can even read $$$10^6$$$ integers in less than 200ms.

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

        cin is tied to cout by default, meaning that it'll flush the output stream everytime it's called, unless you turn that off by adding ios::sync_with_stdio(0); cin.tie(0);. It may be the case that the judge you've mentioned uses some kind of modified compiler.

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

what is wrong with this approach for problem D we will fill the value in increasing order for example if we have queries like + + 2 + 1 + 3 + 4 bla bla bla so for (first 2 pluses ) we will assign 2 and 4 next we will assign 1 and so on but this gives wrong answer can anyone explain.

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

When will rating be updated?

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

Any issue with this contest ? Can't find the problems in problemset

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

Can someone tell me why I am getting TLE in problem D2B? If I am not wrong, I think it is O(nm.log(nm)) solution.

https://mirror.codeforces.com/contest/1435/submission/96684311

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

    I don't know the exact reason but your code is working fine after adding "return 0" at the end of your code. You can see it from my submissions.

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

When will ratings update ?

Edit : Updated

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

Screenshot-2020-10-25-235710.png When shit gets too overwhelming to handle

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

    You can see his submissions not hacked they just skipped. Probably he cheated in contest and submit close codes with someone so he got dedected and all of his submissions skipped because of this.

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

For div2 c, I thought about an algorithm to check whether all values ​​of 1-n appear in the interval. I thought of a hash algorithm, specifically like this, for each i of 1-n, generate a 40-bit random number x, and then use an array of 128-bit numbers to store the hash value. For 6*n numbers, if each number is generated by the i-th number, the upper 40 bits will XOR a random number x no matter what, if i is the odd number of times (you can use map to count), the middle 40 bits The upper 20 bits of the XOR of the upper 20 bits of x, if i is the even number of occurrences. The lower 20 bits of the middle 40 bits are exclusive OR of the lower 20 bits of x. Divide x into four segments, each 10 digits, marked as 0-3, set y as the number of occurrences of i%4, if y=0, XOR the lowest 10 bits of the lower 40 bits to the segment 0 of x, and so on . Then the XOR sum of the interval (l,r) can be calculated like this: XOR hash[r] into hash[l-1]. For each i, if it appears an odd number of times, there must be x in the upper 40 bits, if it appears 2, 6 times, there must be x in the middle 40 bits, and if it appears 4 times, there must be x in the lower 40 bits x, then just take out the high 40 bits, the middle 40 bits, and the low 40 bits and then XOR, the value obtained is XOR with the random number x of 1-n, and check whether it is the same.upd: I found that I was wrong, sorry.

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

Sad, why is the first digit of my ID not a number

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

    I think that reason is time of last submit. Not handle)

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

Will we get editorials for this round? coz I am waiting for it.

→ Reply