### doreshnikov's blog

By doreshnikov, history, 4 weeks ago,

### Short information

Sorry for another delayed editorial, I know I promised that it will come out sooner the previous time, but I wasn't feeling well today, so the work was slower than usual.

I am once again sorry for the inconveniences caused by tight ML in this problem. It was not the intended behavior since we relied too much on the main solution and didn't assume most of the solutions using DFS will fail. In this editorial I attach the code of the main solution that we expected from the beginning, it uses ~75MB of memory.

I guess, Div. 3 Rounds are not only for participants to learn but also can serve as educational for authors as well. I'll try not to repeat the same mistakes the next time :) Thanks to everyone for participating and hope to see you again!

### The editorial

1607A - Linear Keyboard

Tutorial
Solution

1607B - Odd Grasshopper

Idea: doreshnikov

Tutorial
Solution

1607C - Minimum Extraction

Idea: doreshnikov

Tutorial
Solution

1607D - Blue-Red Permutation

Idea: MikeMirzayanov

Tutorial
Solution

1607E - Robot on the Board 1

Idea: MikeMirzayanov

Tutorial
Solution

1607F - Robot on the Board 2

Idea: doreshnikov

Tutorial
Solution

1607G - Banquet Preparations 1

Idea: doreshnikov

Tutorial
Solution

1607H - Banquet Preparations 2

Idea: MikeMirzayanov

Tutorial
Solution

• +122

 » 4 weeks ago, # |   +12 Thanks for an amazing round !
 » 4 weeks ago, # |   +5 Correct me if I'm wrong but I believe there's a typo in the editorial to problem B. It says "coordinate −1 is even, jumping right to 2 leads to 2", when jumping right 2 from -1 should be 1 (2-1 = 1).
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   +8 The 2nd and 3rd statements should have been like this:2.coordinate −1 is odd, jumping right to 2 leads to 13.coordinate 1 is odd, jumping right to 3 leads to 4
•  » » 4 weeks ago, # ^ |   +8 Sorry, that's a typo, fixed
 » 4 weeks ago, # | ← Rev. 2 →   -31 Thank you for fastn't editorial.
 » 4 weeks ago, # | ← Rev. 2 →   +9 I finally know why so many people I know can't solve problem F.But I get TLE because I forgot to push a tag XD.
 » 4 weeks ago, # |   0 doreshnikov Can you explain the following line in the editorial with an example for problem : Robot on the Board 1?Since the robot breaks as soon as goes outside the field, if any command causes it to break, it either leads to its total shift relative to (r, c) of exactly c to the left or exactly m — c + 1 to the right, or, similarly, of exactly r up or exactly n — r + 1 down.
•  » » 4 weeks ago, # ^ |   +15 If there's a moment in time when the robot moves to the left exactly c times more than to the right, it will fall off the left edge of the board. And the similar statements for each other direction.
 » 4 weeks ago, # | ← Rev. 2 →   0 MikeMirzayanov I wonder how did you come up with problems like 1607D - Blue-Red Permutation What i mean is how do start thinking while framing a problem (sorry if question is too broad).
 » 4 weeks ago, # | ← Rev. 2 →   0 can anyone share accepted java solution for problem C. mine is https://codeforces.cc/contest/1607/submission/134305901 giving TLE
•  » » 4 weeks ago, # ^ |   0 Try to shuffle the array before sorting.
•  » » 4 weeks ago, # ^ |   +3
•  » » » 4 weeks ago, # ^ |   0 it worked....thanks [user:m1_k3][user:UpAndDown]
 » 4 weeks ago, # | ← Rev. 2 →   0 For the case n=10 and x0=10 in problem B, where x0 is the starting point and n is total number of steps, how the output is 11? From what I understood from the problem statement, I was getting 15.10-1+2-3+4...+10 -> 15
•  » » 4 weeks ago, # ^ |   0 The correct sequence is 10-1+2+3-4-5+6... 10 — even, then -1 9 — odd, then +2 11 — odd, then +3 ...
•  » » » 4 weeks ago, # ^ |   0 Oh..got it what I was mistaking. Thanks for clarifying.
 » 4 weeks ago, # |   0 Question D was really interesting
 » 4 weeks ago, # |   +3 Why in problem F the solution with dfs gives MLE?
•  » » 4 weeks ago, # ^ |   0 Don't you see the reason in the post?Authors didn't suppose that participants will use DFS for solving this problem...
•  » » » 4 weeks ago, # ^ |   0 No, I saw. I'm just wondering why the solution crashes and how I can optimize my dfs
•  » » » » 4 weeks ago, # ^ |   +21 I'm kinda scared answering to such questions since my comments on the topic tend to get highly disliked (though, maybe, it's deserved in some way, I feel some people are just still unhappy with my existence) xDThere are some solutions using dfs that passed. I can't guarantee that for your particular solution it will work, but you can try inlining local variables in dfs moving dfs parameters to the outer scope reducing the number of unnecessary arrays/vectors (for example, to implicitly store edges) submitting your solution under 32-bit g++ instead of 64-bit One of the testers' solutions used tail recursion, so maybe it was optimized by the compiler, but I'm not that familiar with the fact whether g++ can do such optimizations and if they are used by Cf's compilers. Sorry if I missed something, maybe someone else can help you a bit more. Good luck!
•  » » 4 weeks ago, # ^ |   +3 I guess that's because the maximum recursion stack size is about 2e5, while in problem F there could be 4e6 recursive calls of dfs.
•  » » » 4 weeks ago, # ^ |   0 Maximum stack size is not 2e5 -_-. Stop confusing people. Dfs with 4e6 size can pass.
•  » » » » 4 weeks ago, # ^ |   0 So what was the problem then?
•  » » » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 The problem is that your recursion takes up space. So if you have dfs with depth 4e6, it will take extra MBs.For example if your arrays and vectors use 80 megabytes. This dfs of size 4e6 will add extra 180 MBs. And total will be 80+180=260 which will get MLE. But if you optimize your dfs. Then it can use less memory.
•  » » » » » » 3 weeks ago, # ^ |   0 How to calculate the "180 MB", thank you a lot.
•  » » » » » » » 3 weeks ago, # ^ |   0 there is no accurate way to do so. But it depends on the depth and number of variables that you initialize inside of it.
•  » » 4 weeks ago, # ^ |   +3 Using iterative DFS instead of recursive DFS using stacks(or deque) bypasses the recursion stack limit problem: My Solution
 » 4 weeks ago, # |   0 I think the tutorial of problem C has a mistake: The Words in the tutorialIndeed, if we look at $a_0=[1,4,7,12,13]$, it will undergo changes as follows: $[\color{blue}1,4,6,12,15]→[\color{blue}3,5,11,14]→[\color{blue}2,8,11]→[\color{blue}6,9]→[\color{blue}3]$.I think $a_0$ should be [1,4,6,12,15].
 » 4 weeks ago, # |   0 can anyone explain problem E
 » 4 weeks ago, # |   0 There is also an O(n) approach to problem D. I solved it without sorting the array. Link to my submission.
 » 4 weeks ago, # |   0 I think my code is correct. And the sample is passed too. But WA. Help me! #include #define N #define ll long long #define re register #define in inline using namespace std; in int read() { re int s=0,w=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9')s=s*10+ch-'0',ch=getchar(); return s*w; } int t,ans; int biao[26]; int main() { t=read(); while(t--) { ans=0; for(int i=1;i<=26;i++) { char s; int a; cin>>s; a=s&31; biao[a]=i; } string st; cin>>st; for(int i=1;i
 » 4 weeks ago, # | ← Rev. 2 →   0 I am getting WA on problem G on the codeforces compiler, but have copied the exact test cases into my compiler and confirmed I'm getting a different (the right) answer on my local machine. https://codeforces.cc/contest/1607/submission/134616768 Can anyone help me figure out what's wrong?
 » 4 weeks ago, # |   0 I have a problem in the problem C that is minimum extraction. Is it mandatory that after the subtraction the new element in the first positon of the array be the smallest? It can be a negetive element at first and then after the subtraction can be a positive element greater than rest of the elements of the array. Does in that case also this logic holds?
 » 4 weeks ago, # |   0 Used Binary Search for E:Solution
•  » » 4 weeks ago, # ^ | ← Rev. 2 →   0 What's the invariant you used ? And why does your O(NlogN) solution passes and mine(has same TC) doesn't ? My submission : E-TLE
•  » » » 3 weeks ago, # ^ | ← Rev. 2 →   0 If you carefully analyze my code you will see my code is doing less operations as compared to your code . 1) No extra vector is created 2) i am trying to calculate x and y coordinated in only 1 binary search .Even your code is under the limit n*log(n) but there are too many operations .I have just used simple binary search. Approach:set left and right limit of the coordinates for both x and y then do binary search ...check for the number of commands executed using those coordinates . Check whether x coordinates exceeded the limit or the y then according to that update the x and y . if whole string is covered ...then that's your ans (simple break)
 » 3 weeks ago, # |   0 what does "max[->]" mean in editorial of problem E
 » 3 weeks ago, # | ← Rev. 2 →   0 jj