vovuh's blog

By vovuh, history, 4 years ago, In English

All problems, except the problem D, are mine. The problem D author is MikeMirzayanov.

1353A - Most Unstable Array

Tutorial
Solution

1353B - Two Arrays And Swaps

Tutorial
Solution

1353C - Board Moves

Tutorial
Solution

1353D - Constructing the Array

Tutorial
Solution

1353E - K-periodic Garland

Tutorial
Solution

1353F - Decreasing Heights

Tutorial
Solution
  • Vote: I like it
  • +150
  • Vote: I do not like it

| Write comment?
»
4 years ago, # |
  Vote: I like it +86 Vote: I do not like it

Video Editorials for D and E

Enjoy watching!

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

    dev manus ( "GOD" for those who don't know Hindi ).

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

    Thanks stefdasca

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

    Please Keep Making Videos of Div2 Problems as well. They are very helpful. Thank you so much.

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

    The video was quite nice. It is great to see that you made the videos while the contest was going on. lol :-)

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

      Well, I full solved the contest quick enough, so I had time to do the videos.

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

    for E, I was getting TLE for the same solution. UPDATE Ok i got it, my outer loop was running n times instead of k.

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

    For E I implemented the same solution in Python. I get TLE on test 4. Are the problems not meant to be solved in python? Should I learn C++ instead?

    Edit: Including submission link https://codeforces.net/contest/1353/submission/80416176

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

      If you want to stick with Python, use pypy instead, it's faster most of the times.

      In the long term, C++ is better in competitive programming, not every time python is guaranteed to pass.

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

    Thanks!!

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

Too fast editorial!!

  • »
    »
    4 years ago, # ^ |
    Rev. 5   Vote: I like it +23 Vote: I do not like it

    F video editorial: Link

    E video editorial: Link

    D video editorial: Link

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

      Sir why can't we move from mat[i,j] to mat[i,j+1] or mat[i+1,j] if mat[i,j]>( mat[i,j+1] or mat[i+1,j]) bcz we can decrease mat[i,j] such that it becomes less than mat[i,j+1] or mat[i+1,j] whichever we are going to follow..here mat is the given matrix in the question

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

        You can decrease it. That is the question only. But when we are trying to solve the problem, we keep trying all possible values hence we are keeping the first constant, since we are trying all possible values the case you are talking about gets covered.

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

Editorial is out but nothing under tutorial section?

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

⚡Lightning speed editorial

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

Stupid question here...can someone explain the solution to first question(the last test case). Thanks

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

    first index 0, second index the big number, and the rest is 0. u can't get any better than this (if u split it up, then ur basically splitting up the sum into two, but making the sums twice as plenty). so for all cases n>=3, u do 0, m, 00000000....

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

Omg, i don't know that i can modify the set like that.

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

Problem C can be solved in O(1) as well by counting for one quadrant of the board and using symmetry the answer for the rest of the quadrants is the same as calculated. There comes out to be a formula in terms of n for the counting of one quadrant.

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

    The final formula comes out to be n*(n-1)*(n+1)/3!!

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

      $$$\frac{4 \lfloor\frac{n}{2} \rfloor (\lfloor\frac{n}{2} \rfloor + 1) (2\lfloor\frac{n}{2} \rfloor + 1)}{3}$$$

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

        Oh, now I see, it's equal to yours formula after simplification.

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

      Please Explain How u getting it?

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

        draw each iteration out, and you'll quickly see the pattern. hint: think of the layers as actual squares

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

        First, you need to get following picture:

        2 2 2 2 2
        2 1 1 1 2
        2 1 0 1 2
        2 1 1 1 2
        2 2 2 2 2
        

        So, answer is sum along this table. Now, derive formula how many zeroes there, how many ones, and so on: 0*1, 1*8, 2*16... You should get $$$\sum i(4(2i+1)-4) =\sum i(8i) = 8\sum i^2$$$

        Sum of squares is famous formula = $$$n(n+1)(2n+1)/6$$$. If you want derivation, google for it.

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

    Made a DP Solution for problem C .

    Explanation , Code

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

      This solution doesn't actually utilize dp, since you are not using the data you precompute more than once. You can remove the memoization array (dp) and the same code will run at the same time if not faster.

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

Is there a way to solve D in O(n)?

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

can anyone please explain D

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

    what he's trying to do is make a set with compare function, you can make a priority queue too.

    COMPARE FUNCTION (class) EXPLAINED: It takes a pair as input(l,r) l = left index and r = right index . Then it sorts the pair in decreasing order of length( which signifies the length of zero sub array).

    This helps us to always get the longest zero sub-array with ease, hence, we can solve the problem.

    when it comes to why he used a struct for compare function, go through the link below.

    https://stackoverflow.com/questions/16111337/declaring-a-priority-queue-in-c-with-a-custom-comparator

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

    Consider the array [1,n] with initially all elements as zero let the interval [L,R] be defined as a part of array such that such all its elements are zero.Initially this part will be [1,n].Take std::set or std::map to store this interval. But the next interval which we will take should have maximum length and least 'L'; To do that we have to change the default sorting of set using comparator function. Then everytime we take the first interval from the set calculate the middle element and insert two new intervals in set [L,middle-1] and [middle+1,R] only if left<=right for this interval.If our set becomes empty at any instant then stop. Hope it helps

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

When do our ratings change? This is my first div 3 contest, so i don't know if it's different for div 3 than it is for other divisions.

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

    A little while after the hacking phase (12 hours) ends

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

    It will change after 12 hours (after passing on whole test-sets and after hacking phase will end)

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

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

Interesting problems! and fast editorial

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

Why B have more submissions than A?

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

    We decided to allow $$$O(n^3)$$$ solutions because we thought that this greedy observation can be not so obvious for Div.3 participant and implementation part can be difficult, but... We were so wrong :)

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

fastest editorial in the NEWS

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

What is the correct path for the F problem in 2 example? (btw in this example n = 5 m = 5)

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

Is vovuh competing with USAIN BOLT

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

How to solve 'D' using priority queue can someone help me with comparator function in priority queue.

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

    i used this


    pi = pair<int,int> struct cmp { bool operator()(pi const& p1,pi const& p2) { int f = p1.second- p1.first ,s = p2.second - p2.first; if(f == s){ return p1.first > p2.first; } return f < s; } }; priority_queue<pi,vector<pi >, cmp > pq;
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    change the positive to negative for reverse priority queue

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

    Approach to solve problem D with priority queue : [ With C++ pseudocode ]

    1. Create a structure for segment :
    struct segment 
    {
    int start;
    int end;
    };
    

    ``

    1. Create a comparator function by overloading the () operator in a struct such that the top of the priority queue contains the segment which has a greater length and in case of equal lengths, the element with smaller start position (left segment) is at the top.
    struct comp{
    	bool operator () (segment l1, segment l2) 
    	{
    		int len1=l1.end-l1.start+1;
    		int len2=l2.end-l2.start+1;
    		return (len1<len2)||((len1==len2)&&(l2.start<l1.start));
    	}
    };
    
    

    Declare a priority queue in main() :

    priority_queue<seg,vector<seg>,comp> pq;
    

    If you don't understand this syntax, go through this article :
    Priority queue for a struct in C++

    1. As initially , the array contains all zeros. So, insert {0, n-1} to the priority queue initially.

    2. Iterate for all numbers 1 to n and pop the top segment, in the priority queue. Place the number at appropriate position as indicated in the question. Suppose the number is placed at an index ind
      Now, there are 2 new segments, which needs to pushed into priority queue:
      I. { start,ind-1}
      II. { ind+1,end }
      (Check for the corner case, when start > ind-1 or ind+1>end)

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

      You don't need separate struct for comparator. You can include it in seg itself. look here for example: 80120262

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

can anyone explain this submission of 300iq?

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

    This is the minimum subarray sum problem.

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

      Thanks a lot bro! I got it now.

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

      Can you explain a bit ? I didn't get it. What his solution is exactly doing?

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

        First he separates the places whose index%mod value is same..

        Now he may have a string like consisting of 1s and 0s

        He has to light off all the ones outside of these places...

        And for the new string, his target is to create a contiguous block of 0s, then a contiguous block of 1s and then a contiguous block of 0s..

        Now solving this contiguous part making can be done using minimum/maximum subarray sum problem.

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

          please EXPLAIN! how to make the new string a contiguous block of 0s, then a contiguous block of 1s and then a contiguous block of 0s.. by using maximum subarray sum problem??

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            Rev. 3   Vote: I like it +6 Vote: I do not like it

            Consider 1in / 0in = the number of 1s/0s inside the block of 1s and 1out/0out = the number of 1s/0s outside that block. Then the cost for a given block of 1s is equal to 0in+1out (because we need to transform the 0s inside the block into 1s and the 1s outside into 0s). Then we can see that 0in+1out = 1total-1in + 0in = 1total-(1in-0in). We want the cost to be minimum so that means we want (1in-0in) to be maximum possible, so we pick the subarray with maximum sum (after replacing 0s with -1).

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

              thankyou so much lucaperju you finally made me understand something which i was wondering for almost a day. Man you are a saviour !

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

              ohhh..thanks it was helpful

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

          How is this contiguous part solved by minimum/maximum subarray sum problem?

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

            So, according to the explanation of lucaperju we want to find the maximum value of 1in-0in among all the subarray. Now, if we define a variable curr_sum and whenever we encounter a '0' we subtract 1 and whenever we encounter '1' we add 1. So effectively, by doing this we are keeping track of 1in — 0in. Now when we are doing maximum sum subarray problem then we are keeping track of the sum of subarray and maximising it, but instead here, we want to keep track of 1in — 0in, so in the logic of maximum subarray problem, we will change the definition of the variable that keeps track of the current sum of subarray. Here, r is the rightmost index of the subarray. curr_sum is the current value of 1in-0in. max_sum is the max_sum of the 1in-0in among all the subarrays ending before r. r = r + k because we are considering all the elements that gives same remainder with k; This code snippet gives maximum value of 1in-0in among all subarrays.

            If you have a problem in understanding why this is working, I would advise you to watch this video first: https://www.youtube.com/watch?v=86CQq3pKSUw

            Full submission: https://codeforces.net/contest/1353/submission/80282348 ~~~~~ while(r<=index2){ if(arr[r]==1){ curr_sum = max(arr[r],curr_sum+1); max_sum = max(max_sum,curr_sum); } else{ curr_sum = max(arr[r],curr_sum-1); max_sum = max(max_sum,curr_sum); } r = r + k; }

            ~~~~~

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

vovuh , can D be solved using recursion ? Thanks.

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

can someone explain why its TLE?

80160568 it is not nlogn complexity?

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

    I'm not sure, but maybe something's wrong with PriorityQueue. I replaced it with heapq in your solution and it got AC 80179294.

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

      хмэ. понял/принял. но все равно не понятно почему так, в документации написано что PriorityQueue это обертка над heapq. спасибо

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

        Обёртки по умолчанию работают хуже, так же это касается например queue/deque

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

Super fast editorial, time complexity O(1), great!!!!

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

How to prove that optimal solution for A is 2*m if n>2 ?

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

    Isn't that obvious? If you consider each unit independently, then it's obvious that you cannot obtain the answer more than two using one unit (because this is $$$1$$$-dimensional array). Thus if the number of units is $$$m$$$ then the maximum possible answer is $$$2m$$$.

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

      Thanks.

    • »
      »
      »
      4 years ago, # ^ |
      Rev. 2   Vote: I like it -9 Vote: I do not like it

      Not really , maybe it is because I don't have much experience.It is the first time I guess , I am seeing this idea. B-D were familiar.

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

      Hi can you help in getting why my code is giving wrong answer on testcase 2 for Problem F, My approach is different from the editorial, I understood the editorial solution and got AC with that approach but I am not able to get why my approach is giving Wrong Answer, I have asked about it to many people but got no replies. I am unable to generate a small testcase where it is failing, I tried on several testacases but all are working fine, can you please help me by telling what is going wrong in my approach? Actually my dp[i][j] stores a pair of integers, whose first element stores that what should be the optimal value of ar[i][j] to reach (n, m) and second element denotes the minimum total cost required from (i, j) to (n, m) with that value of ar[i][j].

      Here is my solution link: https://codeforces.net/contest/1353/submission/80376675

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

    Let n be odd and suppose you divided m into (n/2) numbers such that one number is (m/(n/2) + m%(n/2)) and other (n/2) — 1 segments of (m/(n/2)). So the optimal answer, in this case, is to place these numbers on even positions i.e. 2, 4. In this case, you can observe the maximum you can get is 2*m. However, if n is even, you will get less 2*m sometimes. So, in general, the optimal way is to place m to one position such that it's not ending position of the array. But for n==2 there is not such positon.

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

      I didn't go through your solution as I already understood one by Vovuh. But thanks for giving such a detailed solution. It might come in use to someone else.

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

is there any chance of solving E by binary search ???

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

Did anyone solve E with D&C?

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

I see a lot of priority queue submissions for problem D. Can anyone who has done using pq explain their solution? I guess it compensates for the comparator function written in editorial. Thanks!

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

    The segment should be sorted by size (biggest first), then by index (smallest first). One can write an comparator to do this comparation. Or one can put the values into a pair, change the signs of the size of the index field (the second) and use the default comparator of the prioriy_queue.

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

So 1s can take nlogn complexity for n<10^5. Can someone help me understand the time complexity and time per test case relation? I missed D just because I thought nlogn wouldn't work fml.

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +5 Vote: I do not like it

    There is a thumb rule stating that it takes roughly $$$1$$$ second for $$$10^8$$$ operations to get executed. Hence, $$$10^5$$$ operations are likely to take $$$5*10^5*10^{-8}$$$ second or $$$0.005$$$ seconds which is well within $$$1$$$ second.

    Disclaimer: this is a rough estimation. Constants might affect this calculation to a great extent!

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

      that makes me curious, when standard computers get significantly better will time limits also be adjusted for problems?

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

        You can already see that happening in older problems like this. The time your solution takes is multiplied by 2 to justify the change in speed between computers 10 years ago and computers now.

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

I've solved D using set, it gave me Runtime error on 3rd pretest. Whereas, it passed using Priority queue. (using set) 80128604, (using priority queue) 80135811. Can someone explain the reason, please.

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

    Iterator p becomes invalid after you erase the first element. Just move that line backwards a bit. 80179242

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

Quick Tutorial

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

I think I did not fully get E.

I understand that there are $$$k$$$ posibilities for positions of on-bulps, and for every such position we need to find the first and the last one of the optimal solution.

But I do completly not get how the calculation of the dp[] values work. How do we consider the end of the block of on-bulbs? The editorial text at this point is not really clear.

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

    I have a simple solution for E 80161569

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

      What is $$$dp[i]$$$ in your code. The min value we can get if first on-bulb is at position i, plus some..values?

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

        I think of it like

        $$$000000001(k - 1 \ lamp \ 0)1(k - 1 \ lamp \ 0)1(k - 1 \ lamp \ 0)1(\leftarrow i)00000000000$$$

        $$$a_i$$$ be the state of the lamp $$$i$$$

        $$$sum_{l, r}$$$ be number of lamp is on at the initial moment in $$$range[l, r]$$$, this is just prefix sum.

        So let $$$dp_i$$$ be the minimum move we can make first i lamp satisfy the condition and lamp i is on

        We get following formula:

        $$$dp_i = min(sum_{1, i - k}, dp_{i - k}) + sum_{i - k + 1, i - 1} + !a_i$$$

        Because if it ends at $$$i$$$ all lamps from $$$i + 1 \rightarrow n$$$ need to be off so the answer is

        $$$\min_{i = 0}^{n} dp_i + sum_{i + 1, n}$$$

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

      very nice solution, it took some time for me to get it,

      so here I try to make more clear for those who are facing difficulty in understanding it.

      Please keep on referring the code below to understand better :)

      we will maintain dp array to get our answer,

      1. dp[i] represents cost up to indx 'i' such that the last turned on lamp is 'i'th lamp

      we can come to indx 'i' from previous indx i.e 'i-k' and can have two states

      1.  All the lamps upto indx 'i-k' are turned off ( it is nothing but prefix sum upto 'i-k')
      
      2. Last turned on lamp is 'i-k'th lamp         ( it would be stored in dp[i-k] )
      
      we will take minimum of the above two

      this is not enough we also need to turn of lights between 'i' and 'i-k'
      so we add (pre[i-1] — pre[i-k] ) to the one we just calculated above

      and at last, we also need to check if the 'i'th lamp is turned on or not

      so we add (s[i-1] != '1')    // note assuming that dp array is 1 based indx and string is 0 based

      hence we calculate


      dp[i] = min( pre[i-k], dp[i-k] ) + (pre[i-1] - pre[i-k]) + (s[i] != '1');

      as we assumed that 'ith' lamp is the last turned on lamp ( we need to turn off the remaining lights ( indx > i) )

      hence answer at every step would be calculated as :

          ans = min( ans, dp[i] + (pre[n]-pre[i]) );
      
      
      CODE
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Thanks for the explanation. I can now sleep peacefully :)

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

        Thanks a lot, I didn't come up with an O(N) DP.

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

Is this fair? @vovuh @MikeMirzayanov

Kindly ban this user who is using multiple handles and hacking one account using the other account-

mamun360 and 550mamun

https://codeforces.net/contest/1353/submission/80148191

https://codeforces.net/contest/1353/submission/80124724

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

    Well, they are not getting any kind of advantage by doing this. I don't get the reason why some users are doing this.

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

So good contest, thanks

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

Can D be Solved with recursion ? My recursive solution is failing

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

    Yes

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

      can you explain how you solved it using recursion ! here is my code :

      int res[MAX] = {0} ; 
          int val = 1 ;
          void action(int start,int end,int val,int t)
          {
              if(start>end)
                  return ; 
              int length = end - start + 1 ;
              int mid = (start + end)/2 ; 
              db(mid,t);
              res[mid] = val ; 
              if(length&1)
              {
                 
                  action(start,mid-1,val+1,t);
                  action(mid+1,end,val+2,t);
      
              }
              else
              {
                  action(mid+1,end,val+1,t);
                  action(start,mid-1,val+2,t);
              }
          }
      

      can you point out the mistakes ?

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

        while making function call i.e in action you cant just select part of previous segment bcz it may case that their exist segment with greater size that is not explored yet . So you need additonal data structure which can help you decide what will be your begining and end for your next call .

        for example segment which is being explored now have size 7 so you mark the middle element . But after marking middle element you can't just call(be,m-1)or call(m+1,en) . bcz their may be case that their exist segment of size 5 which is not explored yet .

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

        You are trying to solve the subproblem on one segment of the splitting first, and then going to the other segment. But the required solution is for you to solve only one step in either direction. This cannot be done using recursion. You check the outputs of your code for sample cases and you will get a clear picture of what I am saying.

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

Hi, could anyone explain in problem F, why a certain cell doesn't change its height? How to prove it?

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

    Suppose there is any optimal path. Now, look at array of heights in all steps $$$h_i$$$. You need somehow make them into array of consecutive numbers, for example: 3,4,5,6,7 or -3,-2,-1,0,1. First, understand that resulting array has values of form: $$$i+b$$$ where $$$i$$$ is index of value and $$$b$$$ some constant. We need to find value of $$$b$$$. You can't increase any of $$$h_i$$$ so you want such $$$b$$$ so $$$h_i$$$ >= $$$i+b$$$ for each $$$i$$$. In other words, it's condition to be able to make from original heights, heights of consecutive numbers. From the other hand, we need to have maximum $$$b$$$ among all possibilities to reduce heights as less as possible. Now two points of view:

    • let say you set $$$b$$$ to some very big value like 1e18. then for each $$$i$$$ you'll have $$$h_i$$$ < $$$i+b$$$. Lets call those indexes like "bad" indexes. Now, decrease one by one $$$b$$$. At some point number of "bad" indexes will decrease. Then, it'll decrease again. Until their number hit zero. Zero number of "bad" indexes means that it's maximum $$$b$$$ that we need. Also, it's time when last $$$h_i$$$ become equal to $$$i+b$$$. As you can see, this index $$$i$$$ is our non-changing height.

    • Other view is: rearrange $$$h_i - i >= b$$$, now we can make new array $$$z_i = h_i - i$$$ and find minimum here. Index of minimum is index of height that won't change.

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

In problem F, why is Now we can notice one important fact: in the optimal answer, the height of some cell remains unchanged true?
And how to approach to that result?

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

    Imagine that you have a path, on which every cell has been decreased at least once. You can increase each value by 1, which still produces valid path, but gives us better result. Doing that multiple times leads to some cell being unchanged.

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

Oof I used segtree instead of prefix sums for E like an idiot :(

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

In C: what is this wrong with this logic? logically we are counting the outer part of the odd squares * distance from the centre, which is (2*i+2*(i-2))*(i-1)/2 i.e adding 1 on both the sides(left and right of the previous odd square ) to get 2*i and remaining part(above and below) becomes 2*(i-2) and the outermost square is at a distance of (i-1)/2 hence the expression (2*i+2*(i-2))*(i-1)/2

for(int i=3;i<=n;i+=2)sum+=(2*i+2*(i-2))*(i-1)/2;

Example

| | |
| 0 |
| | | 

"|" this denotes the outermost square which has elements 2*3+2*(n-2)=8

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

    We are moving from the center of the square grid, to the outermost square. It is obvious, that on moving towards the bigger square we find that, number of cells for each square we reach is 4*(n-1) where n is an odd number dimension of grid. Now, as we know that how many cells are at a particular distance from center. We simply iterate all odd numbers from 0 to size of grid and multiply each with their distances.

    for i in range(0,n+1): sum+=4*(i-1)*dist; dist+=1

    Also, if you look closely you find that after doing a little rearrangement the number of moves, boils down to just finding the sum of squares upto floor(n/2) and multiply result by 8. 80118906

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

After reading the tutorial of F, I am still confused.

If I got it right, the b(i, j) represents the real height of cell(i, j). So how could a(i, j) < b(i, j) happen? We can only decrease the height, so the real height of cell(i, j) must be less or equal to the initial height.

Can anybody explain that to me? Thanks a lot.

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

    a[i][j] is initial height and b[i][j] is final height.

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

      Yes I got it. My thoughts go wrong elsewhere. Thank for your reply.

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

Problem statements are very clear and even a beginner like me could understand all of them very well, solved ABC.

In problem D, I thought I have to come up with a solution that can have $$$O(t.n)$$$. Here $$$t.n = 10^9$$$ that made me confused as it might give TLE.

I also didn't understand: It is guaranteed that the sum of n over all test cases does not exceed $$$2⋅10^5 \sum n ≤ 2⋅10^5)$$$.

Please teach me, how I should calculate the complexity properly in this kind of problem? Please explain that statement as well. Thank you.

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

    It is guaranteed that the sum of n over all test cases does not exceed 2e5. This means that say, u have n=n1 in 1st testcase, n=n2 in 2nd testcase and so on. Then (n1 + n2 + ...... n(t)) will not exceed 2*(10^5). In short you don't need to multiply t with n . You can calculate the complexity using n = 2*(10^5) only.

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

I have doubt in B sol . what if the 3rd case would be

5 3,

9 9 10 10 10,

1 2 3 4 5,

this??

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

    all element of array a will be considered

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

    In problem B, it said

    Your task is to find the maximum possible sum you can obtain in the array a if you can do no more than (i.e. at most) k such moves (swaps).

    No more than k moves, so you can just do 2 moves in your example

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

      why two moves?? it will reduce the answer, if you will do 0 move answer will be maximum for this case

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

        Yes, 0 move will be the maximum, and 2 moves give the same answer, I just give out an example to show you that you don't need to do exactly k moves

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

      when run the exact same code in code chef compiler , the output was

      48

      but, it should be 39

      which indicates that there is a problem in solution .

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

        It says at max k moves. It doesn't mean that we have to perform all k swaps. We can choose to use less than k swaps if that gives us the optimum answer.

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

          But in the test cases the solution should be 39 , or it would reject the solution .

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

            What do u mean by it will reject the solution. ? The answer should be 48 only. 39 will give you a Wrong Answer Verdict.

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

              ok ,thank you got it.

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

how to solve F .i didn't understand second paragraph of F editorial.

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

Issue solved.

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

    You can generate some random input and compare result of your solution with of the editorial solution. I am sure you can find a bunch of short counter test cases.

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

Someone please point out the mistake in my approach for 1353F — Decreasing Heights

For a fixed value of a[0][0], I can find the min number of operations required to reach a[n — 1][m — 1] (if possible). The approach for this is pretty similar to the one explained in the tutorial.

ll solve(vvl &a, vvl &e, int &n, int &m)
{
	ll z;
	f(i, 0, n)
	{
		f(j, 0, m)
		{
			if(i == 0 && j == 0)
			{
				e[i][j] = 0;
				continue;
			}
			z = i + j;
			e[i][j] = LLONG_MAX;
			if(j > 0)
			{
				if(a[i][j] >= (a[0][0] + z) && e[i][j - 1] != LLONG_MAX)
				{
					e[i][j] = e[i][j - 1] + (a[i][j] - a[0][0] - z);
				}
			}
			if(i > 0)
			{
				if(a[i][j] >= (a[0][0] + z) && e[i - 1][j] != LLONG_MAX)
				{
					e[i][j] = min(e[i][j], 
						e[i - 1][j] + a[i][j] - a[0][0] - z);
				}
			}
		}
	}
	return e[n - 1][m - 1];
}

Now, I try fixing different values for a[0][0] (<= a[0][0]), and the maximum value of a[0][0] for which we are able to reach a[n — 1][m — 1] is optimal value of a[0][0]. For this, I used binary search.

Also the minimum value of a[0][0] for which we'll definitely get an answer is somewhere close to -1 * (n + m).

ll st = -300, en = a[0][0], z = a[0][0], ans = 1e18;
	while(st < en)
	{
		ll mid = ((st + en + 1) / 2);
		a[0][0] = mid;
		ll y = solve(a, e, n, m);
		if(y != LLONG_MAX)
		{
			st = mid;
			ll temp = y + (z - mid);
			ans = min(ans, temp);
		}
		else
		{
			en = mid - 1;
		}
	}
  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    I don't think the maximum value of a[0][0] for which we can reach a[n — 1][m — 1] is always the optimal value of a[0][0]. Consider this case:

    3 3
    5 5 6
    9 9 7
    9 9 9

    The answer is 2, but if you use the maximum value of a[0][0], which is 5, you'll need more than 2 steps.

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

      Now, I try fixing different values for a[0][0] (<= a[0][0]), and the maximum value of a[0][0] for which we are able to reach a[n — 1][m — 1] is optimal value of a[0][0]. For this, I used binary search.

      What I meant was, the max value of a[0][0] has to be less than or equal to the original value of a[0][0].

      Here the max value of a[0][0] for which we are able to reach a[n — 1][m — 1] is '1', and hence answer = 4.

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

        I'm sorry, added a different test case now.

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

        Let M be a very large number

        Try this case:

        2 2

        4 M

        4 6

        You can reach the last cell while keeping a[0][0] = 4 and by decreasing M to 5 thus incurring cost M — 5.

        Whereas the optimal solution is to reduce a[0][0] and a[1][1] by 1 each incurring total cost 2.

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

OMG! A was that easy! xD I did it in a very bad way :( my one-> 80090151

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

Anyone solved E recursively ? Please reply with your submission. I'm having trouble understanding the editorial and iterative code.

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

I have solved D using priority queue. When I am running my code for T=1 and n=10000, it is taking long time to execute. But I submitted the solution and it got accepted. In question n<=2*10^5. Then why it is not showing TLE during submission. My submission 80166026

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

    Now don't say you were using online compiler as it was the queue time of online compiler

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

For problem D

// set element is pair<segment_length,pair<left,right>>

define pi pair<int,int> bool cmp(pair<int,pi> a, pair<int,pi> b) { if(a.first != b.first) return a.first < b.first ; else return a.second.first < b.second.firstd ; } I use this type of function while sorting a vector using sort(). But it is not working for set declaration. Do I always need to make a structure as shown in editorial or am I doing some error? Please help.

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

    You either define struct with implemented operator, or use hacks based on fact how pairs compared under hood (lexicographically), or you need to define class or struct implementing operator () like this:

    struct cmp {
        bool operator() (pair<int,pi> a, pair<int,pi> b) {... comparator code ...}
    };
    // then your set will be:
    set<pair<int,pi>, cmp> my_set;
    
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    oh, I didn't check what is in editorial. Here is what I thought is there, this is from my code:

    struct seg {
    	int l, r;
    	seg (int l = 0, int r = 0) : l(l), r(r) {}
    	bool operator < (const seg &s) const {
    		int a = r - l;
    		int b = s.r - s.l;
    		if (a != b)
    			return a > b;
    		return l < s.l;
    	}
    };
    
    set<seg> segs; // usage.
    
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

For problem D: If anyone like me hates to make a custom comparator, then just keep values in your vector or pair in the order in which you want it to be sorted. For example, here length is more important than start index, so make it the first value of the vector.

In case of a tie we need to check on the basis of start index, so make it the second value. But, since we want it to be on the basis of the min index. So, if we were using max priority queue, then this value should be negative(to reverse the effect).

Code: 80167424

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

    Just make the length negative, that's solved !!!!!. so initially make s.insert({-n,{1,n}}); Btw i also hate comparator function its a waste of time

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

    Thanks!!!

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

i didn't get problem C! !

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

    You are asked to count the minimum steps to bring everything on one point. Initially every block on board has one element. Your task to arrive at solution was to bring everything at center.

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

Hello guys,

I tried a different DP for Problem E. For each period from 1 to k, I stored the value of last and the first appearance of 1 in the string in an array for each period and stored the total number of ones in 'sum'. Then iterating for a period, as all periodic position between 'first[i%k]' and 'last[i%k]' has to be either one or zero,I chose a minimum value as 'ans' and added the leftover ones in the array in the 'ans'. Still I am getting WA in test 2.

Solution Link : https://codeforces.net/contest/1353/submission/80167997

Please help

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

I wan't to share my solution for 1353F - Decreasing Heights. Because I think it's simple.

First, consider we have optimal path. Let's look at its array of initial heights $$$h_i$$$ in order of visit. Resulting heights should be $$$i+b$$$ for some constant $$$b$$$. And answer is $$$\sum (h_i - (i+b))$$$ We know that $$$i$$$ is also number of step. Notice that any path from cell $$$(0,0)$$$ to cell $$$i,j$$$ require $$$(i+j)$$$ steps. So, any cell $$$(i, j)$$$ can be only at index $$$i+j$$$ in array $$$h$$$. This means from this height will be subtracted $$$i+j+b$$$ where $$$b$$$ is constant that we don't know. Now, let $$$c_{ij} = a_{ij} - (i + j)$$$. Consider array $$$d_i$$$ to be values of $$$c_{ij}$$$ that we travel across optimal path in order of visit. Then answer is $$$\sum (h_i - (i + b)) = \sum (h_i - i - b) = \sum (d_i - b)$$$ because $$$d_i$$$ is exactly height without index of step. The sum has exactly (n+m-1) elements (cells required to travel). So answer is $$$(\sum d_i) - (n+m-1)\cdot b$$$. This means, for known b we only need to find path with minimum sum.

Now, what is $$$b$$$? It is the minimum value across the path. Why? Well, you may look here: https://codeforces.net/blog/entry/77373?#comment-622300 Probably it will help. I'll just add. Value $$$b$$$ can be used if for each $$$h_i >= i + b$$$ rearrange $$$h_i - i >= b$$$ and we have $$$d_i >= b$$$ so $$$b$$$ should be less or equal than all of values in $$$c_{ij}$$$ across the path. Also, we want it to be maximum. Thus, it's just minimum among all $$$c_{ij}$$$ across the path.

The only issue left: for different paths there is different minumum. Solution: fix minimum to be $$$b$$$ and then find minimum path with all cells in the path greater than $$$b$$$. Change $$$b$$$, find minimum path again.

My implementation: make array $$$c_{ij}$$$, now find minimum path using dp. Remember answer. Because we know answer, we also know minimum along all table. now, ban all cells with value equal to current minimum. This will forbid any path having current minimum cells. Find minimum path again. Also, find minimum among allowed cells. Update answer. Ban cells with current minimum again. And so on. Repeat this cycle until no valid path left.

This works in $$$O(n^4)$$$ Source: 80165280

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

    Here is cleaned source. 80174342. In previous source dp was filled diagonally (I'm retarded). And, there was check for int64 overflow.

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

I managed to find a DP Solution for Problem C . To compute a particular solution for $$$n$$$ , I recursively calculated the solution for $$$(n - 2)$$$, which is like emptying out the inside of the board and keeping only a border of figures around the square of dimensions $$$(n - 2)\times(n - 2)$$$.

Picture

Then , with simple mathematics , it can be shown that , this border of symbols can be converged to the center in $$$2\cdot(n - 1)^2$$$ moves .

Thus, the solution becomes : $$$solve(n) = solve(n - 2) + 2\cdot(n - 1)^2$$$ for $$$n > 1$$$.

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

    I have doubt, can you help? I tried an approach that is similar to yours, but in my case, the time complexity is O(N * N / K) which will give TLE. But you have done it in O(K * N / K) => O(N).

    But, with what I am thinking, we need to consider each index as start and then take jumps of k. How does your code check other cases with considering only K indices as start?

    My TLE approach: 80175775

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

      Explanation to my solution: Basically what we need in the string is, for every consecutive 1 in the string, the distance has to be equal to k. Now consider all the characters that have their index modulo k as equal (i%k) because we wanna make string k palindromic. For example if we have string as 10100 and k=2 then we can see that for indices i=0,2,4, i%k==0 and for indices i=1,3, i%k=1. So we have to only evaluate for two cases in the mentioned case in the first for loop that is running from 0 to 1(0 for calculation of 0,2,4 part and 1 for 1,3 part). Generalizing this will be running a for loop with variable i between 0 to k-1 inclusive. Now for every i we will see into the sequence by running a for loop with variable j from i, incrementing j with k and limiting j less than n(in above case if i=0 then we will look into 0,2,4 indices and if i=1 then we will look into 1,3 indices).

      Now comes the logic part. Remember we have choice of changing state of any bulb. So firstly for every j, we will see that if changing it's state is worth doing or not. Consider the following example, n=11,k=2 and string is 00010001000 then we don't need to turn on the bulbs at indices 1,9(because what we want is just k length gap between consecutive 1s). We will just turn on the bulb at index 5 and we are done with one move. Consider another example, n=11,k=2 and string is 01000001010. In this case, rather turning on bulbs at indices 3,5; we can just turn off the bulb at index 1 to minimize number of moves. These examples show that the method of counting 1s and 0s in every kth character and subtracting total ones in the "sequence" from number of ones in the "string" and then adding number of zeros in the "sequence" to that will not work.

      That's why we can have a variable d which will display if we have s[j]=='1', is it worth to let it remain to '1' or is it worth to make it '0' and similarly for s[j]=='0'. That's why when we have s[j]=='1' then we will just increment d assuming that it will remain '1'. But when we encounter '0', we make d as max(0,d-1); because if we had encountered one '1' or zero '1' then changing that previous to zero will cost us 1 or zero move respectively, but if we had encountered more than one '1's then changing the current '0' to '1' is worth doing. We will save this d in co for every position in the "sequence"(talking about loop on j) we visit and we will try to maximize this co because you can say that d is the number of free '1's you are getting overall and we will maximize these free '1's. For every "sequence" (talking about loop on i) we will try to minimize m which is the number of total '1's in the "string" minus total free '1's in the sequence you are hoping to become k palindromic. the sequence which will have minimum m will be candidate to the answer but we are only asked to write total moves which are m.

      I hope this will help.

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

In problem F, I had used binary search in range(-201 to a1,1) to find the optimal height of (1,1) position.But it didn't work. Can anyone explain why binary search property failed here?

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

Please someone tell me the mistake in my approach for E my submission

Approach

  1. for every possible series with period k I am building up a dp[i][j] where i is the state 0(lamp off) or 1(lamp on) for jth lamp.

  2. for every series the table value only contains the count of moves applied from the first 1 in that series to the last 1.

3.to get minimum number of moves = min(#moves to turn on series i + #moves to turn off every other series) for every series.

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

    At same test case my submission was going wrong and I had almost similar approach. Probably to get minimum number of moves, you had to check whether turning that bulb on in the series is worthy or not. For example, lets say we have n=11,k=2 and sequence is 01000001010. Here, bulbs at index(0-indexed) 1,7,9 are turned on. Now if we turn on the bulbs at index 3,5 then it is gonna cost us two moves. But if we turn off the bulb at index 1 then it will only cost 1 move. I think that's where this solution of yours might go wrong. You can look at this. https://codeforces.net/contest/1353/submission/80167362

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

Is there an O(N*M*(N+M)) solution for problem F? I was unable to find one, but luckily the O(N^2 * M^2) solution worked just fine for me.

  • »
    »
    4 years ago, # ^ |
    Rev. 2   Vote: I like it -16 Vote: I do not like it

    I don't know slope trick well hence I might be wrong, but the question seems similar with dp, but if it is applicable here it is solvable in nmlog(n+m)

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

Is D solvable using segtree(by substituting 0 with 1 and updating each element with negative infinite values) ,have anyone done D in this way.question gets converted to max subarray sum with leftmost boundary.
Update::
my submission using segment tree
using priority queue without custom comparator

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

For problem F editorial, "in the optimal answer, the height of some cell remains unchanged". What is the proof of that?

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

    Imagine if all cells were changed, and the minimum number of changes applied to a cell was $$$x$$$. Then you could have done $$$x$$$ fewer changes on each cell and not affected any of the paths. It follows that in the optimal solution, $$$x$$$ must be $$$0$$$, and thus at least one cell must be unchanged.

  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +19 Vote: I do not like it

    Check out this picture for some intuitions.

    Basically if none of the positions on the final path have unchanged heights. We can shift up the final heights therefore getting a lower total cost.

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

    Let's say there is a path in which we have decreased every element value. Let "x" be the minimum amount of decrease in any value on the path. We can increase every element on the path by "x" and still the path will remain valid. But notice that we have just made the element which had least amount of decrease to be same as it's original value.

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

Well commented and clean code for E
Submission — 80186993

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

https://codeforces.net/contest/1353/submission/80187990

using heap for D problem, gives TLE in python, any tips? (code is working for all sample cases)

using (length of subarray, [left index, right index]) in queue

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

How about this approach for E: I made a 2-D dp as dp[N][2] where if dp[i][j] represents minimum number of moves to make [1....i] k-periodic and the last character as j. Now dp[i][0] can be minimum of dp[i-1][0] and dp[i-1][1] plus state of ith character. Now, when we want to put 1, if (i<k) then this would be the 1st one till now and dp[i][1]= state of ith character+number of ones in [1.....i-1] because we need to make all ones before this one as zero. If (i>=k), we have 2 options: if this the 1st one till now we will do as in previous case, and if it is not the 1st one, dp[i][1]=state of ith character + dp[i-k][1] + number of ones between [i-k+1......i-1]. In the end, we can do min(dp[n][0],dp[n][1]).Solution Link:80187295

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

Great Editorial.

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

Please tell me what is wrong with this code?(E) https://codeforces.net/contest/1353/submission/80154768

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

I have a doubt in Problem B .

The solution given in the tutorial is O(nlogn). If we use buckets, can we do it in O(n).

Basically,

Take input array A(in a bucket array of size 30) — O(n)

Take input array B(same as above) — O(n)

While loop, two iterators, for the bucket arrays, — O(c*n)

Total = O(n) Is this correct?

EDIT- Here's is a link to my submission, you can check to see how to do away with sorting by using "bucket array" LINK

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

    Not sure what a "bucket" does, but somehow it has to sort the elements. Which is the logn factor.

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

      I've updated the comment with link. You can have a look to see what I mean by "bucket".

      Basically, since the elements are in the range [1,30]. I have an array of 30 elements, all initialized to 0. When taking input in some variable x, you do the follwing —

      arr[x]++;

      You can check the submission for the whole solution. I think its O(n).

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

        You are right. Using the fact that not only the size of the array but also the values are limited to $$$n$$$ you get along without sorting.

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

For problem D, one can also avoid the comparator function (if one feels uncomfortable using it) by modifying the set a bit:

set< pair <int, pair <int, int> > > s; 

We can insert values as follows:

s.insert({-length, {left, right}});

The negative value of length makes sure that the maximum element is at the beginning.

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

Can anyone pls explain the intuition or proof behind the last line os solution of F. The line is -" Now we can notice one important fact: in the optimal answer, the height of some cell remains unchanged."

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

Can anyone help me with E? This is my submission 80196393

I'm getting WA on 71st test case on test 2.

P.S. Spent a lot of time debugging it.

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

An easier solution for E(at least more understandable)- let our answer be number of ones in the string(because "0000...000" is also acceptable)

Now let say ith position has 1 in resultant string then we will calculate left cost and right cost which means the cost because of left substring(1, i-1) and right substring(i+1,n).

LEFT COST ---LEFT_COST[I]=min(cost of having all element in left to zero, LEFT_COST[i-k]+number of ones in substring(i-k+1,i-1))+(s[i]=='0') number of ones in substring(i-k+1,i-1) is added because u don't want any one between i-k to i as it will decrease the period to lees than k. and first term and the window term can be calculated easily by prefix function.

Similarly RIGHT COST ---RIGHT_COST[I]=min(cost of having all element in RIGHT to zero, RIGHT_COST[i+k]+number of ones in substring(i+1,i+k-1))+(s[i]=='0')

Now the total cost of having s[i]=='1' in the resultant string is COST[i]= s[0]=='1'?(LEFT_COST[i]+RIGHT_COST[i]):(LEFT_COST[i]+RIGHT_COST[i]-1); try to find out why that -1 is in above term

now traverse from i=1 to n and update answer as min(answer, COST[i])

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

Can someone explain me how did he come up with the formula of dpi[p] in the problem of kth-periodic garland(Prob 1353E)??

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

Hi all, why is the time complexity of D nlogn? Is sorting always logn?

Also, I'm a beginner and I'm not sure why this code is getting TLE. Am I doing something differently from the editorial? 80201800

Thank you for your help :)

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

    Good sorting techniques are O(nlogn). There's no sorting technique with a complexity of O(logn).

    You sort all the numbers for every iteration of the for loop so your complexity turns out to be O(n*nlogn).

    Use heaps to do what you intend to do. Sorting for every iteration will time out here.

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

The tag for Problem F also contains "$$$dfs$$$ $$$and$$$ $$$similar$$$". Does anyone know the approach?

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

I have solved 1 problem(A), yet my rating is decreased. Would someone please tell me the reason?

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

    As a new user your rating is initially 1500. This is a completly arbitrary value, so it takes some contests until your rating is on a more realistic level. Solving one problem in a Div3 contest is seen from a rating perspective some hundred points below 1500.

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

      Ohh, I got that bro. So if I solve Div2A then what will happen?Shall i touch the rating of 1500? Thanks for your reply

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

        The calculation of ratings is based on ranking in contests. The changes in ratings of people sum up to zero.

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

          thanks

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

            So... did it went well?

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

              I am now understanding the system first. will participate in contest bit latter.Actually I am a clear newbie. What is meant by rated problem?whereas every problem have a rating..

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

                The problems in the problemset have a "rating", too. It is an indicator of the difficulty of the problem. But this problem rating has nothing to do with contests, it is just usefull while practice.

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

                  I would be glad if could make result like you in contests. Will you please help me grow guiding me in the way that you have followed?

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

                  Just practice, there is no silver bullet.

»
4 years ago, # |
  Vote: I like it -9 Vote: I do not like it

Is there something wrong with the time complexity in D part.

n=order of 10^5

we are able to solve in nlogn

and test cases=order 10^4

But time limit is 1 sec which only supports 10^8... so why is the solution not giving tle ?

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

    "It is guaranteed that the sum of n over all test cases does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$)"

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it
class cmp
{
	public:
	bool operator()(const pair<ll,pair<ll,ll>> &p1,const pair<ll,pair<ll,ll>> &p2) const
	{
		if(p1.first==p2.first)
		{
			if(p1.second.first==p2.second.first)
			{
				return p1.second.second<p2.second.second;
			}
			return p1.second.first<p2.second.first;
		}
		return p1.first>p2.first;
	}
};

I used this comparator function for

set<pair<ll,pair<ll,ll>>,cmp>,

it works perfectly fine. But when I used this for

priority_queue<pair<ll,pair<ll,ll>>,vector<pair<ll,pair<ll,ll>>>,cmp>,

it is not working. Can anyone please tell why this comparator function is not working for priority_queue?

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

    A priority_queue works with biggest element as next, ie it returns what set.rbegin() returns. Just a guess.

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

My code is getting TLE in D but I think my code is n*logn, am I missing something here? I created a vector of l, r and number of zeros and I sort it according to the logic, delete the first element and push break-up parts

#include <iostream>
#include <vector>
#include <algorithm>

#define ll long long      
#define loop(i,a,b) for(int i=a;i<b;i++)
#define pb(x) push_back(x)
#define eb(x) emplace_back(x)
#define F first
#define S second
#define mp(x,y) make_pair(x,y)
using namespace std;

struct seg{
	int l;
	int r;
	int zeros;
};

bool cmp(seg a,seg b){
        if(b.zeros>a.zeros){
        	return false;
        }
        if(b.zeros==a.zeros){
        	return b.l>a.l;
        }
	return true;
}


void solve(){
        int n;
        //cin>>n;
       	cin>>n;
       	vector<seg> v;
       	vector<int> ans(n);
       	seg f={1,n,n};    
       	v.pb(f);                     
       	int cnt=n;
       	int i=1;
       	while(cnt--){
       		int left=v[0].l;
       		int right=v[0].r;
       		int mid=(v[0].l+v[0].r)/2; //this is the index;
       		ans[mid-1]=i;
       		i++;
       		//v[0]={left,mid-1,mid-left};
       		v.erase(v.begin());
       		seg gh={left,mid-1,mid-left};
       		seg g={mid+1,right,right-mid};
       	        v.eb(g);
       	        v.eb(gh);
       	        sort(v.begin(),v.end(),cmp);
       	}           	
       	for(int i=0;i<n;i++){
       		//cout<<x.l<<" "<<x.r<<" "<<x.zeros<<endl;
       		printf("%d ",ans[i]);
       	}
       	cout<<endl;                        
}


int main(){
	ios_base::sync_with_stdio(false);
    cin.tie(NULL);
//	freopen("input.txt","r",stdin);
	int t;
//	t=1;
	cin>>t;
	while(t--){
		solve();
	}
	return 0;
}





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

    Bro, your TC is O(NlogN * N) because you are sorting vector at every point. Use a data structure like set(ordered) or priority queue which performs insertion and deletion in logN.

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

can anyone plz tell me what is wrong with my solution for E https://codeforces.net/contest/1353/submission/80215731

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

    How this code is supposed to work?

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

      initially ans is all the 1's then in the while loop we will count all the zeroes that are between two ones that is for example in this case 9 2 010001010 in first loop there we will encounter with 0,0,0,0,0 and in second 1,0,1,1 so in first there are 0 no. of zeroes that we need to switch on where as in 2 there is only 1

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

Can anyone tell me why I am getting WA in test 2 in Problem F:

My logic is almost same as in the tutorial.

Here is my solution link: https://codeforces.net/contest/1353/submission/80220039

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

Anyone solved question D in python??

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

Can someone help me to figure out? Why I am facing Time limit exceed on complexity n*log(n) My submission is https://codeforces.net/contest/1353/submission/80220753

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

problem D can be solved in O(n)

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

Can anyone explain problem E? I'm not a native speaker and just can't fully understand E's editorial. Thanks a lot.

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

Has anyone solved E with memoization approach? I have construct recursive solution for same but I'm stuck at optimisation My submission

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

Can we do Problem-D by BFS? I tried doing it.. but apparently its failing at even numbers >=10

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

Can anyone please provide a counter test case(or tell me my mistake) for my solution to problem E? it's giving wrong answer on test 2.

https://codeforces.net/contest/1353/submission/80218519

Thanks in Advance :)

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

In the editorial of question F, are we trying to find a path through which it should definitely pass through (x,y) or is it not necessary but instead we are only taking into account the existence of (x,y) for some optimal answer ? Thanks in advance.

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

    In optimal answer there should be atleast one point unchanged . E.x :there is a 1×2 matrix 5 3 then you should definitely keep 5 unchanged and make 3 to 6 or keep 3 unchanged and make 5 to 2. You can change both but ans for that will always be greater than the ans you get in the previous way. Hope you understood.

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

      so after choosing every cell as a representative for a[0][0] of the outer loop, the optimal path of the inside n^2 dp would always include that chosen cell?

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

In Problem F,

Why aij>=bij ?

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

    Because you can only decrease height, aij. So for it to become equal to bij, aij has to be atleast equal to bij. Thus aij >= bij.

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

Can anyone provide a DP solution for E? I'm curious to know about that possibility.

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

Hello guys I have some troubles in promblem E. I do a 2D dp[i][j] as a minimum number of moves to make j first lamp become good with the last lamp is i this is my submission https://codeforces.net/contest/1353/submission/80232689 please help me =(( thanks in advance

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

Problem Div3-F

Can someone please help me debug this code. I have tried some small test cases of that problem and those were giving correct output. SUBMISSION DIV3-F Edit: I have found the mistake.

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

anyone can help me out on question F. why my code is failed on test 2.i am filling dp from bottom to up 80189787.

»
4 years ago, # |
  Vote: I like it -16 Vote: I do not like it

Mike, thanks for the round, the difficulty of the tasks was well chosen

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

Could someone explain how to make '111100000' 3-periodic in 2 moves as it is in the example of problem E ?

Input:
1
9 3
111100000

Output:
2

In other words, if the followings are all possible 3-periodic binary strings, which one is produced in 2 moves?

'000000000'
'100100100'
'010010010'
'001001001'

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

    100100100 is also correct but takes 3 moves. 100100000 takes 2 moves. There is not any need to have 1s till end.

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

Could someone pls explain me E..?

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

In problem C (n(n+1)(2n+1))/6 how it come... Please Anyone explain it..

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

Can someone explain why my solution for E is giving TLE??

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

Does my Python solution to problem E TLE simply because it is in Python?

My solution is DP in that

dp[n][0] = minimum number of moves to make the first n chars cyclic and the last one is 0 dp[n][1] = minimum number of moves to make the first n chars cyclic and the last one is 1

and using a prefix sum, I don't have any loop in my recursive function

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

    Yes. TLE because it's python. In case if you wonder how to make it fastest speed, here is a little guide by me:

    1. Any builtin function is faster than your implementation. So: list.index, str.find, sum, max, sort — is your friends. They work faster than if you make same things by hands.
    2. Try to avoid .append for lists. Allocate whole list at once using [None]*n or [0]*n. I don't know which one is faster, but it's faster than .append for sure.
    3. All dictionary / set stuff has additional constant. So use plain list when applicable. (in code above dp can be done by just two plain list, and check in by comparison with None)
    4. Avoid recursion: python require more resources and time for argument passing. 1e5 recursion gives stack overflow. To increase stack use sys.setrecursionlimit(10**6) for example.
    5. Code outside of functions is slower than code inside. So wrap solution in function or at east each test should be solved in function
    6. PyPy can speedup even more. But sometimes PyPy is slower than raw Python.

    I was trying to list in order of how often each thing is used. But regarding to impact on code I think from highest caused slowdowns order is: 4, 3, 2, 5. Regarding to 6 you can't compare it with others. And 1 — you use it well.

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

Why my solution for D giving RTE even though it's same as tutorial's.

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Questions like F MAKE ME RAGE, SUCH A SIMPLE QUESTION BUT MY IMPLEMENTATION HAS SOME BUG I CANT FIND :(

Can anyone help me find the bug (my submission)