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!
We hope you will have fun!
We sure did!!
Great Contest
Hope your contest will be success <3
I see no contest in the link ?
We'll add the contest to the group only on Sunday
Show when can I register for it ?
You can register for the contest a few hours before it starts
How hard is it, is it estimate about Div2 A-B-C ? (600 ~ 1500 *rate ?)
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.
How many Div2-B and Div1 estimated-difficult-problems are there ?
Sorry but I can't answer this question :/
Ok, how about the topic use for the contest, are they all randomly ?
Yes, they all are random.
Okkk. Thanks for replying
Asking for too many things then forgot to take part in the contest. Sorry problem-setter :((
what will be the range of difficulty ?
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.→
Will it be rated?
No it is not
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.
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.
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 :)
I don't think we're on an enough level to help create an official round :(
Thank you for your efforts! Hope it's gonna be fun!
The contest is now available to register!
The participant's solutions will be made available?
Can anyone explain how to solve C. Trees and Decrees?
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.
thank you for responding Devil, but can you elaborate it a bit more after sorting the queries by r.
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:
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
Please release the solutions and test cases. Leonardo_Paes
What was the expected solution for D? Felt something like connected components, but no luck.
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.
I don't get why this is valid?
Your solution seems to be wrong for this case, unless you're doing something I'm not understanding.
Yep it seems like my solution is wrong for this case, it looks like tests are weak for this problem!
what is the expected solution to this problem? Also could you allow us to see other people submissions?
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:
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).
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
It's quite funny that we posted exactly same countertests to the abovementioned solution :)))
I think they forgot about this test, I totally agree with both of you!
Nice contest! Thanks :)
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 :(
Oh, sorry :/ The array is destroyed but the index was already used :/ We are working hard to rejudge the solutions.
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.
Divide and Conquer DP Optimization, check this problem and its editorial for a detailed explanation
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 :)
I didn't prove it :(
It just seemed really intuitive
It's easy to prove https://codeforces.com/blog/entry/8219?#comment-139242
It can be done with D&C, as RedNextCentury sad, but it also can be done with segment trees, stacks + multiset, or normal DP!
Can you please explain those solutions? Also, will you be publishing an editorial?
We are thinking about it, but we are almost sure we will!
Thanks for the contest :)
Thanks for the contest! Will there be an editorial?
We are thinking about it, but we are almost sure we will post it!
can you please allow us to see other users submissions?
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.
Nice contest! Can you please make all the testcases visible to us?
Problem K doesn't work again.
Btw. nice contest! Enjoyed it.
can someone help me in problem B,i tried to solve it using weighted bipartite matching but i got TLE in test case 85.
Use https://en.wikipedia.org/wiki/Hungarian_algorithm
thank you
i got TLE on test 88 is there another approach?
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
Can someone share their solution for problem H?
Any editorial? Leonardo_Paes yan.silva
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...
https://codeforces.com/group/t62S9paTEF/contest/274030/submission/75540140