vovuh's blog

By vovuh, history, 5 months 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
Tutorial of div3 E-onwards #1
 
 
 
 
  • Vote: I like it
  • +150
  • Vote: I do not like it

»
5 months ago, # |
  Vote: I like it +86 Vote: I do not like it

Video Editorials for D and E

Enjoy watching!

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

Too fast editorial!!

  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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

      • »
        »
        »
        »
        5 months 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.

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

          Many many thanks for answering my query.However,It's a hard to get how that case is getting covered. Your solution videos are really good.hope to be like you some day.

»
5 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Editorial is out but nothing under tutorial section?

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

what a super duper fast editorial :D thanks you

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

Wow!....so fast tutorial. Thanks for that.

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

⚡Lightning speed editorial

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

which is faster @vouvh's editorial or speed of light?

»
5 months 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

  • »
    »
    5 months 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....

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

      Thanks,finally i understood.

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

    In that case, n and m are equal to 1e9 . Consider it as 10 and 10, then we can make the array as 2,0,2,0,2,0,2,0,2,0. Then, we get the ans as 20. Similarly, in that test , we get ans as 2e9.

»
5 months 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.

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

    look for custom comparators c++ , useful stuff.

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

    Especially functors they are hybrid custom functions which can take more than two variables

»
5 months 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.

  • »
    »
    5 months 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!!

    • »
      »
      »
      5 months 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}$$$

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

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

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

      Please Explain How u getting it?

      • »
        »
        »
        »
        5 months 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

      • »
        »
        »
        »
        5 months 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.

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

          We can calculate answer for i and it can be extended for (i+2) where i is odd number. check it out here, link

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

    Made a DP Solution for problem C .

    Explanation , Code

    • »
      »
      »
      5 months 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.

    • »
      »
      »
      5 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

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

is it like magic or what..

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

can anyone please explain D

  • »
    »
    5 months 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

  • »
    »
    5 months 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

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

    did it with priority_queue, where one element is consists of len of segment,it's left index and right index, check it out here

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

      How does priority queue know which pair has higher priority?

»
5 months 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.

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

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

  • »
    »
    5 months 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)

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

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

editorial speed > 3*(10^8) metre/sec

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

Interesting problems! and fast editorial

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

Why B have more submissions than A?

  • »
    »
    5 months 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 :)

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

fastest editorial in the NEWS

»
5 months 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)

»
5 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Is vovuh competing with USAIN BOLT

»
5 months 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.

  • »
    »
    5 months 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;
  • »
    »
    5 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
  • »
    »
    5 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    change the positive to negative for reverse priority queue

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

    You dont need comparator function. just use negative value see this 80158855

  • »
    »
    5 months 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)

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

can anyone explain this submission of 300iq?

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

    This is the minimum subarray sum problem.

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

      Thanks a lot bro! I got it now.

    • »
      »
      »
      5 months 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?

      • »
        »
        »
        »
        5 months 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.

        • »
          »
          »
          »
          »
          5 months 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??

          • »
            »
            »
            »
            »
            »
            5 months 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).

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

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

          • »
            »
            »
            »
            »
            »
            5 months 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.com/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; }

            ~~~~~

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

vovuh , can D be solved using recursion ? Thanks.

»
5 months 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?

  • »
    »
    5 months 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.

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

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

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

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

»
5 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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

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

Please help with this comment: link

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

Can anybody help me what is wrong in this code? Problem B 80159137

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

    if k == 0 you dont read array b =>

    on next test prev array b reads as array a, current array a reads as array b =>

    error

»
5 months 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 ?

  • »
    »
    5 months 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$$$.

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

      Thanks.

    • »
      »
      »
      5 months 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.

    • »
      »
      »
      5 months 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.com/contest/1353/submission/80376675

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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.

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

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

Did anyone solve E with D&C?

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

Thanks for good problems! I really enjoyed it! :D

»
5 months 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!

  • »
    »
    5 months 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.

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

      Yeah I get the idea spookywooky, seems like I need practice in implementation of pq in problems, Thanks!

»
5 months 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.

  • »
    »
    5 months 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!

    • »
      »
      »
      5 months 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?

      • »
        »
        »
        »
        5 months 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.

»
5 months 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.

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

C was interesting but messed up badly

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

Quick Tutorial

»
5 months 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.

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

    I have a simple solution for E 80161569

    • »
      »
      »
      5 months 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?

      • »
        »
        »
        »
        5 months 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}$$$

    • »
      »
      »
      5 months 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
      • »
        »
        »
        »
        5 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

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

      • »
        »
        »
        »
        5 months 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.

»
5 months 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.com/contest/1353/submission/80148191

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

  • »
    »
    5 months 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.

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

So good contest, thanks

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

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

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

    I don't think so, it's not about just dividing the array into segments and process them. You have to chose the leftmost maximum segment. Recursion — I think — can't handle this.

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

    Yes

    • »
      »
      »
      5 months 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 ?

      • »
        »
        »
        »
        5 months 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 .

      • »
        »
        »
        »
        5 months 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.

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

I failed to solve D because I used '==' operator instead of using equals method, Amazing :) .

»
5 months 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?

  • »
    »
    5 months 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.

»
5 months 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?

  • »
    »
    5 months 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.

»
5 months 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 :(

»
5 months 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

  • »
    »
    5 months 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

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

I think priority_queue is more sutible than set for D

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
5 months 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.

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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.

»
5 months 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.

  • »
    »
    5 months 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.

»
5 months 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??

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

    all element of array a will be considered

  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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

      • »
        »
        »
        »
        5 months 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

    • »
      »
      »
      5 months 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 .

      • »
        »
        »
        »
        5 months 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.

        • »
          »
          »
          »
          »
          5 months 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 .

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

            Can you explain

          • »
            »
            »
            »
            »
            »
            5 months 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.

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

              ok ,thank you got it.

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

        Ans will be 48 only and one more protip prefer using offline compiler like sublime or any other as sometime online platform take too long to compile due to traffic

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

          Thank you kingkong1. I would prefer taking your advice next time . :-)

»
5 months 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.

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

Issue solved.

  • »
    »
    5 months 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.

»
5 months 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;
		}
	}
  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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.

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

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

      • »
        »
        »
        »
        5 months 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.

»
5 months 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

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

I have query about problem D, if n is odd the problem have O(n) solution so is there any ways to do same when n is even??

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

    I don't think so but even if it existed it will be easier to submit O(nlogn) solution as it would be quite difficult to observe

»
5 months 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.

»
5 months 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

  • »
    »
    5 months 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

»
5 months 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.

  • »
    »
    5 months 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;
    
  • »
    »
    5 months 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.
    
»
5 months 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

  • »
    »
    5 months 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

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

    Thanks!!!

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

i didn't get problem C! !

  • »
    »
    5 months 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.

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

Good

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

The queue is so fast today. Thank you.

»
5 months 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.com/contest/1353/submission/80167997

Please help

»
5 months 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.com/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

  • »
    »
    5 months 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.

»
5 months 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$$$.

»
5 months ago, # |
  Vote: I like it +1 Vote: I do not like it
  • »
    »
    5 months 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

    • »
      »
      »
      5 months 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.

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

https://youtu.be/DtWXAHIN2ys Solutions and Discussion.

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

Anyone can help to understand how problem C can be solved using this formula ..

sum of squares of all integers from 1 to n−1 / 2. Thanks

»
5 months 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?

»
5 months 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.

  • »
    »
    5 months 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.com/contest/1353/submission/80167362

»
5 months 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.

  • »
    »
    5 months 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)

»
5 months 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

»
5 months 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?

  • »
    »
    5 months 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.

  • »
    »
    5 months 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.

  • »
    »
    5 months 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.

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

Well commented and clean code for E
Submission — 80186993

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

Thanks vovuh for the amazing and fast editorial (like always :) )

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

https://codeforces.com/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

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

Was this contest unrated? My rating is still not updated

»
5 months 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

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

Great Editorial.

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

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

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

problem E: if you know regex, idea is make a automata like 0*1+0+, state count is 3, trans is simple. use state stand for mod k index. finally, answer is find 1 state is 0*1+0+ or 0*1+, and k — 1 state is 0*.

»
5 months 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

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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).

      • »
        »
        »
        »
        5 months 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.

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

    Yes, the range of elements was small, so we can do that.

»
5 months 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.

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

Please can someone elaborate the tutorial for Problem F.

»
5 months 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."

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

In problem E, C++ in-built function count which has linear complexity and we run for loop for k times. So shouldn't it be O(n*k) time complexity? It's mentioned as O(n) in the editorial. Could anyone explain?

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

    Well, I think prefix array can also be used(instead of count) to serve the purpose which will eventually lead to O(n) complexity. If we are using count, we are increasing complexity to O(nk). Thanks!

»
5 months 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.

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

    Got it, my approach was actually incorrect.

»
5 months 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])

»
5 months 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)??

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

when ratings will be updated??

»
5 months 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 :)

  • »
    »
    5 months 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.

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

      hi, thanks for the speedy reply. Appreciate it very much. Will look into heaps now, :)

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

Another solution for C part[submission:80129435]

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

1353B - Two Arrays And Swaps can be solved by sorting array B and inserting the last K elements to array A. Then we sort array A and find the sum of last N elements. Time complexity will be O(NlogN).

»
5 months 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?

»
5 months 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?

  • »
    »
    5 months 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.

    • »
      »
      »
      5 months 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

      • »
        »
        »
        »
        5 months 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.

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

          thanks

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

            So... did it went well?

            • »
              »
              »
              »
              »
              »
              »
              5 months 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..

              • »
                »
                »
                »
                »
                »
                »
                »
                5 months 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.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 months 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?

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

                  Just practice, there is no silver bullet.

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

                  your progress looks stable. You have never dropped as much as me :)

»
5 months 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 ?

  • »
    »
    5 months 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$$$)"

»
5 months 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?

  • »
    »
    5 months 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.

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

for problem F, I also had same solution but I was stumbled on the proof of optimal situation, can anyone help me to prove that if we change all values, how it can not be optimal answer?

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

vovuh Someone please explain clearly the tutorial for problem F — Decreasing Heights

»
5 months 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;
}





  • »
    »
    5 months 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.

»
5 months 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.com/contest/1353/submission/80215731

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

    How this code is supposed to work?

    • »
      »
      »
      5 months 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