Привет, Codeforces!
Мы рады пригласить вас на Codeforces Round #610 (Div. 2), который пройдет в 24.12.2019 17:35 (Московское время). Он будет рейтинговым для всех участников, чей рейтинг ниже 2100. Вам будет предложено шесть задач и два часа на их решение.
Задачи были придуманы и подготовлены коллективом университета ИТМО Supermagzzz, Stepavly, AdvancerMan, unreal.eugene, MikeMirzayanov.
Особую благодарность выражаем MikeMirzayanov за замечательные системы Codeforces и Polygon, а также за координирование нашего раунда.
UPD1: Выражаем благодарность команде тестеров университета ИТМО: budalnik, Alexxx, Darui99, golikovnik, sharepoLOVEDDD, Mr.Hakimov, zergey.gad, MeowMr, Ilya-bar, 1ncendiary
Одна из задач раунда будет интерактивной. Вы можете прочитать руководство по интерактивным задачам здесь.
UPD2: Разбалловка: 500 — (500 — 1000) — 1750 — 2500 — 2500
Надеемся, вам понравятся задачи. Удачи и высокого рейтинга!
UPD3: Поздравляем победителей!
- Tsypkokokokoko
- K.Yuuki
- hyhtsdy
- ptica
- junukwon
- gumnam
- AnotherRound
- conqueror_of_obd
- rtilikay
- p1rattttt
Разбор будет опубликован в ближайшее время.
UPD4: Разбор опубликован!
Меня очень б
аттхёртитеспокоит, что пешки Мирзаянова могут проводить два контестанизкого качества
в месяц, а остальные ждут в очереди по полгода
Чтобы review на раунд пришло за день надо всего лишь
взять MikeMirzayanov соавтором
Any subtasks?
This is an online contest so there will be no subtasks
He seemed to mistake subtasks of problems to subtasks of pretests. Why is everybody going so hard on him lmao?
I am very worried about the fact that Mirzayanov’s pawns can hold two contests a month, while the rest are waiting in line for six months
New pawn of rotavirus
Hello everyone — Good luck for all I hope I can become a Candidate Master after contest
.
Before round:
Round is rated for Div.2 participants
After round:
UNRATED!
Sad story......
that is a very bad joke.
Finally there is an interactive problem after 9 rounds ! :D
hope interactive problem is not a binary search. pleaaase
It can be a geometry problem too.
or a probability one
are there interactive problems in ICPC contests !
Yes there are!!!
hope for short statements like the last round !
it's look like interesting contest
Can someone please explain what is an interactive problem and whats the difference between and regular problem and an interactive one?? Bcuz i did not really understand the meaning by reading the blog from MikeMirzayanov :) tnx for your help!
Interactive problems(over simplified): the input isn't given all at once, or it's in a "Q&A" style.
Which problem will be Interactive ?
I just finished my graduate entrance exam.It is so excited that I can join contest now.
Excited about the contest after a long break.
Interactive problem and 20 questions ..
can somebody help me with interactive problems
you give the jury some numbers and it will give some information about that. then you should use this information for next question or guess the answer.
What interactive problem will be A,B,C?
Unlikely
I bet that 80% participants of this contest has no girlfriend. It's Christmas Eve!! Go hang out with friends!!
Why you don't go !?
I guess that 100% is much more accurate!!!
for sure 1% of this 10000 person have girlfriend.Don't you think?
Well that sounds true but I'm confident enough they are not more than 5%!
Me either.
Yesterday I was broken up with her. :< Sad ChristMas
Pressing F for you
[deleted]
Can anyone provide link to the mirror website m1/m2/m3 I am not sure where to find it
They will put it just before the contest I think.
m1.codeforces.com
m2.codeforces.com
m3.codeforces.com
Tnx.
Thanks
Merry Christmas!!!
Good contest
feeling orz................
Problem statements are longer than my
hair.Hope for strong pretests. Merry Christmas!!
What is test 6 for D?
Am I the only one who over-killed C with segment tree and stuff and later realize it could have been done simply:((
Am I the only one who doesn't know how to do C?
I think problem C has some problem
Problem C- In statement: 2 <= n <= 1e5
Whereas just changing maxn=1e5+5 to 2e5+5 changed an RTE to AC
This should be rejudged with proper input files and first ac submission should be counted.
UPD5: sorry seems like, I've missed the announcement
It's written 2e5 in C statement
It was 1e5 at the start of the round and updated during the round.
How to solve D?
Solution of D :
You can get length of required string and number of 'b' by asking two queries.
String of 300 a's will give you value = 300 — n + no. of b's.
String of 300 b's will give you value = 300 — n + no. of a's.
Plug them to get above length and no of b's.
Take a string of n a's and start locking the indexes in order by using provided answer and no. of b's left to be selected.
Just curious: Are you intentionally dropping your ratings?
No.
My approach for D, making at most $$$n+2$$$ queries: 67539477
First make two queries, one with 300 A's and the second with 300 B's to figure how many A's and B's are in the string, and therefore its length.
Notice that the edit distance from a string of length $$$k$$$ with all of the A's already placed is $$$n-k$$$ if and only if between no two A's we have more B's than in the hidden string (as then we could not make only insert-operations).
Using this, add B's before the first A until the edit distance doesn't decrease, then place the first A and repeat. Thus after the $$$i$$$th operation, we know a prefix of length $$$i$$$ of the hidden string. Thus after $$$n-1$$$ operations we know the entire string (as we know character counts). Including the first two queries, we make at most $$$n+2$$$ queries in total.
To get number of A's and B's you can also query a single "a" first, and then an all "b" string of length equal to answer of first query.
I think I did this, but I'm getting WA on Q5 with the comment:
Do you know what is wrong?
My solution is failing with input abababababababab, and the error message is
wrong answer Line [name=s_17] equals to "", doesn't correspond to pattern "[ab]{1,300}"
However, when I tested locally it seems to work, and I also added asserts to check that I never output empty strings. My code is below.
http://codeforces.net/contest/1282/submission/67561919
Thank you!
I couldn't solve the problem, but I think you should look over here probably. This comment
Hey simp1eton, Could you tell what the problem was. I am receiving the same verdict as you mentioned. I used 300 a's and 300 b's to find the length. Here is my submission 67569644
I assumed wrongly how edit distance is computed. I think if your program throws and exits for any reason, the checker says that your program outputs an empty string
I was also having the same issue. But later found that, when testing locally I was miscalculating the edit distance.
This was happening because my program existed before and the testing program was getting EOF and probably taking it as an empty string.
Can anyone help me why I am getting wrong answer for Div2 B1??? My approach- Sort the array. Check if you can buy all items till index 'i' supposing that you got i-1 item for free. 67533371
Do you consider the case when you purchase the first item itself, and not for free?
YES
Your program outputs 4 for this, but should be 6
Can you please clarify your test case what are you taking?
The test case is as follows -
1
6 4 2
1 1 1 1 2 2
Answer should be 4 right???
No, you can buy all, choose the 2nd 1, the 4th 1 and the 6th 2
Update — I think you somewhere forgot to do i += 2
please explain solution of B1 i am beginner here
Sure, for the case of $$$k = 2$$$ (which is easier actually, since you need to solve the problem in $$$O(n)$$$ time); first of all, sort the array on the basis of prices. Now try to understand the points mentioned here as to why they're true. Now, going ahead, since k is just 2, you either choose the first one and then keep taking 1 on 1 as the offer; or you take all goods on offer, the answer is the max of the two.
with two 1's can take other two other 1's and with one '2' can take other '2', in all 6 while spending 1+1+2=4.
Got it. We can apply the offer again and again. I thought that we can apply it only once. Wasted an hour on this.
Oh shit dude (cries in corner)
what is the hack of B2??
O(k*k) Algorithms will not work. While there were no tests as such in Pretests.
how to solve B2?
first sort all items. then you make a list with size k that ith element is the cost if you take i starting elements alone. for each item(after k initial items) you update the list.
can you please elaborate more?
Sort the array first.
Try to understand the following facts -
If not choosing to use the offers, you should buy only the first few(< k) items, and not from any later part of array.
Once you buy some or all of the first k items, you would only use the offer now, and no individual buyings.
thanks a lot.
Can someone please explain why I got TLE in the problem Div 2-B2 ? Here is the link to my solution.Solution
Because PriorityQueue.remove() function has O(n) complexity instead of O(log n) in Java
1
6 17 2 6
0 0 1 0 0 1
7 6 3 7 10 12
Why should that give us 1 as an output? (Problem C-petya and exam) can someone help me?
At t = 2, you can solve any one of the non mandatory easy problems
oh thank you man, I've understood it now
Ultra fast system testing
Ok codeforces
*your worst
Hey man, your contribution is already -26. So I strongly recommend you think twice before you make a comment .
I agree tbh. The problem statements are overcomplicated and the score distribution is really not balanced. Who decided to put D = E?
E was a very nice problem. Among the best I've seen in a while. Too bad I had a silly bug in my code during the contest.
D was also nice. Hats off to the authors.
One of the fastest one I've ever seen...
D&E are realy good problems! ABC — stupid idealess problems!
Hello Codeforces, I didn't see the notification that the bounds for problem C were changed. As a result, I didn't notice the change for a long time. Would it be possible to unrate me? thanks!
My first correct sub with wrong bounds: https://codeforces.net/contest/1282/submission/67543972 Changed to 2e5: https://codeforces.net/contest/1282/submission/67558110
Unrate :eric:
Am I the only one who did B by handling $$$K >= \sqrt{N}$$$ and $$$K < \sqrt{N}$$$ differently?
Well, I was planning to do the same at first :D
I'll post a screencast of the round within 12 hours. (I will also add those 5 minutes which I did not have enough to pass E).
UPD I hope the screencast will be available tomorrow at 07:00(MSK) by this link in good quality
UPD2 It is available
Approx 25% of all ACs of D ended up in fst, the edge case being bbbb...300 times. This was an obvious edge case and I do not get why you guys did not include it in pretests. Was this deliberate by any chance?
Fortunately, Tsypkokokokoko hacked my solution with this test case and I managed to correct my solution
Congratulations on your 1st rank, Tsypkokokokoko!
Actually I do not understand what is the difference between bbbb… 8 times (as in test 4) and 300 times. What's more, I wonder why would anyone want to include the 300 constant in their program (and so, it's no longer an "Edge case")
Well I was checking your code and it seems the rand() part saved you. try printing just "a" in the beginning and you will know.
Oh, that's like the weirdest thing that happened to me for the past 2 years on Codeforces :P If I print just "a" in the beginning (which I tried to do, submit #1...) I get TLE 4 (which is the first monochrome test). There are MANY such tests up to #67, so idk why those solutions make it that far...
Seem like you got really lucky :p
More like time trouble :)
With 5 minutes left, I couldn't figure out how to find |s| and I just made this leap of faith, haha
Btw, I was 110% sure this would fail the systests and even now I don't know why it passed (there were soooo many monochrome strings)
My program uses aaa..aaa (301 times) as second query in this case and for some crazy reason it is not allowed. I would be very angry if this was an actual round for me, not the one where I do educational video.
Guess, it's time to rewrite this one :D https://codeforces.net/blog/entry/62744
More like reread, and also the story with Golovanov399 and 22 vs 20. Yes, double standards.
Rereading this particular fragment would be enough I guess:
Nope, this is not it. I didn't ask for a clarification. Also I'm not that mad to consider the problem bad because of small issue.
Well, you don't have to build so literal analogies. It's up to you to decide what conclusions you leave for yourself from this situation. I just suggest you to think why you call not allowing
string(301, 'a')"crazy" and compare this to that sentence from your blog.There is a clear divide between ranting about the problem during the contest in a clarification and ranting about the contest afterwards.
Also I didn't call allowing crazy.
And yes, I already did admit that there is a resemblance, what's the problem?
Test 67 for D?
bbbbb....300 times
67542439 Can you help me with finding out what is wrong with this solution? It works with 5b's, and I don't see anything that would make it not work with 300 b's.
your code is probably printing 301 characters somewhere.
Thanks, I figured it out, it was because if there was 300 a's or b's, my code would continue after getting a query of 0.
Amazing system testing speed. Like
In problem C, I created 2 sets one to store hard problems mandatory time and the other to store easy problems mandatory time. Every time I check first problem in Easy problem + a and first problem in Hard problem + b and i take the one which Solved eailer. then I check if any problem should be solve in this time and I add it I only update the answer if the time at the end <= the total time of exam
Why this idea is wrong ? 67550974
Checker for D is incorrect. This solution https://codeforces.net/contest/1282/submission/67555058 still outputting things after getting 0 as response for the test "b" * 300, but I got incorrect hacking attempt on this one.
Hack is here https://codeforces.net/contest/1282/hacks/603027
In the problem statement it says that on such cases the checker will give an "arbitrary" verdict, which can include Accepted (depending on how the checker is written).
Good evening everyone! Help me please understand what am I doing wrong on the second problem, so for the input (n = 4, p = 9, k = 2) and the numbers { 2, 3, 4, 5 } the expected output is 4, mine is 3. Thanks in advance!
If you buy the 2nd good then it will cost you 3, and you will get the first one for free and you will be left with p = 9-3 = 6. Then just buy a good 4 for 5 and get good 3 for free. Hence finally, you have 4 goods.
Offer can be used more than once. You can pick 3 and 5,you get 2 with 3 and 4 with 5 for free
Yeah, cool!
Can someone tell what's wrong in this solution of D? 67559495
How come the pretests for D didn't include a single string with max length? It seems the longest string in the pretests had only 17 characters.
to add a little bit of suspense, I guess :)
Can not understand why let $$$O(k^2)$$$ solution pass B2 pretest.
how to $$$O(k^2)$$$?
Hello. Please AdvancerMan could you help me understand why 67555899 got WA. The problem is that when I run locally the 5th case it returns the correct spell.
Thanks in advance
Check how you calculate the edit distance.
that is exactly the problem. I am calculating the edit distance in a wrong way.
Thank you so much
I didn't submit because i couldn't solve Div2-B1. And i couldn't solve B because I kept thinking offer had to be applied once. I really think the setter should have clearly mentioned that :'( . Looking forward to next contest
can someone explain how to solve C?
I am getting WA for Problem D.
The checker says I printed an empty line (" ") which not acceptable , but my code doesn't print any such line.
Here it it : My Submission
Thanks in advance!
UPDATE : Resolved! :)
> If the number of spells exceeds limit (n+2, where n is the length of the spell s, which is unknown to you), you will get the Wrong Answer verdict.
That could be the reason
Yup I did check for that. My code always prints n+2 strings , no more than that!
AdvancerMan can you please have a look?
Thank you!
UPDATE : Resolved! :)
Your program prints no more than $$$n + 2$$$ strings but it doesn't print the correct answer to the first test as well. Your output for the first test:
Just came online to update this XD
Thanks I messed up edit-distance part!
Thanks for the help! :D :)
Awesome problemset, super fast system testing and rating change -> In a word a nice contest!
This contest is also exiting for me, because I found my mistake in code for problem C last minute and submitted 30 seconds before the contest ends and it got Accepted, and became blue after a long gap.
Thanks for the nice contest!
div2 b is similar to house robber but cannot solve in the contest :(
For a second I thought I can't solve B2 so i went for naive approach in B1. after writing some stupid long worthless code i tried B and solved it much faster and with less lines of code.Should have just sticked to B2.
My solution for D got AC code. But it is wrong, because i write always n + 2.. Ok.. This solution on C++11 got RE code. Then this solution got RE too. Can anyone explain me, how is it working?
Try exiting the program if a == 0 or b == 0 as soon as you get them. I don't know why that would give an out of bounds error, but I had the same problem.
Ok thanks, it is really strange...
I don't understand the WA message
wrong answer Line [name=s_8] equals to "", doesn't correspond to pattern "[ab]{1,300}"on D. I tested my solution locally and I am not printing any empty strings.you can't ask an empty string
No, I am not asking any empty strings.
It seems to me that checker does not handle termination after "-1" properly.
Shoudn't B2 be done this way?
sort the given array. maintain K lists of prefix sum of (i%k) indices only. Then find upper bound of p in these lists, return the max. of these upper bounds. Also add to these upper bounds, those gifts which still can be bought without any offers, after each upper_bound applied.
My submission is failing on 55th TC of 2nd test case. Can someone please help me with that? I am not able to get that particular test case, since it is not being rendered on CF.
It is simple dp, where dp[i] is min money to pay for first i problems. Sort the goods by price.
dp[i]==min(dp[i-1]+a[i], dp[i-k]+a[i])
You can allways buy goods one by one, or choose at any point to buy k goods at once. Anyway, you allways buy the cheapest goods.
What strange problems this contest have. I felt upset from Problem B(1).
Problem D
Why if I do more than N + 2 requests (exactly 1000 times) "aabba" it passes 1st test? link. I guess that checker counts only unique requests, not the actual number of requests. My solution was making N + 3 requests (while I thought it was N + 2) and I was getting WA 5 the whole contest. I couldn't even think that the problem was with a checker :(
after first time you print "aabba" checker stop it 67562780
I think that wasn't mentioned in the problem statement.
Anyone solve B with binary search..
Not sure it would work. In this problem if you can buy x items, there is no guarantee you can also buy x-1 items.
But some are manage to pass by using binary search. Can't understand how.. sol 1 — https://codeforces.net/contest/1282/submission/67533137 sol 2 — https://codeforces.net/contest/1282/submission/67532628 In the second case the user use the binary search twice.. Can u explain the logic behind both the solutin... Thanks..
My submission using binary search: 67564167. Not sure if my idea is the same as those above.
My idea is to sort the goods by their prices, then fix the number of goods that we have to buy separately (obviously, it's in range $$$[0,k-1]$$$), and finally using binary search to find the number of group of k goods that we can buy.
If the numbers of good that we buy separately is
i, it's optimal to buy the firstigoods.Overall complexity should be $$$O((n+k)logn)$$$.
If you really want to you can binary search on the number of groups of size K you buy, then binary search on the number of singletons you additionally buy.
Yeah u are correct if your predicate is
can we buy x itemsbut if you consider predicate to becan we buy at least x itemsthen BS can be applied code : 67538774Thanks for replying, can u explain what does second while loop do i.e inside bs.
Can anyone explain that why in this solution https://codeforces.net/contest/1282/submission/67533137 they use midb and the for loop for midb, with using only mid as in normal binary search answer fail on first case on test case 7.. Pls explain why midb is necessary.
For binary search, your function needs to be monotonic, and this is not the case when you just use the "mid" approach. In the seventh case, note that it costs 7 to get three things, but 3 to get four.
This is caused by being forced to buy mid%k items individually. The "midb" approach compensates for this by "rounding up" and checking the answer for the next multiple of k. This works because the cost for all values between mid and midb is greater than or equal to the cost of mid and the cost of all values larger than midb is greater than or equal to the cost of midb (proof left as an exercise).
How would the solution for D be affected if the strings were not binary? Let's say you had 26*(n+2) queries. Would the same technique work? If not, what would change?
How this test case in 1282C - Petya and Exam is getting the answer as 1. Shouldn't it be 0?
You can solve any of the easy problems and leave the exam at t = 2, which nets you one point.
Thanks, I got it.
No At time t = 2 he can leave the exam after solving 1 easy problem.
WA because of integer overflow hurts again
In Problem C, second Testcase, the 12th test is
Since mandantory times are 2 and 0, and a==3 I would expect the answer to be 0, no problem can be solved in time, since the first solved problem is at t==3, that is after 0 (and 2).
But grader says answer is 2, so both problems should be solvable in time.
What did I get wrong, can somebody explain? submisson
It is not necessary to start solving problem before it's mandatory time.
Ahhh, I understand. There is no need to solve the problems until mandatory time. Only, if one finishes after mandatory time, that problems must have been solved.
Funny, that the whole first test and the 11 ones before the 12th work correct, even after getting the problem so wrong.
Because T = 13, you can solve the two problems and leave at t = 6 (which is < T).
Mandatory doesn't mean it has to be solved before that time, it means that if you don't leave before it becomes mandatory, then you cannot leave until you solve it (it doesn't matter when you solve it but you have to solve it before leaving), but you still have to do that before you run out of time (t=T).
Ok, got it, thanks.
This was one of the worst rounds I've done. I hope none of real coordinators would allow problems ABE in the contest. D was nice, but forbidding to ask queries longer than maximal string is a bit silly. Still, having one nice problem is not enough to make a round out of it. I like when new people are starting in problemsetting, but next time ask for an actual coordinator who is willing to say that your problems are bad.
Just out of curiosity, what was bad in A and B other than the long problem statement?
None of these problems are fresh in any sense.
Cool, makes sense. The problem ideas may seem old especially given your level of experience.
Still according to me both A and B were good problems for beginners.
The first time that I see Nutella's comments are downvoted!
U haven't seen many comments of Um_nik
I would agree on A (probably, suits Div.3 better). B seemed okay, but maybe too complicated statement for little thinking effort. E was nice although seemed too easy for the last problem. But in the end the contest seems to be well-balanced, maybe one more hard problem was missing.
Nah, nice contest :D
E was really nice
I think he forgot to look at... It was Div2 not Div1.
What is the reason for having an upper bound on the size of string query you can ask?
Do stop people from bruteforcing everything.
I'm guessing it's mainly for hacks. It's easy to forget the condition and print a 301 length string
i solved E with topological sort . Is there any other way (for finding the vertices permutation)
Not sure if we can call it topological sort. It's just a simple circular cycle which isn't even directed. Maybe calling it a dfs is enough.
Guess i made it over complicated for me then
can you explain how to use dfs to solve this problem ?
There was a bit of preparation needed before doing the dfs which was the crux of the problem, dfs was simple once you get the idea that —
My code: https://codeforces.net/contest/1282/submission/67581486
thanks.can you explain that idea which led to dfs as solution.I mean can you elaborate a little more.
The main idea was -
How to find those shared edges?
map[edge_a_b]++. Whichever edge has count 2 are the ones where knife went.I solved it like this: the last piece to be cut must contain a vertex which only appears once. So, find such a piece (let's call it [t,a,b], where t only appears once), remove it, solve recursively for the remaining pieces, then in the linked list obtained by solving recursively, replace edge (a,b) with edges (a,t) and (t,b).
Can some one help me find the mistake in my submission 67570438 for Problem D.
When you think your approach is wrong but after contest you realize it is just -1 which gives causes WA, it hurts.
Master as christmas present!
Hello everyone,
I have tried to make video solution for the first four problems of Codeforces Round 610 Div. 2, hoping to help people understand the problem and what was my approach for the same. Please do like the video and do subscribe for more such content.
Video playlist: Codeforces 610 Div2 Video Solutions Playlist
Separate links are as follows: A B1 B2 C
Happy Coding
Divyanshu Kumar
Using google translate for the editorial makes it super hard to understand :(
in problem B1 how can (4 9 2 ) 2 4 3 5 results into 4. its impossible to buy 4 items with 9 coins
Pay 5 coins and take the items 5 and 3. Then, pay 4 coins and take the items 4 and 2.
thanks i thought we could buy only one item for k=2