By Vladosiya, history, 5 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: SixtyWithoutExam

Tutorial
Solution

1650F - Vitaly and Advanced Useless Algorithms

Idea: Aris

Tutorial
Solution

1650G - Counting Shortcuts

Idea: MikeMirzayanov

Tutorial
Solution

• +73

 » 5 months ago, # | ← Rev. 2 →   0 Thank you codeforces for this contest!
 » 5 months ago, # |   +22 my solution for problem D using deque: https://codeforces.com/contest/1650/submission/148940490 I think it's easier, if you know data structure.
•  » » 5 months ago, # ^ |   0 Yeah+
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 please explain your solution
•  » » » 5 months ago, # ^ |   0 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.
•  » » » » 5 months ago, # ^ |   0 thank you
•  » » » » » 5 months ago, # ^ |   0 You're welcome :)
•  » » » » 5 months ago, # ^ |   0 Dude you are amazing!
•  » » » » » 5 months ago, # ^ |   0 It's a her btw.
•  » » » » » » 5 months ago, # ^ |   0 dude is a universal term
•  » » » » » » » 4 months ago, # ^ |   0 so straight men sleep with dudes?
•  » » 5 months ago, # ^ |   0 Thank you!
•  » » » 5 months ago, # ^ |   0 You're welcome :)
•  » » » » 5 months ago, # ^ |   +4 I love you!
•  » » » » » 5 months ago, # ^ |   0 hh
•  » » 5 months ago, # ^ |   0 It was easy to understand . Thank you.
•  » » 5 months ago, # ^ |   0 thank you!
 » 5 months ago, # | ← Rev. 3 →   +4 E has an answer binary search.
•  » » 5 months ago, # ^ |   0 Can you please explain your approach ?Thanking you in advance
•  » » » 5 months ago, # ^ |   0 we send a value to the binary search If the value satisfies the condition then there is a solution greater than our value
 » 5 months ago, # |   +14 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.
•  » » 5 months ago, # ^ |   0 Will this work for contest problems during the contest?
•  » » » 5 months ago, # ^ |   0 Works for me. ¯\_(ツ)_/¯ To make it work for you, you need to learn about 1) stress testing and 2) run a local development server of the website.
•  » » 5 months ago, # ^ |   0 Thanks, Was really helpful
 » 5 months ago, # | ← Rev. 3 →   0 Ok
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Ok
•  » » » 5 months ago, # ^ |   0 You don't have to Build SegTree for this problem bro! It can be solved very easy))
 » 5 months ago, # | ← Rev. 3 →   0 Resolved
 » 5 months ago, # |   0 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?
•  » » 5 months ago, # ^ |   0 Can anyone plese explain this.
•  » » » 5 months ago, # ^ |   +5 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.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 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$.
•  » » » » 5 months ago, # ^ |   0 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
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 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$.
•  » » » » » » 5 months ago, # ^ | ← Rev. 4 →   0 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 .
•  » » » » » » » 5 months ago, # ^ |   0 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$.
 » 5 months ago, # |   +9 finally a div3 contest after 2 month break^^
 » 5 months ago, # |   0 Why havn't the rating changed yet?
 » 5 months ago, # |   0 Why are the ratings not updated yet?
 » 5 months ago, # |   +18 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 :)
 » 5 months ago, # |   +4 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.
 » 5 months ago, # |   0 Can anyone explain G, I'm having a little trouble in understanding editorial.
 » 5 months ago, # |   +3 Can the problem D be solved in O(n) time complexity?
•  » » 5 months ago, # ^ |   0 I wasted whole time trying that, would be helpful if some did solve it using O(n)
 » 5 months ago, # |   0 Why I used memory search on G and got a TLE :(
 » 5 months ago, # |   0 I love practicing CP but editorials like this are really hard to read and understand
 » 5 months ago, # |   0 In problem E is it possible to reschedule one of exams to day one?
•  » » 5 months ago, # ^ |   0 yes but that would never help bc the time between the start of the session and the first exam is counted in the answer.
•  » » » 5 months ago, # ^ |   0 Thank you. I didn't realize it
 » 5 months ago, # |   +3 where can i found similar problems to G-Counting shortcuts ? i suck at dp on trees/graphs :(
 » 5 months ago, # |   0 Could somebody, please, explain how do we use dp in G-problem?
•  » » 5 months ago, # ^ |   0 I don't understand too :(
•  » » 5 months ago, # ^ |   0 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.
 » 5 months ago, # |   0 Question D is little tricky...
 » 5 months ago, # |   +4 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
•  » » 5 months ago, # ^ |   +3 yea my sol was very similar haha, multiset is a lot more intuitive isnt it :p
 » 5 months ago, # |   0 Can someone explain with an example what are they asking for output in problem C ?
 » 5 months ago, # |   0 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
•  » » 6 weeks ago, # ^ |   0 can you explain why vertices u and v should be included in same level?