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

1324B - Yet Another Palindrome Problem

1324C - Frog Jumps

1324D - Pair of Topics

1324E - Sleeping Schedule

1324F - Maximum White Subtree

• 3 years ago, # ^ | You can always look at the problemset and turn on the dp tag and sort by rating or number of solves in ascending order. I'd recommend looking around a rating of 1600-2000 for some basic (or a bit harder) dp tasks.

  • 3 years ago, # ^ | I'm aware of that feature but in practice, I found that most 1600-2000 problems tagged with dp don't have their intended solutions with dp. Rather they are some greedy problems which have in their editorials "This problem can be solved using dp also", which is not helpful when I'm unable to solve the problem. This is why I'm asking :)

• 3 years ago, # ^ | Good DP problems for all rating range.AtCoder Educational DP

• • 3 years ago, # ^ | Thanks.It really has good quality of DP problems

• 3 years ago, # ^ | DP is a good choice

• 3 years ago, # ^ | are all the cases covered in such? can you elaborate? thanks in advance

  • 3 years ago, # ^ | I think my solution will be clear to you. Just have a look, basic recursive function with memoization. https://ideone.com/i53rk9

    • 3 years ago, # ^ | can you explain your approach a little bit ??

      • 3 years ago, # ^ | 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).

        • • 3 years ago, # ^ | 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 !!!

            • 3 years ago, # ^ | Thanks.

            • 2 years ago, # ^ | Thank you so much man. I was completely frustrated as my code was not working but your comment was here to help me. :-)

        • 3 years ago, # ^ | What does the dp[i][j] state signify ?? Thanks

          • 3 years ago, # ^ | dp[i][j] signifies the total number of good sleeps from index i to n.

        • 2 years ago, # ^ | Plzz can you explain about the state transitions.

    • • 3 years ago, # ^ | Read the previous comment. Your code also behaves similar.

    • 3 months ago, # ^ | yeah, I also use the recursion technique followed by memoization. here is my Code Link :) https://codeforces.com/contest/1324/submission/162427599

  • 3 years ago, # ^ | 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 years ago, # ^ | I did the same using memoization table.

• 3 years ago, # ^ | 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.

  • 3 years ago, # ^ | 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]; }

    • 3 years ago, # ^ | hmm, got it...you have done push dp and i have done it in reverse way.

• 3 years ago, # ^ | ← Rev. 2 →   0 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 years ago, # ^ | 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.

    • 2 years ago, # ^ | ← Rev. 3 →   0 or if by chance you did not observe the pattern like me ,you can binary search the value for d https://codeforces.com/contest/1324/submission/96364535

• 3 years ago, # ^ | This is what I did..but by seeing others solution I thought it was wrong lol

• 3 years ago, # ^ | ← Rev. 3 →   0 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 years ago, # ^ | 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.

• 17 months ago, # ^ | Hey, zekigurbuz I almost did the same but, I am not understanding why by changing vector<int> new_dp(H, INT_MIN); to vector<int> new_dp=dp; in the below code, I was getting WA. As for updating dp[k] we need its value from the previous iteration, isn't it?? Code

• • 3 years ago, # ^ | Thank you ^_^

  • 3 years ago, # ^ | luciocf Can you tell how to solve the first one — Save Nagato!

    • 3 years ago, # ^ | Do the same as said, in the above editorial ! Instead of keeping the black and white count keep a multiset for each vertex storing the depth using each branch, now reroot for each vertex and then erasing the largest depth kept in the multiset,putting the largest depth into each children multiset and then finally erasing it from each children multiset & putting it back in afterwards in the vertex' multiset. Have a look here at my submission : https://dmoj.ca/src/1961273

      • 3 years ago, # ^ | I am unable to see your solution. It is showing access denied

    • 3 years ago, # ^ | ← Rev. 4 →   0 you can see my code : https://dmoj.ca/src/1961373. I think i write a similar structure to the solution given by vovuh.

• 3 years ago, # ^ | Yes I will dm you

  • 3 years ago, # ^ | ok will wait for your message

  • 3 years ago, # ^ | Kindly post it here, it will help others too. TIA

• 2 years ago, # ^ | Akshay184 luciocf A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T. Can you please tell me whether this problem follows this standard definition? Because I dont see it following. Or may be I am wrong.

  • 14 months ago, # ^ | No, in this problem, a subtree means a connected subgraph of the tree. It does not include all its descendants.

• 3 years ago, # ^ | I think your mistake is that you are keeping track of the last seen element rather than the first seen.

• 3 years ago, # ^ | 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 years ago, # ^ | Thank you, I'm new to CodeForces so I didn't know how to view the test that hacked my code.

    • 3 years ago, # ^ | To view the hack: Your Profile -> Submissions -> Hacked Submission -> # Button -> View Hack Your Hacked Submission

• 3 years ago, # ^ | the problem is on how you build the tree, i changed your buildTree method, check https://codeforces.com/contest/1324/submission/73114269

  • 3 years ago, # ^ | Oh, yeah, I definitely did not build tree correctly :). Thank you very much!

• 3 years ago, # ^ | Why 6 downvotes?? :(

  • 3 years ago, # ^ | 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 years ago, # ^ | 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 years ago, # ^ | Thanks got it now. The pairs will be unique anyways as per the above solution.

• 3 years ago, # ^ | Its a simple include/exclude concept used in dp/recursion problems, like subset sum, Coin change etc.

  • 3 years ago, # ^ | Thanks

  • 3 years ago, # ^ | thanks NoobCoder1998. That's also my question too.

• 3 years ago, # ^ | The sort itself takes O(nlogn)

  • 3 years ago, # ^ | ← Rev. 3 →   0 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 years ago, # ^ | And yet, the solution still has a time complexity of O(NlogN)...

    • 3 years ago, # ^ | 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 years ago, # ^ | 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 years ago, # ^ | 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 years ago, # | this contest be like:

• 3 years ago, # ^ | ← Rev. 2 →   0 THIS COMENT DELETE

• 3 years ago, # ^ | 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 years ago, # ^ | Thanks!

  • • 3 years ago, # ^ | Yes , im sorry . its n*log(n).

• 3 years ago, # ^ | 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 years ago, # ^ | 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 years ago, # ^ | 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 years ago, # ^ | You are not alone.I spent much more time on A than B、C、D.

• 3 years ago, # ^ | 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 years ago, # ^ | ← Rev. 2 →   0 Thank you all for your attempts. I think I have a somewhat better understanding now.

• 3 years ago, # ^ | Your approach is O(N Log N) sort function

  • 3 years ago, # ^ | oh,sorry I forgot it,haha!

• 3 years ago, # ^ | 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 years ago, # ^ | 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.

{ 
        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 years ago, # ^ | change the data type of result as long. Overflow is happening.

  • 3 years ago, # ^ | Wtf!!! Such a silly mistake. I wasted an hour almost to debug my solution. Thanks a lot

• 3 years ago, # ^ | ← Rev. 2 →   0 2 pointer is good approach ............

• 3 years ago, # ^ | No, you can't solve E by greedy.

• 3 years ago, # ^ | ← Rev. 2 →   +1 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.

  • 3 years ago, # ^ | Thanks it worked. P.S I love pizza as well

• 3 years ago, # ^ | 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.

• • 3 years ago, # ^ | 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; }

• 3 years ago, # ^ | 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

  • 3 years ago, # ^ | thanks a lot. got it. I didn't know that I can delete elements between two 6's

• 3 years ago, # ^ | 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.

• 3 years ago, # ^ | the problem is nothing we have to remove the duplicacy therefore we have neglected the negative terms...

• 3 years ago, # ^ | I finally figure it out. Help this can help you. After we sort it, we make the list sort from smallest to biggest. Because we are using the lower_bound() function, which imply we only find the is smaller than . That's why we could skip .

• 3 years ago, # ^ | ← Rev. 3 →   0 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 :)

  • 3 years ago, # ^ | Thanks! I can understand it now.

• • 3 years ago, # ^ | 10/10 Mr. Specialist a14789654. Thank you very much!

• 3 months ago, # ^ | did u find the reason how its working after getting sorted

• 2 years ago, # ^ | solved.. it may be an interesting task to find out bug in this solution. Spoiler

• 2 years ago, # ^ | Assuming you're talking about problem F, we don't want to add to since we want to maximize .

  • 2 years ago, # ^ | mphillotry A subtree of a tree T is a tree S consisting of a node in T and all of its descendants in T. But doesnt the condition max(0, dp[child]) violate the above standard definition? Please reply.

    • 2 years ago, # ^ | The tree is unrooted therefore descendants don't make sense in this context. The editorial only fixes the tree on some root to help solving the problem. Perhaps it wasn't the best choice to call them subtrees as confusions like yours may result, but the problem statement does give its own definition of a "subtree": the subtree of the tree is the connected subgraph of the given tree.

      • 2 years ago, # ^ | mphillotry Got it. Thank you so much.

• 2 years ago, # ^ | In this problem, just assume it to be a tetris game and we have unlimited (2*1) blocks with height 2 and width 1, and we have to clear everything on the board, it gets cleared when a full row is completed, so for clearing everything we must have already existing columns w same parity only then they all can have same height and all the rows can be deleted.

• 13 months ago, # ^ | Resolved .. Error was :- c++ stl unorderd_map can have O(n^2) time complexity . Using map ( ordered map ) solved the problem because it's worst time complexity in O(logn)