B was so similar to this

I was thinking of another approach for E.
For x<y, what if we change the problem a bit? I mean now instead of filling on starting of day, we fill at the end of day. And now initial k=r-k+l and we swap(x,y).

Now we have a similar problem where y<=x, and the only change is that we are now filling at the end of the day. Would this work?

What will be the space complexity in Problem D?

There are quite a few O(n*m) solutions for problem B , not sure why O(n*m*m) is the intended solution. I will share approach i have used .

Let dp[i][j] be the number of spruces having (i,j) cell as the bottom center point of the spruce . then dp[i][j] = min(dp[i — 1][j] + 1, min(left[i][j], right[i][j])) . Here left[i][j] is the number of * to the left of (i,j) and right[i][j] is the number of * to the right of cell (i,j) . Both left and right can be easily computed in o(n*m) . The final answer is simply sum of all dp[i][j]

Link : https://mirror.codeforces.com/contest/1461/submission/100925269

If i am passing a new vector in each new recursive call in D then what is space complexity for it.. How should i Calculate time complexity for this??

Link- https://mirror.codeforces.com/contest/1461/submission/100962372

In problem D,What can be the maximum size of the set or map used to store all the possible sums?

I am sure many contestants wouldn't able to solve c if only one example was given. (including me :>)

What's the complexity of problem E? Where is the proof it can pass in time? Is it obvious?

Interesting solution for E.

My unnecessarily over-optimized solution to problem D for anyone interested.

100958922 Can someone tell me, why it is giving TLE in pretest 1, in single for loop... Though giving correct answer..

C was nice

My solution for E is O(1). It's a bit complicated to explain but if interested, you can see the code here.

Edit 2: It turns out that my algorithm was incorrect at the last step after one user hacked my submission. Read this comment below.

Edit: After some people asked, I decided to give a rough idea of my solution. I strongly suggest you to draw a number line on a paper while reading my solution. $$$[x]$$$ represents $$$floor(x)$$$.

I am calculating the max number of days for which it is possible to maintain the water level between $$$l$$$ and $$$r$$$, and storing this value in $$$num$$$ which I will later compare with $$$t$$$ to output "Yes" or "No". If initially $$$k-x < l$$$ and $$$k+y > r$$$ then clearly $$$num = 0$$$ and the ans is "No".

If $$$x = y$$$, then we can maintain the water level indefinitely and the answer is "Yes", no matter what $$$t$$$ is.

If $$$x > y$$$, then the water level must decrease every day at least by an amount of $$$x-y$$$. Assuming $$$k+y \le r$$$, $$$num = \left[\frac{k-l}{x-y}\right]$$$. However if $$$k+y > r$$$, then $$$k-x$$$ must be greater than or equal to $$$l$$$ and so in the first day, we don't add $$$y$$$ and our new $$$k$$$ becomes $$$k-x$$$. Then using the same logic as above, $$$num = 1 + \left[\frac{k-l}{x-y}\right]$$$ (here $$$k$$$ is the new $$$k$$$).

The difficult case is when $$$y > x$$$. Note that if at any point, if $$$k$$$ takes a value in the interval $$$[r-y+1, l+x-1]$$$ then we cannot maintain the water level for another day. So if the interval itself does not contain any integer points, then we can safely say the answer is "Yes". This happens when $$$(r-y+1) - (l+x-1) \ge 1$$$, or equivalently, when $$$x+y \le r-l+1$$$. Otherwise, there is a "danger zone" (i.e. the interval $$$[r-y+1, l+x-1]$$$) where we don't want to step in. If we are on the right side of that danger zone, it means we cannot add $$$y$$$ and on the left side, we cannot subtract $$$x$$$. Inside the danger zone itself, we cannot do either. If we are on the right, we subtract $$$x$$$ as many times as possible which is equal to $$$\left[\frac{k-l}{x}\right]$$$. After doing this, our $$$num$$$ becomes $$$\left[\frac{k-l}{x}\right]$$$ and we reach $$$k = k - \left[\frac{k-l}{x}\right]\cdot x$$$. If we reach the danger zone (can be checked by checking if $$$k+y \le r$$$ is false), then we are done. Otherwise, we must be on the left side of that danger zone and now we need to add $$$y$$$ to our $$$k$$$. If $$$x$$$ divides $$$y$$$, then we can repeat this process indefinitely (adding $$$y$$$ and subtracting $$$x$$$ multiple times) and in that case, our answer will be "Yes" (I have set t = -1 in the code because I am comparing num with t at the end). If there is some non zero remainder, call it $$$rem$$$. After adding $$$y$$$ and subtracting $$$x$$$ $$$\left[\frac{y}{x}\right]$$$ times, we will reach at $$$k = k + rem$$$. We keep doing this until we are outside that danger zone i.e. $$$\left[\frac{r-y-k}{rem}\right]$$$ times. We add $$$\left[\frac{r-y-k}{rem}\right]\cdot\left[\frac{y}{x}\right]$$$ to $$$num$$$ and add $$$\left[\frac{r-y-k}{rem}\right]\cdot rem$$$ to $$$k$$$. After taking another step (1 step = $$$\left[\frac{y}{x}\right]$$$ days), either we can land inside the danger zone meaning we are done, or, we can cross over that danger zone. If we land in the danger zone, then we just simply add $$$\left[\frac{y}{x}\right]$$$ to $$$num$$$ and we are done. Otherwise, we reach at $$$k = k + rem$$$ which lies on the right of danger zone. Since $$$rem < x$$$, subtracting $$$x$$$ will surely take us to the left of danger zone and that too on a location which is left to our original location (before taking the step). The "decrease" in our position after $$$\left[\frac{y}{x}\right]+1$$$ days is $$$x-rem$$$. We can afford to let it decrease only $$$\left[\frac{k+rem - (l+x)}{x-rem}\right]$$$ times and that consumes another $$$\left[\frac{k+rem - (l+x)}{x-rem}\right]\cdot(\left[\frac{y}{x}\right]+1)$$$ days. After another $$$\left[\frac{y}{x}\right]$$$ days, we finally land inside the danger zone and we are done.

I know how can problem B be solved with Dynamic programming, but the explanation in the editorial does not explain 1 single thing about the usage of DP in the problem and why we should use DP instead of just simulating the explanation.

Very poor explanation with very low effort.

when will the rating changes will be published ???

Can someone please explain how to solve the question B ? The solution given in editorial is not clear to me. Thanks

Can someone please explain E? I get the initial part where y<=x.

Otherwise, let's note, when we use the rise in water level, we change the value of the expression k mod x. At each step of the algorithm, we will lower the water level as many times as we can, and then raise the level.

What does this mean? What exactly is the value k mod x. And why do we lower till the time we can and not add y litres of water somewhere in between of this process?

I'm thinking another approach for E:

Determine a range [r-y+1,l+x-1], if we reach this range at the beginning of day, its impossible.

Then use extended euclidean to find the minimum number of days to reach each number in this range

in problem b to decrease the complexty you need to the bigest sprcues for every position and add to the (weidgh-1)/2 to answer and add the number of * to do that you will need to use binary search or memoistion the number of * before the curent index so the complexty will be n * m * log(n)

EDIT: My question (for F) was resolved -- My example in the previous post was wrong -- now makes sense that the case with * and — is very easy as was mentioned in the editorial.

Could somebody explain the following, please? If the product of numbers is greater than or equal to 10^16, then it is beneficial for us to put the multiplication sign everywhere.

can someone please help in B(find the spruce)?

Can anyone help me in figuring out on which test case my code for problem B failed on system test.

My code

Problem link

Please tell me how to solve E if $$$x \le 10^{18}$$$? The problem is that when $$$y > x$$$ then the lowest point may or may not be able to form full cycle (modulo $$$x$$$), how to check this for big $$$x$$$

.

My answer to B was way simpler than the editorial. I just did this 2D DP

if (!block[i][j]) continue;
dp[i][j]=bock[i][j]+min(dp[i+1][j],min(dp[i+1][j-1], dp[i+1][j+1]));
ans+=dp[i][j];

where block[i][j]==1 if (i,j)=='*' else 0 The complexity of this solution is O(NM) so it is the best complexity you can get.

Can anyone xplain the question A(string generation)??

https://mirror.codeforces.com/contest/1461/submission/100931552 Isn't this a simpler approach to B? Also I think it has O(n*m) complexity too.

In editorial of problem E , for y>x , how to justify that doing "we will lower the water level as many times as we can, and then raise the level" will be optimal ?

In problem C, why do we make ans = 0.0, when last correct position is -1?

Why is this solution not correct? https://mirror.codeforces.com/contest/1461/submission/101000199

what's wrong with my code problem A i'm so confused......

Hey guys, so I made this screencast and solutions from A-D, hope you find it useful and am looking forward to honest feedback: https://www.youtube.com/watch?v=JsHC-GW8UVc

So i had a terrible contest. (yet again!) My submission to C gets Wrong Answer on Test case 8 submission

However i can't see any flaw in my approach, guide me. I am maintaining a DP sort[i] if all elements till i are sorted, not_sort[i] otherwise. My recursion is this: where mp[i] is the probability of sorting operation.

if(arr[i]==i)
    sort[i] = sort[i-1] + not_sort[i-1]*mp[i];
    not_sort[i] = 1 - sort[i];
else
    sort[i] = mp[i];
    not_sort[i] = 1-sort[i];

I am getting wrong answer on 10th test case of B. can any body explain the error. https://mirror.codeforces.com/contest/1461/submission/100931109

i wasted a lot of time in B then implemented using dp approach.it was so simple with dp;

I don't know if my method to solve F. Mathematical Expression was smart or dumb. If we observe that it is beneficial to multiply if the product is greater that size of the array. After that we can simply use bitmasking to solve and the complexity would be linear with respect to n.

How to solve C using dynamic programming??

While solving problem E during the contest , what was train of thought which brought you to the conclusion that when y>x we need to decrease water level as much we can and then raise the level ? Was it simply guessing and then proving or there was some steps of thoughts after which you arrived to that conclusion .

can someone explain Problem E i didn't get what editorial wants to say

So i don't know why but my F doesn't work. My solution is this[submission:101137585].So the idea is pretty much the same except for the last part.We can watch every 2 subsequences of array which have 0's in between them. So the solution for subsequence is next: first because 1's on the start and end of subsequence cant help with product but can with addition we know that they must have a '+' sign in between them. So lets watch now for subsequence that starts and ends with numbers that are not 0 or 1. There are 2 cases:if me multiply every number in this subsequence or to multiply every subsequence of this subsequence that consists of numbers greater than 1 and to add the 1's(there is no point in adding any numbers but 1's (because if x, y != 1 then x + y < x * y so it would always be more beneficial to just multiply)).Example: for this subsequence 2 2 1 1 1 2 if we multiply every number we would get 8 but if we multiply the first 2 then add that to the ones and then add the 2 at the end we would get 9 which, indeed, is the best solution. So we are basicly looking for max(product of all elements, number of 1's + sum of products of all subsequences which dont have 1's). So if you can help me i would really appriciate it.

Can someone explain F? Its too difficult to understand from the editorial.

Vladik Can you please tell why I need to handle the separate case of $$$y<=x$$$? means where/how the remainder method will fail.

E: water level input: 7 1 10000 4 2 1 answer: YES

was this test case considered by the jury?

void solution(vector<vector>& v, ll i, ll j, ll height) { if (i >= v.size() || i < 0 || j < 0 || j >= v[0].size()) { return; }

ll cnt_l = 0, cnt_r = 0;
for (ll k = j; k < j + height; k++) {
    if (k >= 0 && k < v[0].size() && v[i][k] == '*'){ cnt_l++;}
    else if(v[i][k] == '.') break;
}
for (ll k = j; k >= j - height + 1; k--) {
    if (k >= 0 && k < v[0].size() && v[i][k] == '*'){ cnt_r++;}
       else if(v[i][k] == '.') break;
}
if (cnt_l != cnt_r) {
    return;
} else if(cnt_l == cnt_r and  cnt_l == height){
    ans += 1;
    solution(v, i + 1, j, height + 1);

}
return;

}

void solve(){ ll n, m; cin>>n>>m; vector<vector>v(n,vector(m)); for(ll i=0; i<n; i++){ for(ll j=0; j<m; j++){ cin>>v[i][j]; } } ll result=0; for(ll i=0; i<n; i++){ for(ll j=0; j<m; j++){ if(v[i][j]=='*'){ ans=0; solution(v,i, j,1); result+=ans; } } } cout<<result<<endl; }

int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); ll t; cin>>t; while(t--){ solve(); } return 0; }

How to convert this recursive solution into dp solution ??