Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

# | User | Rating |
---|---|---|

1 | Benq | 3783 |

2 | jiangly | 3666 |

3 | tourist | 3611 |

4 | Um_nik | 3536 |

5 | inaFSTream | 3477 |

6 | fantasy | 3468 |

7 | maroonrk | 3464 |

8 | QAQAutoMaton | 3428 |

9 | ecnerwala | 3427 |

10 | Ormlis | 3396 |

# | User | Contrib. |
---|---|---|

1 | Um_nik | 184 |

2 | adamant | 177 |

2 | awoo | 177 |

4 | nor | 169 |

5 | maroonrk | 165 |

6 | -is-this-fft- | 163 |

7 | antontrygubO_o | 152 |

8 | ko_osaga | 151 |

9 | dario2994 | 150 |

10 | SecondThread | 148 |

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial is loading...

Tutorial of Codeforces Round 619 (Div. 2)

↑

↓

Codeforces (c) Copyright 2010-2023 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jun/08/2023 20:37:22 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

LOL, my solution for E in $$$O(n^3+qn)$$$ passed. Although, I know how to make it $$$n^3+q$$$.

I think authors didn't want to cut off solutions with such complexity.

Authors solution seems to be a lot faster. Mine works in nearly 1.9 sec, which is very tight.

I wrote this approach (which works in O(n*(nm + q))) and it works about 1076 ms on the worst test-case.

Looks like it is impossible to distinguish between log n log m, which is approximately 100, and n / 2, which is 250.

BTW the math markup appears to be broken, as a line break is added everywhere after using it.

It makes sense but they could make q equal to 2e6.

Do you know solution with such comlexity O(min(n,m)*nm + q)?

Yes, I wrote it in my first comment.

Can you explain it please?

Well basically I reduce the problem into $$$O(n^2)$$$ arrays of length $$$n$$$ and then use some imple of RMQ. Stupid one is $$$O(n)$$$ per query, but (we all know) it can be solved in $$$O(n)$$$ precount and $$$O(1)$$$ per query using the method of four Russians.

I'm sorry, but I still couldn't understand your algorithm. Would you mind elaborating it or posting your submit?

At first I precount a cubic dp[i][j][len] — best ans for a square len * len at position (i,j). Now when a query comes we need to check $$$O(n)$$$ squares to find the optimal answer. That's where I use RMQ (so it can be implemented in many ways). You can read more about best RMQ algorithms on wiki.

Submission is here 70999212.

I'm sorry, I mean the algorithm with the time complexity of O(n^3+q), which you have mentioned previously.

I suppose you can go here RMQ solution and follow Farach-Colton and Bender algorithm link.

Because I haven't learnt 2D sparse table,I tried to solve the problem in

.But it seemed to be failed... In this problem,

is much slower than

...

The problem is $$$log^{3}n$$$ is actually a lot more than $$$n$$$. Does anybody know what's wrong with math parsing?

Yeah,you are right,so I have to rewrite my code now...

Why I got TLE in O(n^3 + qn)??

The TL is very tight, you must write optimal code to pass.

can you tell me proof that the required element for problem number 2 is always the average of the lowest number and the highest number in the array? Thanks in Advance

Formal proof: for any two numbers $$$a$$$ and $$$b$$$ we need to minimize $$$max(|a-x|,|b-x|)$$$. This happens when those functions intersect which occurs in $$$(a+b)/2$$$.

Typo in C, should be $$$\dfrac{n\cdot(n+1)}{2} - \dfrac{k\cdot(k+1)}{2}\cdot g - (k+1)\cdot(z\mod g)$$$

You're right, sorry I will fix it.

In the editorial of problem C, it's mentioned that

(k+1)zeroes are given to(z mod g)groups and the remaining groups are givenkzeroes.That means the number of substrings which need to be subtracted from the total

Despite being written in the explanation about the count of substrings having

'L'zeroes, the final equation was directly written.But nevertheless the editorial is very well written.

Can You please explain, why are we assigning (k+1) zeroes to first z mod g group?

See we that there are total

zzeroes in the string and we want to equally divide it into the string in sets of continuous substrings of zeroes so that the substrings removed from the total possible substrings of the complete binary number get reduced.So,

zzeroes need to be divided intoggroups.Let

So,

Now if

(g-(z mod g))groups are assignedkzeroes and(z mod g)groups are assigned(k+1)zeroes, then total should come asz(as it's the total number of zeroes present).Thus,

(g-(z mod g))groups are assigned k zeroes and(z mod g)groups are assigned(k+1)zeroes. Now we simply apply the formula of possible substrings when we have a string of lengthLas mentioned in the tutorial.It is not necessary that you assign the

(k+1)zeroes to the first(z mod g)groups only. You can assign(k+1)zeroes to any of the(z mod g)groups out of theggroups available.thanks i was also unclear about (k+1)*(zmodg)

In the D problem, the contraints for the number of steps is too weak

(1<=a<=3000)when all the paths can be traversed in just1500 stepsonly (even mentioned in the editorial as3nsteps).El3ageed_Abu_Shehab, I really have to admit the round as a whole was very well written along with the tutorials to the problems. Despite being a little tough round and getting a dip on my ratings, I have to say, I loved upsolving the questions of this round. Learned new concepts, especially from the

E problem.El3ageed_Abu_Shehab Thank u for this Editorial But i thnik you mean "at most" instead of "at least" in the last problem tutorial !

Can you point where in the problem statement that "at most" is? I missed it.

I mean here in the tutorial of F " you may use an edge that goes from a cell to another one with the same color at least once"

Yes, I understand. But I cannot find that in the problem statement. So, I do not understand why this sentence is there.

I think the problem statement says we can use edges between cells of same color as many times as usefull, no limit at all. Not at least, not at most.

Can you explain?

As i understood , you don't have to use two edges or more and stay in the same color .. because if you at the cell x and go to y with the same color then go from y to z with the same color.. that is not optimal because u can go from x to z directly .. so that i say you may use "at most" one edge

Ahh, ok, makes sense. Use every color at most once.

But what about going from color c1 to c1 then to c2 and then c2 again. Here we have used the "same-color type" edge twice!!

The path never used the same color twice, because it would be shorter using the color only once.

Problem F, how do we find a path where we have to use "tunnels" of more than one color, one after the other?

We can do this during the BFS.

We need to BFS for $$$k$$$ times and every time we calculate one color. Now we only consider one BFS which calculates color $$$a$$$.

Let $$$d$$$$$$i$$$$$$s$$$$$$[$$$$$$i$$$$$$]$$$ the minimum cost from color $$$a$$$ to cell $$$i$$$.

During the BFS, when we reach cell $$$u$$$, whose color is $$$b$$$, we update all the cells in color $$$b$$$ by $$$d$$$$$$i$$$$$$s$$$$$$[$$$$$$u$$$$$$]$$$$$$+$$$$$$1$$$, because we can go to them from $$$u$$$ in one second.

In this way, when finding pathes we can use "tunnels" of more than one color.

Here's my code. 71045624

I see. Since you have to do this for every pair of colors only once you use cvis[]. Thanks!

Nevermind, I messed up with author's solution

.

Imagine that you have a set of 1D points and need to find a point such that maximum distance between this point and any point in the set is minimised.

This is exactly the same problem here. The point that will minimise that distance is the mid point.

I don't understand why the solution works for problem B

Place all the determined numbers on an axis, and your mission now is to find a point where the maximum of the distance from that point to any other points is minimized. There are three conditions: on the left of the min, on the right of the max, and in between the min and the max. It's obvious that the first two conditions are not better than the third one, and in the third one You'll find out by intuition(apparently) that the mid point of the min and the max is the optimal choice. On top of that, you have to consider the determined numbers adjacent already, which have to be calculated, and is hinted in the sample.

Nicely Explained!

"The current mid is correct if the maximum element in that 2D range is greater than or equal to (4⋅mid⋅mid)". How does the existence of such an element guarantee that the

answer >=4*mid*midfor the given submatrix ?Can someone explain the binary search version of B?

The problem asks to find the smallest number of an absolute value function. If you plot an absolute value function (for eg. f(x) = |x|) on a graph, it's V shaped — both negative and positive values of x converge at a minima (in case of f(x) = |x|, that minima is 0). The goal is to find this minima.

In the given problem, f(x) generates a similar graph — if mid is too large, then f(x) (which returns the max between mid and every element in the array) can be very large. Same thing when mid is too small (the absolute difference between max value and mid can be very large). You want to find the right middle ground.

So, by comparing f(x) with f(x+1), you can get a sense of which direction to go: - If f(mid) <= f(mid+1), you want to go the direction of mid. Drop the second half of the array (mid+1 through high), and focus on low through mid - If f(mid) > f(mid+1), you want to go the direction of mid+1. Drop low through mid, and focus on mid+1 through high.

So in a gist, keep comparing mid with mid+1, and go in the direction of the smaller value. Stop as soon as l>=h. (Reference: https://codeforces.com/contest/1301/submission/71083423)

There's another approach (https://codeforces.com/contest/1301/submission/70970135) which seems to follow a similar concept though I'm not clear on the implementation details.

Can i suppose that ternary search is easy to think/realise in case of mod based problem than binary. Binary seach is also logical but need more implementation. I should apply ternary seach algo in case of mod/parabolic functions ?

Actually, a ternary search may be more appropriate than a binary search here: https://cp-algorithms.com/num_methods/ternary_search.html

(Reference: https://codeforces.com/contest/1301/submission/70967290)

Thanks for the quick editorial <3

Let me show a solution for problem D with quite short code. 71031620

Move like this: Pictrue

The largest number of steps is 2996.

Can you please tell me how you come up with this solution?

E can be solved in O(n^3 + q log n) without the use of data structures. Call a red point such that they are part of the center of a Nanosoft logo a "critical" point, and it's "range" half the maximum subsquare that can be a Nanosoft logo. Then we can run binary search on answer. In order to check if subrectangle (r1, c1) — (r2, c2) can contain a subsquare of size m such that it is a Nanosoft logo, the subrectangle (r1 + m — 1, c1 + m — 1) — (r2 — m + 1, c2 — m + 1) must contain a critical point with range m (and it's green, blue, yellow counterparts as well). In order to check this in O(1), we can use prefix sums, and since you need to calculate it for all values, it works in O(n^3). Here is my code: https://codeforces.com/contest/1301/submission/71003726.

Thanks for the hint. It's much easier.

Question of problem F "But visiting all other cells that has the same color every time is too slow, so we can only visit these cells when we reach the first cell from every color." what does that mean? How do you complete bfs while skipping grids with same color? I did not understand this part…

Read the code, then you can understand it.

Can anyone mathematically prove for problem B that the best k is equal to (minimum value + maximum value)/2 ? Thanks.

Let us denote minimum value by min, maximum value by max. Let us assume that k is best at some point other than the average say t, this gives the cost to be maximum(abs(max — t), abs(min — t)). Case 1: t > average, cost = t — min > average — min >= average — min + 1 (since average can be 1 more from the right than left). Therefore the calculated cost is greater or equal to the cost when we choose k to be the average of minimum and maximum value. Similarly, we can show for the case when t < average. I hope that helps.

`

I am having problem in question C for k size string their will be k*(k+1)/2 substring but for k+1 size why the total substrings are k+1 ? UPD: i got it now

Hello,

In Problem 1301B, why doesn't calculating the mean(average) of all the non-negative numbers adjacent to -1s, instead of

(minimum value + maximum value) / 2, give the correct answer. Really stuck at this :) Thank you for the help.Because you can consider ,Test_case: 1 -1 100 -1 101 So as per your logic k=67 so m=66 but if you do k=(max+min)/2 k=51 so m=50 I hope this helps!!!

Why did no one ask about whether you can rotate the square in problem E to make it a valid logo...? I think this should be made a clarification for future virtual pariticipants.

The hard part of the proof in C is proving that it should be "as equal as possible". The author conveniently skips that.

Can you please explain me the proof for it

Yes can anyone give the proof for this?

Well the hint to the proof is: you can see that for

$$$f(x)=\frac{x\cdot(x+1)}{2}$$$

and you have $$$x_1=t-d$$$ and $$$x_2=t+d$$$, $$$x_3=t$$$ and $$$x_4=t$$$,

we have, $$$x_1+x_2=x_3+x_4$$$ and,

$$$f(x_1)+f(x_2)>f(x_3)+f(x_4)$$$

so, reducing the "distance" between variables always minimises the value of the function.

Why does this straightforward $$$ O(n * m * k + q * k) $$$ solution fail for problem F https://codeforces.com/contest/1301/submission/72293018

B's second test's 369th testcase sucks

I have an alternate solution to E with time $$$O((nm+q)\sqrt[3]{nm})$$$.

A logo with radius $$$k$$$ has area $$$4k^2$$$, and logos can't overlap. So, there are at most $$$\frac{nm}{4k^2}$$$ logos with radius at least $$$k$$$.

Because large rectangles are rare, we can check each of them with every query. And for smaller rectangles, we can build a DP table of size $$$n\times m\times k$$$ to quickly check for small logos in a subrectangle.

Preprocessing takes $$$O(nmk)$$$ time and each query takes $$$O(k+\frac{nm}{k^2})$$$ time, which is optimal when $$$k=\sqrt[3]{nm}$$$.

Hi, El3ageed_Abu_Shehab, somethings puzzled me in problem F:

what's the "+1" for in "Otherwise you should find the best color that you will use that edge in it, the cost will be (the minimum cost between any cell of that color with first cell + the minimum cost between any cell of that color with the second cell + 1)."?

don't we need to consider the possibility of jumping using multiple colors? As I see from your code, it seems it just use one color for jumping in the min solution.

In problem C can someone please explain me the proof for why the greedy strategy of dividing m+1 groups "as close as possible" works

Here my Binary Search approach for B, I check all the difference using binary search and choose the smallest one.

<spoiler summary="#include<bits/stdc++.h> using namespace std;

## define ll long long int

## define ul unsigned long long int

## define speed ios_base::sync_with_stdio(false); cin.tie(NULL)

int main() { speed; int t; cin>>t; while(t--) { ll n,l=0,h=INT_MAX,ans=0,diff; cin>>n; ll a[n]; ll m=-2; bool minus=true; for(ll i=0;i<n;i++){ cin>>a[i]; m=max(m,a[i]);

}"> ...

My Pattern for D:I agree the Editorial's approach is a bit simplier.

Also, I was unable to fix an upper bound to as how many number of steps were required, so I simply checked the Max. Case 500 500 998000 and submitted. I'm not sure though. I think constraints for 'a' could be tightened.

Anyways, Great Problemset !

Nice and Useful Contest

174332065 i tried problem B using binary search but it is giving wrong answer on test case 2 ? anyone please help ?

I really don't know how to binary search it , but you can visualize a line of points( a rope) going up from min to max values in the array adjacent to the -1. you can see that the only two points that we want to care about is the max and the min why? because our maximum will really be impacted by the maximum and the min more than the other points because the maximum value of abs value can't actually come from other points (visualize it and try to convince yourself)

now let's proove for maximum-min even and do the odd yourself,

let's proove that the best answer is X=(maximum-minimum)/2

this way we can say the maximum Abs Value is X right? right .

it's obvious that we can't make X above maximum because we can minimize the max by lowering X :) (same for below the minimum)

now let's discuss the case the new X is between maximum and minimum and not the old X (maximum-minimum)/2 , so let's say X=X+delta,

say delta > 0 (the same thing for delta <0) this way we got further from the minimum -> our max abs value will be bigger by that delta

I think this method of proof is called the exchange arguments.