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

Автор emorgan, 3 года назад, перевод, По-русски

Всем привет!

В это воскресенье, 20-го марта 2022 года в 11:00 по московскому времени начнется Финал Технокубка 2022!

Итоговые результаты финального раунда Технокубка >>>

Для тех, кто хочет посоревноваться на тех же задачах, будет проведен обычный раунд Codeforces, совмещенный для всех дивизионов. Раунды начнутся в 20.03.2022 14:35 (Московское время), не пропустите!

Конечно, если вы участвуете в финальном раунде Технокубка, то вы не можете участвовать в раунде 778. Мы просим участников официального финала воздержаться от обсуждения задач в открытых сообществах до конца раунда.

Этот раунд подготовлен при участии следующих людей:

Разбалловка (для раунда 778): $$$500 - 750 - 1250 - 1750 - 2250 - 2500 - 3500 - 4000$$$.

Editorial

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

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

I hope I can get to blue, although that's impossible for me.

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

Please no boring&standart segment tree problems, dont repeat mistakes of the previous 2 years... Please...

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

Clashing with ABC 244 :(

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

I will lose blue in this round

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

as a tester, the problems are pretty neato burrito!!

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

Is this the remorphed version of "Go Study Round 1"?

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

    This is the problem set that was originally intended for Go Study Round 1. It's possible that the Go Study round could still happen in the future with a different problemset, but I don't know anything about it.

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

Both the UTC and Moscow time are incorrect. Please rectify.

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

As a tester, I don't remember having so many positive feelings about a problemset. I had a lot of fun testing, and I am sure you'll enjoy the contest, too!

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

If there is no particular reason for the unusual time then I would like to request to authors and coordinators of this round to please shift it to the usual time so it doesn't clash with AtCoder Beginner Contest 244 and we can have a nice 35 minutes break.

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

    It clashes with ABC 244 not ARC 137

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

    Timings of CF round will most probably not be changed as it is based on Technocup finals.

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

    At 11 o'clock Moscow time, as it was written in the announcement, the Russian Olympiad for schoolchildren Technocup starts. Obviously, the round based on this Olympiad should not start much later, because otherwise the participants will have time to tell all the tasks and their solutions

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

Expected to get cyan after this round.

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

Unusual time again :(

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

Why 8 problems in 2:15 and not in 3 hours?

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

hello sir, may i knwo how to be a tester, for the april fools round 2022 ?

Thnks

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

I am looking forward to this round, but emorgan, did you write 2022 as 2021 in the first sentence?

upd : I'm glad to see that this problem has been fixed.

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

I was really looking forward to giving both Atcoder ABC and this round but looks like I am gonna have to choose.

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

What fuck?! It's time is as same as ABC244!

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

Orz USA Round!

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

:)

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

Can someone please explain what does it mean by Div 1 + Div 2 ?? Is it a combination of two rounds?

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

    It means it will be rated for both div1 and div2 and questions could be expected to have difficulty accordingly. Like generally, these 2 are held separately. To get a better idea go through other div1+div2 rounds' questions. All the best btw.. :)

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

It clashes with AtCoder Beginner Contest 244 :(

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

I hope I will become CM tonight

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

firs time on rated. lets go green :'v

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

Good luck to everybody and myself. hoping to get green :)

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

Score(A+B) == Score(C)

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

Round will it not be rated?

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

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

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

Bye ! expert

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

How to do C?

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

    Store all the values in the array in a map. Find the sum and use recursion to see if you can construct the number backwards.

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

      How didn't you get tle? The recursion can visit 2*sum nodes no?

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

        But we should stop it as soon as the resulting array's size exceed n , since if you observe the number of nodes we get in resulting array always increases by atleast 1 at every step of recursion.

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

          But if you stop how do you check if the current elements in the resulting array can reach the elements from the original array that you are trying to get?

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

            With the map he mentioned, each time you get to an element of the array it increases total by 1. If total is equal to n at the end, the answer is yes.

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

        As a matter of fact, what you should do is to store the values together. It means that if you have k numbers of i, you can divide them into k numbers of i/2 and (i/2+i&1), which speeds up the whole process.

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

        No, because of short circuiting. You can take a look at my submission here (Ignore the sort beforehand, it doesn't do anything I just forgot to take it out) : https://codeforces.me/contest/1654/submission/150261342

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

          Interesting. I did the exact same thing though and TLEed. Is it something i am missing or is it jus that i am using a multiset? 150259740

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

            You are missing the short circuiting part. The way your code is written now, it will continue to try to look for possibilities even when found that the number cannot be constructed. I made a couple of changes to your code here and got AC

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

    Keep dividing the biggest piece of the cake if it exists delete it if not then it should be bigger than the biggest number in array a because if the biggest piece you have right now is smaller than the biggest piece in array a then you can't achieve that number

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

Can someone explain why does this code gives wrong answer on Problem D 150270389

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

Is F 2^27?

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

    It should be $$$O(n2^n)$$$, but I'm still debugging my code due to some annoying border cases.

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

    It can be solved with classic suffix array construction. If you sort prefixes of length $$$2^k$$$ for every $$$j$$$, then

    $$$s_j s_{j \oplus 1} \dots s_{j \oplus 2^{k+1}-1} = (s_j s_{j \oplus 1} \dots s_{j \oplus 2^k-1})(s_{(j \oplus 2^k)} s_{(j \oplus 2^k)\oplus 1} \dots s_{(j \oplus 2^k) \oplus 2^k-1})$$$

    Thus, you can compare prefixes of length $$$2^{k+1}$$$ by comparing pairs of prefixes of length $$$2^k$$$.

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

How to solve E?

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

    I want to know this too

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

    My approach is as follow:

    Let $$$b_i=a_{i+1}-a_{i}$$$ for $$$1\le i<n$$$

    If final $$$|b_i|> \sqrt n$$$,there will be less than $$$\sqrt n$$$ elements not being operated. Calculate for every $$$i$$$ with brute force is okay.

    Otherwise we have $$$|b_i|\le \sqrt n$$$ we can calculate the most remaining element for every $$$b\in[-\sqrt n,\sqrt n]$$$. We can classify every $$$a_i$$$ with $$$a_i-(i-1)b$$$.

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

    Either $$$|\text{difference of AP}| \lt \sqrt{a_{max}}$$$ or $$$len(AP) \lt \sqrt{a_{max}}$$$.

    We can check for all possible differences in the first case in $$$O(n \sqrt {n})$$$

    In the second case realize that for a difference $$$d$$$, the difference between two terms at positions $$$i \lt j$$$ must be $$$(j - i) \cdot d$$$. Since $$$|d| \gt \sqrt{a_{max}}$$$, this will exceed $$$a_max$$$ in at most $$$\sqrt{a_{max}}$$$ steps.

    Unfortunately I didn't realize that the initial statement directly gives you the way to solve the second part during contest T_T.

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

    You need to find maximum sub-sequence $$$i_1, \dots, i_m$$$ such that for each $$$k$$$ in the sub-sequence

    $$$a_k = b \cdot k + c,$$$

    where $$$b$$$ and $$$c$$$ are some constants. If $$$i$$$ and $$$j$$$ both belong to the sub-sequence, then

    $$$b = \frac{a_i - a_j}{i - j}.$$$

    But $$$|a_i - a_j| \leq 10^5$$$, so either $$$|b|$$$ or $$$|i-j|$$$ is less than $$$\sqrt{10^5}$$$.

    So, you check all $$$b$$$ that are smaller than $$$\sqrt{10^5}$$$ and also all sub-sequences that their width is at most $$$\sqrt{10^5}$$$.

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

why the memory limit of D is 256MB. My program can't pass only because of this limit. I think this problem would be better if it's memory limit is 1GB

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

    I think we both tried prime factorisation. Apparently it isn't the intended solution

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

      i didn't do prime factorisation. and i think my program's memory is not so big.code[submission:150269946]

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

        Nevermind. The editorial's solution is doing exactly what i did in my solution (using maps to maintain prime factorisation). Now I am curious to know how the people who got AC implemented the same.

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

Great problemset, thanks to authors!

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

How difficult...TAT

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

What is the reason for higher time constraints on the problem 1654B - Prefix Removals?

This N^2 150248852 submission passes because of that.

And I also have a failed hacking attempt on it :-/

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

    This is actually $$$O(26 * n)$$$ — it traverses the string only once for each letter of the alphabet

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

      Yes, I understand that but the string is passed by value which is O(N), and also the erase function should give O(N) complexity for every operation.

      Also, you can see that the code takes 1000+ ms for execution, which an N*26 solution won't give.

      The time constraints should be accordingly so these types of solutions don't pass.

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

        Yeah, I guess the compiler optimizes it and the time limit allows it to pass the pretests Not sure whether it will pass systest though

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

          It will pass. Two seconds of time allocation for this question is really too much.

          I don't know about compiler optimization, but strings take lesser memory than integer arrays of the same size, so maybe lesser complexity for operations.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Here's the solution for C if you're curious that's the simplest way i think
  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
    One can also implement it like this. I think this way is easier.
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Surprised to see multisets works. I thought we must use maps.

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

      The same complexity finding elements is log(n) erasing element is log(n)

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

If s is a multiset, is if(s.count(x)) $$$O(\log n)$$$ or $$$O(c\log{n})$$$ ($$$c$$$ is count of $$$x$$$ in s)?

I used to think it's $$$O(\log n)$$$ cause the compiler will optimize it. Until today I found this will keep fucking TLE unless I change it to s.find(x) != s.end() or add Ofast optimization manually.

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

    $$$O(c + log(n))$$$, see complexity section of these docs.

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

    With the grace of cpp20 now we get a new function known as contains(x), which can be used like s.contains(x), as the name suggests it checks if the data-structure contains the value x or not. The great fact about this is that its just log(n) and plus is more good suiting name

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

For C this was my approach. Can someone explain why this is wrong.

example: 7 1 1 1 3 1 3 3 2 3. Sort the array in descending. 7 3 3 3 3 2 1 1 1 1.

Divide the array in equal sum halves. Meaning this array will be divided into 7 3 3 (sum1 = 13) and 3 3 2 1 1 1 1 (sum2= 12). If abs(sum1 — sum2) <= 1. I will recursively apply this on half1 and half2 until either only one element is left (which return true) or this (abs(sum1 — sum2) <= 1) condition is not met in which case false is returned. if both halves return true then only the answer is yes otherwise no.

My submission: https://codeforces.me/contest/1654/submission/150266681

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

    It's not quite clear what's going on, but I'm going to guess that given a '1 1 2' you do not know if it combines to 2 2 or to 1 3.

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

      it will be combined to 1 1 and 2 because the total sum is 4 and halves will be 2 and 2. My code returns YES in this case btw.


      if (half1 + a[i] <= ((SUM + 1) / 2)) half1 += a[i]; ll half2 = SUM - half1;

      This is how i select the numbers. To be able to select them greedily i sorted the array initially. SUM is the sum of entire array.

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

        What happens if you have 2 2 1 1 ? You can't divide it to 2 equal sums but this can be achieved 6= 3 3 = 2 1 2 1

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

          why tho? My code will separate it into exactly this, 2 1 and 2 1. I ran this test case and my program is return YES.

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

            But you're sorting the array descending right? if you do then what's the point of sorting if you can separate the halfs without being adjacent

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

https://codeforces.me/contest/1654/submission/150251750

can anyone please tell why this code is getting TLE on test#7, it seems correct to me

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

    Imagine when you have 200000 numbers each 10^9, and you have to break everything into 1 before returning NO

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

      I don't think so because i have written the condition if (*s.begin() > x)return; inside recursive function that way it will break much before.

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

        Have a globally declared flag value, and use it to stop the unnecessary calls if you already got the answer, before solve(a) and solve(b). I also got tle at tc7, but after adding flag got AC.

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

        As mindFlayer said, you will be making some additional calls to solve. You will be returning from that function call but all the other calls to solve will not end. this works

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

Can anyone tell me why this code is getting TLE(on pretest 9) for problem 1654C - Alice and the Cake, I think My code complexity is O(logn*log(sum)) My code

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

    Complexity is O(2 * sum * logn)

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

    Solve function goes like that

    Sum + Sum / 2 + Sum / 4 + .... + Sum / Sum = Sum * (1 + 1/2 + 1/4 + ...) = 2 * Sum

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

Why not test problem A first?

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

The questions are nice, but time limits/constraints are not (For problem E).

My solution for problem E runs in $$$O(n\sqrt n)$$$ and I believe it is already the optimal time complexity (correct me if I'm wrong). However, I still had to do like 40 minutes of constant optimisation and get a few penalties for the TLE verdicts.

I have also seen that many other submissions are only just under the time limit, in fact, 1/3 of solutions that passed pretests used more than 4s. There are also around 2.3 times more TLE submissions than AC submissions to add to the fact.

This also caused bottlenecks for other languages, with only 4 languages (C++, D, Java, Rust) having AC solutions on this task.

I believe these kinds of constant optimisation are absolutely unnecessary to competitive programming and does not bring anything extra except benefitting those with templates optimised for constant optimisation, which is irrelevant to one's actual algorithmic skills which competitive programming is supposed to test.

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

    For me, $$$O(n \sqrt n)$$$ with unordered_map got TL, but just sorting and solving in $$$O(n \sqrt n \log n)$$$ somehow passes...

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

    well.. I just failed system tests.. I should have done more constant optimization xD

    upd: my solution got rejudged and got accepted. Is that a new feature?

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

      I think they always rejudge TLE submissions a few times during system tests to avoid subtle differences in runtimes between different executions bringing in a "luck" factor

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

    Dear contestant,

    Please don't worry if you had to make some formulas shorter in order to pass a time limit that was set as a triple of our solution's running time. In a programming competition, the way you express your ideas in code actually matters. Apologies if this does not fit your view.

    Thanks for the feedback,

    A mere alt account.

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

    I agree with your perspective that requiring constant factor optimization does not make the contest any more interesting. We did not want any solution with correct complexity to get TLE (at least I didn't, I cannot speak for the other preparers). In this case, we made the constraints of E more lenient several times during testing, until the official solution (which uses hashmaps) ran in 1700ms -- at that point we thought the time constraints were reasonable.

    In the majority of cases where contestants complain about problems requiring constant factor optimization, it's not because the authors intentionally wanted to require it, but rather because there was a known brute force solution that could easily pass if the constraints were more lenient, or because changing the constraints would give away the intended complexity, or because increasing the TL would lead to queuing during the round.

    In this case, in hindsight, I would say we perhaps should have lowered the constraint on $$$n$$$, but I'm not 100% sure about it. Such a change would have likely allowed a few highly optimized $$$O(n^2)$$$ solutions to pass, and it's not clear whether that's a "lesser evil" than causing some solutions with poor constant factor to get TLE.

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

      This is a good thing for people to learn that sort + two pointers is often faster than map/unordered_map.

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

My approach for C:

-> The sum of array is the starting weight.

-> We can store the count of array elements in a map.

-> We start the simulation using a priority queue, with starting weight inserted in PQ:

->We take the top most element from PQ and check if it exist in the map:(2 possibilities)

  • If it does not exist, it means probably it was divided into 2 pieces later, so we will divide this piece into 2 parts and push them into PQ, to get divided later.

  • If it exists, it means this will be part of the final array, so we will consider that this particular element has been obtained correctly and thus won't be divided further, and we will update the count of this element in map by decreasing by 1;

-> We do this simulation n-1 times.

-> Now, in the ideal case, all the keys in map should have a value 0 as its count.

-> if above statement is true -> return YES; else return NO;

P.S.: Queue would also work fine in this case, as processing the elements in any order will give the same end result. 150248249

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

    Instead of Priority Queue I was wondering why not normal queue would work. I took some test cases and dry run it, luckily I found that normal queue would work. Anyways thanks for your intuition, it helped me a lot.

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

How to solve problem D? I have a basic idea but couldn't figure out how to deal with node with n-1 degrees. It would easily overflow.

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

I fell shocked when refreshing the status page and found lots of my friends fst on problem E

panic

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

Me after submitting D in the last 5 seconds with a correct solution but then realized I'm printing the value at the root and not the sum.

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

It's a pity that I've only got 15 minutes to participate in the contest :( Luckily, I solved 2 problems within 12 minutes, so this contest is almost unrated for me XD

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

problems A and B were actually pretty easy but then C was very hard compared to A and B

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

I got TLE on problem E in the system test. https://codeforces.me/contest/1654/submission/150264452 After the system test, I resubmit the same code. Then, I can get AC! https://codeforces.me/contest/1654/submission/150275130

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

    This happens to someone every contest. The CF grading servers have some variance in time measurements, and there is nothing we can do about it.

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

      Thanks. I had a rare experience. I feel the ordinary judge is a little bit faster than in the system test (though I have no evidence).

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

[Deleted] I put the discussion under the editorial blog.

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

Why was my first AC submission for C was canceled ?

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

    If you submit a new solution after passing all the pretests, the earlier ones will be skipped.

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

Can anyone help me explain why this code get tle on test 3 :(( https://codeforces.me/contest/1654/submission/150283548

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

In problem E, why use 50 as constant can solve the problem but bigger number cannot.

The right constant should be $$$\sqrt n$$$ ,isn't it?

I don't understand why?

My code https://codeforces.me/contest/1654/submission/150288568

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

I tried explaining my solutions for problem A,B and C . Link to the video

Hope this can be of any help.

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

The editorial is amazing! I hope all the editorial have "Hints".

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

nice problems.

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

Wait!Could you get into the editorial?

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

Can anyone tell me why my code got TLE please :/ It's only O(nlogn)

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

    In case answer is "NO" loop can run long before it breaks. If origi.begin() is 1 and x is 1e9 it can create near 2^30 elements for split multiset when the x is invalid.

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

Does it seem strange to anyone else that F from this contest is rated 2800 while G is rated 2900? F was solved by 107 competitors in-contest, while G was solved by 10, which intuitively suggests that G is vastly harder than F; Carrot tells me the performance corresponding to 107th place is 2670, while 10th place corresponds to a performance of 3296. It seems to me that F is perhaps slightly overrated, but G is definitely highly underrated. (Admittedly, part of the reason G had so few solves is probably that it appeared late in the problem set, but even so, it's hard for me to imagine that the problem deserves a rating lower than 3100 or 3200.)