300iq's blog

VK Cup 2019-2020 -- Engine Editorial
By 300iq, 4 years ago, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +116
  • Vote: I do not like it

Comments Comments (150)
| Write comment?
»
4 years ago, # |
← Rev. 2   Vote: I like it +21 Vote: I do not like it

Edit: Nvm, it's showing up now

→ Reply
»
4 years ago, # |
  Vote: I like it +29 Vote: I do not like it

How does the interactor work for F?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    You can find Smith values for all vertices in $$$O(E \sqrt{E})$$$, and then all the arithmetic should be simple enough.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      Could you elaborate? (What's a smith value?)

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +42 Vote: I do not like it

        The only source I know about Smith theory is Winning Ways For Your Mathematical Plays, chapter 12. In short, every position in such a game is equivalent to a nim heap $$$*k$$$, or $$$\infty_S$$$ for a set of non-negative numbers $$$S$$$. $$$\infty_S$$$ is winning if $$$0 \in S$$$, and a draw otherwise. Smith value of a position is one of these options.

        The addition rules are: $$$*a + *b = *(a \oplus b)$$$ (just Grundy), $$$\infty_S + *k = \infty_{S \oplus k}$$$ (XOR every element of $$$S$$$ with $$$k$$$), $$$\infty_S + \infty_{S'} = \infty_{\varnothing}$$$.

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        This paper has a short summary in section 6: https://www.msri.org/people/staff/levy/files/Book56/12siegel.pdf

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -25 Vote: I do not like it

        I just wanted to ask you a question Benq. Tried to message you but was unable to do so.

        "do smth instead of nothing and stay organized". What is "smth" in here? I am so curious and can not resist asking.

        → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +10 Vote: I do not like it

      Any tips on how you can compute the values in $$$O(|E|\sqrt{|E|})$$$? I figured out how to do it in $$$O(\sum_{i=1}^{|V|}degreein_{i} * degreeout_{i})$$$ which is bounded to $$$O(|V| * |E|)$$$, but I can't seem to find any improvement.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        You can place $$$*k$$$ in a vertex $$$v$$$ if:

        • there are edges from $$$v$$$ to vertices marked $$$*0, \ldots, *(k - 1)$$$, and no edge to a vertex marked $$$*k$$$;

        • for each $$$u$$$ -- unmarked option of $$$v$$$ there is an edge to $$$*k$$$.

        If the rule can not be applied anymore to any vertex, then all remaining vertices are $$$\infty$$$'s.

        If all $$$*0, \ldots, *(k - 1)$$$'s are placed, then all possible $$$*k$$$'s can be placed in $$$O(E)$$$ with a reverse BFS-like traverse. We can stop after

        Unable to parse markup [type=CF_MATHJAX]

        , since there has to be $$$\Omega(k^2)$$$ distinct edges for a $$$*k$$$ to exist.
        → Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Div2 C can be solved with binary search for the answer. 97454890

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

    Sir, can you please tell me how did got to the solution of A? I just couldnt solve it after spending 2 hrs on it

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Well, this is how I thought: -the easiest way for gcd not to be one — to take even numbers only, so gcd of any two to them is at least 2. -Okey, now it is necessary that there are no pairs of numbers that one is divisible by another. And again the easiest way to do so is to make ratio of any two less than 2. So we would have no such pairs for sure.

      With two observations above I immediately got to the solution.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Thank you sir...really dont know how to bring those ideas even after regular practice..

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

    Can you please explain your logic too!

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      In C?

      First, let's say we are given some time x. How can we determine whether it's possible to get all the food in no more than x?

      Let's go throw the a array. If a[i] > x then we need to go to take this item on our own. Summarise all such a[i]. If sum <= x, then it's ok, we can do this. Otherwise, it's not possible to do this in x.

      Now we can use binary search on answer. (read about it in internet). We can do this since for some first x-s we can't do this in no more than x and starting from some x, which we want to find, we can. So in fact just need to find the first x such that we can do that in no more than x. And to find it we use the binary search.

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

        can you see my code for C ? 103697796

        i can neither understand the editorial nor your explanation.

        what i did was , i would add up the time of the user if and only if that resulting sum after going to restaurant is less than the max(delivery) time.

        But my solution is failing the 2nd test case itself ?

        #define f(n) for(int i=0;i<n;i++)

typedef long long ll;

void solve()
{	
   int n;
   cin>>n;

   vi v(n); //vector<int>
   f(n)
   {
   	cin>>v[i];
   }

   vi k(n);

   f(n)
   {
   	cin>>k[i];
   }
   
   ll s1=0,s2=0;
   
if(k[0]<v[0])
   {
   	s1+=k[0];
   }
   
else
   {
   	s2=v[0];
   }
   
   ll sum;
   



for(int i=1;i<n;i++)
   {
   	sum=s1+k[i];
   	if(sum < max(s2,ll(v[i])))
   	{	
   		s1+=k[i];
   		
   		
   	}
   	else
   	{
   		if(v[i]>s2)
   		{
   			s2=v[i];
   		}
   	}
   }
//   cout<<s1<<s2;
   cout<<max(s1,s2)<<'\n';
	
}
        → Reply
»
4 years ago, # |
  Vote: I like it +70 Vote: I do not like it

Straightforward dp solution, where s(i,j) – max possible sum after j operations on first i arrays and transition in O(k), has complexity of O(nk2) or precisely O(k⋅min(nk,∑i=1nti)) and doesn't fit into the time limit.

Or does it?

97479244

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please tell me in whats wrong with my this solution for Div2D ? Submission

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

    I can give a counter testcase Try 1 5 2 5 4 5 3

    The answer should be no I think your code would output yes

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

    The answer should be no in the following array But this program says yes
    ~~~~~ 13 20 13 10 13 15 10 15 15 14 ~~~~~

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it -9 Vote: I do not like it

In 1443D-Extreme Subtraction, my idea was to maintain two other arrays which will store the minimum element to the left of element in array and minimum element to the right of element in array respectively for each element in the array. This way I could check for all elements if they are less than or equal to the sum of left minimum element and right minimum element and if there is an element which is greater than this sum then for sure we can not reduce that element to zero. I passed the given test case but failed pretest 2. I'm attaching the code below please help if you can in letting me know where exactly I went wrong. Here is the code 97483817

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    The condition is not sufficient, e. g. your code prints yes for the following counterexample

    5
1 2 1 2 1

    (It's not possible, the output should be no)

    P.s. Please don't post whole code, since it makes the comment section longer and less readable

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

      Sir, can you kindly tell why the above approach of pythonPappi doesn't work?

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

        As said, the described condition is necessary (all the inputs that produce "Yes" have to satisfy this condition), however, it's not sufficient (meaning that not every input satisfying this condition will have a "Yes" as solution). To see this, you can look at the counterexample I provided in my original comment. You need to come up with another condition.

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

          Actually I came up with the same example when my solution gave WA. So, from your reply, shall I conclude that the above solution is not logically incorrect but rather it's not sufficient to solve the problem??

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

            Yep. Exactly. The actual condition is narrower than the condition mentioned.

            → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Div2B is simple. I wonder why I wasted my time to come up with a dp solution :))

→ Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

I want to cry out loud, got almost all things in problem C except the case when you have to bring all the parcel on your own!!! I feel it happened because I stressed out in the last, won't do that from next time. AC https://codeforces.net/contest/1443/submission/97496785

→ Reply
»
4 years ago, # |
  Vote: I like it +9 Vote: I do not like it

What does engine editorial mean?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    This VK cup contest has several tracks (mobile, design, machine learning), and one of them is called "engine" which is basically a competitive programming track.

    → Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Div2D/Div1A tagged dp and greedy. Anyone please explain dp solution.

→ Reply
»
4 years ago, # |
  Vote: I like it +6 Vote: I do not like it

In Div-2 D,

The problem sounds like this — check that there are increasing and decreasing arrays, the element-wise sum of which is equal to the given array.

Can someone elaborate on what this means and how it relates ?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    If we could only decrease prefixes, then the whole array would need to be non increasing. If we could only decrease postfixes, then the whole array would need to be non decreasing.

    Since we can do both, it must be a sum of both.

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

    same, what is "the element-wise sum"?, can someone explain it?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Consider a non-decreasing array1 [2,4,5,8,11] and a non-increasing array2 [14,8,5,5,1]. As said above: If we could only decrease prefixes, we would want the array to be something like array2. If we could only decrease suffixes, we would want the array to be something like array1. Since we can do both, an array of the type array1 + array2, i.e. [2+14, 4+8, 5+5, 8+5, 11+1] would also give us a "YES"

      → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Very short $$$O(n)$$$ solution for div2F/div1B 97497692, but I'm not fully clear about why it works.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    Take a look at this submission 97441804.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    Try to prove these facts:

    • if $$$a_{i-1}$$$ hasn't been chosen yet, but it will be chosen later, and $$$a_i$$$ exists (1), then they are still adjacent in the current array
    • if $$$i \neq 1$$$, $$$a_i$$$ exists and $$$a_{i-1}$$$ has already been removed (2), then $$$a_i$$$ is adjacent to the left to a visited integer in the current array
    • if $$$i \neq 1$$$, $$$a_i$$$ exists and neither (1) nor (2) holds, then $$$a_i$$$ is still adjacent to $$$a_{i-1}$$$ in the current array
    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For 1443A — Kids Seating, If there are 3 kids, can't we print "202 204 206" as answer? I get this when i submit the code "wrong answer Integer element [index=1] equals to 202, violates the range [1, 8] (test case 1)"

→ Reply
»
4 years ago, # |
  Vote: I like it +33 Vote: I do not like it

Can someone give an explanation for div2D solution? I can't really understand what is written in the editorial.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +47 Vote: I do not like it

    Editorial of D is written for those who have solved D, I think :(

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +29 Vote: I do not like it

    Observation 1:- We can do operations in any order it doesn't affect our final array A.

    Observation 2:- If we do all prefix operation first and after it we get an array A which is non- decreasing then the ans is YES(as now you can apply suffix operation and decrease one by one from last also all elements must be greater than or equal to 0) if we get any other array then the ans is NO.

    now our only motive is to make the array non-decreasing after applying prefix operations.

    Why observation 2 is correct(with example) :-

    A = [12,7,20,8,17]

    step 1 -> at first we can decrease A[0] to 7 A = [7,7,20,8,17]

    step 2 -> Since 7 7 20 is already in non decreasing order now we check 20 and 8 ..... since 20 > 8 so we have to decrease our first k(k=3) elements by 20-8 to make 20 equal to 8 . A = [-5,-5,8,8,17]

    though we got an non — decreasing array but our First two elemnts are less than 0 so ans = "NO"

    for more clarity https://codeforces.net/problemset/submission/1443/97522500

    sorry for bad english.

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

    As stated in other comments, We can just chose to perform all the prefix operations first. In that case, the array after performing the prefix operations must be non-decreasing.

    I saw I_will_come_back's submission. Thank you for the explanation. Just wanted to post a simpler way to solve it using the same concept.

    So I traversed the array from the end and kept a count of the decrement till the index 'i' For eg. [11 7 9 6 8] initially: count =0 , i = n-2 Since the final array should be non-decreasing,Whenever we encounter, arr[i]> arr[i+1] we'll update count and arr[i] i.e. for i = 2 here, arr[i] will become 6 and count will be updated to 3. After the loop, we just need to check if all elements in the modified array are >=0 or not.

    Take a look at my submission if needed.
    97652518

    Have fun coding :')

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why this code is getting different verdicts for the same code in C++17(64) and C++17 ?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Accessing a[i] if i is out of bounds is undefined behavior. Anything is allowed to happen.

    Maybe your solution is just too slow, but in one case you were lucky to get runtime error. Another theory is that accessing a[i] for some big i overwrote n causing your loops to go on very long.

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

      Thanks! n must have been overwritten. The solution isn't slow, this submission got accepted. This thing ruined my contest, I am not using global variables ever again.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Global state is evil, but I'm not sure how you will prevent out-of-bounds access just by not using global variables.

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

          Would double check too. I wouldn't at least get weird verdicts by not using global variables.

          → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

11 6 7 10 9 9 8 ,can anybody explain why and how it is yes

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it 
    11  6  7 10  9  9  8
 6  6  7 10  9  9  8
 6  6  6  9  8  8  7
 6  6  6  6  5  5  4
 5  5  5  5  5  5  4
 4  4  4  4  4  4  4
 0  0  0  0  0  0  0

    BTW, my solution to Div2.D problem.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This may be a dumb question but how is the answer for sample 3 in div2D NO?

Is the following not a possible sequence of performing operations?

[1 3 1 3 1] -> [0 2 0 3 1] -> [1 2 0 3 1] -> [2 2 0 3 1] -> [1 1 0 3 1] -> [0 0 0 3 1] -> [0 0 0 2 0] -> ... (and similarly for the 2 0 in the suffix)

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

    You can't increment! The question states that you can pick first k or last k elements of the given array and decrement it by 1.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Made the silliest mistake of my life in Div2D.
if(n==1) cout << arr[0] << endl;
instead of
if(n==1)
cout << "YES" << endl;
:(

→ Reply
»
4 years ago, # |
  Vote: I like it -14 Vote: I do not like it

is it rated?

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +39 Vote: I do not like it

Just to mention, as a full-BFS solution to Div.1 problem C:

Let $$$base_{0,u}$$$ be the minimum (even) number of required transpositions to reach the vertex $$$u$$$. Similarly let $$$base_{1,u}$$$ be the minimum (odd) number of required transpositions to reach the vertex $$$u$$$.(Note that their difference wouldn't be greater than 1.) We can evaluate $$$base$$$ numbers by a 0-1 BFS algorithm:

Create a graph with a node for each of the $$$base$$$ array cells;

  • Connect $$$(i, u)$$$ to $$$(1 - i, u)$$$ with a 1 weighted edge.
  • For each u->v edge in the original graph, connect $$$(0, u)$$$ to $$$(0, v)$$$ with a $$$0$$$ edge.
  • For each u->v edge in the original graph, connect $$$(1, v)$$$ to $$$(1, u)$$$ with a $$$0$$$ edge.

Now declare $$$dis_{u, i, j}$$$ as the minimum number of token movements needed to reach $$$u$$$ while $$$base_{i, u} + j$$$ transpositions have been applied and the oddity(# % 2) of the applied transpositions is equal to $$$i$$$(Yes! Half of the states are unused/invalid.). To update $$$dis$$$ values, create a new graph with a node for each triple $$$(u, i, j)$$$.

  • Connect $$$(u, i, j)$$$ to $$$(u,\ !i,\ j + base_{i, u} - base_{1 - i,\ u})$$$ with a $$$0$$$ edge.
  • For each u->v edge in the original graph, connect $$$(u, 0, j)$$$ to $$$(v, 0, j + base_{0, u} - base_{0, v})$$$ with a $$$1$$$ edge.
  • For each u->v edge in the original graph, connect $$$(v, 1, j)$$$ to $$$(u, 1, j + base_{1, v} - base_{1, u})$$$ with a $$$1$$$ edge.

Then run a 0-1 BFS from the $$$(1, 0, 0)$$$ node to evaluate each $$$dis_{u, i, j}$$$.

The answer equals to the minimum value among $$$2^{base_{i, n} + j} + dis_{n, i, j}$$$ with all of the possible $$$i, j$$$ values.

It can be easily proved that it's enough to set the $$$log(m)$$$ as an upper bound for $$$j$$$(third argument of $$$dis$$$) and still solution works correctly. So the size of $$$dis$$$ would be $$$n . 2 . log(m)$$$ and the whole solution would work with $$$O((n + m).log(m))$$$ time complexity.

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

    Is this just for the first part of the problem? What about when you have to do $$$m-1$$$ transpositions? (A line graph with alternating directions on edges.) It seems $$$j$$$ will have to be $$$O(m).$$$

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

      Not actually; Note that $$$j$$$ is the difference between "minimum number of required transpositions to reach $$$u$$$(i.e. $$$base_{i, u}$$$)" and "the actual number of applied transpositions to reach $$$u$$$ in an optimal way", this difference wouldn't exceed $$$log(m)$$$.

      I think in your example $$$base$$$ values would be large enough(almost equal to m or n).

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

        Oh, of course, I understand the definition now. Cool!

        → Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Is there any explanation (proof) for 1442B — Identify the Operations for a fact that decisions 1..X-1 (to pick i-1 or i+1) doesn't influence outcome of step X? Basically that it doesn't matter what we did before, step X will always have 0, 1 or 2 options for all possible sequences. I got AC, but wasn't able to prove it.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Here's my thought:

    Suppose that we're currently processing $$$a:=b_i$$$ and let $$$c:=b_j$$$ for some $$$j>i$$$. There are two possible cases that previous operations influence our current choice:

    1. $$$a$$$ moves to the border
    2. $$$a$$$ and $$$c$$$ become adjacent.

    The first case is impossible because, before $$$a$$$ moves to the border, the number between $$$a$$$ and the border must be deleted and thus $$$a$$$ is added to $$$b$$$, but numbers in $$$b$$$ are unique, so it's impossible. The proof for the second case is similar.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    We need to choose the elements in b[] in given order. So, foreach the coresponding a[i] we can choose the left or right neighbour if it exists. Doing so does not change the number of chooseable neigbours of other elements. Because the removed one is replaced by the choosen one. Because of this the 0, 1 or 2 is invariant.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have an easier solution for Div2F — Div1B: Go through the elements of b, look the position of the current number in b. If there is only one possible neighbour to delete (either on edge of list or one neighbour is a future number in b) take it, if there is no possible neighbour then the answer is 0, and if both are possible you can take either one since the result is in each case the same (the other not taken numbers are equal to the other two possible not taken numbers, each of those numbers can be taken in the future and which two we take doesn't influence the indexes of future takes). You can maintain this with a linked list, nodes have two pointers for neighbours, EZ O(n). Here's my submission: https://codeforces.net/contest/1443/submission/97489269, it's ugly cuz I didnt have much time left, should have made some Node classes instead of just keeping it in an array but thankfully I didn't make any mistake while implementing it (unlike on most tasks in the contest lmao).

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

    nvm the solution in the editorial actually isn't really different, I just thought it must have been cuz it was nlogn. The problem was really easy for a F type.

    → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

In problem B, I used memoization. int memo[1e5+1];

I do a memset(memo, -1, sizeof memo); at the beginning of each test case.

There are 10^5 test cases, and i do memset at each one of them. yet my solution was accepted !!?

any explanation?

https://codeforces.net/contest/1443/submission/97508001

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    It looks like the answer could be weaker test cases — even though the limit is given as 1e5, the max value in the test cases seems to be about 11000. Whilst this would still result in many operations, my understanding is that 1e9 of the very simplest operations is achievable in the time limits. You could try a custom invocation with 1e5 test cases and I suspect it might fail. I’m not certain, though.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Maybe the test data is too weak...

    I even saw that someone use an $$$O(n^2)$$$ algorithm to pass a problem that $$$n\leqslant 10^6$$$. It worked successfully and accepted the problem :)

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Your code passes T = 1e5 in 900 ms :)

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

How to solve Div1B — 1442B - Identify the Operations if the resulting array $$$b$$$ is not distinct?

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +42 Vote: I do not like it

I thought I'd share my solution for 1A as I think it's way more interesting than the editorial's solution.

Let's assume the input array $$$a$$$ is the prefix sum array of some array $$$b$$$. Then it's obvious that $$$b_{i} = a_{i}-a_{i-1}$$$ for all $$$i \geq 2$$$ and $$$b_{1} = a_{1}$$$. Now we simply check to see if the absolute value of the sum of negative elements in $$$b$$$ is strictly greater than $$$a_{1}$$$. If it is, the answer is "NO" otherwise "YES"

This boils down to the fact that an operation on the prefix decreases $$$b_{1}$$$ by $$$1$$$ and increases $$$b_{x}$$$ by $$$1$$$ where $$$x$$$ is the length of prefix chosen. An operation on the suffix simply decreases $$$b_{y}$$$ by $$$1$$$ where $$$y$$$ is the length of suffix chosen. Because of the 2nd operation, we can always make the entire array $$$0$$$ if array $$$b$$$ consists of all non-negative numbers. In order to make negative numbers $$$0$$$, we have to "move" a $$$1$$$ from $$$a_{1}$$$ without letting $$$a_{1}$$$ becoming negative itself.

97513072

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Perfect. but it is hard to come up with a solution like this At least for me in contest time or may be after that :).

    → Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

In DIV1C, for the second part, when we know that B > log2(m), I used Dijkstra where distance is a pair where the first part of pair is B and second is A (B and A are same notations used in Editorial). Instead of splitting the graph into two different graphs, I used the number of transpositions till now to decide whether I can traverse the edge or I need to transpose it again. I ensure the minimum value of B, and if B is same, then I checked the value of A. But this approach is getting wrong answer on test 7, and I'm not sure whether there is something wrong with my approach or I can't implement Dijkstra in this way. Please help me understand my mistake. I really appreciate any help you can provide. Link to my submission.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +18 Vote: I do not like it

    Consider 3 vertices a, b and c. You are currently in a, but you need to reach c, and the only way to do that is through b. To reach b you can either transpose and go to a short path to reach b, or you take a long path to reach b without transposing. But once you reach b you need to transpose to reach c, so it would be better to have transposed earlier (in a) so you could take this shorter path. Thats why you need to duplicate the graph, you cannot transpose lazily.

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

      It took me some dry runs to understand what you are saying, but I finally understood it. Thanks a lot.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I have a solution that is different from 1443A: You can preprocess the first 100 prime numbers and, when you print the answer, times 2 for each number and that could be fit for the request of the problem :)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    It will run into an issue for n=6 (it gives 4, 6, 10, 14, 22, 26). Here, 26 exceeds the limit of 24 (4*n). I started solving it that way and ran into this issue — had to improvise. However, the editorial solution is cleaner (i.e. take multiples of 2 starting backwards from 4*n, you'll be okay every time — since their gcd will be at least 2 and they won't divide each other).

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

    I tried that but it had some problem. Like when n = 5, then your answer is 4, 6, 10, 14, 22. But 22 violates the range [1, 20]

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

    Oh I forgot! I didn't pass using the algorithm :(

    → Reply
»
4 years ago, # |
  Vote: I like it +39 Vote: I do not like it

Why didn't you post analysis for 1441F - Matching

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    Fixed

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      I still don't see it. Also, could you open up that contest (or at least that problem) for practice?

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    This is apparently a classical problem. This 2001 paper has the solution: https://collaborate.princeton.edu/en/publications/unique-maximum-matching-algorithms

    The main observation is a theorem of Kotzig: Consider any graph with a unique perfect matching. Then, that perfect matching contains a bridge of the graph. Intuitively, any biconnected graph has either 0 or at least 2 perfect matchings, because there are enough cycles to find a second matching. I found a short proof here: https://arxiv.org/abs/1402.0949.

    Now, to solve the problem, we just need to repeatedly identify bridge edges, decide if the two components it connects are odd-sized, and if so, use the edge and delete both endpoints. We can do this with merge-smaller-into-bigger or parallel-BFS type algorithms on the faces.

    → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I had different solution for problem C. I searched for the minimum number of steps that we should make if we are allowed to make up to $$$T$$$ transpositions. To find such value we can duplicate all nodes, assign cost 1 to regular edges, and cost $$$X$$$ to edges that make transposition. Then, with binary search we can find such values. To avoid several binary search, we can run a single binary search that looks for all values at the same time.

I didn't put too much thought about what was the complexity of this solution during the competition (lucky me). The complexity is $$$O(|V| \cdot \log |E| \cdot |C| \cdot \log |C|)$$$ where $$$|C|$$$ is the total number of distinct target paths that exist. Target paths are those such that a value $$$X$$$ exists where $$$T \cdot X + steps$$$ is minimum among all paths. During the competition I thought this number was bounded by $$$O(n^{\frac{1}{4}})$$$ but it turns out that there are graphs where the number of distinct target paths is $$$O(n^{\frac{1}{2}})$$$.

I managed to hack my solution with one such graph.

→ Reply
»
4 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

I was solving div2B, and found this unexpected runtime error in the below piece of code, can anyone explain what's going on?

while debugging, I found that even after prs.size()==0, for loop is getting executed and then giving the error. Pls help.

for(int i=0; i<(prs.size()-1); ++i){
    int diff = (prs[i+1].first - prs[i].second -1);
    if((diff*b)<a){
        cost+=(diff*b);
        segs--;
    }
}

here is the full code for div2B- https://codeforces.net/contest/1443/submission/97530452
I had to use if else to get AC

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

    prs.size() is unsigned type, so prs.size()-1 is unsigned, too.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

What is the proof for Div1B?

Let's say the answer to the problem is not $$$0$$$. Then how to prove that in the case $$$(3)$$$ while choosing any of the $$$a_{i-1}$$$ or $$$a_{i+1}$$$ will always lead to the solution in the end rather than ending up in a contradiction later on.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +12 Vote: I do not like it

    First, we can notice, that the actual values are not very important. Let's use | to denote something that we will use later, and . to denote something removable. You should note, that the order of the | chosen is still important, though not represented here.

    So our array looks like ..|...|...|...|...|....

    Now we can see that one of the | will be next. After we add it to the array b, it is useless, and removable like a ., because all values in "b" are distinct. So using either |. and .| in .|. yield a ... So the next state is the same regardless of whether we choose left or right.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone Pls suggest some more problems like div2D/div1A.

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

    it's the easiest pblm in this contest! A was way harder for me! -_-

    → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Don't know who needs this counter test case in div 1C but I definitely did, so I'll share it:

9 9
2 1
2 3
9 3
1 4
4 5
5 6
6 7
7 8
8 3

Expected Output: 8

→ Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I think the test data of Div2D/Div1A is not so strong, here is an accepted $$$O_{(n^2)}$$$ solution.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +36 Vote: I do not like it

About Div.1 D, I have another solution with complexity O(nklgn)，the idea is that some of element will never be choice.Then we calculate the prefix sum and sort the column，for the j-th column the last n-1-k/j element will never be choice. here is code. https://codeforces.net/contest/1442/submission/97548953

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Someone can explain Div2E task. How we generate a permutation with the corresponding number?

And why only the last 15 elements need change, if there may be such a situation when the last 15 elements are initially in descending order and the 16th element needs to be changed

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    There are n! permutations of {1,2,3,...,n}. But how do they look in lexicographic order?

    Let's look at first 6 permutations (n >= 3): 1: {1,2,...,n-2,n-1,n}, 2: {1,2,...,n-2,n,n-1}, 3: {1,2,...,n-1,n-2,n}, 4: {1,2,...,n-1,n,n-2}, 5: {1,2,...,n,n-2,n-1}, 6: {1,2,...,n,n-1,n-2}. As you see, only last three elements were changing their positions. Why? Because 3! = 6, so first 3! = 6 permutations only permute last 3 elements. In general, for given 1 <= k <= n first k! permutations of {1,2,...n} only last k elements change their positions, the first n-k elements are always {1,2,...,n-k} in that order.

    "And why only the last 15 elements need change?" - Let's notice that we have x <= 2e5 and q <= 2e5 and we start from X=1 permutation index. Therefore at the end maximum possible index is X <= 1 + 2e5 * 2e5 = 4e10 + 1. Just because 15! > 4e10 + 1, we know that only last 15 elements can change. In fast it is sufficient to look at 14 last elements, as 14! = 87178291200 > 4e10 + 1.

    "How we generate a permutation with the corresponding number?" - We can enumerate all permutations of {1,2,...n} with integer numbers from [1,n!]. An example algorithm of retrieving permutation from its index is explained here: https://www.geeksforgeeks.org/find-the-k-th-permutation-sequence-of-first-n-natural-numbers/. However, this code returns string and assumed an integer index, but in our case it can exceed integer range, remember about it. My code (https://codeforces.net/contest/1443/submission/97579828) uses this approach to retrieve permutation from index, you can look at it.

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

In editorial of problem Div2 D : How to prove that " maximizing each element of the decreasing array" is the best way to construct the increasing and decreasing array and can people tell their train of thought while arriving at above during contest.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please help me to find what I did wrong in my code.

https://ide.codingblocks.com/s/367339

In my Approach, I simply created two partial sum arrays. The first from the beginning called pre and the second from the end call sum.

→ Reply
»
4 years ago, # |
  Vote: I like it -12 Vote: I do not like it

D <= C <= B <= A <= F <= E for div2 -_- A ruined my whole contest!

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Did anybody solve div2D using segment tree like me :v

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

someone please explain how third statement is correct? According to me array should become [2 1 0 -1 2]

1.decrement from the first two elements of the array. After this operation a=[2,1,2,1,4]; 2.decrement from the last three elements of the array. After this operation a=[3,2,1,0,3]; 3.decrement from the first five elements of the array. After this operation a=[2,1,1,0,3];

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me how the divide and conquer works in Div1 D?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +14 Vote: I do not like it

    Basically, we are aiming to solve knapsack problem (precisely, calculate entries of dp array) for $$$n$$$ elements but $$$i$$$-th one for all $$$1 \le i\le n$$$ mentioned in the editorial.

    Here, we will divide $$$n$$$ arrays into two halves ($$$A$$$ and $$$B$$$), and then calculate the dp array $$$dp_l[]$$$ (resp. $$$dp_r[]$$$) if we take the first half (resp. second half) elements into account， i.e. we are free to choose any subset of the first half(resp. second half) elements. With auxiliary array $$$dp_l[]$$$(resp. $$$dp_r[]$$$) in hand, we may only focus on the initial problem for the second half(resp. first half) and merge them in the obvious way.

    btw, you may check others' implementation to get a better understanding. (That's how I understood above approach... I was confused by editorial as well)

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

      I understand , thank you very much:)

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

      Can you more explain what does it mean?

      "With auxiliary array dpl[](resp. dpr[]) in hand, we may only focus on the initial problem for the second half(resp. first half) and merge them in the obvious way."

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem C, why does Accepted one works while this almost identical one Wrong One gives memory limit exceeded . The only difference between the two solution is that I copied the contents of the loop from the wrong one and pasted it in a function, then called it instead in the loop to solve, and now I don't get memory limit exceeded using the function. Why is this happening ?

Problem C

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain me problem D of div 2. I am not getting it

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    We can decrement any suffix by 1. We can decrement any prefix by 1.

    Now we are asked if its possible to make each element of given array as 0 by performing above 2 operations.

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

      thanks but i am not getting how taking difference and subtracting it from first element and checking that it is greater than or equal to 0 give yes. Please can you explain it.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I've written a blog post to explain the solution to 1443D (D1A / D2D)

→ Reply
»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Squeezed $$$O(n k \sqrt n)$$$ solution in D1D. With pragmas submission

→ Reply
»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Good evening, this is our solution for problem C with explanation.

Video link

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In C I used multimap and it was ac,then i used map and for multiple same courier delivery time i kept summation of all the pick up time at the index of that courier delivery time.Rather than this one difference everything else was same.why it isn't working? Example 3 3 5 5 / 2 2 2 2 I kept 4 at index 3 and 4 at index 5.

Here are my submissions: AC:https://codeforces.net/contest/1443/submission/97495754 WA at TC2:https://codeforces.net/contest/1443/submission/98000111

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Div 1C is just pure genius (the making copies of graph part). Never seen this before. Just....wow.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

300iq This page is not linked with the contest problem page neither is the announcement page .. Can you please look into it

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

memory efficient DP approach for problem B: https://codeforces.net/contest/1443/submission/101710030

→ Reply
»
10 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Hi, I didn't want to make a new blog for this, so here I am. Regarding problem D.

Spoiler

Please correct me if you see a mistake. Any help is greatly appreciated.

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So, basically, for each i, we have a range of $$$[L,R]$$$. For all ranges of all element, could we choose a number $$$X$$$, such that if we create an array which will stores the value $$$X$$$ for all $$$i$$$, the array could be non-increasing ?

    → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, why is it check that there are increasing and decreasing arrays ? why not check that there are decreasing and then increasing arrays ? Isn't the problem basically boils down to whether we could make the the array decreasing and then increasing ?

→ Reply