### yan.silva's blog

By yan.silva, history, 4 months ago, ,

Hey guys, what's up? How's the quarantine going?

Leonardo_Paes and I are preparing our first contest. It is ICPC-style, but we recommend that it should be done individually. You'll have 5 hours to solve between 10 and 12 problems. It will be held on this Sunday ( 03/29/2020 ), 14:00 UTC-3 in a private group. You can join this group using this link: https://codeforces.com/group/t62S9paTEF.

We really hope you enjoy the contest!

• +165

 » 4 months ago, # |   +61 We hope you will have fun!
•  » » 4 months ago, # ^ |   +47 We sure did!!Great Contest
 » 4 months ago, # | ← Rev. 2 →   +13 Hope your contest will be success <3I see no contest in the link ?
•  » » 4 months ago, # ^ |   +13 We'll add the contest to the group only on Sunday
•  » » » 4 months ago, # ^ |   +3 Show when can I register for it ?
•  » » » » 4 months ago, # ^ |   +19 You can register for the contest a few hours before it starts
•  » » » » » 4 months ago, # ^ |   +3 How hard is it, is it estimate about Div2 A-B-C ? (600 ~ 1500 *rate ?)
•  » » » » » » 4 months ago, # ^ | ← Rev. 2 →   +30 There are easy, medium and hard problems. The easy ones are around Div-2 B difficulty and the hard ones are in Div-1 range.
•  » » » » » » » 4 months ago, # ^ |   0 How many Div2-B and Div1 estimated-difficult-problems are there ?
•  » » » » » » » » 4 months ago, # ^ | ← Rev. 2 →   +19 Sorry but I can't answer this question :/
•  » » » » » » » » » 4 months ago, # ^ |   0 Ok, how about the topic use for the contest, are they all randomly ?
•  » » » » » » » » » 4 months ago, # ^ | ← Rev. 4 →   +5 Yes, they all are random.
•  » » » » » » » » » 4 months ago, # ^ |   +1 Okkk. Thanks for replying
•  » » » » » » » » » 4 months ago, # ^ |   -27 Asking for too many things then forgot to take part in the contest. Sorry problem-setter :((
 » 4 months ago, # |   0 what will be the range of difficulty ?
•  » » 4 months ago, # ^ |   +43
 » 4 months ago, # |   0 Will it be rated?
•  » » 4 months ago, # ^ |   0 No it is not
 » 4 months ago, # |   0 It would be great, if this contest will be in other date, because at this time a lot of cf users(and ICPC teams) will be in opencup.ru contest.
•  » » 4 months ago, # ^ |   +31 We think that changing the date of this contest it's a bad idea because we had announced it to many people already. But, if people like this contest, we'll make more contest and more people will be able to participate.
 » 4 months ago, # |   +36 Why not using those problems in Codeforces Round?I know it's kinda difficult to prepare official rounds but official rounds are also well organized :)
•  » » 4 months ago, # ^ |   +49 I don't think we're on an enough level to help create an official round :(
 » 4 months ago, # |   +3 Thank you for your efforts! Hope it's gonna be fun!
 » 4 months ago, # | ← Rev. 2 →   0 The contest is now available to register!
 » 4 months ago, # |   +46 The participant's solutions will be made available?
•  » » 4 months ago, # ^ |   +19 Can anyone explain how to solve C. Trees and Decrees?
•  » » » 4 months ago, # ^ |   +6 Binary search on the answer, sort the queries by $r$ and for each query go from $l$ to $r$ taking the maximum you can until that query become 0 or it's impossible.
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 thank you for responding Devil, but can you elaborate it a bit more after sorting the queries by r.
•  » » » » » 4 months ago, # ^ |   +11 Suppose that you want to know for a fixed $k$ if the answer is $\le$ $k$Let's see it as an array $A$ of $n$ elements with value $k$Then for each query $l, r, x$ you need to subtract a total of $x$ between $[l, r]$, if you can do that and $A_i \ge 0$ for all $i$ in the end then the answer is $\le k$The best way of do that is greedy sorting the queries by $r$ and for each one do: for i in [l, r]: z = min(x, A[i]) A[i] -= z x -= z if all the queries have $x = 0$ in the end the answer is $\le k$For speed up the solution just use the compression path idea of disjoint set for find the next $A_i > 0$ instead of iterate from $l$ to $r$, here are the solution
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 Please release the solutions and test cases. Leonardo_Paes
 » 4 months ago, # |   +31 What was the expected solution for D? Felt something like connected components, but no luck.
•  » » 4 months ago, # ^ | ← Rev. 3 →   +40 You need to just find the smallest rectangle such that all points lie in it or on its borders, then just remove the points on the borders of this rectangle and start again until no points are left. Here is my code.
•  » » » 4 months ago, # ^ | ← Rev. 3 →   0 I don't get why this is valid?
•  » » » 4 months ago, # ^ |   +24 Your solution seems to be wrong for this case, unless you're doing something I'm not understanding.
•  » » » » 4 months ago, # ^ |   +8 Yep it seems like my solution is wrong for this case, it looks like tests are weak for this problem!
•  » » » » 4 months ago, # ^ |   +3 what is the expected solution to this problem? Also could you allow us to see other people submissions?
•  » » » 4 months ago, # ^ |   +1 I didn't submit the solution during the contest, and I think that I've misread the statement in some way. Tried re-reading it, but didn't help.So, on the following test: test16 1 1 1 2 1 3 2 1 2 3 3 1 3 2 3 3 4 4 4 5 4 6 5 4 5 6 6 4 6 5 6 6  visualization0000000000 0111000000 0101000000 0111000000 0000111000 0000101000 0000111000 0000000000 your code outputs 3, but the answer, in my understanding, is 2 (you can deal with the top left square and the bottom right square separately).Could someone please point out what piece of the statement I understood incorrectly? :) (since I'm pretty sure that it's my problem — there are x16 accepted solutions).
•  » » » » 4 months ago, # ^ |   +8 It's not just you, I talked to some of the people who got AC in this problem and they seem to be confused by this test too :P
•  » » » » » 4 months ago, # ^ |   +8 It's quite funny that we posted exactly same countertests to the abovementioned solution :)))
•  » » » » 4 months ago, # ^ |   +11 I think they forgot about this test, I totally agree with both of you!
 » 4 months ago, # |   +28 Nice contest! Thanks :)
 » 4 months ago, # |   +8 Problem K: The arrays x and y will be destroyed after this query; the new array receives the index of the smallest positive integer that has not been used yet. The meaning of destroyed in this case is very confusing, I couldn't send it in time because I understood that destroying restores the id :(
•  » » 4 months ago, # ^ |   +16 Oh, sorry :/ The array is destroyed but the index was already used :/ We are working hard to rejudge the solutions.
 » 4 months ago, # |   +25 How to solve H? I came up with the obvious O(n^2*k) dp solution but couldn't figure out a way to optimize it.
•  » » 4 months ago, # ^ |   +28 Divide and Conquer DP Optimization, check this problem and its editorial for a detailed explanation
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 I solved this problem using the Divide and Conquer optimization too, although I don't know how to prove the monotonicity of the argmin. Do you know how to prove it for this particular problem?Thanks :)
•  » » » » 4 months ago, # ^ |   +5 I didn't prove it :(It just seemed really intuitive
•  » » » » 4 months ago, # ^ |   +5 It's easy to prove https://codeforces.com/blog/entry/8219?#comment-139242
•  » » 4 months ago, # ^ | ← Rev. 2 →   +19 It can be done with D&C, as RedNextCentury sad, but it also can be done with segment trees, stacks + multiset, or normal DP!
•  » » » 4 months ago, # ^ |   +15 Can you please explain those solutions? Also, will you be publishing an editorial?
•  » » » » 4 months ago, # ^ |   +22 We are thinking about it, but we are almost sure we will!
 » 4 months ago, # |   +15 Thanks for the contest :)
 » 4 months ago, # | ← Rev. 2 →   +12 Thanks for the contest! Will there be an editorial?
•  » » 4 months ago, # ^ | ← Rev. 2 →   +16 We are thinking about it, but we are almost sure we will post it!
•  » » » 4 months ago, # ^ |   +24 can you please allow us to see other users submissions?
 » 4 months ago, # |   +22 Really my fault for not asking clarification, but the phrasing led me to believe the first query in K meant adding $v$ to the $y$-th element of the $x$-th array, rather than setting the $y$-th element of the $x$-th array to equal $v$ :(Anyways, thanks for the contest! The problems were pretty nice.
 » 4 months ago, # |   +6 Nice contest! Can you please make all the testcases visible to us?
 » 4 months ago, # |   +10 Problem K doesn't work again.Btw. nice contest! Enjoyed it.
 » 4 months ago, # |   0 can someone help me in problem B,i tried to solve it using weighted bipartite matching but i got TLE in test case 85.
•  » » 4 months ago, # ^ |   +3
•  » » » 4 months ago, # ^ |   0 thank you
•  » » » 4 months ago, # ^ |   0 i got TLE on test 88 is there another approach?
•  » » » » 4 months ago, # ^ |   +3 The idea is start a bfs from every possible start for a total of $O(n^3)$ and use Hungarian with the same complexity, look at my solution
 » 4 months ago, # |   0 Can someone share their solution for problem H?
 » 4 months ago, # | ← Rev. 2 →   +6 Any editorial? Leonardo_Paes yan.silva
 » 4 months ago, # | ← Rev. 2 →   0 I have solved the problem A using DFS , I have an intuition about what to do but i am getting wrong answer in the fourth test case,can someone help me out with that. By the way,i am not even taking the edges with composite weights as inputs,as they really don't matter.This is the link to my code.... UPD..I found my mistake,btw thanks...
•  » » 4 months ago, # ^ |   0