Codeforces will not be available in the period 01:00-05:00 May, 30 (MSK, UTC +3) because of maintenance. ×

vovuh's blog

By vovuh, history, 3 months ago, In English,

Suddendly, all ideas of this contest are mine. And I'm very sorry about one missing small test in the problem B. This is the biggest mistake I made during the preparation of this round.

1324A - Yet Another Tetris Problem

Tutorial
Solution

1324B - Yet Another Palindrome Problem

Tutorial
Solution

1324C - Frog Jumps

Tutorial
Solution

1324D - Pair of Topics

Tutorial
Solution

1324E - Sleeping Schedule

Tutorial
Solution

1324F - Maximum White Subtree

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

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

Can someone suggest some basic dp problems like E (same or little higher difficulty) please.

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

E: A different dynamic programming approach, with runtime O(n*h).

Let dp(i,j) be the maximum number of good sleeping times if Vova slept the i to n times with the starting time j. Then, the value dp(1,0) will be the answer. Initially, all dp(i,j) = 0.

Transitions (to be done from i = n to i = 1, with j being all possible values of time (0-h)):

Let t1 = (j + a_i) % h and t2 = (j + a_i - 1) % h

Then, dp(i,j) = max(good(t1) + dp(i+1, t1), good(t2) + dp(i+1, t2))

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

    are all the cases covered in such? can you elaborate? thanks in advance

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

      I think my solution will be clear to you. Just have a look, basic recursive function with memoization. https://ideone.com/i53rk9

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

        can you explain your approach a little bit ??

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

          Since, we know that we can either select 'a[i]' or 'a[i]-1'. So, I called the recursive function two times, one with 'a[i]' as sum and the other with 'a[i]-1' as sum and hence returns the maximum of that. Do the same for all i from 1 to n-1. It is just the same as calling 'fib(n-1)' and 'fib(n-2)' in fibonacci series. 2-d DP works because 'n' is in the range [1,2000] and every time we are doing 'sum%h' the range of value will be [0,h) and h ranges from [3,2000]. I recommend you to make a recursive tree of the given sample input (take the help from my code). This will help you to see the repeated calculation which I am storing in array(dp).

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

            https://codeforces.com/contest/1324/submission/73769097

            Can you please see to my code . why my code fails for testcase 40

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

              Your code fails for input when L contains 0 i.e, when L,R is [0,..]. This happens beacause at the time of calling you are passing sum as 0. For example try for input (1 44 0 14 23), the answer should be 0 as neither 23 nor 22 lies between L,R but your code gives 1. To remove this problem, you just need to call the recursive function two times : (1. index=1,sum=arr[0]) (2. index=1,sum=arr[0]-1). And finally returns maximum of 1 and 2. Hope it helps !!!

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

            What does the dp[i][j] state signify ?? Thanks

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

        Hi I used similar approach getting WA on test 40 can u please help me https://codeforces.com/contest/1324/submission/73656520

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

          Read the previous comment. Your code also behaves similar.

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

      Essentially, what my state is how many good sleeps Vovu can have by starting from this hour and disregarding the previous i-1. Now, we can only disregard the first 1,2,3,...n and starting hour can only be in 0,1,2,...,h-1 so we have n*h states which cover all possible cases.

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

    I did the same using memoization table.

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

    Hey, i have solved question E. but i have done it in different way !! can you please explain, what you have done? i can't understand what you are trying to say !! please reply, i am right now focusing on DP.

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

      Well I don't get what exactly u didn't understand, so I am copying the main logic of my code which got AC in hopes you can get the algorithm I used:

      int n,h,l,r;
       
      int add(int t1, int t2){
      	int t = t1+t2;
      	if(t>=h) t-=h;
      	return t;
      }
       
      signed main() {
      	cin>>n>>h>>l>>r;
       
      	vector<int> a(n);
      	for(auto &i: a) cin>>i;
       
      	vector<vector<int>> dp(n+1,vector<int>(h,0));
       
      	for (int i=n-1; i>-1; --i){
      		for(int t=0; t<h; ++t){
      			int t1 = add(t, a[i]);
      			int t2 = add(t, a[i]-1);
      			int cost1 = (l<=t1 and t1<=r) ? 1 : 0;
      			int cost2 = (l<=t2 and t2<=r) ? 1 : 0;
      			dp[i][t] = max( cost1+dp[i+1][t1] , cost2+dp[i+1][t2] );
      		}
      	}
       
      	cout<<dp[0][0];
      }
      
      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        hmm, got it...you have done push dp and i have done it in reverse way.

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

Simpler way to solve C is to calculate the longest contiguous sequence of L's and then output it plus one.

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

    Or you can find out farthest 2R's and print the difference in their positions. Edit : The editorial says the same . Sorry I hadn't read editorial before commenting here . XD

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

      Still though, there is no need to remember the whole array of distances between R's. Instead, it is enough to remember the max distance.

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

    This is what I did..but by seeing others solution I thought it was wrong lol

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

Alternate solution to task E:

Considering all times of the day modulo h, let dp[i][j] be the maximum number of good sleeping times assuming that Vova has slept the first i times and that the current time of day is j.

Also, let's maintain boolean array pos[i][j] such that pos[i][j] is true IFF it is possible to end up at time j after sleeping i times.

Now, transitions can be calculated by setting dp[i+1][(j+ai)%h] to max(dp[i+1][(j+ai)%h, dp[i][j] + ((j+ai)%h >= l && (j+ai)%h <= r ? 1 ; 0) and applying a similar transition for ai-1.

Now, the answer is just the max dp[i][j] such that i = n.

I noticed a comment denoting a similar solution although my submission was in-contest unlike the other comment.

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

    i thought exactly the same but mine seems doesn't work

    can you please help me

    my submission

    Thanks in advance

    EDIT:

    Now it is working but why do we need to maintain a boolean array of possibilites?

    Shouldn't it be handled automatically by setting to zero the dp matrix initially

    please explain.

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

      During the contest, my intuition was thinking that not all (i,j) pairs would be possible during DP, so I included the boolean matrix as an extra precaution.

      I knew that the extra space wouldn't really matter and played it safe. IDK if it makes a difference but I wasn't worried in-contest because I wanted to make sure I just got the task right.

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

Can anyone suggest where can we study and practice rerooting question like F. Thanks in advance : )

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

What was the case that wasn’t included for B? I got hacked and I just wanted to know what the case was.

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

    I think your mistake is that you are keeping track of the last seen element rather than the first seen.

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

    I just know a bit of cpp so I'm unable to run your code, but I can tell you the test case on which most of the codes where hacked It was: 1 3 1 1 1, try running this and the output should be "YES"

    Incase you want the specific test case on which your code was hacked, you can check it at https://codeforces.com/contest/1324/submission/73037905, you will be getting an option of view test (right under Hacked written in red text)

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

      Thank you, I'm new to CodeForces so I didn't know how to view the test that hacked my code.

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

@vovuh I tried to solve F using two DFS but kept failing test case 3 and I couldn't figure out why it fails on this test case. Can you help me point out my mistake? My submission is 73111564 and I've added comments to make it easy to read.

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

In the 1324D — Pair of Topics's Tutorial

at the beginning of the Tutorial is $$$ i < j $$$ , but then turn into $$$ j < i $$$

can someone explain it ? plz.

Edit : i made a mistake , sorry

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

A can also be done by checking if difference of adjacent elements mod 2 equals 0 or not

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

    Why 6 downvotes?? :(

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

      Codeforces community is kinda weird and specific to it's liking. Don't pay attention to upvotes or downvotes on your comments. Do check the FAQ on this to know more.

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

Can somebody explain why the above solution for D works? Once we sort all Ci there is no track of their original indexes anymore.. so how is it correct?

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

    The indexes don't matter. The condition i<j is given just so that you don't count (1,2) and (2,1) as different pairs. Ex. If the array is a, b, c, Then the pairs are ab, ac and bc. But if it is b, a, c, Then also the pairs are ba, bc and ac.

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

      Thanks got it now. The pairs will be unique anyways as per the above solution.

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

When will the ratings get updated... Generally how much time it takes after the contest ends .?

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

What type of dp in problem E. Editorial said that is a standard dp problem, but i can't recognize that. Help me plz.

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

Question D can be solved in O(n) after sorting also using two pointers, which seems a bit efficient.

Link to my solution

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

    The sort itself takes O(nlogn)

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

      I clearly said after the sort, it takes O(n). It is just an efficient way to do the same thing. Suppose the sorted array is given, my logic would take O(n), but the given would still take O(nlogn).

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

        And yet, the solution still has a time complexity of O(NlogN)...

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

        Lol , If the array is sorted you say,its the same as saying that you would have done it in O(1) time if they gave you a table with sum of pairs which is O(n^2) or an array which is sorted(which is what you are asking). But O(1) doesnot matter because of the O(n^2) process , similarly , The very thing that your O(n) approach depends on an O(nlogn) process (doesnt matter if it is sorting) is what makes your solution O(nlogn) .

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

Can somebody explain palindrome problem? How does it check the palindrome by removing characters in between?

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

    the question says we need a palindromic sub sequence of length greater than or equal to 3, So the easiest palindrome that can be formed by sub seq is of length 3 which has 1st and 3rd elements same, the 2nd element won't matter . Simply search for 2 same elements in the array but they should not be consecutive (so that you can insert any 1 element between the 2 similar elements).

    If the array has 2 same elements that don't occur together then the answer is "YES".

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

The solution given by vovuh for E is giving WA on tc 2. Any suggestions on what could be wrong in it?

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

    I copied the code from local directory, not from the polygon, the local code contained one bug which was fixed on polygon. You can realize what is this bug yourself (there is some kind of hint in the tutorial). And now you can copy and submit the correct solution but I don't know why do you need it.

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

this contest be like:

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

Can anyone explain O(N) solution for problem B ??!

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

    The only thing important is the indexes of repeated elements in the array. so what we could do was to store the min index and the max index where each element is in the array and then just check is the diff of min index and max index is greater than 1. If it is then we could include any element between these indices to make a palindrome of length 3.

    Link to my submission — https://codeforces.com/contest/1324/submission/73029984

    P.S this is my first post so please ignore the informalities.

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

    You can maintain an auxiliary array whose index will be the numbers present in the original array. That auxiliary array may be initialized by -1. So when you traverse the array if the corresponding index in aux array is -1 that means it is the first occurence of that number in the main array and you can replace -1 with that first index of that number. Now if you encounter that number again you can simply take the difference between current index and first index(stored in the aux array). if that difference is >1 then just print yes and return. Or if you cant find any such index print NO

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

    $$$O(N)$$$ 73087070

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

Perhaps I am very poor at parity-trick questions, but problem A is very non-intuitive to me, and I was very shocked to see the number of submissions, problems B,C,D were much more straightforward for me.

I still don't think I understand problem A fully.

The answer is "YES" only if all $$$a_i$$$ have the same parity (i.e. all $$$a_i$$$ are odd or all $$$a_i$$$ are even). That's because placing the block doesn't change the parity of the element and the −1 operation changes the parity of all elements in the array.

OK, but this can prove that answer is "NO" when parity of any two numbers is different. But how do I prove that it has to be "YES" when all numbers have same parity?

It's somehow very non-intuitive to me :(

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

    The way Tetris(the game) works is the bottom most row gets cleared if there is a block present in every column. Since the block we can add spans 2 rows and 1 column, the height increases by 2 when we add it to a column. If the parity of each column is same then you can add those blocks to make the height of each column equal to, say, x. Therefore, you can clear the bottom-most row x times to get a fully empty board. Lets say your numbers are 1 3 5 9 3. Then you can add some number of blocks to each of the columns to get 9. After doing that, you can clear the whole board. Hope this helps :)

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

    When parity of all numbers is same, in one step you can increment the minimum element by 2 and then decrease all elements by 1. So the overall effect is that minimum element got increased by 1 and rest all elements were decreased by 1. Now it's easy to see why after a finite number of steps all elements in the array will become equal.

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

    You are not alone.I spent much more time on A than B、C、D.

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

    I don't know it will help you this way or not but here's how I looked at it. Consider the cases when when all the adjacent numbers differ by an even counts(which means all the numbers have the same parity). Like 3 5 7 5 3 1 or 2 4 2 16 4. The only motto of the question is to make all numbers equal(Obviously, after that you can turn them all to zero).You start by adding +2 to the minimum number possible and then decrease the numbers till at least one of the numbers reaches to zero. Let's say p q r s t (numbers differs by an even count) and let's say t is the smallest number , you add +2 to t and let's say (for simplicity) t+2 is again the smallest number in the array so what happens if you actually perform operation 2nd described in the question — you subtract (t+2) to all numbers because t+2 is still the smallest number (so it's the first number that will be turned to zero) so the numbers become p-(t+2) q-(t+2) r-(t+2) s-(t+2) 0. Now you add +2 to zero and repeat the process and now it's easy to see that you can turn down them to same number if and if only they have same parity.

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

    Thank you all for your attempts. I think I have a somewhat better understanding now.

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

The solution provided for E is not running. I think the issue is that we are running inner loop from 0 to n which includes the case of dp(i,j) where j>i which is invalid. Please correct if I am wrong.

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

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

IN PROBLEM A, The two processes are given in the problem. Does the process 2 has always to be performed whenever process 1 is performed or we can perform process 1 as many times as we want and then perform process 2. Can someone explain it please. Thanks in advance.

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

I have an interesting approach to question D,Time complexity: O(n).

You can define c[i] = a[i] — b[i],then sort them,finally while(l<r){ if(c[r]+c[l] > 0){ ans+=r-l; r--; } else { l++; } I think many people will use it to pass;

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

Hi! I solved Problem F but it throws TLE on Test case 42. Unable to understand why, can someone please help? https://codeforces.com/problemset/submission/1324/73134886

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

Where can I practice tree dp problems like https://codeforces.com/contest/1324/problem/F. Thnaks!

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

I never saw that kind of lengthy system testing. Did it happen like this before?

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

Can anyone explain Problem A.Tetris problem?

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

    Yes !! In this problem we can observe that if there all odd nor even numbers in the array then the ans is yes else it is no It is just simple observations nothing else

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

    Adding block of size 2x1 will not change the parity (eg. if a number is odd after adding 2 it will remain odd).So, in order to complete tertris we must have all elements of array of same parity either odd or even.

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

After 100% it went to 91% .WTH

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

When will the ratings get updated ?

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

I did my first Problem E in life but after the contest myself. I'm happy. I used Memoization. This question was much like LIS to me.

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

My F question uses two DFS, the complexity should be no problem, why is it TLE?73153261

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

I tried the same approach with question D as given in tutorial, still i am getting a wrong ans. Can someone please spot where i might have gone wrong? It goes wrong in test case 12. Thanks in advance.

/* arr[i]= a[i]-b[i]; ->as in the tutorial

only that arr is sorted in DESCENDING order

and i have used a 2-pointer technique */

static int findPairs (Long arr[] , int n )

{ 
        int l = 0, r = n-1; 

        int result = 0; 

        while (l < r) 
        {                              
            if (arr[l] + arr[r] > 0L) 
            { 
                result += (r - l); 
                l++; 
            } 
            else
                r--; 
        } 
        return result; 
    }
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    change the data type of result as long. Overflow is happening.

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

      Wtf!!! Such a silly mistake. I wasted an hour almost to debug my solution. Thanks a lot

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

    2 pointer is good approach ............

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

Can anyone help me in knowing https://codeforces.com/contest/1324/submission/73161536 is giving a TLE

I have been looking at it for a long time and unable to understand why.

Thanks!

»
3 months ago, # |
  Vote: I like it -18 Vote: I do not like it

I think problem E can be solved by greedy Did anyone solved it by greedy ? I have tried , but i failed

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

    No, you can't solve E by greedy.

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

Can someone help me find the error in my solution of E https://codeforces.com/contest/1324/submission/73208155 It gives wrong answer verdict on test 40

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

    Replace the line if(sleep>=l && sleep<=r) with if(sleep>=l && sleep<=r && i>0)

    This is because both l and r have lower limit 0 in the question. So you need to omit that case.

    See my solution for clarity.

    P.S — Assuming you don't have made any silly mistakes elsewhere.

»
2 months ago, # |
  Vote: I like it -14 Vote: I do not like it

I am the first russian?

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

Someone please explain me the rerooting technique used in problem F. I am unable to understand it's editorial. Please help.

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

    If you don't understand the editorial, just see others code, i think it is more straight forward, when you understand the code, then you can go back see if you can understand the editorial.

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

Just solved E all by myself. I think it is an easier approach. my solution

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

someone plz drope solution for A by using eazy c++

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

    here is my solution in c++

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

      thanks but i couldnot understand anything i prefer this one

      include <bits/stdc++.h>

      using namespace std; int x, t, i, j, n, l, k; int main() { cin >> t; for(i=1; i<=t; i++){ cin >> n; int a[n]; for(j=0; j<n; j++) cin >> a[j]; l=0; k=a[0]%2; for(j=1; j<n; j++) if (a[j]%2!=k) {cout <<" NO " << endl; l=1; break; } if (l!=1) cout << "YES"<< endl;

      }

      return 0; }

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

Why is this code of 1324D — Pair of Topics getting TLE?

Idea of code in short :- BIT / Fenwick tree is implemented using unordered_map (C++) to query smaller values, of type (b[ j ] — a[ j ]), than (a[ i ] — b[ i ]) for all j < i.

Any suggestions to optimize this code using the same idea?

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

what's wrong in my code(failed on test case 4)

include <stdio.h>

include <stdlib.h>

int main() { int T,n,i,j; scanf("%d",&T); while(T--) { scanf("%d",&n); int arr = (int)malloc(sizeof(int)*n); for(i=0;i<n;i++) scanf("%d",&arr[i]); for(i=0;i<n/2;i++) { for(j=n-1;j>i+1;j--) { if(arr[i] == arr[j] && j-i >1) { printf("YES\n"); break; } } if(arr[i] == arr[j]&& j-i >1) break;

}
    if(i==n/2 && j== n/2)
            printf("NO\n");
            free(arr);
            arr = NULL;


}
return 0;

}

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

someone plz drope solution for D by using eazy c++

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

can someone please explain that in pair of topics why -c[i] is not working,why **-c[i]+1 **.

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

where does my code goes wrong for PROBLEM E link of solution:-

solution here...

.thank in advance:)

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

1 1 2 2 3 3 4 4 5 5 14 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 6 15 15

the checker is saying this is a palindrome. can anyone explain how? this is test 5,1st problem

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

    as you can see number 6 occurs 2 times => 6 7 7 8 8 9 9 10 10 11 11 12 12 13 13 14 6 so you can choose any number of those 6 {7 7 8 8 9 9 10 10 11 11 12 12 13 13 14} 6

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

      thanks a lot. got it. I didn't know that I can delete elements between two 6's

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

Is there any other DP solving for E problem?(thanks in advance)

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

I did D in some different manner and got wrong answer on test 6 . can anyone find where i am doing mistake

my submission : 73524489

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

can anyone please help me uderstanding the editorial of problem D; we have to contruct the Ci array Now if ci+cj is greater than zero atleast one will be positive so as to ci+cj to be positive. I don't understand this part of the editorial---- "Now ci>0 and we need to calculate the number of such j that ci+cj>0 and j<i. It means that each cj≥−ci+1 (for some j<i) will be okay."

please help

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

Can anyone explains why my solution for the Problem-F is giving TLE. According to me its complexiety should be O(2*(n+v)) in worst case?

vector mv[200005];

int a[200005];

int dfs(int x,int p)

{

int newcost=0;

for(int i=0;i<mv[x].size();i++)

if(mv[x][i].first!=p)

if(mv[x][i].second!=-2)

{

    if(mv[x][i].second>0)

    newcost+=mv[x][i].second;

}

else

{

    mv[x][i].second=dfs(mv[x][i].first,x);

    if(mv[x][i].second>0)

    newcost+=mv[x][i].second;

}

if(a[x])

newcost++;

else

newcost--;

return newcost;

}

void solve()

{

int n;

cin>>n;

int flag=0;
for(int i=1;i<=n;i++)
{
    cin>>a[i];
    if(a[i]==1)
    flag=1;
}

for(int i=0;i<n-1;i++)
{
    int u,v;
    cin>>u>>v;
    mv[u].push_back(mp(v,-2));
    mv[v].pb(mp(u,-2));


}

if(flag==0)
{
    for(int i=0;i<n;i++)
    cout<<"-1 ";
    return;
}

int i=1;
while(i<=n)
{
    if(mv[i].size()==1)
    break;
    i++;
}
mv[i][0].second=dfs(mv[i][0].first,i);
for(int i=1;i<=n;i++)
{
    int newcost=0;
    for(int j=0;j<mv[i].size();j++)
    {
        if(mv[i][j].second==-2)
        {
            mv[i][j].second=dfs(mv[i][j].first,i);

        }
        if(mv[i][j].second>0)
        newcost+=mv[i][j].second;

    }
    if(a[i])
    newcost++;
    else
    newcost--;
    cout<<newcost<<" ";
}

}

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

This gives TLE : * Used Arrays A,B,C and 2 loops to input A and B and form C * Sorted C * This finally used lowerbound thing https://pastebin.com/icGaeuH8

This doesn't give TLE : * Used vectors A,B,C and 3 loops to input these * Sorted *Lower bount thing https://pastebin.com/9fajyGEi

Can anyone help me out ?

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

Tutorial Question E :

loop 1: i=0;i<n;i++ loop 2: j=0;**j<=n**;j++

-> i is number of sleeps -> j is number of sleeps he goes one hour earlier

So j <= i for all j Thus, j<=i rather than j<=n.

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

can anybody explain to me that in problem d -c[i]+1 logic? I didn't get it

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

    I hope you got c[i] + c[j] > 0. Now for this inequality , either c[i] must be positive , or c[j] or both. So we consider c[i] to be positive for all cases. Now c[j] has to be greater then -c[i] atleast to be 0 or positive. However c[i]+c[j] > 0 and not equal to zero and thus c[j] >= -c[i]+1.

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

    the problem is nothing we have to remove the duplicacy therefore we have neglected the negative terms...

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

can someone please explain me problem D. I am not getting after sorting how we implement it.

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

    I finally figure it out. Help this can help you.

    After we sort it, we make the $$$c$$$ list sort from smallest to biggest. Because we are using the lower_bound() function, which imply we only find the $$$c[j]$$$ is smaller than $$$c[i]$$$. That's why we could skip $$$c[i] <= 0$$$.

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

For problem D, I still can't understand why we can skip it when c[i]<=0? Can someone help me?

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

    We sort c: c[i-1] <= c[i]

    We need c[i] + c[j] > 0 (j < i). So, if c[i] <= 0 with all j = 0..i-1 we can't get c[i] + c[j] > 0 :)

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

      Thanks! I can understand it now.

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

Question (B) says that we can solve it by $$$O(n^2)$$$ or by $$$O(n)$$$. I cannot understand the writer's explanation of how we will do it in $$$O(n)$$$. Can anyone please provide code for the same. Thank you.

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

int problem E am getting WA on test 40 can anyone help please my code : code

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

can some explain how can we use binary search in C i saw it in its tags

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

In problem D, doesn't sorting the c[] array mean losing information about i < j?

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

For the sleeping schedule problem, there seems to be a logical problem as in the first and the second transition. For the ith time you go to sleep, you can't go to sleep earlier more than i times or you can go to sleep early at most i times & the code or the tutorial doesn't address that.

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

Hi, I am not able to figure out the error in my logic for the problem E. Start with range [0, 0] and keep updating the range by adding ai-1 to the left border of range and ai to right border of the range. So, basically the range tells you the possible sleeping times after i_th time. At each i, check if there is any intersection with [l, r]. If yes, then good sleeping time++. Following is the code-

bool check(int a, int b, int l, int r){
    if(max(a,l)<= min(b,r)) return true;
    if(b<a){
        if(a>l && b<r)return false;
        else return true;
    }
    return false;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int n,h,l,r; cin>>n>>h>>l>>r;
    int a=0, b=0, ans=0;
    vi q(n);
    loop(i,0,n){
        cin>>q[i];
        a += q[i]-1;a %= h;
        b += q[i]; b %= h;
        if(check(a, b, l, r))ans++;
    }
    cout<<ans;
    return 0;
}
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

iam not able to understand F problem please help

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

Also, what does this even mean? The subtree of the tree is the connected subgraph of the given tree.

I feel the english is bad and it should be: A subtree of the tree is a connected subgraph of the given tree.

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

can somebody explain why in problem F the dp[v] = a[v] + max(0,dp[to]) as in subtree all nodes are included so it should be dp[v] = a[v] + dp[to] why we are taking max over 0 . can somebody explain 1st testcase how for node 1 ans is 2.

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

In E can anyone please point the mistake in dp equation :

  • if(j>i) dp[i][j]=0;
  • if(j==0) dp[i][j]=dp[i-1][j]+is((sum[i]-j)%h,l,r);
  • else dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+is((sum[i]-j)%h,l,r);
  • Logic is that one can sleep j times in first i sleeps only if he either sleeps early j times in first i-1 sleeps and not sleeps earlier in ith sleep or if he sleeps early j-1 times in first i-1 sleeps and sleeps early this time.
  • where dp[i][j] : maximum number of good sleeping times in first i sleeps, in which j were slept earlier
  • sum[i] : sum of sleeping times till first i sleeps
  • is(s,l,r) : returns true if s belongs in range [l,r]
  • And final answer is maximum in array dp[n][1:n]
  • If the logic is correct kindly help me debug my submission 78897404
  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    solved.. it may be an interesting task to find out bug in this solution.

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

The approach used in solving problem D- is it any algorithm or has it any name? I find the way really cool.

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

Sorry to bother you vovuh, but it seems like problem B is broken. Validator is crashing and solutions are not being evaluated. "Denial of Judgment" is being shown on evaluator

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why am I getting time exceed error? Q 1324D Pair of Topics I have done sorting by both ways i.e quick sort and also using heap. Still, I am getting this error.

Please Help!

The code is written below.

import heapq

def countGreater(arr, n, k): l = 0 r = n — 1 leftGreater = n while l <= r: m = int(l + (r — l) / 2) if arr[m] > k: leftGreater = m r = m — 1 else: l = m + 1 return n — leftGreater

N = int(input()) l1 = list(map(int, input().split())) l2 = list(map(int, input().split())) diff1 = []

for i in range(N): diff1.append(l1[i]-l2[i])

diff = [] heapq.heapify(diff1)

for i in range(N): diff.append(heapq.heappop(diff1))

count = 0

for i in range(N): if diff[i] > 0 : a = countGreater(diff[0:i], i, -diff[i]) count = count + a print(count)

»
12 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me why this submission is going wrong on TC 12 for problem D? Submission Link. Its very odd, I see that the Editorial solution isn't too far off from my method (It uses binsearch while I use a ptr method).

»
34 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain me why he took max(0,dp[child]) everywhere?