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

Автор cry, 18 месяцев назад, По-английски

We hope you enjoyed these problems :) This contest has been in the works for almost a year.

About the Authors

UPD: D1D Editorial have been updated

UPD 2: D1D Editorial now has images by EmeraldBlock. As an apology gift for being so slow, the image generator is programmatic and available here.

1853A - Desorting

Problem Credits: buffering

Analysis: buffering

Hint 1
Solution
Code (C++)

1853B - Fibonaccharsis

Problem Credits: ntarsis30, cry

Analysis: cry

Hint 1
Solution
Code (C++)

Bonus: Solve for $$$n, k \leq 10^9$$$

Bonus Solution

1852A - Ntarsis' Set

Problem Credits: nsqrtlog

Analysis: nsqrtlog, buffering

Hint 1
Hint 2
Solution
Code (C++) -- Model Solution
Code (C++) -- Simulation (more readable)

1852B - Imbalanced Arrays

Problem Credits: nsqrtlog

Analysis: buffering, nsqrtlog

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Code (C++)

1852C - Ina of the Mountain

Problem Credits: Ina

Analysis: Ina, EmeraldBlock, GusterGoose27

Hint One
Hint 2
Hint 3
Tutorial
Code (C++)

1852D - Miriany and Matchstick

Problem Credits: ArielShehter

Analysis: EmeraldBlock, emorgan

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Code (C++)

1852E - Rivalries

Problem Credits: buffering, ArielShehter, Ina

Analysis: oursaco

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Code (C++)

1852F - Panda Meetups

Problem Credits: Benq

Analysis: Benq, oursaco

Hint 1
Hint 2
Hint 3
Hint 4
Solution
Code (C++)
Разбор задач Codeforces Round 887 (Div. 1)
Разбор задач Codeforces Round 887 (Div. 2)
  • Проголосовать: нравится
  • +183
  • Проголосовать: не нравится

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

One of the editorials of all time.

  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +144 Проголосовать: не нравится
    Fun facts about my problem D1C/D2E (Ina of the Mountain):
»
16 месяцев назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

such a well written editorial :heart_eyes:

also i get photo credits :OO

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

great contest and Very interesting problemset :) ,but HUGE skill gap between div2B and div2C

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

Interesting Problems and quick editorials :3

I like problems 1A 1C very much, but have not enough time for 1D...

Also, isn't 1A too difficult for this place?

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

wow, that is fast

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

the hardest div 2 i have ever seen :<

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

    I am not able to implement C on time. But this is not the hardest.

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

      oh so which is the hardest TvT

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

        I don't remember a lot. But, the contest(Codeforces Round 885 (Div. 2)) was hard for me. Contest of love(Vika).

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

        Try C problem from goodbye 2022,that I consider hardest C, considering binary search solution for this problem its a pretty easy problem , its a plain binary search.

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

Slightly sad that more people didn't find the really cool O(n) solution for C, but glad that people who solved it seemed to like it

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

    Can you explain the $$$O(n)$$$ solution?

    Additionally, my solution for D1A was $$$O(k \log n \log nk)$$$ and I can't understand the editorial of $$$O(n + k)$$$ solution, can you explain it more in details!?

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

      I can take a stab at it! I am not sure if this is the same as the editorial, but the following submission: 215239360 has the same complexity O(n+k).

      The first thing to notice is that the answer is at least the mex of the array. Therefore, we can start from the mex. If this is 1, then the answer MUST be one which should be intuitive. Otherwise, lets sort the array and try to build the answer from day 1 to day k.

      Notice that with any day, the answer will increase by an amount equal to the current prefix of the array we take.
      ie. Let us say we have the array [ 1 , 15 , 30 ]. The answer will increase by 1 while it is <15, then we "take" 15 and the answer will increase by 2 while it is <30, then the answer will increase by 3 for the rest of the days. Using this idea, all we have to calculate is the number of days until we can take the next element. Look at the above solution for more details :) Let me know if you have any questions.

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

        hi, but in the example that you showed I understood that we keep on taking 1 while the answer is < 15 but how are we going to take into account the fact that the elements at the position 15 and 30 are going to be removed because If we don't take that into account and I am assuming that ans in your solution represents the current mex then when we reach 30 it is already removed similarly 31 is already removed and ...

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

          Well, the elements that 15 and 30 affect don't matter until we take them. When taking 15, all that means is accounting for elements 15 would have deleted.

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

The condition that "no two elements sum to 0" implies that every bi has a distinct absolute value

Why?
For a = [4,4,4,4], b = [ 4,4,4,4] is a valid solution.

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

    Sorry, I was reciting my thought process to come up with the intended solution. I've deleted that part now; it's not necessary to solve the problem.

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

      I thought that too, "all absolute values are different", and it helped me to solve the problem faster. Later I realized that this mistake doesn't affect the solution

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

in C you have four paragraphs of absolutely obvious text then only one sentence related to the solution and it's absolutely unclear

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

good 1a/1b/1c! I'm trying to improve my IQ for 1d.

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

Another way to solve Div2C is to note that the answer for $$$day=k$$$ is the $$$\text{(answer for day=k-1)^{th} }$$$ mex of the array $$$a$$$.

Overall time complexity is $$$O(n+k*\log_2(n))$$$.

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

    can you share how did you reached to this conclusion? Non-origination

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

      Denote $$${mex}_i$$$ to be the $$$i^{th}$$$ mex of the array $$$a$$$, i.e. the $$$i^{th}$$$ smallest positive integer that is not present in $$$a$$$. The values remaining after Day 1 are seen to be $$${mex}_1,{mex}_2,{mex}_3,{mex}_4,\ldots$$$. View this sequence as just a symbolic replacement of the values remaining initially($$$1,2,3,4,\ldots$$$). Since the algorithm of removal is the same for each day, it follows that the values remaining after Day 2 are $$$mex_{mex_1},{mex}_{{mex}_2},{mex}_{{mex}_3},{mex}_{{mex}_4},\ldots$$$. This pattern holds for the values remaining at the end of any Day by induction.

      For example, consider the second sample test case. Here $$${mex}_1=2,{mex}_2=4,{mex}_3=8,{mex}_4=9,{mex}_5=10,\ldots$$$. The values remaining at the end of Day 1 are $$$2,4,8,9,10,\ldots$$$ i.e., $$${mex}_1,{mex}_2,{mex}_3,{mex}_4,{mex}_5,\ldots$$$. $$${mex}_{{mex}_1}={mex}_{2}=4,{mex}_{{mex}_2}={mex}_{4}=9,{mex}_{{mex}_3}={mex}_{8}=13,\ldots$$$. The values remaining at the end of Day 2 are indeed $$${mex}_{{mex}_1},{mex}_{{mex}_2},{mex}_{{mex}_3},\ldots$$$=$$$4,9,13,\ldots$$$.

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

        How are you keeping track of k-1th mex of the array?

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

          In my submission, I iteratively compute the ith mex of the array for all 1≤i≤k. You can refer to my submission https://codeforces.me/contest/1853/submission/215255944

          Here $$$f(a,prefix,i)$$$ computes the ith mex of the array $$$a$$$. The jth element of the prefix array stores the number of positive integers that are not present from $$$1$$$ till the value of the jth element of the array $$$a$$$ (So $$$prefix[j]$$$ is actually just $$$a_{j}-(j+1)$$$ in 0-based indexing). You can binary search the value $$$i$$$ in this prefix array in order to calculate the ith mex of the array in $$$log2(n)$$$ time. The base case where $$$i=1$$$ is calculated beforehand and the ith mex for 2≤i≤k can be calculated by iteratively calling the function $$$f(a,prefix,\text{answer for day i-1})$$$.

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

I was about to become Candidate Master today but got FST (Failed System Testing) on the B problem : (

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

Quoting from 1852B/Solution -

The condition that "no two elements sum to 0" implies that every $$$bi$$$ has a distinct absolute value.

That is incorrect. Two elements can still have equal absolute value (for e.g. -3 and -3). However it can proved that if a solution with two equal elements exists, then there must also be a solution having every $$$bi$$$ value distinct.

Luckily, I made the same conclusion as given in the editorial at the time of the contest, so I did not have to prove the above statement mid contest. But those who did realize it, I feel bad for you for having to prove it xD

P.S. great problem, btw!

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

    Please, can you kindly tell me how to prove it? ty very much!

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

Love the editorial with hints :) Also C was hard, I solved B fast but stuck at C until the end of the contest lol.

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

tnx 4 fast editorial

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

Must problem div2C use long long? I found one of my friends passed it without using long long.

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

I solved Problem C with binary search. I search if we can delete a prefix of numbers 1, 2, 3, ... x using given operations. If we can delete it then we can also delete prefix upto x-1, x-2 and so on.

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

    Can you explain it please? I am facing trouble to understand this. I worked specific number. Like I took a number and checked whether it can be the answer or not. That's why I didn't get exact answer.

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

      Let's say if x is the answer, then we should be able to delete everything from 1, 2, ... x-1 but not x. So I search for the smallest ending prefix that we can't entirely delete using all operations and that would be our answer.

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

A recursive solution of 1853B - Fibonaccharsis:

If n equals to the k-th Fibonacci number F[k], then the answer is 1.

If n < F[k], then the answer is 0.

Otherwise, let us replace n by n-F[k]. Note that the difference of any fibonacci-like sequence and the standard fibonacci sequence is also fibonacci-like, unless the case where the first two elements of our initial sequence are equal. But this happens if and only if n is divisible by F[k+1], and this adds precisely 1 to the answer.

Code: 215213454

  • »
    »
    16 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится
    • Thankyou so much for sharing. I also had a similar observation but being a noobie couldn't build a solution.
    • I understood how the recursion will work-out by using the fact that "...Note that the difference of any fibonacci-like sequence and the standard fibonacci sequence is also fibonacci-like"
    • I did not understand this part "...unless the case where the first two elements of our initial sequence are equal. But this happens if and only if n is divisible by F[k+1], and this adds precisely 1 to the answer." Can you PLEASE explain this a little more. I tried for a good amount of time but can't figure this out.
    • »
      »
      »
      16 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Consider a fibonacci-like sequence S[1], S[2], S[3], S[4] ... and let us try to subtract the standard fibonacci from it. We obtain S[1], S[2]-1, S[3]-1, S[4]-2, ....

      If S[1] < S[2], then this new sequence is non-decreasing, so it is also fibonacci-like.

      Otherwise, we have S[1] = S[2] = c for some c. But then S[3] = 2c, S[4] = 3c, S[5] = 5c, etc. So this is the standard fibonacci sequence scaled by c and shifted by 1. That is, S[m] = cF[m+1] for all m. In particular, n = S[k] = cF[k+1]. Therefore, the case S[1] = S[2] is possible if and only if n is divisible by F[k+1], and this sequence is uniquely determined by S[1] = S[2] = n / F[n+1].

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

        WOAHH, THAT WAS SO NEAT. THANKS A LOT AGAIN. I understand it now. This brought me so much joy. God bless you.

        By, the way any comments about time complexity of this solution ?

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

          The time complexity is O(n/F[k]). So in the worst case (for small k) it becomes O(n).

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

            That means this works faster than the editorial's solution in the average case ?

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

              Since the editorial's solution has complexity O(n log(n)), then, theoretically, yes.

              But actually the editorial's solution 215343605 works faster, even after replacing recursion with the while loop in my solution 215343795.

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

Cannot understand editorial of div2C

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

    In the editorial, I visualize the numbers in Ntarsis' set in a line arranged in increasing order; I'll make that part more clear.

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

Well, I couldn't solve B yet I want to know if the following observation is correct ? "if the k-th element of a real-fibonacci(starting with 0,1) is greater than the required n, then the ans has to be zero". I just don't trust myself so it would be nice if anyone could point out if this wrong ?

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

1852D — Miriany and Matchstick

how would ABABAABAB be a valid answer for:

9 17 BAAABBAAB since its just 13 and k is 17 ?

B A A A B B A A B | | | | | | A B A B A A B A B

thats 6

A_B_A_B_A.A_B_A_B

and thats 7

what I miss ?

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

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

div1D can also be solved using greedy, because most of the time, each operation only adds one to the answer.

Here's my code: https://codeforces.me/contest/1852/submission/215259895

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

I used a mysterious method to pass this problem in C of Div2, with time complexity O(n). Is anyone interested in proving the right thing to do? https://codeforces.me/contest/1853/submission/215254923

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

Was somebody able to AC div1D with divide and conquer + fft/ntt in O(nlog^2n)? My code ACs in around 15s, which is not close to the TL, but maybe it's possible to squeeze it in the TL with a faster fft/ntt implementation

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

    I am, but only after contest. Link

    It demanded a lot of constant optimizations — like making simultaneously fft and inverse fft for two polynomials at once (described here in p.16) and using float as data type for complex numbers.

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

      Thanks for sharing, I'll definitely take a look at those optimizations

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

I saw many solving C with binary search, can anyone explain it?

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

    I solved Div2 C by binary searching on the minimum length $$$\ell$$$ of the set $$$A_\ell = [1, \ldots, \ell]$$$ such that performing the operations on the (finite-size) array $$$A_\ell$$$ left the set nonempty after $$$k$$$ steps. Observe that if $$$A_\ell$$$ is empty after $$$k$$$ operations but $$$A_{\ell+1}$$$ is not, then $$$\ell+1$$$ is our answer. For a given $$$\ell$$$ my solution determined the smallest $$$k'$$$ such that $$$A_\ell$$$ is empty after performing $$$k'$$$ steps, and compares $$$k'$$$ to $$$k$$$ to update the search bounds.

    To simulate the procedure for a given $$$\ell$$$, notice that up to relabeling, all that really matters at each step is the number of elements $$$x$$$ remaining in the set. This allows us to simulate the deletion in $$$O(n)$$$ regardless of $$$\ell$$$ by repeatedly (1) updating the number of elements $$$m$$$ that will be removed (i.e., the maximal $$$m$$$ such that $$$a_m <= x$$$) and (2) performing the maximum number of steps removing that many elements in $$$O(1)$$$.

    The answer is upper bounded by $$$nk + 1$$$. The total runtime is thus $$$O(n \log (nk)) = O(n \log n + n \log k)$$$.

    Submission: 215276044

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

      My binary search is similar. I do binary search on the answer (that is $$$l+1$$$, but call it $$$ans$$$), and check if it is deleted from $$$a_n$$$ to $$$a_1$$$.

      Suppose the number deleted by $$$a_i$$$ in the $$$j$$$-th round is $$$x$$$. Since in this round i numbers $$$\le x$$$ are deleted, the number deleted by $$$a_i$$$ in the $$$(j+1)$$$-th round should be the $$$i$$$-th undeleted number after $$$x$$$. The numbers deleted this time which are greater than $$$x$$$ must be deleted by $$$a_{l>i}$$$, so do it from $$$a_n$$$ to $$$a_1$$$.

      Suppose $$$y$$$ numbers smaller than $$$ans+1$$$ are deleted by $$$a_{n},a_{n-1},\dots,a_{i+1}$$$, there're now $$$ans-a_i+1-y$$$ numbers not deleted in $$$[a_i,x]$$$. Since it goes $$$i$$$ steps each time, the answer for $$$a_i$$$ is $$$\lceil\frac{ans-a_i+1-y}i\rceil$$$.

      Just sum them up and check if the value is $$$\le ans-1$$$. If so, the real answer should be less or equal to the current. The time complexity is $$$O(n\log \text{ANS})$$$

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

      esr6vqa LMydd0225 thanks to you both, I got the intuition and how we could come up with such solution,thanks again.

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

Bonus solution of D2B can be optimized up to O(1) per testcase (with the precalc of Fibonacci numbers) knowing that

$$$F_{k-2} * F_k - F_{k-1} * F_{k-1} = +-1$$$
  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    can someone explain how to reach this equation?

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

      Assume that we've proven

      $$$|F_{k-2} * F_{k-2} - F_{k-1} * F_{k-3}| = 1$$$

      .

      Thus

      $$$|F_{k-2}*F_{k-1} + F_{k-2} * F_{k-2} - F_{k-1} * F_{k-2} - F_{k-1} * F_{k-3}| = 1$$$

      We can close the brackets and see that

      $$$|F_{k-2} * (F_{k-2} + F_{k-1}) - F_{k-1} * (F_{k-2} + F_{k-3})| = 1$$$

      Which means that

      $$$|F_{k-2} * F_k - F_{k-1} * F_{k-1}| = 1$$$
»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This div2C is where I doubted my entire existence :( --> cries in low IQ

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

Is it just me or C was harder than D?

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

In problem D(Div2),can someone please explain the Hint1 given in the editorial(I mean why is this statement true).

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

    Let's say you have 2 ones in $$$b$$$. Then you didn't use at least one number from $$$1$$$ to $$$n$$$ as the absolute value. You can add 1 to all numbers, which absolute values are less than that missing number, then you won't have $$$2$$$. Then you can replace one of ones with two and all constraints will still be true.

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

Another solution for Div $$$2$$$ B.

We can write $$$f_k$$$ as a linear combinaison of $$$f_1$$$ and $$$f_2$$$. Thus by precomputing these coefficient for $$$k \le 30$$$. Let $$$f_k = a \cdot f_1 + b \cdot f_2$$$ the problem is reduced to finding $$$f_1$$$ and $$$f_2$$$ for which $$$f_k = n$$$. now knowing that $$$f_1 \le f_k$$$ since $$$(f)_n$$$ is increasing we can try all $$$0 \le f_1 \le n$$$. Since $$$a, b, f_k$$$ are fixed we can check if there is $$$f_2$$$ verifying the aforementioned conditions. Submission

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

The explanation for div1D is kinda bad. "we can show that [...]" isn't sufficient, please show it. It took me a long time to realize that when you flip b2...bn-3, then the thing changes by some odd value.

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

    Hi, we are already in the process of rewriting the editorial for this problem. Please wait a bit and check back :)

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

A little late, but I wanted to share my solution for div2C/div1A that runs in $$$O(k \log n \log a_i)$$$ time.

Consider binary searching on the answer. To check if a certain $$$mid$$$ is valid, we have to determine if all the values $$$\leq mid$$$ will end up getting deleted over the course of the $$$k$$$ days. To determine the number of values $$$\leq x$$$ which get deleted for some $$$x$$$, we just have to find the number of values in $$$a$$$ that are $$$\leq x$$$. This can be done with a second binary search or builtin functions like std::upper_bound. After determine the amount that are deleted, we can subtract this from $$$mid$$$ and simulate the remaining days on the new $$$mid$$$. This gives an $$$O(k \log n$$$ check function and an $$$O(k \log n \log a_i)$$$ sol overall.

Code:


#include <iostream> #include <algorithm> #include <vector> using namespace std; int main(){ cin.tie(0) -> sync_with_stdio(0); int T; cin >> T; while(T--){ int n, k; cin >> n >> k; vector<long long> arr(n); for(auto& x : arr) cin >> x; long long l = 0, r = 1e18; while(l != r - 1){ long long mid = (l + r)/2; for(int i = 0; i<k; i++){ mid -= upper_bound(arr.begin(), arr.end(), mid) - arr.begin(); } if(mid <= 0) l = (l + r)/2; else r = (l + r)/2; } cout << l+1 << "\n"; } return 3366^3366; }
  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    This is basically what I did; the inner check can additionally be done in $$$O(n)$$$ by maintaining a pointer to the amount $$$m$$$ subtracted off (it can only decrease) and additionally subtracting off as many multiples as possible in a single step. In my code this looks like

    lli pos = (lo + hi) / 2;
    lli ct = pos;
    lli t = 0;
    lli m = n - 1;
    
    while (ct > 0) {
        while (arr[m] > ct) --m;
        int times = 1 + (ct - arr[m]) / (m + 1);
        t += times;
        ct -= (m + 1) * times;
    }
    

    This nicely allows larger constraints on $$$k$$$.

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

i love cerealcodes <3

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

Great round! but the statement of 1852D is a little unfriendly to people suffer from red-blindness like me, it will be better if you show "the pairs of different characters" in bold rather than in red.

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

Tough round. Yes, I cry.

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

Good round! I love the ideas, very stimulating. Here's another solution for D1B/D2D, using hashing.

Firstly sort $$$a$$$, then $$$b$$$ becomes a increasing sequence. Try to find a $$$pos\in [0,n]$$$ satisfies that $$$b_{pos}<0$$$ and $$$b_{pos+1}>0$$$ (we assume that $$$b_0=-\infty$$$ and $$$b_{n+1}=+\infty$$$). Notice that for a $$$b_i<0$$$,it will exactly match up with $$$[n,n-a_i+1]$$$. and for a $$$b_i>0$$$, it match up with $$$[pos+1,n]$$$ in addition. Now we say there's a solution, if and only if there's a $$$pos$$$ that satisfies every index $$$i$$$ have been matched exactly $$$a_i$$$ times.

Now let's construct a solution to prove it. Assume that $$$b_{pos},b_{pos+1},…,b_{n}$$$ equals to $$$1,2,…,n-pos$$$ at the beginning. For every $$$b_i<0$$$, we let $$$b_i=b_{n-a_i+1}$$$, and add $$$1$$$ to all the $$$b_j(j\not =i)$$$ that are equal or greater than it. In the end it will generate a correct $$$b$$$. We can use a difference array to make it in $$$O(n)$$$.

Then the problem is how to find a $$$pos$$$. Check every possible value. Process the hash value of sequences like $$$1111…1$$$, then you can check each value in $$$O(1)$$$.

The total time complexity is $$$O(n\log n)$$$ due to sorting.

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

In div1C, I try to use dp to solve it but failed. let dp[i][j] be the min operations that position i is decreased by a[i]+j*k times and dp[i][j]=min dp[i-1][j']+max(0,a[i]+j*k-a[i-1]-j'*k) I don't know if there are anywhere wrong.

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

It's been a day but I still don't understand what is the (a[inc] — ans + inc — 1) in the problem Ntarsis' Set :-(

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

    Check out the other solution here; the model has lower readability, it's there to showcase an $$$O(n)$$$ solution.

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

    $$$\lfloor \frac{a[inc]-ans+inc-1}{inc} \rfloor \equiv \lceil \frac{a[inc]-ans}{inc} \rceil$$$ is the number of days before $$$a[inc]$$$ becomes active, until then $$$inc$$$ numbers are inserted each day in the region of interest.

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

thanks for information

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

can someone explain how they solved B(1853B — Fibonaccharsis) by using binary search....

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

    you get the equation , now we need to find the number of solution to this equation , now you can find any one solution which satisfies the equation , now you can get the parametric coordinates for the soln of the equation , now you have to find the answer only when y is greater than x , this can be done using binary search.

    parametric coordinates (x0 , y0) for the soln will be ,

    let p , q be any solutions for the equation. let a , b be the coefficients of x and y

    x0 = p + K * b / gcd(a , b)
    y0 = q — K * a / gcd(a , b)

    binary search on value of k

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

I remember that this div1A appeared as the last problem in some div1 contest but with many queries asking for the number at position P at time T. Anyone that upsolved that one can link it here?

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

I can not understand jiangly's 1A.

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

Hi, I was just curious what does "Analysis" in editorial mean. Is it preparation of testcases or finding the solution to the problem and proving it or maybe converting idea into problem statement.

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

In editorial for div1C "Our goal is to find a path of minimum cost from (0,0) to (k+1,0)", shouldn't it be (n+1,0) ?

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

samples are really great

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

link to problem: https://codeforces.me/contest/1853/problem/B

I have come up with an O(n*log(n)*k) solution where I loop through all possible f1, then binary search on f2. I confirm the f1 and f2 combo works through a memoized Fibonacci dp, that runs in O(k) where k denotes the kth term. But when I run it, my program times out.

Can someone help me identify what is taking my solution so long? (implementation or strategy)

I submitted it so you can view my solution: https://codeforces.me/contest/1853/submission/216182584

If you hate java like me, here is the c++ version: https://codeforces.me/contest/1853/submission/216183198

Thank you in advance

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

In Problem — D — Codeforces,dose the dp only consist two intervals which are adjacent

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

On the surface, it looks like you have put a lot of effort in writing the editorial. But for someone, who was not able to solve a problem, to be able to read what you have written, understand it and solve it on their own is simply not possible.