Codeforces Round #642 (Div. 3) Editorial
source link: http://codeforces.com/blog/entry/77373
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Codeforces Round #642 (Div. 3) Editorial
All problems, except the problem D, are mine. The problem D author is MikeMirzayanov.
1353D - Constructing the Array
3 years ago, # | |
-
For E I implemented the same solution in Python. I get TLE on test 4. Are the problems not meant to be solved in python? Should I learn C++ instead?
Edit: Including submission link https://codeforces.com/contest/1353/submission/80416176
3 years ago, # | Too fast editorial!! |
-
-
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
-
3 years ago, # | Editorial is out but nothing under tutorial section? |
3 years ago, # | ⚡Lightning speed editorial |
Stupid question here...can someone explain the solution to first question(the last test case). Thanks |
3 years ago, # | Omg, i don't know that i can modify the set like that. |
3 years ago, # | 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. |
-
The final formula comes out to be n*(n-1)*(n+1)/3!!
-
Please Explain How u getting 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.
3 years ago, # | Is there a way to solve D in O(n)? |
3 years ago, # | can anyone please explain D |
-
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.
-
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
3 years ago, # | 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. |
3 years ago, # | Why B have more submissions than A? |
3 years ago, # | fastest editorial in the NEWS |
3 years ago, # | What is the correct path for the F problem in 2 example? (btw in this example n = 5 m = 5) |
3 years ago, # | How to solve 'D' using priority queue can someone help me with comparator function in priority queue. |
-
Approach to solve problem D with priority queue : [ With C++ pseudocode ]
- Create a structure for segment :
struct segment { int start; int end; };
- 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++As initially , the array contains all zeros. So, insert {0, n-1} to the priority queue initially.
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, whenstart > ind-1
orind+1>end
)
3 years ago, # | |
-
This is the minimum subarray sum problem.
-
Can you explain a bit ? I didn't get it. What his solution is exactly doing?
-
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.
-
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??
-
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).
-
-
How is this contiguous part solved by minimum/maximum subarray sum problem?
-
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; }
~~~~~
-
-
-
can someone explain why its TLE? 80160568 it is not nlogn complexity? |
-
I'm not sure, but maybe something's wrong with PriorityQueue. I replaced it with heapq in your solution and it got AC 80179294.
3 years ago, # | Super fast editorial, time complexity O(1), great!!!! |
3 years ago, # | How to prove that optimal solution for A is 2*m if n>2 ? |
-
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$$$.
-
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
-
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.
3 years ago, # | is there any chance of solving E by binary search ??? |
3 years ago, # | Did anyone solve E with D&C? |
3 years ago, # | 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! |
-
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.
3 years ago, # | 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. |
-
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!
-
that makes me curious, when standard computers get significantly better will time limits also be adjusted for problems?
-
3 years ago, # | Quick Tutorial |
3 years ago, # | 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. |
-
I have a simple solution for E 80161569
-
What is $$$dp[i]$$$ in your code. The min value we can get if first on-bulb is at position i, plus some..values?
-
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}$$$
-
-
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,
- 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 aboveand 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
-
3 years ago, # | So good contest, thanks |
3 years ago, # | Can D be Solved with recursion ? My recursive solution is failing |
-
-
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 ?
-
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 .
-
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.
-
-
3 years ago, # | Hi, could anyone explain in problem F, why a certain cell doesn't change its height? How to prove 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.
-
Hi, Can you please help me in understanding why my solution for Problem F is giving WA, I am really not able to find a case for it! https://codeforces.com/contest/1353/submission/80304472
3 years ago, # | In problem F, why is Now we can notice one important fact: in the optimal answer, the height of some cell remains unchanged true? |
3 years ago, # | 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
"|" this denotes the outermost square which has elements 2*3+2*(n-2)=8 |
-
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
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. |
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. |
-
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.
3 years ago, # | I have doubt in B sol . what if the 3rd case would be 9 9 10 10 10, 1 2 3 4 5, this?? |
-
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
-
when run the exact same code in code chef compiler , the output was
but, it should be 39
which indicates that there is a problem in solution .
-
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.
-
3 years ago, # | how to solve F .i didn't understand second paragraph of F editorial. |
Issue solved. |
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.
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).
|
-
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 9The answer is 2, but if you use the maximum value of a[0][0], which is 5, you'll need more than 2 steps.
-
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.
-
3 years ago, # | Anyone solved E recursively ? Please reply with your submission. I'm having trouble understanding the editorial and iterative code. |
3 years ago, # | 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 |
For problem D // set element is pair<segment_length,pair<left,right>>
|
-
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;
-
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.
3 years ago, # | 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 |
3 years ago, # | i didn't get problem C! ! |
3 years ago, # | 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 |
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 |
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)$$$. 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$$$. |
-
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
-
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.
-
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? |
Please someone Approach
3.to get minimum number of moves = min(#moves to turn on series i + #moves to turn off every other series) for every series. |
-
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
3 years ago, # | 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. |
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. |
3 years ago, # | For problem F editorial, "in the optimal answer, the height of some cell remains unchanged". What is the proof of that? |
-
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.
-
Hi, Can you help me in getting whats going wrong in my approach, I am unable to get a testcase for which my approach is giving Wrong Answer in Problem F. Here is my code link: https://codeforces.com/contest/1353/submission/80304472
-
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.
-
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.
3 years ago, # | Well commented and clean code for E |
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 |
3 years ago, # | 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 |
3 years ago, # | Great Editorial. |
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 |
-
Not sure what a "bucket" does, but somehow it has to sort the elements. Which is the logn factor.
-
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).
-
3 years ago, # | For problem D, one can also avoid the comparator function (if one feels uncomfortable using it) by modifying the set a bit:
We can insert values as follows:
The negative value of length makes sure that the maximum element is at the beginning. |
3 years ago, # | 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." |
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. |
3 years ago, # | 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]) |
Can someone explain me how did he come up with the formula of dpi[p] in the problem of kth-periodic garland(Prob 1353E)?? |
3 years ago, # | 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 :) |
-
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.
3 years ago, # | The tag for Problem F also contains "$$$dfs$$$ $$$and$$$ $$$similar$$$". Does anyone know the approach? |
3 years ago, # | I have solved 1 problem(A), yet my rating is decreased. Would someone please tell me the reason? |
-
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.
-
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
-
The calculation of ratings is based on ranking in contests. The changes in ratings of people sum up to zero.
-
thanks
-
So... did it went well?
-
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..
-
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.
-
-
-
-
-
-
3 years ago, # | 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 ? |
3 years ago, # |
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? |
3 years ago, # | 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
|
-
How this code is supposed to work?
-
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
-
Can anyone tell me why I am getting WA in test 2 in Problem F: My logic is almost same as in the tutorial. Here is my solution link: https://codeforces.com/contest/1353/submission/80220039 |
3 years ago, # | Can someone help me to figure out? Why I am facing |
3 years ago, # | problem D can be solved in O(n) |
3 years ago, # | Has anyone solved E with memoization approach? I have construct recursive solution for same but I'm stuck at optimisation My submission |
3 years ago, # | Can we do Problem-D by BFS? I tried doing it.. but apparently its failing at even numbers >=10 |
3 years ago, # | Can anyone please provide a counter test case(or tell me my mistake) for my solution to problem E? it's giving wrong answer on test 2. https://codeforces.com/contest/1353/submission/80218519 Thanks in Advance :) |
3 years ago, # | In the editorial of question F, are we trying to find a path through which it should definitely pass through (x,y) or is it not necessary but instead we are only taking into account the existence of (x,y) for some optimal answer ? Thanks in advance. |
-
In optimal answer there should be atleast one point unchanged . E.x :there is a 1×2 matrix 5 3 then you should definitely keep 5 unchanged and make 3 to 6 or keep 3 unchanged and make 5 to 2. You can change both but ans for that will always be greater than the ans you get in the previous way. Hope you understood.
3 years ago, # | In Problem F, Why aij>=bij ? |
3 years ago, # | Can anyone provide a DP solution for E? I'm curious to know about that possibility. |
-
https://codeforces.com/contest/1353/submission/80223587
This is my one...Though,it will work little slower than the editorial,But easier logic I think so...
3 years ago, # | Hello guys I have some troubles in promblem E. I do a 2D dp[i][j] as a minimum number of moves to make j first lamp become good with the last lamp is i this is my submission https://codeforces.com/contest/1353/submission/80232689 please help me =(( thanks in advance |
Problem Div3-F Can someone please help me debug this code. I have tried some small test cases of that problem and those were giving correct output. SUBMISSION DIV3-F Edit: I have found the mistake. |
3 years ago, # | anyone can help me out on question F. why my code is failed on test 2.i am filling dp from bottom to up 80189787. |
3 years ago, # | Mike, thanks for the round, the difficulty of the tasks was well chosen |
Could someone explain how to make '111100000' 3-periodic in 2 moves as it is in the example of problem E ? Input: Output: In other words, if the followings are all possible 3-periodic binary strings, which one is produced in 2 moves? '000000000' |
3 years ago, # | Could someone pls explain me E..? |
3 years ago, # | In problem C (n(n+1)(2n+1))/6 how it come... Please Anyone explain it.. |
3 years ago, # | Can someone explain why my solution for E is giving TLE?? |
3 years ago, # | Does my Python solution to problem E TLE simply because it is in Python? My solution is DP in that dp[n][0] = minimum number of moves to make the first n chars cyclic and the last one is 0 dp[n][1] = minimum number of moves to make the first n chars cyclic and the last one is 1 and using a prefix sum, I don't have any loop in my recursive function Spoiler |
-
Yes. TLE because it's python. In case if you wonder how to make it fastest speed, here is a little guide by me:
- Any builtin function is faster than your implementation. So: list.index, str.find, sum, max, sort — is your friends. They work faster than if you make same things by hands.
- Try to avoid .append for lists. Allocate whole list at once using [None]*n or [0]*n. I don't know which one is faster, but it's faster than .append for sure.
- All dictionary / set stuff has additional constant. So use plain list when applicable. (in code above dp can be done by just two plain list, and check in by comparison with None)
- Avoid recursion: python require more resources and time for argument passing. 1e5 recursion gives stack overflow. To increase stack use sys.setrecursionlimit(10**6) for example.
- Code outside of functions is slower than code inside. So wrap solution in function or at east each test should be solved in function
- PyPy can speedup even more. But sometimes PyPy is slower than raw Python.
I was trying to list in order of how often each thing is used. But regarding to impact on code I think from highest caused slowdowns order is: 4, 3, 2, 5. Regarding to 6 you can't compare it with others. And 1 — you use it well.
10 months ago, # | A. Most Unstable Array. Can anyone explain clearly for me the answer as Min(2,n-1)*m ? I read the tutorial but don't understand |
2 days ago, # | Questions like F MAKE ME RAGE, SUCH A SIMPLE QUESTION BUT MY IMPLEMENTATION HAS SOME BUG I CANT FIND :( Can anyone help me find the bug (my submission) |
-
Take a look at Ticket 16797 from CF Stress for a counter example.
Recommend
-
19
Upd: fixed author's solution links.Sorry for the slow Editorial, I am new using Polygon.Special thanks to TechNite for his help.About one hour before...
-
15
Bidhan's blog
-
16
I'm sorry for a delay with publishing the editorial. 733A - Grasshopper And the StringIn this problem you have to find the longest sequence of...
-
22
editorials_late_again's blog
-
18
Codeforces Round #726 (Div.2) Editorial ssense's blog
-
11
350A - TLLet's v = min(ai), p = max(ai), c = min(bi). So, if max(2 * v, ...
-
14
okwedook's blog
-
4
4qqqq's blog ...
-
35
1625A - Ancient CivilizationNote that the problem can be solved independently for each bit, as the bits don't influence each other. Set the iith bit to ze...
-
15
Maksim1744's blog
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK