IgorI's blog

By IgorI, history, 2 weeks ago, Thank you for participation! Here is the editorial:

1621A - Stable Arrangement of Rooks

Editorial
Solution

1621B - Integers Shop

Editorial
Solution

1621C - Hidden Permutations

Editorial
Solution

1621D - The Winter Hike

Editorial
Solution

1621E - New School

Editorial
Solution

1621F - Strange Instructions

Editorial
Solution

1621G - Weighted Increasing Subsequences

Editorial
Solution

1621H - Trains and Airplanes

Editorial
Solution

1621I - Two Sequences

Editorial
Solution Tutorial of Hello 2022 Comments (170)
 » 2 weeks ago, # | ← Rev. 3 →   Hello, Fastest editorial of 2022 :)
•  » » You've achieved comedy
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   Also the slowest so far as of 2022
•  » » » Also my favorite contest of 2022
•  » » » » 2 weeks ago, # ^ | ← Rev. 2 →   Also The one where the tourist beats himself. SpoilerCongrats magic man!
•  » » » Funniest comment so far as of 2022
 » I hate problem B
•  » » I hate test case 1
•  » » » I hate pretest 2
•  » » » » I hate test case 3
•  » » » » » I have test case 4
•  » » Only B?
•  » » » After trying to solve it for 1.5 hours and submitting 5 almost correct solutions. I didn't had time to try any other problem.
•  » » » » sounds like a you problem.
•  » » » » » I don't think I ever said it's -is-this-fft-'s problem or writer's problem. I know it's my problem that I'm not good enough but that being said my comment was simply his reply to why the OP only disliked B (like me). So, I replied and I don't think my original comment in any way says it's anyone else's problem.
•  » » I do not understand at all what is wrong with problem B. After reading the reviews, I sat down and solved this problem in contest mode. She's great! There's a simple greedy idea in there. It is not another math puzzle. There is a place for a little coding in it.If you have difficulties with its implementation, it rather means that you need to write more code. I'm afraid this is one of the basic skills that you can learn from CP: to accurately and quickly implement simple logic. Do this in such a way as to minimize the number of special cases.The only minus of the problem is that it is a bit difficult for position B.I was lucky to solve it in without any debugging. And it's a nice feeling. My code#include using namespace std; #define forn(i, n) for (int i = 0; i < int(n); i++) int main() { ios_base::sync_with_stdio(false); cin.tie(0); int t; cin >> t; forn(tt, t) { int n; cin >> n; map L, R; map, int> LR; int gl = INT_MAX, gr = INT_MIN; forn(i, n) { int l, r, c; cin >> l >> r >> c; if (L.count(l)) L[l] = min(L[l], c); else L[l] = c; if (R.count(r)) R[r] = min(R[r], c); else R[r] = c; if (LR.count({l, r})) LR[{l, r}] = min(LR[{l, r}], c); else LR[{l, r}] = c; gl = min(gl, l); gr = max(gr, r); int result = L[gl] + R[gr]; if (LR.count({gl, gr})) result = min(result, LR[{gl, gr}]); cout << result << '\n'; } } }
•  » » » I guess what most of us meant was that, it is slightly more tougher than the usual Bs!
•  » » » This is brilliant! Seems like I need to develop a lot in implementing without any bugs. Thanks, Mike!
•  » » » That means sir you are using multiple codeforces accounts....:)
•  » » » Do you agree that hacking during div1 and div2 contests became obsolete after changing single test cases to packets of test cases? The amount of test cases increased and many corner cases are included. For example B and F could have smaller amount of pretests, then participants could search for incorrect solutions, and possibly that round would become no less interesting.How about splitting CF rounds (div1,div2 with uneven scores) into two variants: 1. Round without hacking (full tests) or hacking time 30 min.after solving time finishes, 2. Oldschool round: weaker pretests and hacking anytime (and possibly with novelty — progressive bounty for (un)successful hack).
•  » » » after taking input of l ,r ,c in condition if(L.count(l)) without assigning anything to map L .what does it means?
•  » » Can someone explain why my solution to B (141591638) is getting Runtime Error instead of WA (I'm not handling the case of using a single longest segment, but I don't see anything in my code that wouldn't work) ?
•  » » » NVM it's because 10^5 != 10000
•  » » ++
 » I was clicking the editorial in expectation that I will get to homepage (as editorial can be so fast) and get to know their standings but to my surprise editorial is there.
 » 2 weeks ago, # | ← Rev. 2 →   problems are good but im noob lol Happy new year!
•  » » How can you say that if you're noob.
 » 2 weeks ago, # | ← Rev. 2 →   Problem D was nice
 » How excellent the problem B is！
•  » » it was just simple implementation
•  » » » and i am just a simple pupil
•  » » » » and im just a simpleton.
•  » » » » oh,i am just a simple newbie
•  » » » Simple logic but implementation was little tricky !
 » B
 » I hate WA on pretest(2)
 » Can anyone help me with B ?
•  » » Keep track of three values: i) Lowest cost of range with lowest integer value till now ii) Lowest cost of range with highest integer value till now iii) Lowest cost of range with both lowest and highest integer value till now Then answer is min(i + ii, iii) if iii exists else it is simply i + ii
•  » » » Here is a simple implementation of the above approach:Link
•  » » » Why do we need to maintain (iii) if we are already maintaining (i) and (ii) won't it lead to an optimal solution?
•  » » » »  Example1 5 106 10 101 10 18iii keeps track of last one else we may need to take 10 + 10 
•  » » » » » wow, I never thought of that. Thanks for the help.
•  » » » Got it thanks
 » 2 weeks ago, # | ← Rev. 2 →   Small typo on tutorial for problem E : It can be easy done with prefix sum arrays. --> It can be easily done with prefix sum arrays.
 » Is there any chance you could include the model solutions for our reference? Links to submissions would suffice. Thanks
 » The solution for O (n) on python, problem B shows TL without the use of additional modules. Sorry for my English.
•  » » Use Fast I/O. I faced the same issue, but it worked when I switched to a better I/O method. (Note that we had to take lots of small inputs in this question, unlike usual problems where we take a few very long inputs. Hence, better I/O in Python is necessary, I guess.)
 » I'm curious how you found the solution for problem D? For me, I tried to analyze the problem but got nothing. But since I saw so many people pass this problem, I started to guess some random strategies and verify them manually. But this doesn't seem plausible, so I'm curious if there's some more plausible way to get the solution?
•  » » At first I thought that the solution is to find the shortest path (the one with least snow to clean) from any of the top left squares to any of the bottom right. But there was no way to move the people along it without cleaning one of the 8 cells. Got AC but wasn't able to prove it throughout the competition. The fact that so many people had the problem, made me think of an easier solutin, otherwise I probably wouldn't have solved it.
•  » » when I want to find a way to go from the left-top to right-bottom, I notice these 8 cells are special, because we cannot go to the right-bottom without passing one of them, after that, I found all friends can go to the right-bottom just using one of these cells.
 » For problem E, how do you compare averages : convert them to doubles or convert them to fractions (p and q) ?
•  » » Doubles have precision issues, so it's better to compare them as fractions. A general trick to do the comparison $a/b < c/d$, is to multiply both sides by $b \times d$ (assuming $b, d >0$). Then you get $a \times d < c \times b$. These numbers could be big, so use long longs.
•  » » You can even take ceil value of the division since it has to be greater than or equal to that
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   I use double and Coordinate Compression, so you can only care about intergers with maxval = O(n)
 » 2 weeks ago, # | ← Rev. 2 →   I just spent 1:30 minutes thinking the same and then used if elses for rest of time and WA2 for problem B.
 » In this contest, (and the previous one) I knew the solution (as far as it is covered by the editorial) to problem C after like ten minutes. And then was not able to implement it until end of contest.Now, the question is, isn't that implementation part the interesting one (at least in such problem), the one that should be covered by the editorial? I mean, this observation that there are cycles in a permutation is fairly trivial. I don't think that like 20k partitipants did not solved it because they did not had that idea.
•  » » C wasn't too bad to implement... 141526460
•  » » » Yes, I did inspect some solutions, looks like a three liner. Still there are a lot of partitipants not able to write down that (simple looking) lines of code. How is the process to come up with that? Which abstractions are usefull here, which are not?
•  » » » » 2 weeks ago, # ^ | ← Rev. 2 →   usually, when you can't implement a solution, it means that you don't actually (or deeply) understand the solution you have come up with :v 141527334 btw here is my implementation.
•  » » » » » 2 weeks ago, # ^ | ← Rev. 2 →   I think the difficulty with typical implementation problems is more likely to confuse things, and simple off-by-one errors. The solution is then to use the right abstractions in the thought process and to sort them cleanly.The solution "I have to see it, its simple!" did not work for me in this problem, and actually does not in general.Edit: However, congrats to reaching a new color!
•  » » » » » » UwU thank you
•  » » » » » Thanks for that implementation. I now understood it But why are you not printing cout.flush() after printing the query?
•  » » » » » » I think because endl does the job of printing '\n' as well as flushing the output.
•  » » » » » » » 141634306 and 141634429 why one get accepted and the other not
•  » » » » » » » » #define endl "\n"
•  » » » Yes C was pretty easy to implement as compared to B in my opinion.
•  » » Here is a simple implementation 141573460
 » Could you tell me what's wrong in my solution for task B? 141567260I tried to maintain 5 values: the leftmost number, cost of optimal line containing it, the rightmost number and cost of optimal line containing it, and the flag — are these lines same.
•  » » Input1 3 1 2 1 1 3 3 2 3 1 Expected Output1 3 2 Your Output1 3 3 CommentsWhen all the segments are available, you purchase $[1, 2]$ for a cost of 1, and $[2, 3]$ for a cost of 1.
•  » » » Ah, got it. Thank you!
 » worst ordering of questions
 » tourist's solution to E is so genius, even cleaner than the editorial.Just throw everything into a segtree then forget about casework.
 » In problem D, it took me about 30 minutes just to prove the following case doesn't exist :(
•  » » I didnt realize this until now xD
•  » » I am also thinking about the same case. can you pls provide your proof.
•  » » » lets see on 4 points (1,1),(1,n),(n,1),(n,n) when first of them moved one of them will go to one of 8 points mentioned in solution.
•  » » » 2 weeks ago, # ^ | ← Rev. 5 → Say, you want to take this path. This will result in Now, you want others to follow the same path for which you'll either do a column up or down, so that the element is placed on the same row (So that same path can be followed). This can be done on any column, either up or down. The problem is that, one element moves out of the first n*n square, and takes another path (B) So, the answer becomes Cost(A)+Cost(B) (for now). It will add up even more if you do the same with other columns. But, you can accomplish the same thing with only Path B too. So, that becomes the minimum cost path ( Cost(A)+Cost(B) > Cost(B) ). This way, all eight corners can be proved.PS. Sorry if this didn't explain the problem
•  » » I only realized this in the last 2 minutes of the contest. Also couldn't implement C on time. :(
 » 2 weeks ago, # | ← Rev. 3 →   Could you PLEASE show the solution(code) for B? Have been trying to solve it for hours...
•  » » Thank you so much!
 » Can anybody show the solution for problem a in java? I don't know why mine is wrong. I used prettt much the same logic in the editorial
•  » » I don't know if anything else is wrong in your code but the first mistake i noticed is that you are taking k and n instead of n and k.
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   Yes.. k for the size of board and n for the rooks. Btw thank you for the reply.. I forgot to put the continue; after 2nd if.. jsbsvajnfnn.. but i hope that's not the only error or else i wont sleep tonight.
•  » » » » 2 weeks ago, # ^ | ← Rev. 2 →   Here is the edited code 141579198 I just deleted the k==1&&n==1 and n==1 case as it was redundant
•  » » » » » Thank you so much brothers. Bless you
 » Can anyone please tell me the 94th test case for test 2 in problem B?
 » I literally got the exact solution described in the editorial for B and got WA on 2. What was B?
 » Can someone point out my mistake on B? 141546457
 » 2 weeks ago, # | ← Rev. 2 →   I liked C — interactive problems without binary search have become extinct nowadays. My solution is very short and the problem involved reasonable amount of thinking.On the other side, D is not a great problem. I couldn't come up with the solution during the contest (or, to be correct, I came up with it, but it seemed to me totally wrong). However, the problem is ad-hoc and it is not very beautiful.E was merely an implementation task. I think it's rather good problem. The detail about $m \le n$ (not $m = n$) was unexpected and confusing, though.How do you calculate the number of increasing subsequences that starts in $a_i$ and ends in $a_{x_{y'}}$ in G? For me, it was the most difficult thing in it. Am I missing something? We have $O(n)$ different start points ($a_i$) and also $O(n)$ different end points ($a_{x_{y'}}$) and how we calculate all the numbers fast?
•  » » In G, fix the end point, and calculate the answer for all the starting point that corresponds to the current end point. We can just store the updates done to fenwick for current endpoint and undo them in the end.
•  » » » Ah, thanks a lot! I was missing the moment that no value (no $a_i$) can correspond to different endpoints. I thought it is somehow possible, so we need to consider $O(n)$ values for every endpoint. But actually it is $O(n)$ in summary :)
•  » » How can you think that tasks where you just need to implement trivial idea are good, but tasks where you actually need to think — are bad. Do you think cp should become fast-typing competition?
•  » » » Yes, indeed it sounds strange. No, I don't think so. Competitive programming is solving problems and afterwards coding them. I don't like the problems that omit one or another part. The problem 1375C - Element Extermination is great example of creating a problem that involves pretty much thinking while the correct solution is so simple, that you can't believe in it. Well, to be objective, it is just simple. I am pretty sure that the majority of the participants, who solved it, just guessed the answer. I was one of them (the contest was about to end and I just had different tries). The process of solving the problem didn't get me much joy. I haven't solved the problem D from Hello 2022, but I think the problems are really similiar. The only difference is that it's harder to guess the answer in the problem you were talking about, while one-liner for 1375C - Element Extermination makes it somehow beautiful, while easier to guess the answer. (It is my personal opinion, I am not certain, what is more beautiful or more evident).The proportion (thinking : coding) is really unjust in such problems. You make some complicated thought process and afterwards submit quite easy code. The problem would look much better not here, on CF, but on some mathematical contest. Of course, with proof required.On the other side, in the E problem the proportion (thinking : coding) was the opposite. The implementation part was huge, and because of that I named it implementation task. However I don't think it was stupid straightforward implementation. The problem required some observations: {you can't dynamically move elements in the set and compare all of them to corresponding values in given array. However, here all the values move at most one position to the right, or one to the left. It wasn't obvious for me, while it wasn't difficult too}. It required some data structure to achieve 'range logical AND of boolean array' (prefix sums). Probably, it is too weak for global round E. Well, it may be too standard. However, I managed to mess up something in binary search (it was really disappointing), so it's not only about fingers speed, but also about correctly implementing the solution. Here coding mattered more than thinking, but I believe the proportion was fine.
•  » » » » you can't dynamically move elements in the set and compare all of them to corresponding values in a given array $\pm 1$ shift observation lets you do prefix sum-style solution, but it was not necessary to make it. As long as the array $b$ is split into a constant number of parts one may apply a certain rmq-like structure with a log overhead.Specifically, for all segments $b[l..l+2^k)$ we can precompute the leftmost position $i$ such that $a_{i + j} \ge b_{l + j}$ for all $j \in [0, 2^k)$. Then we can compute the same position for any segment of $b$ with log overhead.
•  » » » » » imo 141620052 is just plain implementation, underwhelming.
•  » » » » » Very cool trick!
 » 2 weeks ago, # | ← Rev. 6 →   Alternative solution for 1621E - New SchoolIf you fix the student to remove, you can check if the answer is 1 with the following algorithm: Keep a multiset of teachers, for each group of students assign them the teacher with the minimum value $\geq$ to the average of the group and remove the teacher from the multiset. The answer is 1 if there is always an available teacher. The key observation is that the algorithm works for any order of the groups of students. So, if you want to check the answer for all the students of a group, you can insert the other groups first, then try to remove each student from that group.Now, we want to solve this problem: For each group, find the result of the algorithm if you consider all the groups except that one. This can be solved in $O(n \log^2 n)$ with D&C (similar to offline deletion). The D&C looks like solve(l, r) { // for each i in [l, r], find answer if you remove group i if (l == r) { // you've inserted all groups except l, so you can check students of group l check(l); return; } m = (l + r) / 2; insert(m + 1, r); // assign a teacher to groups in [m + 1, r] solve(l, m); rollback(m + 1, r); // undo the assignments insert(l, m); solve(m + 1, r); rollback(l, m); } Implementation: 141541065
 » 2 weeks ago, # | ← Rev. 2 →   can anyone tell me what is wrong with my solution for task B??141576250update: I got my mistake
•  » » Can you please tell me a testcase where your code was wrong?
•  » » » 2 weeks ago, # ^ | ← Rev. 2 →   test case1 3 1 10 7 1 4 3 6 10 5 output should be : 7 7 7my code was not working on this test case, so I keep track of maxLen as also mentioned in the editorial.
 » Is the answer to the bonus part of A: $\binom{n-k+1}{k}^2$ ?Basically, there are $\binom{n-k+1}{k}$ ways to choose the rows containing a rook, and $\binom{n-k+1}{k}$ ways to choose the columns containing a rook, independently, such that the arrangement is stable.
•  » » Close, but there are $k!$ ways to arrange the rook given the column and rows.
 » Problem B goes to show many people are brick at implementation.
 » In Problem C, is there any specific theorem of any kind or its just based on observation??
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   "permutation the way it is presented here , exists as a set of disjoint cycles"-> something which is useful here picked from Abstract Algebra
•  » » » Ok, thanks.
 » 2 weeks ago, # | ← Rev. 3 →   I undertand it, pass me!why Problem D can't acts like the following e.gfor simplify e.g, set i = 10e9 4 0 0 0 0 i i i i 0 0 0 0 i i i i 0 0 0 0 i i i i 0 0 0 0 i i i i i i i i 2 0 2 2 i i i i 1 6 2 1 i i 3 4 2 4 7 4 i i 2 i 2 0 1 6 in this case, I think friends can move by (8, 3) -> (7, 3) -> (7, 4)did I ignore something?
•  » » You ignored that one of the friends in the four corners must moved one cell out of the upper left quarter. There is simply no way to move them at all without doing this.
•  » » » thank you
 » Can someone tell me the meaning or compiler error message?wrong answer Token parameter [name=grid] equals to "R", doesn't correspond to pattern "-1|[.R]{3}" (test case 1)Why my pretest 1 was not passing in spite of doing everything correctly ??Problem A — My sub-link - https://codeforces.cc/contest/1621/submission/141523368
•  » » Here You go -->You were using spaces while printing
•  » » » Thanks Bro !!!!
 » So, I think that problem B can’t be on position B
 » B was a hell
 » Why does solution to E work in time?We check the removal of each of the 1e5 students. Foreach one its group will move some positions (i to j). We recheck all groups in range (i,j). i,j is not bounded, the dist can be also 1e5.So how is this not O(n^2)?
•  » » It can be easy done with prefix sum arrays.
 » Can anybody tell me where 141564677 for problem B is wrong?
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   1 4 1 100 50 1 10 20 40 50 20 1 5 5 Sorry, your code is working perfectly fine in this testcase. I evaluated it wrong. Even my submission is giving the same expected answer. We need some other testcase!
•  » » » 50 50 50 50
 » 2 weeks ago, # | ← Rev. 3 →   Need help in finding a test case where my code fails for Problem B! Link to my submission
•  » » Can you tell what was the problem as I seemed to have same problem
•  » » » I thought I had a counter example. But I evaluated it wrong. My code is working perfectly fine in it. We still need help from someone!
 » 2 weeks ago, # | ← Rev. 2 →   Here's a more complex but IMO more intuitive solution to E, which I believe was used by a lot of other participants in contest. It's possible to assign teachers to groups if for every value v, there are more or equal teachers of age at least v compared to groups with average age of at least v. It's easy to see that this is equivalent to the original condition.Let diff[i] be the (number of teachers with age >= v — number of groups with average age >= v). Then, the condition means for all i = 1...1e5, diff[i] >= 0, or min(diff[i]) for all i = 1...1e5 >= 0.It's easy to see adding a teacher of age v will add diff[v], diff[v + 1], ..., diff[1e5] by 1, and a group with their rounded up average v will reduce diff[v], diff[v + 1], ..., diff[1e5] by -1. With this, the problem becomes a straightforward lazy segment tree problem: we add all teachers, then add all groups, when we remove a member of a group we temporarily change it's average, and then change it back. All in all, it uses about n + 4 * m segment tree operations, which is far fast enough to AC.
•  » » Nice approach! But shouldn't the condition be min(diff[i]) for all i from 1...1e5 >= 0?
•  » » » Thanks for pointing that out. That was written in not the best of mental conditions.
•  » » Alternatively, instead of using a lazy segment tree, you can use an ordinary segment tree which stores the sum and the minimum suffix sum in each node.
•  » » » I don't understand can you explain your idea bit more.
•  » » » » (adding a teacher/group should actually add 1/-1 to diff[1..v], not diff[v..1e5] in the original solution)Let a[i]=diff[i]-diff[i+1]. Then what adding 1/-1 to diff[1..v] does is adding 1/-1 to a[v]. You can get the diff array from the a array by noticing that diff is just the suffix sum of a. So, when you're looking for the minimum value in diff, you're looking for the minimum suffix sum in a, which a segment tree can easily handle.
 » Video Editorial for Problem B: Integers ShopI use 3 pair data structures, instead of 6 variables as mentioned in the editorial, in order to reduce the length of the code and make it easier to understand.
 » 2 weeks ago, # | ← Rev. 3 →   Thanks for the editorial.
 » Can someone please explain how to solve problem C? I am having difficulties understanding the tutorial. Thanks!
 » You can do problem I in $O(n \log \log n)$ time (linear time per op)! Code: 141611373We need 3 additional observations. First, we rephrase the copy operation into something a little simpler. Then, we complete the analysis of part 3 of the editorial to find a closed form for whether the the smallest subarray starts at $c_l$ or $c_k$. Finally, we show a linear time algorithm for finding the lexicographically smallest suffix of each prefix based on Duval's algorithm for Lyndon factorization.The copy operationFirst, let's rephrase the copy operation. If, in the $i$th operation, we find the smallest substring of length at least $i$ starts at index $j \le n-i$, then $D_{i} = (D_{i-1}[1:n-i] + D_{i-1}[j:n])[1:n] = (D_{i-1}[1:n-i] + D_{i-1}[j:n-i] + D_{i-1}[n-i+1:n])[1:n]$ (here, we use inclusive substrings). In other words, we insert the string $D_{i-1}[j:n-i]$ (which is a possibly-empty suffix of $D_{i-1}[1:n-i]$) directly after the $n-i$th character, and then we truncate the result to the first $n$ characters. Then, there are a few useful observations: Picking the smallest substring is equivalent to picking the possibly-empty suffix $D_{i-1}[j:n-i]$ of $D_{i-1}[1:n-i]$ (with $j \le n-i$) that minimizes the result $D_{i-1}[j:n-i] + D_{i-1}[n-i+1:n]$. Furthermore, note that $D_{i-1}[1:n-i]$ has not been modified before this step, so this is equivalent to $D_0[1:n-i]$. With this definition, it's easy to see that we don't actually need to truncate the $D_i$ to the first $n$ characters; it's fine to let them grow. We can reindex slightly so that $D_i = D_{i-1}[1:n-i] + D_{i-1}[j:n-i+1] + D_{i-1}[n-i+2:n]$. In this formulation, we need to pick a nonempty suffix $D_{i-1}[j:n-i+1]$ of $D_{i-1}[1:n-i+1]$ to replace $D_{i-1}[n-i+1]$ so the result is minimized. Once again, $D_{i-1}[1:n-i+1] = D_0[1:n-i+1]$. From here on, let $A_i$ denote the suffix of $D_0[1:n-i]$ we inserted in the $i$th step, and let $B_i$ denote the suffix of $D_0[1:n-i+1]$ which we substituted for $D_{i-1}[n-i+1]$, so that $B_i = A_i + D_0[n-i+1]$. Part 3 of the editorial showed that $B_i$ is either the minimum suffix of $D_0[1:n-i+1]$, of it's the maximum number of copies of the minimum suffix. We make a few more observations: Because of the replacement scheme, our final result is $D_n = (B_n + B_{n-1} + \cdots + B_2 + B_1)[1:n]$. Thus, it suffices to find the $B_i$. We can consider 2 consecutive steps at once with our 2 indexing ways: $D_{i+1} = D_{i-1}[1:n-i] + B_{i+1} + A_{i} + D_{i-1}[n-i+1:n]$, where $A_{i}$ is a possibly empty suffix of $D_0[1:n-i]$ and $B_{i+1}$ is a nonempty suffix of $D_0[1:n-i]$ chosen to minimize the result $B_{i+1}+A_{i}+D_{i-1}[n-i+1:n]$. This is convenient because $B_{i+1}$ and $A_{i}$ are both (almost) minimal suffixes of the same string! Closed form for which suffixNow, using the last observation, we can classify whether $B_{i+1}$ starts at $c_l$ (the minimum suffix of $D_0[1:n-i]$) versus $c_k$ (the maximum number of copies of the minimum suffix of $D_0[1:n-i]$): $B_{i+1}$ starts at $c_l$ if $A_i$ is empty, and $c_k$ otherwise. Note that $A_i$ is empty iff $B_i$ has length $1$.The proof of this is pretty similar to the analysis in part 3 of the editorial. Let $S$ be the minimum suffix of $D_0[1:n-i]$, and let $E = D_{i-1}[n-i+1:n]$. Then, either $A_i$ is empty, or $A_i$ starts with $S$, and $B_{i+1} = S$ or $B_{i+1} = S^l$ for some $l$ (this denotes $S$ repeated $l$ times). Then, note that $A_i + E < S + A_i + E$ iff $S + A_i + E < S^2 + A_i + E$ iff $S^2 + A_i + E < S^3 + A_i + E$ and so on, so we should take $B_{i+1} = S$ iff $S + A_i + E < S^l + A_i + E$ iff $A_i + E < S + A_i + E$.Now, because $A_i$ is optimal on the $i$th step, we must have $A_i + E < P + E$ for any other prefix $P$ of $D_0[1:n-i]$. In particular, if $A_i$ is empty, then $A_i + E < S + E = S + A_i + E$, so we should take $B_{i+1} = S$. Otherwise, $A_i$ starts with $S$, so $A_i + E < A_i[len(S)+1:] + E \implies S + A_i + E < A_i + E$, so we should take $B_{i+1}=S^l$.Thus, we've proven that $B_{i+1}$ is the minimum suffix exactly when $B_{i}$ has length $1$.Fast algorithm for min suffixFinally, we sketch a linear time algorithm to find the minimum suffix of each prefix of $D_0$ (and the max number of copies).Note that the minimum suffix of a string $S$ is exactly the final Lyndon word in the Lyndon factorization of $S$. Furthermore, the maximum number of copies is the number of equal Lyndon words at the end of the factorization of $S$. (This is pretty trivial/uninteresting statement, but it's useful terminology/framing.)We can find both using an algorithm similar to Duval's algorithm for Lyndon factorization (emaxx writeup), which is itself similar to KMP. I'll refer to terms from the writeup, so please read that first. In essence, we build the KMP failure function to compare the string to its suffixes, but if the suffix is smaller than the whole string, then the suffix is part of a later Lyndon word, so we can cut off and output some prefixes as a maximal Lyndon word.In this case, we need to modify it slightly. Duval's algorithm is already almost online, so we're pretty close being able to find the Lyndon factorization of every prefix. First, we'll modify it to be a little more online and less amortized: in the case where our next character is small and we want to cut a pre-simple string $ww\ldots w\overline{w}$ down to $\overline{w}$, the algorithm typically resets the state all the way back to an empty string and reprocesses $\overline{w}$. Instead, note that $\overline{w}$ is a prefix of $w$, so we can just store our current pre-simple string in a stack and pop all the way down to $\overline{w}$. (This adds linear memory, which is why it's probably not used in normal Duval's).Now, to find the "tail" of the Lyndon factorization of a prefix, we need to process up to that prefix, and then append a terminator with value $-\infty$. Note that this will cause a series of cuts from $ww\ldots w\overline{w}$ to $\overline{w}$, each of which jumps back to some smaller stack size. The last cut we do is the tail of identical strings in the Lyndon factorization. Thus, we can just precompute the final cut starting at each location: it's just the final cut of the location you would jump to.Thus, we have a linear time algorithm for finding all minimum suffixes of each prefix of $D_0$.
 » 2 weeks ago, # | ← Rev. 2 →   https://codeforces.cc/contest/1621/submission/141560289 Can anyone help me out what i might be missing in B's Implementation Update: Resolved
 » I think that Problem E has a serious problem: Nobody has the age of 1e5
 » can someone please explain problem 'c' in detail i am unable go through the editorial ? are there are any prerequisite for that question ?
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   i have done like this(but after the contest). we can consider p array as directed graph. eg if p=[4,2,1,3] then the graph will be like this https://ibb.co/sJZ4tM2 now there are 2 type of edges, one is self loop. other is cycle. now what i do is, for every i in [1,n], i ask for the value at that index if i dont know p[i]. for every i, i ask multiple times, if corresponding values are equal, then it is a self loop and p[i]=i; else i ask q[i] until i see the complete cycle, lets say q1=a and q2=b, then p[q1]=q2.here is my code: https://codeforces.cc/contest/1621/submission/141614438
•  » » » thanks! with an example i was able to see that elements present in a cycle simply exchange their positions as if they are in cycle . Can any explanation be provided about why this is happening ?
 » My solution for B is similar to editorial but getting wrong answer at Test Case 2. Can someone help me here? Link to solution — here
 » 2 weeks ago, # | ← Rev. 3 →   Hi everyone, can anyone provide me a edge case for my code for problem C? CODE Thank You. My implementation has same logic as the editorial has but I'm not able to find why I'm failing at test 2 subtest 34.
•  » » please check for permutation "1, 2, 3, 4, 5"?
 » The problem statement for B was pretty confusing to be honest.
 » If you are looking for video solutions, HERE they are(for A-D)
 » what is wrong in this implementation for problem B. I tried to implement the same logic as is given in the editorial but could not get it right? void solve() { int n; cin >> n; pair arr[n]; int cost[n]; for (int i = 0; i < n; i++) { cin >> arr[i].first >> arr[i].second >> cost[i]; } int mi = 0, ma = 0, len = 0, costlen = 1e9 + 1; // mi for min index. // ma for max index. // len for max length. // costlen for cost of max length. cout << cost << endl; for (int i = 1; i < n; i++) { if (arr[i].first < arr[mi].first) { mi = i; } if (arr[i].second > arr[ma].second) { ma = i; } if (arr[i].first == arr[mi].first && cost[i] < cost[mi]) { mi = i; } if (arr[i].second == arr[ma].second && cost[i] < cost[ma]) { ma = i; } if (len < arr[i].second - arr[i].first + 1) { len = arr[i].second - arr[i].first + 1; costlen = 1e9 + 1; } if (len == arr[i].second - arr[i].first + 1) { costlen = min(costlen, cost[i]); } if (len == arr[ma].second - arr[mi].first + 1) { cout << min(cost[mi] + cost[ma], costlen) << endl; } else cout << cost[mi] + cost[ma] << endl; }}int main() { int t = 1; cin >> t; while (t--) solve(); }
 » Can someone tell me what I am doing wrong with the https://codeforces.cc/contest/1621/submission/141567369 submission for problem B.
 » Here's another (more systematic) way to arrive at what you want to compute in G. Let $X_i$ be the indicator variable such that $X_i = 1$ if and only if $i$ (by index) is included in an increasing sequence and there exists $x$ such that $a_x > a_i$ and $x$ is past the end of the sequence. If $tot$ is the number of total increasing sequences of the array, we are interested in computing $tot \cdot E[X_1 + \cdots + X_n]$ by definition.Let's focus on the $E$ term. By linearity, this collapses to $E[X_1] + \cdots + E[X_n]$. Note since $X_i$ are all indicator variables, $E[X_i] = P(X_i)$. Let $lst_i$ be the largest index such that $a_{lst_i} > a_i$ (similar to editorial). Then, $P(X_i) = P(i \ \text{is included}) \cdot P(\text{the sequence including} \ i \ \text{ends before} \ lst_i).$ $= P(i \ \text{is included}) \cdot (1 - P(\text{the sequence including} \ i \ \text{includes } \ lst_i)).$If $$tot_i$ denotes the total number of sequences including $a_i$, and $tot_{il}$ is the number of sequences including $i$ and $lst_i$ then this value is just $P(X_i) = \frac{tot_i}{tot} \cdot (1 - \frac{tot_{il}}{tot_i}) = \frac{tot_i - tot_{il}}{tot}.$Proceed as mentioned in the editorial to find$ $tot_i$ and $tot_{il}$, and don't forget to multiply the entire sum by $tot$.Here's my implementation (a bit messy). This idea of assigning indicator variables to compute what we want works on a lot of mathy problems like these, especially on AtCoder. Also, excuse the wonky latex (was being annoying when typing this up).
 » 2 weeks ago, # | ← Rev. 2 →   I solved problem B using priority queue (i.e, heap) in O(n*logn). Added comments for easy understanding. Have a look!! :)I wasn't able to solve it in live contest as I could not think of the third point mentioned in the editorial of the problem. (i, e, The length of the longest segment and the cost of the cheapest of such segments.)Link to solution
 » 2 weeks ago, # | ← Rev. 2 →   The proof in $D$ may not be convincing much as we still can move the columns $[1, N]$ one by one through the $2^{nd}$ column for example. Although will not be able to complete the solution, this does not pass through the mentioned $8$ points in the first operations.Another proof that we must always pass by at least one of the mentioned $8$ points:For the points $(n+1, n+1)$, $(n+1, 2n)$, $(2n, n+1)$, and $(2n, 2n)$ to be filled, they have to be filled from the bottom-right corner itself, as any filling from the other $3$ corners would pass through one of the mentioned $8$ points. Now let's try to fill one of the $4$ points, we will notice that any shifting in the bottom-right corner to fill one of those $4$ points will result in emptying another one of them, and this will just go indefinitely.EDIT: It seems that the editorial's proof is complete as well. We can never make a first move with a row/column having one of the $4$ points $(1, 1)$, $(1, n)$, $(n, 1)$, or $(n, n)$ without moving another one of them to one of the $8$ mentioned points.
 » Can anybody please tell me what's wrong with my solution for problem C? :( code-attempt-wa-testcase2
 » Can anybody help me to find out where my solution to B (using ordered set) is failing in test 2? I tried many random generated small test cases with correct output. Didn't able to find any failure test case. :( https://codeforces.cc/contest/1621/submission/141576936
•  » » 13 days ago, # ^ | ← Rev. 2 →   I didn't look into your code too much, but I found a testcase for which your code gives WA testcase14 1 2 3 4 5 2 1 5 4 1 5 3 expected output3 5 4 3
 » Can someone please help me figure out a test case on which my code will fail for problem B. 141637071
•  » » Hey bro thanks a lot for providing them.
 » Some hints for people stuck at debugging problems B and C (as per the comments above).avkonyahin Input1 3 1 1 1 2 3 1 1 3 1 Expected Output1 2 1 Your Output1 2 2 CommentsWhen all the segments are available, you can purchase $[1, 3]$ for cost of 1.practice_52 Input1 3 2 3 2 1 3 3 1 2 2 Expected Output2 3 3 Your Output2 3 4 CommentsWhen all the segments are available, you can purchase $[1, 3]$ for cost of 3.pks18 Input1 3 1 1 2 2 3 3 1 3 3 Expected Output2 5 3 Your Output2 5 5 CommentsWhen all the segments are available, you can purchase $[1, 3]$ for cost of 3.Abhishek357 Input1 3 1 1 2 2 3 3 1 3 3 Expected Output2 5 3 Your Output2 5 5 CommentsWhen all the segments are available, you can purchase $[1, 3]$ for cost of 3.Mysticode Input1 3 1 2 1 1 3 3 2 3 1 Expected Output1 3 2 Your Output1 3 3 CommentsWhen all the segments are available, you purchase $[1, 2]$ for a cost of 1, and $[2, 3]$ for a cost of 1._s_h_n_ Input1 3 2 3 2 1 3 3 1 2 2 Expected Output2 3 3 Your Output2 3 4 CommentsWhen all the segments are available, you can purchase $[1, 3]$ for cost of 3.AnestheticCoder Input1 2 1 2 1 1 2 2 Expected Output1 1 Your Output1 2 CommentsWhen all the segments are available, you can purchase $[1, 2]$ for a cost of 1.Blinding_Lights Participant-Jury InteractionJury printed the number of test cases as: 1Jury is processing testcase: 1Jury printed the permutation length as: 5 Jury picked the initial permutation as: 1 2 3 5 4 Participant asked for the element at index 1 Jury responded with 1 The permutation Q has now become: 1 2 3 5 4 Participant asked for the element at index 1 Jury responded with 1 The permutation Q has now become: 1 2 3 4 5 Participant asked for the element at index 1 Jury responded with 1 The permutation Q has now become: 1 2 3 5 4 Participant asked for the element at index 2 Jury responded with 2 The permutation Q has now become: 1 2 3 4 5 Participant asked for the element at index 2 Jury responded with 2 The permutation Q has now become: 1 2 3 5 4 Participant asked for the element at index 2 Jury responded with 2 The permutation Q has now become: 1 2 3 4 5 Participant asked for the element at index 3 Jury responded with 3 The permutation Q has now become: 1 2 3 5 4 Participant asked for the element at index 3 Jury responded with 3 The permutation Q has now become: 1 2 3 4 5 Participant asked for the element at index 3 Jury responded with 3 The permutation Q has now become: 1 2 3 5 4 Participant asked for the element at index 4 Jury responded with 5 The permutation Q has now become: 1 2 3 4 5 Participant has exhausted their query quota
•  » » Thanks a lot for providing that testcase. I was trying for hours. Thank you! :)
•  » » Thank you so much variety-jones!!! I finally got AC on B because of you! <3
•  » » Thank you so much for providing the testcase and telling what's wrong. This problem had me stuck. Thanks a lot!
•  » » Thankyou so much!!!!
•  » » Thanks a lot!
 » Hey i am new here, can anyone explain why k>[n/2] is written as k > (n+1)/2 ?
•  » » It is basically telling that ceil(n / 2) = floor(n + 1 / 2) Intuition If n = even, for any non negative i, n = 2i, ceil(n / 2) = floor(n + 1 / 2) = floor((2i + 1) / 2) = floor(i + 0.5) = i If n = odd, for any non negative i, n = 2i + 1, ceil(n / 2) = floor(n + 1 / 2) = floor((2i + 2) / 2) = floor(i + 1) = i + 1
 » 13 days ago, # | ← Rev. 2 →   Alternative solution to G:If $a_{x}$ affects the weight of a subsequence $a_{i_1},...,a_{i_k}$, then this subsequence doesn't maximize the value of $i_{k}$ across all increasing subsequence containing $a_{x}$. We can also see that the latter implies the former.So if we can count the number of increasing subsequence starting in $a_i$ and maximize the position of the rightmost element, we can solve the problem. It turns out that it is possible in $O(n log n)$ using segment tree.Implementation
 » 13 days ago, # | ← Rev. 2 →   Could you please tell me, why my code for problem B (Integer Shop) is wrong. Here is the implementation 141707198Thanks in advance!![Edit: Resolved]
 » I have an interesting idea in problem C:When the change $q_{i}'=q_{p_i}$ turn into $q_i'=q_{q_i}$ ,How to solve the problem?PS: It's also the mistake I made in the contest
•  » » if q is not 1,2,3,4... initially and it is P then the same idea seems to work
 » Hi — I'm pretty sure I have a solution to problem E but i'm not sure it works, and I do not want to implement it right now. Maybe someone could read the following and comment.After sorting as in the editorial (in decreasing order), we first check if before removing anyone, it's possible to start lessons. If yes, the only way to make the lessons not possible is to remove a student with a lower value than the average of his group, which will make the average larger and move that group to the left in the sorted array. Then either that group itself is larger than teacher, or one of the shifted (shifted to the right) groups are larger than the corresponding teacher. Since each group can only move 1 index to the right, we will denote an index as bad if when moved one to the right, it will be bigger than the teacher. Suppose I remove a student and group is moved from index 9 to index 3, the only question is — is there a bad index between 3 and 8? And that's a very easy thing to answer, all you have to do is save the closest bad index to the left of each index. if the closest bad index to 9 is for example 7, then we know there is a bad index between 3 and 8. If the closest bad index to the left is 2, we know there isn't. If no, it's simpler. Look at the set of all indices violating the conditions of being smaller than their teacher. If there is an index in the set such that moving it to the left doesn't fix the condition, it's never possible. Assuming that moving each of them one index to the left fixes the condition, the only way to make the lessons possible, is to move the entire set of these indices one index to the left. Note it's enough to look at the min and max of that set. Say the set includes 3,6,8,11. Then you just need to make sure to move the segment [3,11] to the left, and you fixed the condition (assuming of course that the moved group doesn't ruin it itself). So you just have to go over the groups 0,1,2 (i.e. the ones less than the minimum in the set), and see if removing a student moves the group to an index >= 11. Of course some details are missing, but that's pretty much it. Thinking about it — it might've been faster coding it than describing it ^_^.
 » can anyone have 1621A Bonus Solution?
 » Thanks for the editorial mate :)
 » 9 days ago, # | ← Rev. 2 →   Solution This solution to problem E is failing against second test case, there is only on bit different , tried a lot, please help me out , thanks in advance