Hello, Codeforces!
I am pleased to invite you to Codeforces Round 547 (Div. 3), which will start on Mar/19/2019 17:35 (Moscow time). Everyone whose current rating is strictly less than 1600 is invited to participate officially. All others can take part out of the competition.
It so happened that the schedule of this month is not replete with rounds (coordinators, we hope for you!). Therefore I decided to partially correct the situation. All the problems of this round were invented and prepared by me on the last day of Hello Muscat Programming Bootcamp 2019 and on flights from Muscat to St. Petersburg. I even specially noted the time for preparation: for the current moment (the problems are ready for testing) I spent about 6 hours on their preparation, including inventing some of the problems. I really like working on problems, this is something at the intersection of creativity and programming. I really hope you enjoy the result of my work.
I am in Oman while writing the problems for the round.
The round will be hosted by rules of educational rounds (extended ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over. You will be given 6-8 problems for 2 hours to solve them.
Note that the penalty for incorrect submissions in this round is 10 minutes.
Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:
- take part in at least two rated rounds (and solve at least one problem in each of them),
- do not have a point of 1900 or higher in the rating.
Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.
I hope a little later a list of thanks to testers will appear instead of this paragraph. So far I only plan to give the round to testing. Many thanks to the testers ivan100sic, KrK, Benq, I_love_Tanya_Romanova, nhho! UPD: And extra thanks to more testers Pavs, awoo, Narts, anon20016, Stresshoover, Ivan19981305.
Good luck on the round
— MikeMirzayanov
Round #543?
Fixed, thanks.
Молодец Майк.
MikeMirzayanov is always ready to take codeforces to a great level. Thank you so much for providing us a great platform to learn.
from where mike mirzayanov practice problems ?
He creates new problem and solves it.
Thank you for this sudden surprise during these boring holidays
Just asking, but how many time did you sleep for the last two days?
I think he doesn't sleep!
of course
I'm happy :)
I'm a simple man, i see Mike i upvote
Where are div1 rounds?))
Will Div.2+3 be a new kind of contest
Isn't div.2 pretty much that already?
U R right.
Happy to know that the test cases will be stronger enough.
Best of luck
Happy Coding
Where's the "Thanks to MikeMirzayanov for codeforces and polygon"???
Guys It was a joke why do you minus that?
yeah welcome to trashforces, ignorant people will downvote anyone
you explained your self .. "why"
A round without dear Vovuh, but we still got the great Mike :D
Looking forward to it. ;)
It seems to have been quite a while since the last contest has ended. So I'm looking forward to the next contest. :)
Great to see Mike frequent involvement in the codeforces community, really inspiring :-)
last div3 was awesome!! looking forward to this now...
"It so happened that the schedule of this month is not replete with rounds..." true... thats sad :(
wow(copy-paste is not contained in the blog of div3 round). I think it is going to be an interesting contest.
:3
I'm so happy that the original creator is still in touch with us students. Even takes time to think up new and creative problems for us in Div 3 :D
wata???
You forgot to thank MikeMirzayanov for the awesome Codeforces and Polygon platforms, hope everything goes well!
thank him for rigging it up so we lose? no thanks
ha, some guy at the top said almost the same thing and he got a bunch of downvotes. funny
I think two hours isn't enough to solve 8 problems!!!
It is real to do this, and if this fails, you can always complete tasks after the competition
well it obviously isn't but do they care? no, they don't care about us
Well, it is harder than normal div3.
One of the best contests I have given. All the problems were very interesting. Problem F was very good, I thought of the logic but could not code it within time.
I think this Div.3 is a Good Contest with high quality
I rewrote my solution for D at the last moment and submitted when 3/4 minutes was remaining.But it was kept in queue for the last 3/4 minutes . And after the contest ended I now see that I got WA for a small mistake that I could have fixed if the verdict was given on time . Is this fair !!!
If there is In Queue problem the duration of round should be extended
C was nice. Other ones- Don't give up while implementing. (I did) :p
I go TLE. i tried to avoid it but got TLE in different test cases.
This is my Code
any hint ?
assuming there are n numbers then you can get n equations with n variables from the constraints given. Use the fact that the sum of numbers is S= n*(n+1)/2 and other n-1 equations can be obtained from the q array. You can get the last number using these equations and then all other numbers can be calculated using this and q array.
i don't understand !
See the comment of GrandDaddy below, he has explained it properly.
If you get any element other can be found. So we try to find out the first one. Observe that p2=p1+q1 , p3=p2+q2 = p1+q1+q2 , p4 = p3+q3 = p1+q1+q2+q3 and so on. So add all p1,p2...pn which is an equation in p1 and you already know the sum of the expression. Thus you get p1 and other elements. Output -1 if p1 is not an integer or obtained permutation doesn't contain all numbers from 1 to n.
The time complexity of your code is O(n*n)
C was very nice problem, can anybody explain me the approach. Can't wait till editorials are out!
You are given essentially a difference array, so if you compute the prefix sum array you should get the original elements offset by some number. You keep track of minimum and maximum of this prefix array, and the first element should be 1-minimum. While constructing the original array you also make sure each element from 1 to N is seen once only.
Hello! Let's write our array as: p2-p1, p3-p2, p4-p3, ... , p(n) — p(n — 1).
Now let's find the prefix sum of this array. Then we will have following: p2-p1, p3-p1, p4-p1, ... , p(n) — p1.
I think it is obvious that if we have two same elements in the prefix sum array then answer is -1.
Otherwise let's take element n-p1 (it is the maximum). Let it be equal X. Then n-p1 = X -> p1 = n-X. Now, using this p1, we can construct our array. If such answer is valid, we can print it. Otherwise answer is -1.
You can assume the first element be x. then the second element is q1 + x third element is q1 + q2 + x. the fourth element is q1 + q2 + q3 + x and so on. the sum of all elements is (n*(n+1))/2
so you can find the value of x.
after finding x you can easily find entire permutation
I solved using prefix sums and some basic maths.
Approach:
$$$(q_1) = (a_2-a_1)$$$
$$$(q_1+q_2) = (a_3-a_1)$$$
$$$(q_1+q_2+q_3) = (a_4-a_1)$$$
And so on. Summing all the above equations we get:
$$$\Sigma ($$$prefix terms of $$$q)=(a_2+a_3+...+a_n)-a_1(n-1)$$$
$$$\Sigma ($$$prefix terms of $$$q)=((n*(n+1)/2)-a_1)-a_1(n-1)$$$
Find $$$a_1$$$ from the above equation. Once you find $$$a_1$$$, you can easily find the rest terms using the given values of $$$q$$$. Finally, check if all terms are present in the range $$$1$$$ to $$$n$$$ and also check if all terms are distinct or not. If not, print $$$-1$$$ and exit. Else print the numbers.
I'll leave the implementation part for you to try. Hope this helps. Happy Coding.
Nicely explained. Thanks
I followed the way you explained but getting WA could you please give a look here? 51556867
You are probably getting an integer overflow. Make sure you have used the right data types.
Think of it as plotting n points on a 2d grid where the index of the array is the x coordinate and value at that index is the y coordinate, start from (1,0) (assume the value of the first element to be 0) and use the given array q for calculating the position of next points.
a[1] = 0
a[2] = a[1] + q[1]
a[3] = a[2] + q[2]
and so on. Now find the minimum value in this array, let the minimum value we get from the constructed array be min_val. Now add min_val+1 to all the elements of the array (shifting the whole plotted figure up so that the lowest point is 1).Now check whether the array is a valid permutation or not and print the result. Here's the implementation of above mentioned approach. 51508498 Hope this helps.Very nice explain!
My approach i wrote the O(n ^ 2) approach to find a sequence. let's assume that the first element is a1 = n, so we get sequence a1, a2, .., an if we decrease the first element by 1 all other elements also decrease by 1 so i assume that the first element is n and i make sure that are elements are distinct and if i increase or decrease my sequence the min and max element inside the sequence is 1 and n. 51541819
The speed at which people here solve problems is just unbelievable! Kudos!
Listen to twice and you will solve problems faster.
Kudos to MikeMirzayanov. Organized a great Div. 3 round in minimal time!
Well I thought there were ONLY 24!!!! characters in English then I got sweet WA for D at last second, switch to 26 after the contest and I got AC What the heck I am thinking about ????
Your display picture perfectly describes your reaction.
In this problem 741D - Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths, input ensures that there is only characrer a-v.
I fail to solve this problem, just because I missed it :(
Problem G is a fake problem! I'm so weak
Could you help me problem C, I got TLE. I generate all permutation and check for each of them. My code: https://ideone.com/PME2fJ
This complexity is too high I think you should learn from others' code.
The number of all permutation is $$$O(n!)$$$, and for each permuation, you need $$$O(n)$$$ to check it.
So your solution is $$$O(n\cdot n!)$$$, quite large :(
You can try an array $$$n, n-1, n-2,\dots,1$$$, and n is $$$10^5$$$, your solution will get TLE :(
When n is quite small, your solution can get the answer.
Thank you! I will tried another solution.
How to solve problem F?
Just use map<int,vector<R,L>> store the sum of every l and r,after that you can sort the vector and get the answer.
$$$n \le 1500$$$, so you can use a map to store each block with the same sum.
For each sum, there are many segments, and some of them may intersect. so you need to calculate the maximum number of disjoint segments, and this problem an be solved using greedy algorithm.
How would you calculate time complexity for this solution? O(n^2) for all possible sum but what about upper bound on processing each vector corresponding to a certain possible sum?
There are $$$n^2$$$ possible sum, so $$$O(n^2 log n^2)$$$ insert all the sum into the map.
In the greedy algorithm, we also need at most $$$O(n^2 log n^2)$$$ to sort all the elements(each element will be sorted at most once), and $$$O(n^2)$$$ to get the answer.
Same as total times insertion is done because each pair is processed only once.
I enjoyed this round Strong pretests and balanced problemset
Awsome DIV3 contest!!!
can someone please help with f2
There are only O(n^2) many (L-R) pairs. You can generate all of them, and group them by their sum. Then find the maximal non-overlapping subset of each group. This can be done greedily (by sorting first appropriately).
No need to sort to find overlaps — https://codeforces.net/contest/1141/submission/51548853
Oh, that's nice.
For question 2, How
is invalid input. According to question it seems good.
"It is guaranteed that a_i = 0 for at least one i"
Ohh, Thank You I just forgot about that.
i have a question what will happen if you hack your own code?
The Universe will explode!
How to solve H?
How to solve your blindness? There is not H problem in this round.
Sorry my bad. How to solve I then?
Idk really. I did not read that problem.
kudos to MikeMirzayanov !!! . Conducted really good round with awesome questions.
Why its showing WA even though the TC is giving the correct result on my PC. solution
I'm pretty sure that your solution also gives the wrong result on your computer. Check again.
plz find a test case at which my solution is getting wrong answer. https://codeforces.net/contest/1141/submission/51545372
You can see it after the hacking phase.
Edit: Sorry, I forgot they show all pretests during div 3 rounds.
Actually it is available.test case 38. but it is too large , so all inputs are not visible.so if some one can provide a test case , i would be able to correct it .
5
-2 -2 1 2
Your solution prints -1
The correct permutation is 5 3 1 2 4
Many thanks! Although after updating the solution it is still showing wrong answer . Updated solution:- https://codeforces.net/contest/1141/submission/51545372
5
3 -2 1 2
Answer: 1 4 2 3 5
I checked your code earlier but I gotta admit I was to lazy to understand it. Can you explain your solution?
Problem E , Can anyone tell me why this code is giving wrong answer at test case : 92
https://codeforces.net/contest/1141/submission/51547489
what i did is , suppose we had played x-1 round and currently at round x , we will check whether we can kill monter in that round x or not , if yes we shift high to curr round — 1 else low to curr round + 1 .
Write a brute-force program and make some small scale random input to check whether your algorithm is correct.
If you can't kill the monster in round x, it doesn't mean that you can't kill it in earlier rounds.
why i am dwnvted. have i asked anything wrong
.
Overall round was pretty good, I thought that this was one of the easier Div 3. Although wish I had 10 more min to submit E ;) I hope to see more of these types of problems in the future.
anyone could say me the solution of problem G ?
So, I haven’t submitted this solution yet, but I think I have the idea.
Generate the degree sequence for the tree. The k nodes with the highest degrees will be bad nodes. Then the (k+1)th highest degree (call it c) will be the number of colors needed so that (n-k) nodes are good and k are bad. That is, with c colors, we can color edges so that (n-k) nodes have edges of all distinct colors. This will work because (n-k) nodes will have degrees <= c.
We can then choose a root, and greedily color the tree from the top down.
why color the edge greedily will be the answer ? (with dfs)
let's say the highest degree is C.
if we're at a node which has a degree greater than C we can colour them all the same colour, it doesn't really matter. If it's less than or equal to C, we start colouring it from 1 and keep incrementing it for each child(with the exception that it can't be the edge connecting it to the parent's colour)
thank you . i understood very well :)
Here,the scenario is look like for starting questions Div2<Div3
Has anyone solved problem E using Binary search, I am getting wrong answer on test case 17.
Your binary search borders are so high they cause long long overflow in min hp calculations.
Yes i got it why it is failing. can u suggest what changes should i make?
I set the upper bound to $$$\lceil \frac{hp}{-sum} \rceil$$$ in my solution and it worked fine.
Yes, you are applying binary search for the round right? I was applying for the minute at which the monster will be killed. The solution with binary search on rounds got accepted. Thanks.
Oh, true, binary search on minute is surely inapplicable.
I had to post this
yes.. i solved it.. see my solution and if doubt dm or tag me in announcement
Yes, I saw ur solution, it was involving binary search on rounds right? I was applying binary search for the exact minute at which the monster will be killed, and apparently as Pikmike mentioned, while calculation of min, long long would overflow. Thanks for help!
no calculation of minute along with overflow will give wrong answer .
if it is not possible to kill monter in x th minute then its not possible to kill monster in < x minutes , is wrong approach . u have to take rounds .
at first i thougt bs on minutes , but laster i realized its wrong .
Yes u are right. I realized it very late. :)
Why my contribution went from 0 to -4 by itself (just wondering)
whats going on?? why C is rejudged?
Problem c Many people construct a sequence starting at 1, and then judge whether {1 2 3 ... n} is satisfied. In the judgment, some people use the Vis array mark to determine whether there are duplicate numbers. This is not a good solution. Considering the worst case, (2e5 19999 19999.....), this will appear. The case where the array is out of bounds.
Meh, that's the boring hack. Check this solution 51538168! $$$cp$$$ gets equal to $$$-2^{31}$$$, then $$$x$$$ becomes $$$2^{31} + 1 = -2^{31} + 2$$$ and thus no $$$-1$$$ checks are hit because the conditions are too weak.
X and map should be long long? I think his code is not rigorous.
Basically, $$$x$$$ and $$$cp$$$ is enough to be long long. I don't think you can break map being int tbh.
C:
Runtime error on test 42;
solved: 5->4;
standing:249->756;
I:happy->unhappy;
Anyway, excellent and innovative problemset .
You are already very good, I only solved 3 problems.
Great contest, I learned a lot of ways to think about the problem.
thx XDDD
//谢啦2333
Same thing happened with many people(including me).
Not sure those are final, as an unrated before taking part in the contest, I'm already rated, but seems final standings are yet to be shown.
Can anybody please tell me why this solution for problem F2 is failing at test case 28?
The segments should be sorted by the right end, so you greedily take always the one that ends the earliest.
Thanks. Just by changing sort to right end it passed all the test cases.
Someone, Please explain D.
Just think simple!
We know that ? will make compatible pair with anything!
So first we make pairs that doesn't have any ? and after that pairs that has exactly one ? and at the end pairs that are both ?.
It is clear that the algorithm is the optimal.
wrong answer in D: "You can't use one boot in two pairs", can anyone tell me what it means? and why it give me a wrong answer, this is my practiceYour text to link here...
Look, the boots are for the left or for the right foot.
You want to match these boots (make pairs of left and right boots).
And "You can't use one boot in two pairs" means that you can't match a boot with two other boots.
For example you have two boots of left foot numbered 1 and 2, and two boots of right foot numbered 3 and 4. you can't match boot number 1 with boots 3 and 4, you can choose at most one of them.
oh, Thanks for your answer! I have thought that! But why my practice is wrong, I have checked for much time, can you speed a little time checking my practice? Wrong answer on test 22, the test data is so long, I can't see the remaining part.
I have found it!!!
and here is a test for you
6
??aa??
??????
I thought successful hacking would add my points, but it seems to be not the case. The rule says it's worth 100 points. Has it been changed?
that is for div2 and div1 contests (expect educationals).
hacks in contest's that have hacking phase after the contest don't have any point.
Thanks for clarification! Is it stated somewhere?
Editorial
Thank you for this good contest.
Why did so many people fail problem C? Somehow, my solution passed but I was still wondering.
most people did not check the duplicate elements they generated in permutation
C was indeed a creative problem! :)
When can we expect editorial of this contest?
Editorial