doreshnikov's blog

By doreshnikov, history, 4 weeks ago, In English

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.

About problem F:

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

Idea: doreshnikov, MikeMirzayanov

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
 
 
 
 
  • Vote: I like it
  • +122
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

Thanks for an amazing round !

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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   Vote: I like it +8 Vote: I do not like it

    The 2nd and 3rd statements should have been like this:

    2.coordinate −1 is odd, jumping right to 2 leads to 1

    3.coordinate 1 is odd, jumping right to 3 leads to 4

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Sorry, that's a typo, fixed

»
4 weeks ago, # |
Rev. 2   Vote: I like it -31 Vote: I do not like it

Thank you for fastn't editorial.

»
4 weeks ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

can anyone share accepted java solution for problem C. mine is https://codeforces.cc/contest/1607/submission/134305901 giving TLE

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh..got it what I was mistaking. Thanks for clarifying.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Question D was really interesting

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Why in problem F the solution with dfs gives MLE?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No, I saw. I'm just wondering why the solution crashes and how I can optimize my dfs

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +21 Vote: I do not like it

        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) xD

        There are some solutions using dfs that passed. I can't guarantee that for your particular solution it will work, but you can try

        1. inlining local variables in dfs
        2. moving dfs parameters to the outer scope
        3. reducing the number of unnecessary arrays/vectors (for example, to implicitly store edges)
        4. 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, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Maximum stack size is not 2e5 -_-. Stop confusing people. Dfs with 4e6 size can pass.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        So what was the problem then?

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          Rev. 2   Vote: I like it 0 Vote: I do not like it

          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, # ^ |
              Vote: I like it 0 Vote: I do not like it

            How to calculate the "180 MB", thank you a lot.

            • »
              »
              »
              »
              »
              »
              »
              3 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Using iterative DFS instead of recursive DFS using stacks(or deque) bypasses the recursion stack limit problem: My Solution

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think the tutorial of problem C has a mistake:

The Words in the tutorial

I think $$$a_0$$$ should be [1,4,6,12,15].

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain problem E

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

There is also an O(n) approach to problem D. I solved it without sorting the array. Link to my submission.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I think my code is correct. And the sample is passed too. But WA. Help me!

#include<bits/stdc++.h>
#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<st.length();i++)
		{
			int q1=st[i]&31,q2=st[i-1]&31;
			ans+=abs(biao[q1]-biao[q2]);
		}
		cout<<ans<<endl;
	}

    return 0;
}

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

Used Binary Search for E:Solution

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

      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, # |
  Vote: I like it 0 Vote: I do not like it

what does "max[->]" mean in editorial of problem E

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

jj