cry's blog

By cry, 10 months ago, In English

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++)
  • Vote: I like it
  • +183
  • Vote: I do not like it

»
9 months ago, # |
  Vote: I like it +54 Vote: I do not like it

One of the editorials of all time.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +144 Vote: I do not like it
    Fun facts about my problem D1C/D2E (Ina of the Mountain):
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      The time complexity of problem A is O(n) ?

»
9 months ago, # |
  Vote: I like it +14 Vote: I do not like it

such a well written editorial :heart_eyes:

also i get photo credits :OO

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 months ago, # |
Rev. 2   Vote: I like it +52 Vote: I do not like it

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?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +42 Vote: I do not like it

    yes, it was, we are sorry about that. glad you still liked it.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

wow, that is fast

»
9 months ago, # |
  Vote: I like it +14 Vote: I do not like it

the hardest div 2 i have ever seen :<

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      oh so which is the hardest TvT

      • »
        »
        »
        »
        9 months ago, # ^ |
        Rev. 2   Vote: I like it +6 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          oh the last div 2 TvT it shocked me a lot TvT

      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
9 months ago, # |
  Vote: I like it +16 Vote: I do not like it

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

  • »
    »
    9 months ago, # ^ |
    Rev. 3   Vote: I like it -11 Vote: I do not like it

    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!?

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 2   Vote: I like it +6 Vote: I do not like it

      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.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 ...

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great problemset, Well Written editorial . One of the best editorial i have seen . gap between div2C and div2B was too much.

»
9 months ago, # |
  Vote: I like it +39 Vote: I do not like it

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.

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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

»
9 months ago, # |
  Vote: I like it +52 Vote: I do not like it

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

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    just edited, is it clearer now

»
9 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
9 months ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

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))$$$.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      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$$$.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.com/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})$$$.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 months ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

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!

  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest..i slove 3 problem first time in div 2

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Congo bro!! you are Pupil now! results of your efforts are visible. I have been watching you since some days and today you have inspired me that I can do it too. Any tips so that I can solve problems as consistently as you.

»
9 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
9 months ago, # |
  Vote: I like it -16 Vote: I do not like it

"Reading this editorial is like getting behind the wheel of a turbocharged car in 'Need for Speed'! You blink once, and you've already mastered the problem-solving techniques. It's like they've strapped a rocket to these explanations! #CodeforcesEditorial

»
9 months ago, # |
  Vote: I like it +1 Vote: I do not like it

tnx 4 fast editorial

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    answer can be up to $$$10^{10}$$$, so yes

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Oh, its so pity I cannot hack my friend...

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        le that friend using #define int long long

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        How did you check all the elements before x is deleted or not?

»
9 months ago, # |
Rev. 4   Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it
    • 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.
    • »
      »
      »
      9 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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].

      • »
        »
        »
        »
        9 months ago, # ^ |
        Rev. 2   Vote: I like it +3 Vote: I do not like it

        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 ?

        • »
          »
          »
          »
          »
          9 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          • »
            »
            »
            »
            »
            »
            9 months ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

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

            • »
              »
              »
              »
              »
              »
              »
              9 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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.

              • »
                »
                »
                »
                »
                »
                »
                »
                9 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                I don't have the skill to investigate these things, but that's quite interesting. I saw your solution in C++ also, and the same thing happens.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Cannot understand editorial of div2C

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please tell me why i get Wrong answer on pretest 2 for this code? It seems same as the solution in the tutorial. Thanks in advance! void solve() { ll n; cin >> n;

vector arr; ll y; cin >> y; arr.pb(y); ll mn = INT_MAX; for (ll i = 1; i < n; i++) { ll x; cin >> x; arr.pb(x); if (arr[i] < arr[i — 1]) { cout << 0 << endl; return; }

mn = min(arr[i] - arr[i - 1], mn);

} // deb(mn); ll ans = mn / 2 + 1; cout << ans << endl; }

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1) you should initialise mn = LLONG_MAX (just a nitpick but you can actually get WA's due to this sometimes) 2) You should include the equality while checking for sorted-ness. arr[i] >= arr[i-1]

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well, the same thing happened to me during the contest. The reason for this error is we returned if we find the array unordered but the input stream was still filled with value that needed to be flushed (i.e. array elements are still in the input stream which are not extracted for the current test case). So our previous test case collides with any current test case, leading to incorrect output and chaos.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ah thats true...i kept banging my head against a wall for a couple of days as to how my solution was different from the tutorials. Man you really are a life saver, thanks very much :D

      Lesson Learnt:- Never do anything while taking input!

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

someone please explain div2 c with example

»
9 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

As a Newbie i find a llitle bit extraordinary solution in problem B. When we know the length of the fibbonacchi sequence we can get the f(0) and f(1) multipliers by the Bine's formula. In the n = 22, k=4 (example) we have f(0)=0, f(1)=11 as a solution, n=22=BineFormula(k-2)*f(0)+BineFormula(k-1)*f(1)=0*1+11*2. To solve the problem we should find the solution with maximum f(1), and minimum f(0). The answer would be (max(f(1))-min(f(0)))//(bineF(k-1)+bineF(k-2))+1. My solution: 215255537. Also we can note that k can't be very big, the 50th element of fibb seq equals 12586269025, that is too much for k <= 2*10**5

»
9 months ago, # |
  Vote: I like it +80 Vote: I do not like it

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    I hate the fact that it's so relatable.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Fast and quality editorial. Thanks

»
9 months ago, # |
  Vote: I like it +12 Vote: I do not like it

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.com/contest/1852/submission/215259895

»
9 months ago, # |
  Vote: I like it +4 Vote: I do not like it

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.com/contest/1853/submission/215254923

»
9 months ago, # |
  Vote: I like it +31 Vote: I do not like it

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

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +29 Vote: I do not like it

    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.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    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

    • »
      »
      »
      9 months ago, # ^ |
      Rev. 2   Vote: I like it +1 Vote: I do not like it

      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})$$$

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you so much! Finally understood.

      • »
        »
        »
        »
        9 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        pls can you explain DIV 2 D , I was unable to understand from editorial

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

»
9 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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$$$
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can someone explain how to reach this equation?

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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$$$
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Is it just me or C was harder than D?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
9 months ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

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

»
9 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

»
9 months ago, # |
Rev. 2   Vote: I like it +22 Vote: I do not like it

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; }
  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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$$$.

»
9 months ago, # |
  Vote: I like it +8 Vote: I do not like it

i love cerealcodes <3

»
9 months ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

»
9 months ago, # |
  Vote: I like it -13 Vote: I do not like it

there is another way to solve B (I think):

a[k]=K[k-3]*a[1]+K[k-2]*a[2];

where K is fibonacci-like sequences from 1 and 1

then use binary search can solve problem

code:

int a[N];

int k1[N], k2[N];

inline void solve()

{

int n, k;

cin >> n >> k;

if (k > 2e3)

{

    cout << 0 << endl;

    return;

}

int ans = 0;

int m1, m2;

fore(i, 0, n)

{

    int l = i, r = 2e5;

    while (l < r)

    {

       int mid = (l + r) / 2;

       if (k1[k] * i + k2[k] * mid >= n) r = mid;

       else l = mid + 1;

    }

    if (k1[k] * i + k2[k] * l == n) ans++;

}

cout << ans << endl;

return;

}

signed main()

{

k1[1] = 1, k1[2] = 0;

k2[1] = 0, k2[2] = 1;

fore(i, 3, 2e3)

{

    k1[i] = k1[i - 1] + k1[i - 2];

    k2[i] = k2[i - 1] + k2[i - 2];

}

//cout << k1[11] << ' ' << k2[11] << endl;

int t;

cin >> t;

while (t--)

{

    solve();

}

return 0;

}

»
9 months ago, # |
  Vote: I like it +23 Vote: I do not like it

Tough round. Yes, I cry.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

One of the best rounds in quite a while. Hats off to the authors.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
9 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

In Problem B Solution Code:

We don't need to check for

valid_seq &= min(first, second) >= 0;

Got AC without it

Since we are subtracting the smaller from bigger value, we will never get a negative value.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
9 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    $$$\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.

    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you guys, I've figured it out, I did not notice that the array a in the tutorial begins from zero instead of one haha.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

thanks for information

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    9 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have a solution using binary search https://codeforces.com/contest/1853/submission/215254238

    I hope it will be useful

»
9 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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?

»
9 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

great tutorial

»
9 months ago, # |
  Vote: I like it +5 Vote: I do not like it

I can not understand jiangly's 1A.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    they’re the editorial writers for that problem

»
9 months ago, # |
  Vote: I like it +13 Vote: I do not like it

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) ?

  • »
    »
    9 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    thanks, it has been fixed

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain why this code 215796354 is accepted with GNU C++17 for problem B but 215796303 faces a runtime error with GNU C++20 (64), both the codes are exact same.

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

samples are really great

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

link to problem: https://codeforces.com/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.com/contest/1853/submission/216182584

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

Thank you in advance

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This solves 1853B — Fibonaccharsis in O(n). 216940925

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

There are codes here,it's really great tutorial!

»
5 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

I found a interesting solution for problem B in O(number of fibonacci numbers under n)

        vector<double>fib(35);
        fib[1]=1;
        for(int i = 2;i < 32;i++){
	  fib[i]=fib[i-1]+fib[i-2];
        }
	int n,k;
	cin >> n >> k;
	if(k>30)cout << 0 << nl;
	else{
	    if(k%2==0){
		cout << floor((fib[k-1]*n)/fib[k])-ceil(((fib[k-2]*n)/fib[k-1]))+1 << nl;
	    }
            else{
		cout << floor(((fib[k-2]*n)/fib[k-1]))-ceil((fib[k-1]*n)/fib[k])+1 << nl;
	    }
	}
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.