### IgorI's blog

By IgorI, history, 8 months ago,

Thank you for participating in the contest! I hope you enjoyed the tasks. Here is an editorial with hints.

1474A - Puzzle From the Future

Hint 1
Hint 2
Editorial
Solution

1474B - Different Divisors

Hint 1
Hint 2
Hint 3
Editorial
Solution

1474C - Array Destruction

Hint 1
Hint 2
Hint 3
Hint 4
Editorial

1474D - Cleaning

Hint 1
Hint 2
Hint 3
Hint 4
Editorial
Solution

1474E - What Is It?

Hint 1
Hint 2
Hint 3
Hint 4
Editorial
Solution

1474F - 1 2 3 4 ...

Bonus
Editorial
Solution

Good luck in your future contests!

• +307

 » 8 months ago, # |   +18 thanks for fast editorial
 » 8 months ago, # |   +10 Hope I'll become Candidate master today without new year's magic ;)
•  » » 8 months ago, # ^ |   +25 You already are ;)
•  » » 8 months ago, # ^ |   +5 You can see unofficial results with CF predictor
•  » » 8 months ago, # ^ |   0 In just 6 weeks ! Respect
 » 8 months ago, # |   +18 Man!!! That was really quick! Nice hints and clear insight.
 » 8 months ago, # |   0 If negative numbers allowed in problem C, Is this problem still can be solved ?
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 Sorry I underestimated the fact that, the X will become variable in case of negatives. Ex : 6 4 1 -2 Here we can make X = 5, {4, 1} -> {6, — 2}
•  » » » 8 months ago, # ^ |   0 em...you are right.But this solution can't.
 » 8 months ago, # |   0 Thanks!
 » 8 months ago, # |   +40 Good contest, despite O(N^2LogN) not passing in java for C
 » 8 months ago, # | ← Rev. 2 →   +14 I am not understanding why i am getting tle verdict in third problem. I think i am doing it in O(n2⋅logn) but i am wrong maybe . Here is a link to my submission https://codeforces.com/contest/1474/submission/104839937 I would be extremely glad if someone can point out the error.
•  » » 8 months ago, # ^ | ← Rev. 6 →   +2 for me also the multiset solution was not passing then I did it using the count array as the numbers were restricted to 10**6. So, I modified it to O(N^2) solution. Upd: sorry did not knew that count operation in multiset takes linear time.
•  » » 8 months ago, # ^ | ← Rev. 2 →   +12 I think the issue is in the part after you calculate as where you do s.erase(dusra). Instead you should do s.erase(it).
•  » » » 8 months ago, # ^ |   0 Thanks it solved the provlem. I meant to write it only there i don't know what i was thinking then.
•  » » » 8 months ago, # ^ |   0 I don't understand why 104806538 is getting TLE in problem C. I think it is n2*logn and should pass. It would be very helpful if someone can point out the issue.
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   +9 as rkguptagkp462 pointed out count opertaion takes linear time. Upd: my bad i thought multiset was used instead of set
•  » » » » » 8 months ago, # ^ |   +6 that is for multiset no? count in std::set take logn time only.Although, i tried this as well 104853778.
•  » » » » 8 months ago, # ^ |   0 Use GNU C++17(64) 104917682 ....
•  » » 8 months ago, # ^ |   0 can anyone help me in this ->if 1
 » 8 months ago, # |   0 There doesn't seem to be any hacking round, so When is the rating gonna be updated?
•  » » 8 months ago, # ^ |   0 Wait for 1-5 hours.
 » 8 months ago, # |   +25 Very well written tutorial. While solving C using multiset; one needs to remember that erasing an element by value will delete all elements having same value. And it costs you time to debug it and to read online documents.
•  » » 8 months ago, # ^ |   +1 Use iterators to avoid that!
•  » » 8 months ago, # ^ |   +1 you can just use m.erase(m.find(element));
•  » » » 8 months ago, # ^ |   +1 it looks elegant.
 » 8 months ago, # | ← Rev. 2 →   0 Problem 1474D - Cleaning. I supposed that, if we don't use the ability, the answer is "yes" if and only if the sum of numbers on odd positions is equal to the sum of numbers on even positions, and every number is not greater than the sum of it's neighbors. But the solution fails: 104836378. Is my idea wrong, or is it because of some mistake in the implementation? I wasn't able to find any couterexample(and the test on which it fails is unvisible) nor any formal proof. Thanks in advance.UPD: I have found the counterexample. Very weird my solution passed all those millions of tests. 1 8 2 2 4 3 1 2 1 1 
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 I used the same idea and it worked. You can check my submission.UPD: the counterexample isn't complex but I just couldn't find one during the contest.
•  » » » 8 months ago, # ^ |   0 Thank you, it turns out I used bool instead of int for the prefix sums array, that was the mistake.
•  » » » » 8 months ago, # ^ |   0 Do you have any formal proof of this solution(I also had the same intuition while trying to upsolve it but sadly i cannot prove it)?
•  » » » » » 8 months ago, # ^ |   +5 Sadly, no one can prove it because it is simply wrong. See my comment above.
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   0 Can you please tell why my submission is not accepted like I am also doing using similar approachhttps://codeforces.com/contest/1474/submission/104876110 [My submission]
•  » » » » » 8 months ago, # ^ |   0 Sorry, no idea. Try checking if all the indices are correct.
•  » » » » » » 8 months ago, # ^ | ← Rev. 4 →   +5 Some people were lucky and their solution got accepted otherwise it is giving wrong answer on 1131 2 2 3 1 3 2 1 2 1 2 2 2answer should be no but your and mine approach gives Yes
•  » » » » » » » 8 months ago, # ^ |   0 Just figured that out too.
•  » » » 8 months ago, # ^ |   0 Can you please explain how to choose x for C problem ? i'm stuck at that.
•  » » » » 8 months ago, # ^ |   +5 From the problem statement it can be observed that x will decrease with each operation. So it is necessary for us to take maximum element as one of the constituent of x. whyIf we choose both elements lesser then the maximum elements as constituent of x, then in that case after first operation we are going to have new x as lesser then the maximum value of the remaining elements in the array. In that case it is clear that eventually we will not be able to get solution using that x. So we must combine each of the element with the maximum to get a new potential value of x. and check if it is feasible to go with that value of x.
 » 8 months ago, # |   0 I was only able to solve A and couldn't finish debugging C. Just found out that the only bug in my C code was m.find(t)--. (It should be m[t]--)-99 rating. YAY never been happier
 » 8 months ago, # |   0 I don't really understand the explanation for D. Can somebody explain/give an example for how p_i and s_i are calculated, and what the check mentioned in the last paragraph is? A link to a solution that implements this method would be just as good as well.
•  » » 8 months ago, # ^ |   0 Iguess p_0=0;p_i=a_i-p_(i-1). It simulates from left to right and from right to left how to remove the first/last pile.
•  » » 8 months ago, # ^ |   0 I think I rewrote it somewhat cleaner in 105191466.
 » 8 months ago, # |   0 Video Editorial for
•  » » 8 months ago, # ^ |   +7 I think you should first focus on improving your problem solving skills rather than wasting time in making youtube videos.p.s. NO intention of offending you but just an advice, rest on you .
 » 8 months ago, # |   0 My Java Solution for Problem C: 104839108 Isn't it O(n^2logn) ? I used to HashMap.
•  » » 8 months ago, # ^ |   0 Can you help me with my Java submission for C. Its giving TLE even though its O(n^2 logn) 104873241
•  » » » 8 months ago, # ^ |   +10 No, it's $O(n^3)$: for each starting $x$ ($2n$ variants) you $O(n)$ times call $contains()$ and $remove()$ from $ArrayList$ $l$, where at least one call of $remove()$ is removing the first element and works in $O(n)$.
•  » » » » 8 months ago, # ^ |   0 Thank you :)
 » 8 months ago, # |   0 in 1 sec per test: will our code of O(n^2) passes? if 1<=t<=1000 and 1<=n<=1000 because i read only 10^7 operations will pass... but here (n^2)*t will be around 10^9 right.. any clarification on this will be appreciated...
•  » » 8 months ago, # ^ | ← Rev. 2 →   0 It is guaranteed that the total sum of n over all test cases doesn't exceed 1000. This means: Whether how many test cases there are, n will never exceed 1000. You can remove 't' from your complexity here. Suppose t=1000. Then the value of n in each test case will be 1 only.
•  » » » 8 months ago, # ^ |   0 thanks..
•  » » 8 months ago, # ^ |   0 "It is guaranteed that the total sum of n over all test cases doesn't exceed 1000."
•  » » » 8 months ago, # ^ |   +1 thanks
 » 8 months ago, # | ← Rev. 2 →   +16 This editorial is awesome as it totally focuses on concepts instead of spoon-feeding.
 » 8 months ago, # |   0 It's hard for me to understand why there is only one way to make all numbers equal to 0 in problem D. I don't get how proof works. Can someone explain ?
•  » » 8 months ago, # ^ |   +3 Start from a[0], it necessarily takes a[0] operations. Apply those and now a[1] is fixed and a1~n-1 is a similar problem.
•  » » » 7 months ago, # ^ |   0 Why start from a[0] ? why not from a[n-1] ?
•  » » » » 7 months ago, # ^ |   0 Uh, obviously it is equivalent?
 » 8 months ago, # | ← Rev. 4 →   +55 My soln of F is similar to the model soln mentioned in the editorial of 1295F - Good Contest.Firstly in linear time, we can compute the length of LIS.Let's fix a minimum element of LIS say X and length by L. Then we know that LIS is $X,X+1,..,X+L-1$. We will loop over all possible Xs.dp[0][X-1]=1.dp[i][j] is no of LIS starting at X and end at j using first $d_1,d_2,...,d_i$This soln works in $O(n*(max(Pi)-min(Pi))$.One can refer to this Bruteforce soln for more details about DP states.Soln in one line — dp[i] is a piecewise polynomial function of degree atmax i in j. Let's denote B be the set of all values in prefix sum of the given array in increasing order.Important thing to note here is there exsists a polynomial P(x) of degree less than or equal to i such $P(B_l)=dp[i][B_l],P(B_l+1)=dp[i][B_l+1],...,P(B_{l+1}-1)=dp[i][B_{l+1}-1]$.So instead of maintaining $O(B_{l+1}-Bl)$ states we can just maintain i+1 values and interpolate this polynomial whenever required. Also, X belongs to B.For each polynomial, we maintain O(n) values. Interpolation takes O(n). There are $O(n*n)$ polynomials for each $X$.This soln works in $O(n^4)$.AC Submission
 » 8 months ago, # | ← Rev. 2 →   +34 I just added solutions in C++ to all problems.There are some problems with spoilers now, so hints are published without any spoilers (actually it is the reason editorial wasn't pusblished just after the contest).Anyway, thanks again for taking part in my contest and discussing its problems.UPD: Now hints should be ok
•  » » 8 months ago, # ^ |   +7 The Problems were beautiful.
•  » » 8 months ago, # ^ |   +17 Great problems. The hints in the editorial are excellent as well. Thanks for a very interesting problem set.
•  » » 8 months ago, # ^ |   0 The editorial is great and for the "Hint" giving system, I found it helpful in understanding the solution approach. Great Job.. I just have a little query. Can you tell me why we need two array in Problem D??
 » 8 months ago, # | ← Rev. 2 →   0 Hey, can someone explain why am I getting time limit exceed for problem C : https://codeforces.com/contest/1474/submission/104834766I used a O(n^2log(n)) solution, normally it should pass..I used an unerdored map in the last seconds and got accepted in 982 ms.Thanks in advance
 » 8 months ago, # |   0 Can someone tell me Time complexity of my code , I think it is O(N^2) approx. https://codeforces.com/contest/1474/submission/104834839
 » 8 months ago, # |   +27 Here are my video solutions of this round for A-E, which I'm really glad I didn't do a screencast for
•  » » 8 months ago, # ^ |   0 best !! — i always kinda prefer a video explanation :P
 » 8 months ago, # | ← Rev. 2 →   +13 Can someone explain why we don't need to check the case where $a = p^3$ in problem B ?In other words why can't a solution be of the form: $1$ $p$ $p^2$ $p^3$ ?
•  » » 8 months ago, # ^ | ← Rev. 2 →   +3 $p_1.p_2 < p_1^3$ where $p_1 > d, p_2 \geq p_1 + d.$ Since, we're asked to find the minimum integer $x$. Maybe, It's also because prime numbers are dense at the start.
•  » » » 8 months ago, # ^ |   0 what if $p_1^2 < p_2$ ? or that just never happens due to the limits of this problem ?$p_1^2$ being greater or equal than $p_1 + d$$p_2$ being next prime greater or equal than $p_1 + d$any formal or convincing proof that this never happens?
•  » » » » 8 months ago, # ^ | ← Rev. 4 →   +21
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   +10 Bertrand's postulate, proven in 1852, states that there is always a prime number between k and 2k, so in particular $p_{n+1} < 2p_n$.
•  » » » » 8 months ago, # ^ | ← Rev. 2 →   0 As pointed in above comments , we can prove using Bertrand Postulate .More formally suppose you say answer is $p^3$ and thus it's factors are $1,p,p^2,p^3$ . Difference between each of them should be greater than $d$. Thus $p_1≤p$ . Using Bertrand Postulate we can say that there must exist prime $p_2$ such that $p •  » » » » » 8 months ago, # ^ | 0 No, I don't think$p_1^2 < p_2$since$2p_1 < p_1^2, \forall p > 2$.We can further postulate that, there also exist a prime,$p_x$that is less than$4p_n$with Bertrand's Postulate since,$p_{n + 1}$may not be greater than or equal to$p_n + d$.Thus, We can prove that$p_n . p_x < p_n^3$. •  » » » » » » 8 months ago, # ^ | ← Rev. 3 → 0 I wrote$p < p_2$.It's called proof by contradiction. So i assumed that$p^3$is the best answer but then we arrived at contradiction that a better answer would exist in that case. •  » » » » » » » 8 months ago, # ^ | ← Rev. 2 → 0 Using Bertrand Postulate we can say that there must exist prime$p_2$such that$p^2
•  » » » » » » » » 8 months ago, # ^ | ← Rev. 5 →   0 In Bertrand Postulate , take $n=p$ , also $p≥2$ , thus there must exist prime $p_2$ such that $n •  » » » » » » » » » 8 months ago, # ^ | ← Rev. 3 → 0 In Bertrand Postulate , take$n=p^2$, also$p\geq2$, thus there must exist prime$p_2$such that$n
•  » » » » » » » » » 8 months ago, # ^ | ← Rev. 2 →   0 It can be any integer . I get what you're saying. But $p^2$ has to be a prime number in order to use Bertrand's postulate A less restrictive formulation is: for every $n>1$ there is always at least one prime p such that $n •  » » » » » » » » » 8 months ago, # ^ | ← Rev. 3 → 0 Ok, I take L btw You could've used this before, take$n=p^2$, also$p\geq2$, thus there must exist prime$p_2$such that$n
•  » » » » » 8 months ago, # ^ | ← Rev. 7 →   +3 When you said p ^ 2 < p2 < p ^ 3, didnt you actually prove p1 * p2 is a worse answer? Because suppose p1 = p so then p1 * p2 > p * p ^ 2, because p2 > p ^ 2. So optimal would be p ^ 3.
•  » » » » » » 8 months ago, # ^ |   0 I pointed it out at last and You can still find a prime $p_2 < p_1^2$ which I explained here
•  » » » » » » » 8 months ago, # ^ |   0 Ok thanks
•  » » » » » » 8 months ago, # ^ |   0 Thanks for pointing it out , I have corrected it now. Actually i needed to write $p  » 8 months ago, # | +26 This "Hint by Hint" format is nice. Keep it up.  » 8 months ago, # | 0 I would be very thankful if someone can find the bug in my code https://codeforces.com/contest/1474/submission/104847038 I'm unable to figure it out •  » » 8 months ago, # ^ | ← Rev. 2 → +3 Testcase: 2 8 2 4 5 Correct Answer:NO Your OUTPUT: YES 13 5 8 4 4 2 2  •  » » » 8 months ago, # ^ | 0 You can’t use the same number multiple times •  » » » » 8 months ago, # ^ | 0 Yes,that's why above person's solution is incorrect. •  » » » » » 8 months ago, # ^ | 0 Thank you so much  » 8 months ago, # | 0 Why did my recursive solution to Problem — C got TLE ? Any insight will be really helpful https://codeforces.com/contest/1474/submission/104837945  » 8 months ago, # | +3 Problem B can be solved with help of regexes, as N is not big. Try it yourself. Spoiler 1You can create a string which contains 0 on prime indexes, 1 otherwise. Spoiler 2You can use quantifiers with minimal range, i.e {X,} for preserving minimal distance d. Spoiler 3Even generating an array of primes you can use similar trick.Solution 104855574  » 8 months ago, # | +3 The time constraints for C are absolutely atrocious, I tried 3 different n^2 log n implementation and I wasn't able to make any of them pass  » 8 months ago, # | 0 If anyone is stuck at C https://youtu.be/Y_53vVG7RMw  » 8 months ago, # | 0 I still have a question about prob D, why we just talk about the swap between 'a[i]' & 'a[i+1]' ? •  » » 8 months ago, # ^ | 0 Before the start of cleaning, you can select two neighboring piles and swap them. •  » » » 8 months ago, # ^ | 0 Oppps, what an idot i am... :(by the way, what if there's no this "neighboring" limit? •  » » » » 8 months ago, # ^ | 0 I think there is n^2 solution then  » 8 months ago, # | 0 My solution is getting WA on test 2 and I don't understand why. Can someone please give me a test case where this fails?https://codeforces.com/contest/1474/submission/104864709 •  » » 8 months ago, # ^ | 0 Is fails on test case:151 1 3 3 2 •  » » » 8 months ago, # ^ | 0 Got it, thank you!  » 8 months ago, # | 0 I got a few doubts in n* +max(a) solution of c if (cnt[a[j]] < 0 || cnt[x - a[j]] < 0) { cnt[a[j]] = 0; cnt[x - a[j]] = 0; break; } when the cnt of a[j] will be less than zero ? as for in while loop we check that cnt[a[j]]>0 also if i comment it out, then why it gives wrong answer since in reset(a) after ops, we are anyway setting cnt[a[i]] to zero ?  » 8 months ago, # | 0 brilliant idea for problem D  » 8 months ago, # | 0 Is +460 in first codeforces contest good? What is the metric for good and bad for codeforces contests? •  » » 8 months ago, # ^ | 0  » 8 months ago, # | +1 This format of multiple hints and then answering them is great  » 8 months ago, # | ← Rev. 2 → +3 Problem D, Now we have 0 stones in the 1-st pile and a2−a1 stones in the 2-nd pile. I understood this.We can apply the idea above and get that we should have a2−a1 stones in the 3-rd pile. How do we get a2-a1 for 3-rd pile? •  » » 8 months ago, # ^ | 0 I think he meant to say at least (a2-a1) stones on the 3rd pile. If there were only three piles, then the 3rd pile should have exactly (a2-a1) stones. •  » » » 8 months ago, # ^ | 0 It is probably misprint. The 3-rd pile should be: a3-(a2-a1). a1 -> a2 -> a3 -> a4 ... 0 -> a2-a1 -> a3 -> a4 ... 0 -> 0 -> a3-(a2-a1) -> a4 ... 0 -> 0 -> 0 -> a4-(a3-(a2-a1)) ... and so on  » 8 months ago, # | 0 Why I'm getting RE in Case 6 in problem C, Help me (O_O) :104870245 •  » » 8 months ago, # ^ | 0 upper limit for a[i] is 10^6 but you have made the size of array f as 10^5 so f[a[i]]++ will end up with run time error(as 10^6>10^5 so its array size issue). •  » » » 8 months ago, # ^ | 0 Tnx Man :). Got Ac . Verdict Time : 998 :( 104875146 •  » » » » 8 months ago, # ^ | 0 For each test case, you create a new array$f$of size$10^6$. Don't know why you are sad — you are lucky to get AC on Java with it.  » 8 months ago, # | ← Rev. 2 → 0 What's wrong with my D? I'm confused. 104868453I'm not good at English..Emm...If I don't use the superability,it will be  b[1]=a[1] b[2]=a[2]-a[1] b[3]=a[3]-a[2]+a[1] ... b[n]=a[n]-a[n-1]+a[n-2]-...For odd numbers : b[n]=a[n]-a[n-1]+a[n-2]-...-a[2]+a[1] For even numbers : b[n]=a[n]-a[n-1]+a[n-2]-...+a[2]-a[1]if we swap(a[pos],a[pos]+1]) b[pos] will -a[pos]+a[pos+1]for i>=pos+1 i%2=(pos+1)%2: b[i] will -2*a[pos+1]+2*a[pos] i%2=(pos+2)%2: b[i] will +2*a[pos+1]-2*a[pos]I want b[n]->0 and all i in [1,n] b[i]>=0 I calculate suffix(suf) and prefix(pre)  Oh,I can't make it any clearer,I'm poor in English...upd: Accepted •  » » 8 months ago, # ^ | 0 If I don't use the superability,it will be b[1]=a[1] b[2]=a[2]-a[1] b[3]=a[3]-a[2]+a[1] ... b[n]=a[n]-a[n-1]+a[n-2]-... For odd numbers : b[n]=a[n]-a[n-1]+a[n-2]-...-a[2]+a[1] For even numbers : b[n]=a[n]-a[n-1]+a[n-2]-...+a[2]-a[1] if we swap(a[pos],a[pos]+1]) b[pos] will -a[pos]+a[pos+1] for i>=pos+1 i%2=(pos+1)%2: b[i] will -2*a[pos+1]+2*a[pos] i%2=(pos+2)%2: b[i] will +2*a[pos+1]-2*a[pos] I want b[n]->0 and all i in [1,n] b[i]>=0 I calculate suffix(suf) and prefix(pre) Oh,I can't make it any clearer,I'm poor in English...   » 8 months ago, # | 0 The problems were beautiful!  » 8 months ago, # | ← Rev. 3 → 0 C was just awesome.I solved it using the idea that at each operation we have to select two numbers among which one is always the maximum number among the remaining non selected numbers and the other number can be any number among non selected numbers such that sum of both numbers is equal to x(and then update x and repeat the process) If we can not do it for any selected x then answer will be No. And initial x can be (maximum of all numbers+ any other number from array).  » 8 months ago, # | 0 all editorials should be like this so that while upsolving we can just take hints and not look at whole editorial in first time  » 8 months ago, # | -15 Video Editorial for  » 8 months ago, # | ← Rev. 3 → 0 Hello , Thanks for this awesome contest and awesome solution for Problem D.However I tried to solve D using segment trees and I am able to get AC on it. What I am doing is creating two array for odd and even position and trying every swap by making appropriate updates and then rolling back to original states. I could'nt see anything wrong in my solution. Can someone help me figure it out ? My code//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector") #include #include #include using namespace std; #define ll long long #define endl '\n' #define mod 1000000007 #define pb push_back #define ff first #define ss second #define con continue #define ub upper_bound #define lb lower_bound #define si(x) int(x.size()) #define sum_all(a) ( accumulate ((a).begin(), (a).end(), 0ll)) #define mine(a) (*min_element((a).begin(), (a).end())) #define maxe(a) (*max_element((a).begin(), (a).end())) #define mini(a) ( min_element((a).begin(), (a).end()) — (a).begin()) #define maxi(a) ( max_element((a).begin(), (a).end()) — (a).begin()) #define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) — (a).begin()) #define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) — (a).begin()) const double pi = 2 * acos(0.0); const int dx[] = { -1, 0, 1, 0 }; const int dy[] = { 0, -1, 0, 1 }; const int dx8[] = { -1, 0, 1, 0,1,1,-1,-1 }; const int dy8[] = { 0, -1, 0, 1,1,-1,1,-1 }; ll min(ll a, ll b) { if (a < b)return a; return b; } ll max(ll a, ll b) { if (a > b)return a; return b; } ll ceil1(ll a, ll b) { return(a + b — 1) / b; } void read(vector& arr) { for (ll i = 0; i < si(arr); i++) cin >> arr[i]; } void read_graph(vector>& g, ll m) { while (m--) { ll x, y; cin >> x >> y; x--, y--; g[x].pb(y); g[y].pb(x); } } template struct lazy_segtree { public: lazy_segtree() : lazy_segtree(0) {} lazy_segtree(int n) : lazy_segtree(std::vector(n, e())) {} lazy_segtree(const std::vector& v) : _n(int(v.size())) { log = ceil(log2(_n)); size = 1 << log; d = std::vector(2 * size, e()); lz = std::vector(size, id()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; for (int i = size — 1; i >= 1; i--) { update(i); } } void set(int p, S x) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); return d[p]; } S prod(int l, int r) { assert(0 <= l && l <= r && r <= _n); if (l == r) return e(); l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push(r >> i); } S sml = e(), smr = e(); while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() { return d[1]; } void apply(int p, F f) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = mapping(f, d[p]); for (int i = 1; i <= log; i++) update(p >> i); } void apply(int l, int r, F f) { assert(0 <= l && l <= r && r <= _n); if (l == r) return; l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } { int l2 = l, r2 = r; while (l < r) { if (l & 1) all_apply(l++, f); if (r & 1) all_apply(--r, f); l >>= 1; r >>= 1; } l = l2; r = r2; } for (int i = 1; i <= log; i++) { if (((l >> i) << i) != l) update(l >> i); if (((r >> i) << i) != r) update((r - 1) >> i); } } template int max_right(int l) { return max_right(l, [](S x) { return g(x); }); } template int max_right(int l, G g) { assert(0 <= l && l <= _n); assert(g(e())); if (l == _n) return _n; l += size; for (int i = log; i >= 1; i--) push(l >> i); S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!g(op(sm, d[l]))) { while (l < size) { push(l); l = (2 * l); if (g(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template int min_left(int r) { return min_left(r, [](S x) { return g(x); }); } template int min_left(int r, G g) { assert(0 <= r && r <= _n); assert(g(e())); if (r == 0) return 0; r += size; for (int i = log; i >= 1; i--) push((r - 1) >> i); S sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!g(op(d[r], sm))) { while (r < size) { push(r); r = (2 * r + 1); if (g(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int _n, size, log; std::vector d; std::vector lz; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } void all_apply(int k, F f) { d[k] = mapping(f, d[k]); if (k < size) lz[k] = composition(f, lz[k]); } void push(int k) { all_apply(2 * k, lz[k]); all_apply(2 * k + 1, lz[k]); lz[k] = id(); } }; struct S { ll sum, len, m1; }; struct F { ll a, b; }; S op(S l, S r) { return S{ l.sum + r.sum,l.len + r.len ,min(l.m1,r.m1) }; } S e() { return S{ 0,0,(ll)(1e18) }; } S mapping(F l, S r) { ll a = r.sum * l.a + r.len * l.b; return S{ a,r.len,r.m1 * l.a + l.b }; } F composition(F l, F r) { ll a, b; a = l.a * r.a; b = l.a * r.b + l.b; return F{ a,b }; } F id() { return F{ 1,0 }; } ll n; vector arr; ll calc() { if (si(arr) == 2) { return (bool)(arr[0] == arr[1]); } vector narr(n - 1); narr[0] = arr[1] - arr[0]; for (ll i = 1; i < n - 1; i++) { narr[i] = arr[i + 1] - narr[i - 1]; } ll n1 = ceil1(si(narr), 2); ll n2 = si(narr) - n1; vector seg11, seg22; for (ll i = 0; i < n1 + n2; i++) { if (i % 2 == 0) seg11.pb(S{ narr[i],1,narr[i] }); else seg22.pb(S{ narr[i],1,narr[i] }); } lazy_segtree seg1(seg11); lazy_segtree seg2(seg22); // no swap ll m1 = min(seg1.prod(0, n1).m1, seg2.prod(0, n2 ).m1); ll last; if (n2 == n1) { last = seg2.prod(n2 - 1, n2 ).m1; } else last = seg1.prod(n1 - 1, n1 ).m1; if (m1 == 0 and last == 0) return true; for (ll i = 0, j = 0, k = 0; i < n - 1; i++) { // apply if (i % 2 == 0) { ll val = 2 * (arr[i] - arr[i + 1]); if(j<=n1-1) seg1.apply(j, n1 , F{ 1,val }); if(k<=n2-1) seg2.apply(k, n2 , F{ 1,-val }); } else { ll val = 2 * (arr[i] - arr[i + 1]); if(j<=n1-1) seg1.apply(j, n1 , F{ 1,-val }); if(k<=n2-1) seg2.apply(k, n2 , F{ 1,val }); } // query ll m1 = min(seg1.prod(0, n1 ).m1, seg2.prod(0, n2 ).m1); ll last; if (n2 == n1) { last = seg2.prod(n2 - 1, n2 ).m1; } else last = seg1.prod(n1 - 1, n1 ).m1; if (m1 == 0 and last==0) return true; // rollback if (i % 2 == 0) { ll val = 2 * (arr[i] - arr[i + 1]); if(j<=n1-1) seg1.apply(j, n1 , F{ 1,-val }); if(k<=n2-1) seg2.apply(k, n2 , F{ 1,val }); j++; } else { ll val = 2 * (arr[i] - arr[i + 1]); if(j<=n1-1) seg1.apply(j, n1 , F{ 1,val }); if(k<=n2-1) seg2.apply(k, n2 , F{ 1,-val }); k++; } } return false; } void solve() { cin >> n; arr.clear(); arr.resize(n); for (ll i = 0; i < n; i++) cin >> arr[i]; bool ans = calc(); reverse(arr.begin(), arr.end()); ans = ans || calc(); string res = "YES"; if (!ans) res = "NO"; cout << res << endl; } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int t; cin >> t; while (t--) solve(); } Update: Figured out my bug, I skipped the fact that I had to update previous element also. xd  » 8 months ago, # | 0 Can anyone one help me with D: https://codeforces.com/contest/1474/submission/104881006 •  » » 8 months ago, # ^ | 0 Try this test case:151 1 3 2 3  » 8 months ago, # | 0 104885466 why i am getting tle •  » » 8 months ago, # ^ | ← Rev. 2 → 0 Because if your use find(ms.begin(), ms.end(), val) it is linear in time, instead you should use ms.find(val), which is O(log n). I submitted your code 104886371 with it and got AC. •  » » » 8 months ago, # ^ | 0 thanks sir you really saved me from getting mad  » 8 months ago, # | 0 I think I submitted the same solution as tutorial in contest still its getting TLE please someone help.. 104886277  » 8 months ago, # | +1 for some reason i feel tired of constructive problem.i dont hate them but while doing them i just feel so weird and solution often suprised very hard (like an unexpectd slap)  » 8 months ago, # | ← Rev. 2 → 0 I am not understanding why I am getting wrong answer in second problem. Value output in codeforces' compiler is not correct as in other compilers. Here is a link to my submission https://codeforces.com/contest/1474/submission/104823896. I would be extremely glad if someone can point out the error. In test case 2, wrong anser is given for case 36 where expected value = 6077831, found was = 6060421, whereas in other compilers found value was also 6077831  » 8 months ago, # | 0 I advise everyone to watch this video, hope would be helpful!  » 8 months ago, # | 0 i started doing the task and forgot to register ,dont rely on extra registrations  » 8 months ago, # | 0 Can we solve problem D if we are allowed to swap any two piles once? It could be a variation for this problem. Suggesions are much appreciated.  » 8 months ago, # | ← Rev. 2 → 0 What input data for D test_2 58th token? I can't figure out what problem in my code. UPD:solved.  » 8 months ago, # | 0 IgorI Thanks for the editorial. Including some hints before the actual editorial solution is a very good idea. It encourages me to reconsider my way of approaching the solution a few more times.  » 8 months ago, # | 0 Video Editorial for Problem C Link : https://www.youtube.com/watch?v=8IYbrS_GncwTRIED MY BEST TO EXPLAIN WITH INTUTION . HOPE YOU GUYS WILL ENJOY THE VIDEO !!!  » 8 months ago, # | 0 Video Editorial for  » 8 months ago, # | 0 If someone pls could help ! their solution for C without set ..isn't it O(n³) ? if not then why coz the three loops in worst case are gonna iterate and complete to their limit ?  » 8 months ago, # | 0 @IgorI hey buddy I have found a better approach but still the program is showing wrong even the number which my program is printing is smaller than the online judge is showing and the condition are satisifed in my program. Please tell me anyone  » 8 months ago, # | 0 Can anyone please help why I am getting runtime error if I shift the position of s.erase(it1); after the auto it2 = s.find(y); present in the editorial solution. Here is the link to the solution Editorial Solution  » 8 months ago, # | ← Rev. 3 → 0 can anybody find what is the mistake in 4 th problem... https://codeforces.com/contest/1474/submission/104956224  » 8 months ago, # | 0 In Task 2: Do we need to check for P^3 ? can anyone give a Testcase where p^2 < second prime  » 8 months ago, # | 0 Can anyone tell me why in Question B the answer is not (1 + b) * (1 + 2b) ? Seen the tutorial, but still don't get it because of my fat brain. •  » » 8 months ago, # ^ | 0 if$b + 1$is not a prime, then you can at least find a factor,$x < b$. else if$2b + 1$is composite, you can at least find a factor,$x > b$and$x - (b + 1) < b$. else a possible solution. •  » » » 8 months ago, # ^ | 0 just found out that p and q should be prime, but still, ur reply made it really clear. thanks a lot. •  » » » » 8 months ago, # ^ | 0 Yeah they have to be prime. So you can ensure the difference between them is at least greater than or equal to$b$. You can get the idea if you think about prime factorization.  » 8 months ago, # | ← Rev. 2 → -6 Hi  » 8 months ago, # | 0 Can anyone tell what is wrong in my D? WA on test 2: 105030694  » 8 months ago, # | 0 Still stuck in problem D, can anyone help me? :| thanks. 105049987 •  » » 8 months ago, # ^ | 0 my latest WA submission #105067344 •  » » 8 months ago, # ^ | 0 Oh, I find out why. in case 0 if (Smark==n+1 && s[n]==0) in case 2 (a[i]-s[i-1]>=0 && a[i+1]-p[i+2]>=0 && a[i]-s[i-1]==a[i+1]-p[i+2] && s[i-1]>=0 && p[i+2]>=0)  » 8 months ago, # | 0 https://codeforces.com/contest/1474/submission/105134731 for C getting tle at testcase 2 can anyone point out the time complexity of the code. also the necessary changes to make the code pass Thanks in advance .  » 8 months ago, # | ← Rev. 2 → 0 somebody please explain why this is giving TLE for problem 1. https://codeforces.com/contest/1474/submission/104916660 again for problem 1, the following code prints all digits as 1, i cant see why it is happening https://codeforces.com/problemset/submission/1474/105175403 •  » » 8 months ago, # ^ | 0 hey combinatorialist, well I don't know the reason , but in your code this is because of you are using strings and append in strings like a=a+'1'; and b=b+digit; my suggestion is if you use the char array like this char a[(int)1e5+5],b[(int)1e5+5]; int ai,bi; int main(){ int t; cin>>t; vectorsol; while(t--){ memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); ai=0,bi=0; int prevsum=0; char digit; int n; cin>>n; for (int i=0; i>digit; b[bi++]=digit; if(b[i]+1!=prevsum){ a[ai++]='1'; prevsum=b[i]+1; continue; } if(b[i]!=prevsum){ a[ai++]='0'; prevsum=b[i]; } } sol.push_back(a); } for(auto x:sol){ cout< •  » » » 8 months ago, # ^ | 0 ok.....can you also look at my second submission, it is printing every digit as 1, i cant understand why. https://codeforces.com/problemset/submission/1474/105175403 •  » » » » 8 months ago, # ^ | ← Rev. 2 → 0 bro your code is correct! You just make 1 to '1' and 2 to '2' in if(sum-b[i]==2) and else if(sum-b[i]==1) as it is character so it's sum is 97 ans you are comparing it with 2; •  » » » » » 8 months ago, # ^ | ← Rev. 2 → 0 ok, it worked...but i am still confused. when i write int sum=a[i]+b[i], this means that int sum='1'+'1' which should mean int sum="11", and then the string "11" will be converted to int? basically i am getting confused in adding two chars and then converting into int, can you explain or give me a resource from where i can read this? •  » » » » » » 8 months ago, # ^ | ← Rev. 2 → 0 here co is cout<< char a='1',b='2'; co a+b<  » 8 months ago, # | ← Rev. 2 → 0 Hints for problems is such a great idea! I believe that hints+editorial is way better because some people may need just a bit of help to upsolve. Setters, please, make hints+editorial.  » 8 months ago, # | 0 In the editorial of D, I am unable to understand if we try to swap i-th and (i+1)-th piles, we should check, that we can remove stones from four piles: pi−1, ai+1, ai, si+2. If we can do this for any i, answer is YES. why?  » 8 months ago, # | 0 For question B Different Devisor I have checked that my solution is getting wrong answer for the test case d = 381 for which i have four factors {1,382,763,291466} where 382 = 381+1 , 763 = 382+381, 291466 = 763*382 so my answer is 291466 but the correct answer is showing 294527 but my answer is correct and is smaller than the given am I doing something wrong here ? why do you need prime factors why my answer is not correct ? •  » » 8 months ago, # ^ | 0 for the test case d = 381 for which I have four factors {1,382,763,291466} No, the actual divisors of$291466$are,$1, 2, 7, 14, 109, 191, 218, 382, 763, 1337, 1526, 2674, 20819, 41638, 145733, 291466$. why do you need prime factors why my answer is not correct? I explained it here.  » 8 months ago, # | 0 291466 satisfies for d = 381 for the second test case. Why do we have the real answer as 294527? @ IgorI  » 8 months ago, # | 0 https://codeforces.com/contest/1474/submission/105637453 Can someone help me with the question C as TLE is coming and i think it might work with my approach? So anyone could figure out how TLE is coming and what is my mistake??  » 8 months ago, # | 0 Can someone please explain problem C solution without set. Thanks.  » 7 months ago, # | ← Rev. 2 → 0 My$O(N^2)\$ java sol for problem C is getting TLE. But such similar solution of others getting passed. Can anyone tell why it's getting TLE. I thought a lot but unable to figure it out. Anyone please.
 » 7 months ago, # |   0 in problem b how did you figure out that the number that has 4 divisors is a porduct of two prime numbers??
 » 7 months ago, # |   0 For problem D,in case of no superability, why should we start from 0 ? why not from position n-1 ?
•  » » 6 months ago, # ^ |   -8 It's basically simulation so you can start from either 0 or n-1. It won't have any effect on answers.I used basically simulation to solve like first simulating my code from index 0 to index k upto where it is possible to do this simulation. and similarly used same concept from n-1 to index k upto which simulation is possible. Now for checking swapping we take 4 indexs i-1,i,i+1,i+2. Now I first check that is value at i-1 by forward simulation and i+2 by backward simulation is it possible. If Both are okk.. When no swapping is done a[i]-pf[i-1]==a[i+1]-sf[i+2] When swapping is done a[i]-sf[i+2]==a[i+1]-pf[i-1] Pf and sf arrays are simulations values which we get by continuously subtracting from left and right repectively.
•  » » » 6 months ago, # ^ |   -8 My submission:https://codeforces.com/contest/1474/submission/112208096
 » 7 months ago, # |   0 Are spoilers bugged or is it just me? I have checked in other browsers, yet I still cannot see the hints for B.
 » 5 months ago, # |   0 https://codeforces.com/problemset/submission/1474/113107284 can some one help i am getting TLE on 1474B.
 » 4 months ago, # |   0 Problem B shows tag of binary search. How to do it using Binary search??
 » 4 months ago, # |   0 in question B can't we do ans = (1+d)*(1+2*d)
 » 3 months ago, # |   0 I submitted a solution of problem C in which I had pre defined my debug macros then it gives me TLE but after removing the macro it get AC , but in some other problem when I submit the code with the predefined MACROS it gets ACCEPTED . Can anyone tell me why it is so ?