### cry's blog

By cry, 10 months ago,

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

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++)
• +183

 » 9 months ago, # |   +54 One of the editorials of all time.
•  » » 9 months ago, # ^ |   +144 Fun facts about my problem D1C/D2E (Ina of the Mountain):1: The name Ina of the Mountain was inspired by Vaan Ch.'s Ina of the Mountain series (also linked above).2: Suisei's boulder throwing was inspired by a Holograffiti episode.3: There were at least 9 versions of the problem statement, not including different constraints. (I forget exactly the chronology; this list is out of order to make explanation easier.) If different constraints are counted, there are probably 3-4 more, as I proposed using an $O(n^2)$ solution as a subtask; this was ultimately rejected. My entire life story (all versions of the problem statement)It all started when I was born. Years later, I came up with a certain competitive programming problem.The original problem was inspired by the Collatz Conjecture (more info here). Instead of boulders reducing health values by 1, except for when they regenerate to k, moves would apply the Collatz function, and the final state would be all 1s. The Collatz function has a similar cycle to the current problem, but it only has a period of 3, corresponding to $k=3$ in the version of the problem used in this round.The second version artificially changed the period to be higher, by restricting input values to powers of two and multiplying the number by $2^k - 1$ after it reached 1.This second version solely involved Lothar Collatz, but I decided to include Ina as well, creating the third version: "Ina Solves the Collatz Conjecture".In short, this version went something like this: FlavorNinomae Ina'nis was given a problem by Lothar Collatz. Ina discovered a truly marvelous proof of this, but it was too long to fit in this problem statement.The problem was too trivial, so she wanted to make a more complicated version. She gives you an array of powers of two and a number $k \ldots$Ultimately, the problem was better without the addition of the Collatz function or something similar with a higher cycle period. It did not add significant difficulty to the problem, as either one would have to compute the delay of each number, or the problem would use powers of 2, which reduces immediately to the current version of the problem.Thus, two more versions were created, 4 and 5: one with no flavortext, and one with a simple flavortext mentioning a CerealCodes member.Then, I added my own flavortext, creating version 6: "Ina goes Bonking".After that, I edited the flavortext again to create version 7, using the title as you know it, "Ina of the Mountain".After that, after some complaints relating to translation, the problem statement was changed one last time to version 8, renaming nearly every instance of the word "Takodachi" to "friend", as well as reformatting other things.Finally, in version 9, the only change was that “friend” was again renamed to “octopus”.Additionally, I made an illustration for the problem that was ultimately rejected. It is linked here: Image credits: Ninomae Ina'nis for the illustration of Ninomae Ina'nis. wavelets for the photograph of Mount Fuji. Holograffiti animators for the animation of Suisei throwing a boulder, from which a screenshot was taken (also linked above for the inspiration of Suisei's boulder throwing). MAZEL for the illustration of Kiryu Coco. Myself for the drawing of the Takodachis (octopuses) and healthbars on Krita, as well as chroma-keying all the parts of and putting together the image on GIMP. PS.:I have found a truly marvelous proof of the truth of the Collatz Conjecture, but it is too long to fit in the confines of this postscript.
•  » » » 9 months ago, # ^ |   0 The time complexity of problem A is O(n) ?
 » 9 months ago, # |   +14 such a well written editorial :heart_eyes: also i get photo credits :OO
 » 9 months ago, # |   0 great contest and Very interesting problemset :) ,but HUGE skill gap between div2B and div2C
 » 9 months ago, # | ← Rev. 2 →   +52 Interesting Problems and quick editorials :3I 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, # ^ |   +42 yes, it was, we are sorry about that. glad you still liked it.
 » 9 months ago, # |   0 wow, that is fast
 » 9 months ago, # |   +14 the hardest div 2 i have ever seen :<
•  » » 9 months ago, # ^ |   0 I am not able to implement C on time. But this is not the hardest.
•  » » » 9 months ago, # ^ |   0 oh so which is the hardest TvT
•  » » » » 9 months ago, # ^ | ← 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).
•  » » » » » 9 months ago, # ^ |   +8 oh the last div 2 TvT it shocked me a lot TvT
•  » » » » 8 months ago, # ^ |   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.
 » 9 months ago, # |   +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
•  » » 9 months ago, # ^ | ← 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!?
•  » » » 9 months ago, # ^ | ← 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.
•  » » » » 9 months ago, # ^ |   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 ...
•  » » » » » 9 months ago, # ^ |   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.
 » 9 months ago, # |   0 Great problemset, Well Written editorial . One of the best editorial i have seen . gap between div2C and div2B was too much.
 » 9 months ago, # |   +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.
•  » » 9 months ago, # ^ | ← 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.
•  » » » 9 months ago, # ^ |   +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
 » 9 months ago, # |   +52 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, # ^ |   +3 just edited, is it clearer now
 » 9 months ago, # |   +6 good 1a/1b/1c! I'm trying to improve my IQ for 1d.
 » 9 months ago, # | ← 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))$.
•  » » 9 months ago, # ^ |   0 can you share how did you reached to this conclusion? Non-origination
•  » » » 9 months ago, # ^ |   +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$.
•  » » » » 9 months ago, # ^ |   0 How are you keeping track of k-1th mex of the array?
•  » » » » » 9 months ago, # ^ |   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.com/contest/1853/submission/215255944Here $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, # |   0 I was about to become Candidate Master today but got FST (Failed System Testing) on the B problem : (
•  » » 9 months ago, # ^ |   +20 I still became Candidate Master : )
•  » » » 9 months ago, # ^ |   0 congratulations
 » 9 months ago, # | ← 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 xDP.S. great problem, btw!
•  » » 8 months ago, # ^ |   0 Please, can you kindly tell me how to prove it? ty very much!
 » 9 months ago, # |   0 Nice contest..i slove 3 problem first time in div 2
•  » » 9 months ago, # ^ |   0 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, # |   +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.
 » 9 months ago, # |   -16 "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, # |   +1 tnx 4 fast editorial
 » 9 months ago, # |   0 Must problem div2C use long long? I found one of my friends passed it without using long long.
•  » » 9 months ago, # ^ |   0 answer can be up to $10^{10}$, so yes
•  » » » 9 months ago, # ^ |   +6 Oh, its so pity I cannot hack my friend...
•  » » » » 9 months ago, # ^ |   0 le that friend using #define int long long
 » 9 months ago, # |   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.
•  » » 9 months ago, # ^ |   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.
•  » » » 9 months ago, # ^ |   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.
•  » » » » 9 months ago, # ^ |   0 How did you check all the elements before x is deleted or not?
 » 9 months ago, # | ← 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
•  » » 9 months ago, # ^ | ← 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.
•  » » » 9 months ago, # ^ | ← 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].
•  » » » » 9 months ago, # ^ | ← 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 ?
•  » » » » » 9 months ago, # ^ |   0 The time complexity is O(n/F[k]). So in the worst case (for small k) it becomes O(n).
•  » » » » » » 9 months ago, # ^ |   +3 That means this works faster than the editorial's solution in the average case ?
•  » » » » » » » 9 months ago, # ^ |   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.
•  » » » » » » » » 9 months ago, # ^ |   0 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, # |   0 Cannot understand editorial of div2C
•  » » 9 months ago, # ^ |   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.
 » 9 months ago, # |   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 ?
•  » » 9 months ago, # ^ |   0 Yes
•  » » » 9 months ago, # ^ |   0 Thankyou for answering.
 » 9 months ago, # |   0 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, # ^ |   0 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, # ^ |   0 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, # ^ |   0 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, # |   0 1852D — Miriany and Matchstickhow 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 Bthats 6A_B_A_B_A.A_B_A_Band thats 7what I miss ?
•  » » 9 months ago, # ^ |   +2 you didn't count the adjacencies in the top row of the matchstick
•  » » » 9 months ago, # ^ |   0 oh, thx now I can see that golden TL xd
 » 9 months ago, # |   0 someone please explain div2 c with example
 » 9 months ago, # | ← Rev. 3 →   0 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, # |   +80
•  » » 9 months ago, # ^ |   +14 I hate the fact that it's so relatable.
 » 9 months ago, # |   0 Fast and quality editorial. Thanks
 » 9 months ago, # |   +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.com/contest/1852/submission/215259895
•  » » 9 months ago, # ^ |   +4 Very nice. Our original solution was greedy, but it got RTE after we prepared the problem.
•  » » 9 months ago, # ^ |   +14 It can also be solved through random algorithm, we can determine the answer from back to front and choose the answer which is legal randomly. Here's my code:https://codeforces.com/contest/1852/submission/215263597
 » 9 months ago, # |   +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.com/contest/1853/submission/215254923
 » 9 months ago, # |   +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
•  » » 9 months ago, # ^ | ← Rev. 2 →   +29 I am, but only after contest. LinkIt 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, # ^ |   0 Thanks for sharing, I'll definitely take a look at those optimizations
 » 9 months ago, # | ← Rev. 2 →   0 I saw many solving C with binary search, can anyone explain it?
•  » » 9 months ago, # ^ | ← 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
•  » » » 9 months ago, # ^ | ← 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})$
•  » » » » 9 months ago, # ^ |   0 Thank you so much! Finally understood.
•  » » » » 9 months ago, # ^ |   0 pls can you explain DIV 2 D , I was unable to understand from editorial
•  » » » 9 months ago, # ^ |   +5 esr6vqa LMydd0225 thanks to you both, I got the intuition and how we could come up with such solution,thanks again.
 » 9 months ago, # |   +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$
•  » » 9 months ago, # ^ |   0 can someone explain how to reach this equation?
•  » » » 9 months ago, # ^ |   +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$
•  » » » » 9 months ago, # ^ |   0 Thanks a lot!
 » 9 months ago, # |   0 This div2C is where I doubted my entire existence :( --> cries in low IQ
 » 9 months ago, # |   +14 Is it just me or C was harder than D?
 » 9 months ago, # |   0 In problem D(Div2),can someone please explain the Hint1 given in the editorial(I mean why is this statement true).
•  » » 9 months ago, # ^ |   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.
 » 9 months ago, # | ← 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
 » 9 months ago, # |   +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.
•  » » 9 months ago, # ^ |   +2 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 →   +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 #include #include 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 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
•  » » 9 months ago, # ^ |   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$.
 » 9 months ago, # |   +8 i love cerealcodes <3
 » 9 months ago, # |   +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.
 » 9 months ago, # |   -13 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 1then use binary search can solve problemcode: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, # |   +23 Tough round. Yes, I cry.
 » 9 months ago, # |   0 One of the best rounds in quite a while. Hats off to the authors.
 » 9 months ago, # |   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.
 » 9 months ago, # | ← Rev. 4 →   0 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.
•  » » 8 months ago, # ^ |   0 hm
 » 9 months ago, # |   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.
 » 9 months ago, # |   +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 :-(
•  » » 9 months ago, # ^ |   0 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 →   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.
•  » » » 9 months ago, # ^ |   0 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, # |   0 thanks for information
 » 9 months ago, # |   0 can someone explain how they solved B(1853B — Fibonaccharsis) by using binary search....
•  » » 9 months ago, # ^ | ← 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 yx0 = p + K * b / gcd(a , b)y0 = q — K * a / gcd(a , b)binary search on value of k
•  » » » 9 months ago, # ^ |   0 I don't understand your approach. Can you elaborate more?
•  » » » » 9 months ago, # ^ |   0
•  » » » 9 months ago, # ^ |   0 Cool.. got it now Thanks :)
•  » » 9 months ago, # ^ |   0 I have a solution using binary search https://codeforces.com/contest/1853/submission/215254238I hope it will be useful
•  » » » 9 months ago, # ^ |   0 Thanks @alikhan_emes :)
 » 9 months ago, # |   +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?
 » 9 months ago, # | ← Rev. 3 →   0 great tutorial
 » 9 months ago, # |   +5 I can not understand jiangly's 1A.
 » 9 months ago, # |   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.
•  » » 9 months ago, # ^ |   +3 they’re the editorial writers for that problem
 » 9 months ago, # |   +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) ?
•  » » 9 months ago, # ^ |   +3 thanks, it has been fixed
 » 9 months ago, # |   0 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, # |   0 samples are really great
 » 9 months ago, # |   0 link to problem: https://codeforces.com/contest/1853/problem/BI 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/216182584If you hate java like me, here is the c++ version: https://codeforces.com/contest/1853/submission/216183198Thank you in advance
•  » » 9 months ago, # ^ |   0 O(nk log n) will not pass under the constraints
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 oh okay, thanks for the feedback.
 » 9 months ago, # |   0 In Problem — D — Codeforces,dose the dp only consist two intervals which are adjacent
 » 8 months ago, # |   0 This solves 1853B — Fibonaccharsis in O(n). 216940925
 » 5 months ago, # |   0 There are codes here,it's really great tutorial!
 » 5 months ago, # | ← Rev. 3 →   0 I found a interesting solution for problem B in O(number of fibonacci numbers under n)  vectorfib(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, # |   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.