By Vladosiya, history, 15 months ago, translation, 1650A - Deletions of Two Adjacent Letters

Idea: MikeMirzayanov

Tutorial
Solution

1650B - DIV + MOD

Tutorial
Solution

1650C - Weight of the System of Nested Segments

Idea: myav

Tutorial
Solution

1650D - Twist the Permutation

Idea: MikeMirzayanov

Tutorial
Solution

1650E - Rescheduling the Exam

Idea: DmitriyOwlet

Tutorial
Solution

1650F - Vitaly and Advanced Useless Algorithms

Idea: Aris

Tutorial
Solution

1650G - Counting Shortcuts

Idea: MikeMirzayanov

Tutorial
Solution Tutorial of Codeforces Round 776 (Div. 3) Comments (49)
| Write comment?
 » 15 months ago, # | ← Rev. 2 →   Thank you codeforces for this contest!
 » my solution for problem D using deque: https://codeforces.com/contest/1650/submission/148940490 I think it's easier, if you know data structure.
•  » » Yeah+
•  » » 15 months ago, # ^ | ← Rev. 2 →   please explain your solution
•  » » » First, The problem is he performed n operations sequentially. At the i-th operation, Petya chose the first i elements of the array and cyclically shifted them to the right number of times.we have the final array ! and before operations we know that the array is sorted so how can we do this operations reversely to sort the array ? _we will start from n instead of 1 _and shift left instead of shift rightfirst we want to make the last number in the array equal n , how many times of shift left we can do to make that ? just loop make shiftes untill it happen and then now we will search for n-1 to put it in position n-1 in the array so to make the same thing easier we will remove n from the array, we won't need it again.
•  » » » » Dude you are amazing!
•  » » » » » It's a her btw.
•  » » » » » » dude is a universal term
•  » » » » » » » so straight men sleep with dudes?
•  » » Thank you!
•  » » » You're welcome :)
•  » » » » I love you!
•  » » » » » hh
•  » » Amazing solution !
 » 15 months ago, # | ← Rev. 3 →   E has an answer binary search.
 » If you are/were getting a WA/RE verdict on problems from this contest, you can get a small counter example for your submission on cfstress.com. To do that, click on the relevant problem's link below, add your submission ID, and edit the table to increase/decrease the constraints. If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.
•  » » Thanks, Was really helpful
 » 15 months ago, # | ← Rev. 3 →   Ok
•  » » 15 months ago, # ^ | ← Rev. 2 →   Ok
•  » » » You don't have to Build SegTree for this problem bro! It can be solved very easy))
 » 15 months ago, # | ← Rev. 3 →   Resolved
 » in the following statementnumbers from r−rmoda to r that have an incomplete quotient when divided by a equal to ⌊r/a⌋1) can someone expain me the meaning of the incomplete quotient(does it mean that it will give remainder?)2) How did we arrive at this conclusion?
•  » » Can anyone plese explain this.
•  » » » I find the editorial difficult to understand. Here is my way of explaining a solution to problem B:Imagine a 5x7 monthly calendar where the rows represent work week and the columns represent Sunday, Monday, ... to Saturday. Suppose the upper left hand corner of the has the day start with 0. So, the first row are days 0 ~ 6, second row are days 7 ~ 13, and so on. Day / 7 represents the work week, the row on the calendar. Day % 7 represents the week day (Sunday=0, ..., Saturday=6), the column on the calendar. Suppose the question is to ask you which day from L (eg 20) to R (eg 29) has the Manhattan distance largest from the origin of the calendar. My approach is to check if the L and R are on the same row. If so, then R is the answer. Otherwise, I tried to move R to the closest Saturday on the previous row. Hope you get what I mean.
•  » » » 15 months ago, # ^ | ← Rev. 2 →   We want to prove that for every number $x$ in range $[r - r \ mod \ a; r] \ x \ mod \ a \le r \ mod \ a$; $r - r \ mod \ a$ is divided by $a$, because $r = a \cdot r \ div \ a \ + r \ mod \ a$, it means $r - r \ mod \ a = a \cdot r \ div \ a$, and $a$ multiply something always is divided by $a$. OK, we know that $r - r \ mod \ a$ is divided by $a$ and every number in range $[r - r \ mod \ a + 1; r]$ is not divided by $a$. That means every $x$ from range $[r - r \mod \ a + 1; r]$ has incomplete quotient $\lfloor\frac{r}{a}\rfloor$. For example, $r = 11$, $a = 4$. $11 - 11 \ mod \ 4$ = $8$. $8$ is divided by $4$ and every num in range $[8 + 1; 11]$ is not divided by $4$. $\frac{8}{4} = 2$, $\frac{9}{4} = 2,25$, $\lfloor(2,25)\rfloor = 2$. Maximum in range $[8 + 1; 11]$ is $11$, and for maximum value we still get result $\lfloor \frac{r}{a} \rfloor = 2$ ; $\frac{11}{4} = 2,75$, $\lfloor(2,75)\rfloor = 2$.
•  » » » » We want to prove that for every number x in range [r−r mod a;r] x mod a≤r mod a is it because of this fact:- fact that [x/a] is maximum at x=r so if xmoda<=rmoda ,we can put x=r and make both [x/a] and xmoda maximum simultaneously
•  » » » » » 15 months ago, # ^ | ← Rev. 2 →   Yes, but if $x = r - r \ mod \ a - 1$ we get maximum $r \ mod \ a$, so we just need to check $x = r - r \mod \ a - 1$ and $x = r$.
•  » » » » » » 15 months ago, # ^ | ← Rev. 4 →   the more number of times i read the expainations, the more queries i am having( maybe because i am new to advance number theory concepts or it is the wording of the editorial)1)how did you arrive at the conclusion that every number in range [r−rmoda + 1;r] is not divided by a.i can observe it but i am not able to prove it mathematically2) what do we exactly mean by incomplete quotient3)why does the editoral say the statement (and are guaranteed to have a value fa less than fa(r)) if we find a x such that x%a > r%a, can't we get a fax>far ( i know that is what we are trying to prove but i want to know if i am interpreting this editorial statement correctly .
•  » » » » » » » Let's have an example: $a=7$. $21$ is divided by $7$, next number that can be divided is $21+7=28$. Every number in range $[21 + 1; 28 - 1]$ is not divided by $7$. So, if number $x$ divided by $a$ then $x + a$ also divided by $a$ and every number in range $[x + 1, x + a - 1]$ is not divided by $a$. $r - r \ mod \ a$ is divided by $a$, every number in range $[r - r \ mod \ a + 1; r - r \ mod \ a + a - 1]$ is not divided by $a$, we sure that $r < r - r \ mod \ a + a$, because number $a - r \ mod \ a > 0$, $r \ mod \ a < a$.2) $a \ div \ b$ is incomplete quotient or $\lfloor\frac{a}{b} \rfloor$.
 » finally a div3 contest after 2 month break^^
 » Why havn't the rating changed yet?
 » Why are the ratings not updated yet?
 » Hello there, and thanks for the enjoyable problems.I liked the last two problems since they can have much to teach for people who are new to DP and graph algorithms. Problem F was a combination of two merely classic ideas that are good to know for beginners, and the last problem introduces a useful property of the BFS algorithm and the BFS tree.Thanks to both authors for their cool problems, and I would suggest everyone to upsolve these two problems since they may help you in the future :)
 » Problem statement could be more clearer as I wasted a lot of time in the 3rd question to understand just what I need to print.
 » Can anyone explain G, I'm having a little trouble in understanding editorial.
 » Can the problem D be solved in O(n) time complexity?
•  » » I wasted whole time trying that, would be helpful if some did solve it using O(n)
 » Why I used memory search on G and got a TLE :(
 » In problem E is it possible to reschedule one of exams to day one?
•  » » yes but that would never help bc the time between the start of the session and the first exam is counted in the answer.
 » where can i found similar problems to G-Counting shortcuts ? i suck at dp on trees/graphs :(
 » Could somebody, please, explain how do we use dp in G-problem?
•  » » You store the number of ways to reach a node from source by following a path of min distance and (min distance + 1). Like whenever you're reaching a node from some other node, just ask if the depth of the curr node is equal to min depth or (min depth + 1), based on the ans you get, update your dp values.
 » In problem E , I just used a multiset which stores the difference between every two consecutive exams dates and update it for each element (try to put it in the best place) I think its easier. here it is 148865257
•  » » yea my sol was very similar haha, multiset is a lot more intuitive isnt it :p
 » Problem 1650G - Counting Shortcuts can be solved in another way. Calculate for each vertex: distance and number of shortest paths from $s$ and $t$ (with 2 bfs). Then we can iterate over all edges $\left(u,v\right)$. Firstly, vertices $u$ and $v$ should be included in same level (same distance from $s$). Secondly, $\text{dist}(s,u)+\text{dist}(v,t)=\text{dist}(s,t)$. If both conditions are held, then we can build path $s \rightarrow ... \rightarrow u \rightarrow v \rightarrow ... \rightarrow t$ with length equal to $\text{dist}(s,t)+1$. We need to add $\text{cntShortestWays}(s,u) \cdot \text{cntShortestWays}(t,v)$ to answer. Solution: 150206150
•  » » can you explain why vertices u and v should be included in same level?
•  » » » It prevents us from counting a path multiple times, because any path of length (minimum path length + 1) will have exactly one edge in which two points are at the same level of distance from s.
 » why cannot I understand the drscription of D Problem.