Hello, Codeforces!
We are glad to invite you to take part in Codeforces Round 568 (Div. 2), which will be held on Jun/19/2019 17:45 (Moscow time). The round will consist of 7 problems (possibly, plus subproblems). It will be rated for Div. 2 participants.
We, geranazavr555 and cannor147, are students of ITMO University. And we have recently joined the developers team of Codeforces and Polygon. We have prepared this round for more careful acquaintance with the system. We hope that you will enjoy the competition.
Initially, we had prepared the round for Div. 3, but after testing, it became clear that this round is harder than usual such rounds. MikeMirzayanov suggested to make this to be rated for the second division.
Many thanks to MikeMirzayanov for the tremendous work on the creation and development of Codeforces and Polygon and coordinating our work. Also, special thanks to Vshining, awoo, nooinenoojno, vovuh, Lewin, Dave11ar, T-D-K and Azat_Yusupov for testing the round.
Good luck!
UPD1:
The scoring distribution will be: 500 — 1000 — (1000 + 750) — 2000 — 2250 — 2750 — (2750 + 750). The round will last 2 hours and 15 minutes.
UPD2:
Congratulations to the winners:
UPD3:
Editorials are available here.
Another rare round with 7 problems in Div.2!
I hope the contest provides great experience to both the problemsetters and the contestants.
Congratulations!! for organising first time.Hope it will be a good. Thank You.
Hope, no problems with big numbers. Good luck for everyone!
Lol, I can see the scar of the previous contest.
even problem C was easier to implement than B
really, C was filled with corner cases while B was just sum of big numbers with single corner case.(ending with 0).
What corner cases C had?
it was a really big scar );
try python. Some problems are easy if implemented in python. Especially problems does not constrain strictly on complexity.
Wish you the best of luck for organising your first contest
Thanks!
Initially, we had prepared the round for Div. 3.This round would have been a rare Div. 3 in which vovuh's not a setter.Good luck and have fun everyone! :)
lol
Div (2.5) XD
Div(2.5) XD
It's a Div.3, but rated for blue and purple ones. Doesn't happen every day :)
It seems it turned out to be a typical Div. 2 round with a greater number of problems. I hope that everyone in Div.2 will find interesting problems for him/her.
I love interesting problems
Congrats for your first rated round.Hopes your hard work pays off and we can get many more round in future. Good Luck!!
Thanks a lot! Wish you high scores on the contest! :)
Is div2 contest rated for div3 (<1600) participants? Can someone explain the rules.
PS: i googled it, but couldn't find the answer.
Yes.
Thanks for your reply, but any idea on why it is mentioned "it will be rated for div2 participants" in above contest description?
div_x_participants = ∑( i=x -> i=3 ) div_i_participants
Wrong answer on test 1
Successful hacking attempt!
My fault, since I'm just a poor div2 participants, this is totally extracurricular knowledge for me QAQ
So if x = 1 + 2(div1 + div2)?
Initially, we had prepared the round for Div. 3, but after testing, it became clear that this round is harder than usual such roundsMy prediction : A, B, C, D, E are easy problems with some implementation. F is of level div2 D, and G is hard.
hope it will not be hard code as the last div 2
Codeforces Round #568 (Div. 2.5)
Notable points on distribution
By the way, 2 hour 15 minutes for 7 problems.. Our hands will not be able to stop during contest :(
Back to back rounds...yeahhhh!!!...Thanks for the effort..
AB — Div3
CDE — Div2
FG — Div1
Overall — (1*2+2*3+3*2)/7 = 14/7 = 2
So we are having a Div2 today with +/- error of "possibly, subproblems"
We need more problems!
Ставь класс если хочешь видеть никнейм geranazavr555 в списках проблемсеттеров чаще
Now there are more and more subtasks in the problems.
Hope pretests pass=>system test pass,becomes true in this contest.
Can the contest be longer? That seems like a lot of problems for 135 minutes..
it seems it is not a bad contest with lots of implementations because its 9 problems :)
contest is going to be interesting.i hope more 10000 people will do participate.
Is it a wise idea to write contest on mobile and not using paper-pencil due to power-cut?
It can be true that the number of participators will be greater than 10000.
Why was the game delayed by 10 minutes?
Delayed for 10 minutes!!
Hi. Sorry, the delay is my fault. I forgot to change the contest type from ICPC to CODEFORCES. Now it is fixed.
Never mind :)
Anybody helpful enough to tell the difference between the two types? :)
ICPC -> Educational + Div3
Codeforces -> Score Based. 500 -> 1000 -> .....
I thought it was delayed to reach the 10k mark. Is it happening for the first time though?
was and 11k
11,769 is highest registration in any Codeforces Round (Hello 2019), It looks highest registration for any division 2 Round.
come on, you just wanted 10k+ registrantsFirst time I have seen more than 10k participants.
This is the biggest contest I've ever seen on Codeforces, both tasks wise and participants wise.
for any one have trouble use
http://m2.codeforces.com/
I think it is bad to give 2750 points for problem G1
I think it is bad to write anything about problems during a round.
Maybe people learn to read all problems :D
+1
As soon as I solved G1. I wasn't motivated to think about G2.
OMG this was the BEST contest ever! Incredible one!
Daaaaamn if just 2 minutes I could've tried D
edit : Nevermind it was wrong XD
Great round, thank you a lot!
You should've left it as Div 3.
2 hours would have been enough too
at least it doesn't contain a lot of hacks like your rounds
Ye, ofc it's much better to have 6 dummy problems without hacks than nice problems with hacks
yes it is better, because what is the point of solving great problem and then get hacked because of silly bug ?
Maybe you shouldn't write code with bugs. (:
i think even tourist sometime writes code with bugs
Tourist does write code with bugs sometimes, and he every gets hacked occasionally. But do you think he goes and blames the problem setter when this happens?
(I mean maybe he does, ¯\_(ツ)_/¯)
anyway this is pointless discussion, for me i hate problems with weak cases and i think getting points by easy problems is better then getting them from hacking
At least they could hide that the problems were originally for a Div 3 contest, as this hinted that it would be a speed-coding contest and put pressure on contestants (or at least me).
How to solve D?
There are three cases:
The first two is trivial. For the third one, notice that the maximum and minimum value will not change, and you can use these two value to reconstruct $$$d$$$ (which is $$$\frac{max - min}{n-2}$$$) and then find the element you need to remove.
Please don't put it like this. You make me sound so stupid for not being able to solve it. (pun intended) (T_T)
For 3rd case, it should have been divided by n-2 instead of n-1, since we are assuming after deleting one element, we get the AP correct. Great approach, implemented yours way, and it became so easier to write :)
My mistake. Fixed.
What was the shit about TC21 in D?
same question...
:(
I think this is a test-case where the whole array forms an arithmetic progression and either the largest element's position is not n or the smallest element's position is not 1.
I don't think so.
Maybe this is not your problem. But I got WA on pretest 21, and my mistake was that in case that the array already forms an arithmetic progression, I was printing n (then fixed it to print the position of the largest element before sorting).
Wasted an hour on this bug, thank you for explanation :)
Ohhh. Same mistake.
Thanks.
I was printing 1.
:(
I was thinking of this bug for literally an hour and forty five minutes during the contest and was not able to get it as I was not giving any test cases related to it thinking that it was obvious.
Try this
Thanx man :)
exactly ???
what is the pretest 21 of problem D :(
It was the first test with big n.
That moment when you read G1 when 10 minutes remain and you realize your strategy for the contest sucked
So doing G2 first and submitting both is way less fruitful than quickly submitting G1 and then trying G2? This sucks.
Screencast with commentary
Ah, here lies the Gold among so much Clutter.
That moment when you read G1 when 10 minutes remain and realize your strategy for the contest sucked.
I read and coded it in less than 8 minutes and was also wondering why didn't i read all the problems before.even problem A took me more than 8 minutes :p
A person who solved all the problem has lesser score than some people who solved 8 problems ...well played Codeforces!
So doing G2 first and submitting both is way less fruitful than quickly submitting G1 and then coding G2 again? That sucks!
What was problem F about? Write bruteforce? Probably C requires more thinking.
Also I don't like subtasks in codeforces format. Today correct strategy was to write G1 first, and then think about G2. It is strange.
Problems with subtasks are completely inappropriate for codeforces contest format. For example, today to maximize score one should probably implement a stupid solution for G1 at first and then G2.
Such problems are ok on IOI format (without penalty for wrong submissions and time) but have weird drawbacks here. Also, in most cases including one of the versions in the contest is unnecessary because only one of them contains some idea and another one is well-known optimization or oppositely an obvious realization task and could be removed.
Yes, I agree. It will be fixed somehow.
One suggestion that would be relatively non-disruptive and easy to implement: perhaps it would make sense to set a contestant's submission time for both subtasks to the submission time for their last accepted subtask. For example, someone who solved G1 at 1:15 and G2 at 1:45 would receive a score as if they had submitted both problems at 1:45.
One potential drawback is that if an easier subtask is worth substantially more than a harder subtask, it may be disadvantageous to submit the harder version if you solve it too late into the contest (if doing so would cost you more points by increasing your time on the easy subtask than you would earn by solving the harder subtask). So, this would mean that contest authors would need to avoid awarding too many more points for easy subtasks than for hard ones. (I don't think this would be too problematic--in this particular contest, for example, I would say it would be more fair to award 2000 points for G1 and 1500 points for G2, or maybe even the other way around, irrespective of this potential change.)
Or they can be given scores according to their difficulty. It seems really unfair to give 70-80% of score to the easier part (which is mostly about to brute-force) and remaining to the harder one.
Like, for today's G, it should be like 750 for G1 and 2750 for G2.
Problem D is similar to this problem from cookoff: link
Yeah, D is a very known problem
But they were different. I can tell you one more similar (but that too differs from the problem D). https://codeforces.com/problemset/problem/382/C
I don't think the solution of G1 & G2 is strongly related, not even close.
G1 can be solved by simple mask DP, but G2 is completely different (although it's still DP).
The scoring distribution for prob.G is totally a joke. G1 is too easy, and G2 deserves a higher score!
what if, G2 Pass, G1 Fail.
Like jtnydv25 solutions.
I agree. I think it would be more reasonable to award 2000 points for G1 and 1500 points for G2, or maybe even the other way around (1500 for G1, 2000 for G2).
G1 can be done in $$$O(g*2^n)$$$ or even $$$O(g*T*2^n)$$$ with an obvious solution,those who read G1 first may get massive score which is unfair to those who read ABC first ...
Lol, what's your problem, start reading with G1 too ....
I had really easy dp With O(n^4*m) Witch has also had c=1/16
А чё это в E тесты-примеры неправильные? Они же реально неправильные? Я вообще-то из-за этого не успел сдать! upd: Уже понял, всё правильно.
I solved C1 using multiset, but unable to see the pattern for C2. Any hint ?
since time was never greater than 100 u can use frequency array to store the occurrence of time till i and now when you want to fail someone just start with the largest time
How to solve G2??
I don't think the order of the problems is good.Because G1 can be solved by simple mask DP,and F can be solved in O(2^26).I think F and G1 are even easier than problem D and E because problem D and E have more details to notice.And the scores of F and G1 are just the jokes.
I submitted an incorrect solution to both G1 and G2 initially. G1 passed the pretests but G2 didn't. I fixed the solution and resubmitted only in G2. G1 now failed systests, but I am pretty sure that the solution I have already submitted for G2 should work for G1 as well.
I think problems with subtasks create unnecessary complications in such contests. Also, its really difficult to find a fair point distribution.
Well, your situation has nothing to do with point distribution or anything. You just did something stupid :)
Thank you for opening my eyes :)
:D
F tests are so weak.
Can kill many solutions.
can't check the solution. contest is over.
Hi, when i read problem C2 for the first time I didn't see the small limit for the times and I implemented a solution with a Treap but I got TLE, why is that? Is the limit for N too large for a treap?
Here is my code
I solved it with a treap: 55768688
Interesting, the way you generate the random numbers is better somehow?
It shouldn't be that much better. I'm just directly using the output of an
std::mt19937_64seeded from a bunch of sources while you're usingstd::mt19937andstd::uniform_int_distribution. It could be thatstd::uniform_int_distributionis slow or that Visual C++ is faster than G++.Mmmm, I will try it with this. But i was expecting solved the problem with Treap :c
Anyway, thank you so much!
Wow, another implementationforces round, so cool (no).
For problem D:
TLE Code
AC Code
The only difference is a line with "break" to avoid unnecessary O(n^2) operations and getting overall O(n log n). But i just want to say i was unable to notice this fail because of really weak pretests, because it was accepted during contest...
I implemented an O(n^2) solution for small values of
nand a different solution for larger values ofn(taking the most common difference between consecutive elements after sorting). During testing, I set it to always use the O(n^2) algorithm, but because I'm an idiot, I forgot to change the code back before submitting it and it passed the pretests. Of course, I didn't notice this until system testing. I would have probably been stuck on TC 21 though even if my solution failed the pretests since my solution for large inputs had a bug.https://youtu.be/HDDgJPKuSf0
My solution to A had a misplaced semicolon after an if condition and it passed all the pretests. It also passed 40 tests before WA during system testing. link https://codeforces.com/contest/1185/submission/55757491 I don't know whether I should feel amused or sorry for myself :( I need to indent my code properly.
Какой же ты быдло кодер
You should turn up your compiler warnings. Visual C++ outputted this when I compiled your code:
warning C4390: ';': empty controlled statement found; is this the intent?Thanks, I was using Code: blocks IDE, I don't know if it has an option for that. I will try Visual C++, I have been wanting to change my IDE for some time now.
Great ideas and implement! That’s what I call a good contest
Давайте поговорим серьезно ( я не хотел никого обидеть не надо минусить) раунд состоял из достаточно легких задач для див 2, но их было много, вроде бы компенсировали, но зачем делать контест 2 часа 15 минут ???
Let's talk seriously (I didn’t want to offend anyone, we shouldn’t offend) the round consisted of enough easy tasks for div 2, but there were a lot of them, it seemed to be compensated, but why make a contest 2 hours 15 minutes ???
Do you mean we should give more or less time?
Less time )
I am user Ankit211999 and my ratings for the contest #568 Div 2 had been deducted due to the coincidence of submission Ankit211999/55756528 with kotlin_hero987/55756305. Actually, I used ideone and I didn't knew that its use was prohibited. And the submission which matched was of Problem 118A which is a basic problem and I solved two more problems after that if the submissions would have matched it would be of all the three problems. It might be the case that the style of writing code of both the coders for that basic problem might be same. I worked hard for solving those problems please return my ratings for that contest. It will not happen again!
Well, since you said it will not happen again, we'll reconsider.
in problem A no folowing test: 1 1 1 1000000000 and some code passed but in this case should be received Time limit. https://codeforces.com/contest/1185/submission/55758255
Свободу Дмитрию _overrated_, Kekolokol, i_love_andrei, ESCHKERE Умнову!!!1!!!1
C2 was more difficult than D,E,G1
My verdict was skipped because of similarities with someone else's code but it could be coincidence because our style of writing code could be same. I worked hard for solving those problems please return my ratings for this contest. I will try hard to make sure it won't happen again.
It is not a style, it is the copied code:
Yes.I have noticed the thing. there is a community belongs in our university. ZahinAwosaf is my team mate. He coded in notepad.pw and mistakenly uploaded it to online. There is a notification came to my pc and whenever I checked it..I was coping my code to upload it on my codeforces ide for submission. But whenever I wanted to submit it on my github account I have copied the wrong one(ZahinAwosaf's Code). I haven't noticed the thing as the simulation is pretty much similar and switch to next one. Even I also solved this code earlier. But due to that reason, it happens. You can impose penalty for me. I request you to give his points he deserved.
How did the variable names change then? xD
Wouldn't it make more sense to keep them in the contest and let their rating drop
Indians!
Dude his profile say he is from Bangladesh.
Get your facts corrected before making any assumption.
Trump Supporter btw you are from Mexico strangeee....
Firstly look at your self dude
is that Div.3 rated for Blues . Thank you , very amazing contest !
Is there a simpler solution than treap for C2 if $$$t_i \leq 100$$$ condition is not present?
I used binary search on Segment Tree (works for any ti). Wouldn't say its a simple one though.
I think you can use a BIT
I used a treap, but another solution (in hindsight) is to coordinate-compress the items, then run a binary search on BIT for O(N log^2 N).
Can you please explain your solution. It will be helpful for me. Though treap is new for me. Btw Thanks in advance xD. :)
I will explain both:
Treap
A treap is just an implementation of a balanced binary search tree. What we will do is have a BBST that can support insertion and another special operation for this contest, call it
search. This operation takes a parameterk, and determines the number of elements in the BBST that we can 'take' such that their sum is smaller than or equal to k. The implementation of this is rather simple: if the current node we are processing has a sum smaller than k, we can take the whole node. We take smallest elements first, in order to maximize number of elements taken.Then, we continually add elements to the BBST, and then perform a search on $$$M - v$$$, where v is the value of the element we are considering.
Full solution
Coord compress + Bsearch BIT
If we coordinate compress the components, then each element in our BIT is simply either 0 or the value of the element. In the same way, we want the largest $$$i$$$ such that the sum of the first $$$i$$$ elements is less than $$$M - v$$$. To find this, we can binary search, and use the BIT to get the sum of the first $$$i$$$ elements.
Frankly im way too lazy to code the above, and this specific problem has a better solution because of the lax constraints. If you have any more questions dont hesitate to ask.
Div.3 Rated for Blue and Purple ! very good contest .
Editorials?
What is test case 30 for C2?
I think that the contest is perfectly fine for div 2. Perhaps a small issue was a point value for G2. It may be solved by giving to that subtask 3500 pts (and not treat this as a subtask or let G have 6250 pts in total). I believe that this affected not so many div2 participants (most of the comments to make it div3 came from unofficial contestants...).
Perhaps a bigger, but unnoticed concern were weak tests for task F.
Please take into account an objective level of difficulty. Reading all the tasks, familiarity with bitmasks dp, etc. — these are all the factors of competitive programming. Given that, I think that the difficulty of the tasks compared to the "regular" div2 rounds was the following: A B B C C D E D F
Which in my opinion makes it also a decent, regular div 2 round.
Can anyone please explain how to solve c2? It will be helpful for me. Thanks in advance xD. :)
https://codeforces.com/contest/1185/submission/55759892
I've personally tried to do it using multiset. If you've done C1 by summing up every $$$a_i$$$ and if it crosses M , you declare an array $$$b_i$$$ that has all the elements up to (and not including) $$$a_i$$$ , you sort that array, and then you start from the biggest value to the lowest value and see how many students do you have to kick off, and you print that value. The problem with this task in C2 is time constraints. Sorting takes O(NlogN) and the $$$b$$$ array can be massive.
The idea is to use multiset, because multiset is like a set except you can have multiple values (and $$$a$$$ can have multiple values), and a property of multiset and set (correct me if I'm wrong) is that they're always sorted, and they sort things in logN time.
So when you insert each "student time" into the multiset, it will get automatically sorted in logN time, so when the sum exceeds M, you can just use the highest values in the multiset and find the amount of students needed to be kicked off.
I'm not entirely sure why my code got TLE : https://codeforces.com/contest/1185/submission/55785240
But it worked for Radewoosh: https://codeforces.com/contest/1185/submission/55759936
Probably because he deletes something from his multiset, I'll debug it tomorrow.
In the worse case,
t[i] == Mfor alliwhich means every student will only pass if everyone in front of that student failed. This makes your solution O(n^2) since for every student you iterate through the entire set of previous students.Radewoosh's solution works in time because he observed that if the sum of the times for the students in the multiset exceeds M, we would always have to kick someone out in order for the later students to have any possibility of finishing. Therefore, we can kick out students until the total time of the students in the multiset is less than M.
Since the total time of the students in the set is now always less than M, that time plus the time of the current student has to be less than 100 over M. Kicking out a student decreases the time by at least 1, so we only have to kick out less than 100 students in addition to the students that we've determined will always be kicked out.
Thanks, I understand it now but why does he delete the second biggest (it-- makes it second biggest right?) and not the biggest in the set ?
setel.end()points to the imaginary element right after the last element in the set, so decrementing it results in the largest element.it=setel.rbegin() is the same as it=setel.end() it-- ?
Yes, except that
setel.rbegin()is a reverse iterator which I didn't previously know can't be easily converted into a forward iterator thatstd::set::eraseaccepts. So I was wrong and the easiest way here is to decrementsetel.end().Can anyone tell me how to solve G2?
I don't think this is the optimal solution.
First calculate $$$H[i][j][k][sum]$$$ , this is defined as the number of subsets with $$$i$$$ songs of type $$$1$$$, $$$j$$$ of type $$$2$$$ etc and with length sum equal to $$$sum$$$.
We can store this in a compressed 1d array of size Q1*Q2*Q3*T where Qi is the number of songs of type i.
Once we have these numbers we just have to iterate over all values $$$H[i][j][k][T]$$$ and add $$$H[i][j][k][T]$$$ multiplied by an appropriate coefficient $$$F[i][j][k][end]$$$. which tells us given a specific subset of songs with those quantities how many suitable rearrangements exist, that finish with a song of type $$$end$$$. ( So for each $$$H[i][j][k][T]$$$ we add the product by the three $$$F[i][j][k][end]$$$ corresponding to the $$$3$$$ values of $$$end$$$.
These coefficients can be calculated in time $$$3*n^ 3$$$ via a normal dp.
Be careful when calculating the $$$H[i][j][k][sum]$$$, to make it faster process all songs of type 1 first, then type 2 etc and only fill the entries $$$H[i][j][k][sum]$$$ where the values of $$$i,j,k$$$ are less than the current numbers of processed songs.
How do you calculate the H values while also making sure that you don't chose the same element more than once.
To do this transverse over the values i,j,k in decreasing order instead of increasing order.
I guess my solution is not the official solution since it requires FFT:
First, let $$$dp(i)(j)(k)$$$ be the number of ways that has $$$i$$$ songs of genre $$$k$$$ and the total length is $$$j$$$ minutes. It can be calculated in $$$O(n^2T)$$$. Then, we enumerate how many songs we are going to put in the playlist for each genre (in the worst case it's a loop that runs 17*17*16 times), so we are left to calculate
, and this is a simple fft application. To sum up, the complexity is $$$O(n^3TlogT)$$$, but in fact, it's just 4624 times of fft of size 2500, and my solution runs in 4.5s.
Well, to be honest, the complexity of my solution is $$$O(n^3T^2)$$$, but my solution suns in 733ms.
55809647
I used some sort of meet in the middle approach (after the contest).
I computed $$$dp12[N][i][j][T]$$$ = how many ways to select $$$i$$$ songs from the first genre and $$$j$$$ songs from the second genre so the total sum of the durations is exactly $$$T$$$, using some of the items in range $$$0...N$$$. In practice, we can ignore the first dimension, so the dp will become $$$dp12[i][j][T]$$$. The time complexity will still be $$$O(N^3*T)$$$.
We also compute $$$dp3[i][T]$$$ = how many ways to select $$$i$$$ songs from the third genre totalling $$$T$$$ seconds, in a similar way in $$$O(N^2*T)$$$.
In the above dp's we ignore the order of the songs, so we will also compute another dp $$$perm[i][j][k]$$$ = how many ways to arrange $$$i$$$ songs from the first genre, $$$j$$$ songs from the second genre and $$$k$$$ songs from the third genre, so that there are no consecutive songs from the same genre. The time complexity for this will be $$$O(N^3)$$$.
Now the answer to the problem will be $$$\sum_{i,j,k \le N, t \le T}dp12[i][j][t] * dp3[k][T-t] * perm[i][j][k]$$$.
The final complexity will be $$$O(N^3*T)$$$ and the constant should be ok, since $$$i+j+k \le N$$$ will result in a $$$1/27$$$ constant. I got AC with 120 ms or something like that.
How is that possible?
The complexity of my solution to problem G2 is $$$O(T^2n^3)$$$, and there's a lot of mod, but I got an "Accepted".
Could anyone give me an answer? Or is it just because the computer runs too fast?
My solution here:
55809647
I had the same idea with you :v I think it was accepted because lots of limitations you wrote. For ex, i + j + k <= n => for (i, j, k) will cost O(...) <= O(n^3 / 27) < O(n^2 * 2)
Well, I recalculated my complexity, it is $$$O\left(\dfrac{T^2n^3}{108}\right)$$$ instead of $$$O(T^2n^3)$$$, about $$$7\times 10^9$$$.
I think it was accepted because of this:
And also, the complexity of "%" is only $$$O\left(\dfrac{T^2n^2}{18}\right)$$$
Can someone help me with my solution. 55778971 I am getting a Wrong Answer on Test 13.
What is wrong with the while conditon? The value of j printed after while loop is 104 in codeforces IDE.It works fine in dev. [submission:https://codeforces.com/contest/1185/submission/55793048]
My submission for B in Python WA-d during contest but got accepted after the contest.
During contest: https://codeforces.com/contest/1185/submission/55760801 After the contest: https://codeforces.com/contest/1185/submission/55812461
I wasted an hour trying to find a bug and ended up performing very poorly. I think it will be fair if my rating change is reconsidered.
Also, can you please look into this and let us know why this incident occurred? Compiler seems to behave non-deterministically: here's the same solution, but WA on a different test: https://codeforces.com/contest/1185/submission/55812449
You can see, your answer is empty after some iterations. It seems that the thread exited so the line is empty. Maybe the thread is killed because the computation resource is depleted? That's my guess.
I was also guessing that it is related to threads, but I'm not really sure how exactly that could happen. What exactly do you mean by computation resource?
I don't want to use threads but I don't really know how to increase the recursion limit without them. The inability to change it (without using threads) is really annoying as it renders Python useless for many problems.
computation resource, I mean many submissions are judged the same time, they are competing for resource. Just a guess.
Python is just for quick solutions for easy problems. Hard problems needs faster language.
This is a pretty simple problem and my solution is linear. It seems like the platform should support it.
How to solve G1?
Straight forward bitmask DP. dp[mask][prv] gives the number of ways to arrange a subset of the given songs where prv is the genre of the last used song. Complexity $$$O(n*2^n)$$$
$$$O(n*2^n)$$$
My bad. Thanks
When will the problem setters upload the editorials?
Great round, guys. So, will you post the solutions?
Can someone please help with my solution of problem C2. It's getting TLE on TC13.
https://codeforces.com/contest/1185/submission/55818757
I have used a multiset and every element is inserted and deleted from the multiset only once.
So the time complexity should be O(nlog(n))
any help would be appreciated.
For multisets, erase eliminates all the elements with value == parameter, instead of just one element which is what I guess you were trying to do. You should change erase(largest) to erase(s.begin()).
Can anyone help me find fault in the concept of my implementation for C2? link
I used the priority queue to get the maximum element which hasn't been extracted yet by previous elements. I am storing the sum of time taken by the just previous element. If prev_sum + input[i] <= m, the answer will remain the same as the previous element. Otherwise, I will extract elements from the priority queue and subtract it from my current sum till it becomes less than or equal to m and update the prev_sum to curr_sum.
Please ignore the commented out code. Thanks!
check for:
6 15
1 2 3 4 10 5
for 6th student answer is 1 (remove 5th student).
your logic is OK , but here that array is not always sorted. So , it is possible that answer to ith term can be less than (i-1)th term. example:- 4 10 3 4 10 2
See my soln i also used priority_queue. https://codeforces.com/contest/1185/submission/55817685
i used two priority queues second one in ascending order. I think it will even work for ti<=10^5
Thanks for identifying the mistake in my implementation. I scrolled through your code and got some idea. You should check out the implementation through multiset too. It is quite simple to follow.
Your Code gives wrong answer for test case: 3 100 50 60 41 Your code gives 0 1 2 But it should be 0 1 1. Still your solution got accepted. Weak test cases maybe.
You just hacked my code. Thanks a lot man. I rechecked my code and improved it. https://codeforces.com/contest/1185/submission/55826242 Actually i thought about that case while submitting but since it passed all test cases i left.
I think the score problem is totally wrong. C2&G2 should have more score.
Please provide the editorials.
Really good problems.Isn't it? Hope there will be more rounds like this(easy&many problems).
any editorials?
Editorial coming? :)
Could anybody show me a solution for E?Thanks in advance
Sol Link : https://codeforces.com/contest/1185/submission/55825650
For problem E can anyone expalin me these two test cases test case 1 —
3 5
..b..
aaaaa
..b..
why their output is (NO) and
test case 2-
bc
cc
thankyou.
First case :
in the question it is written clearly that first 'a' is written then 'b' which means that 'b' can overwrite 'a' but not vice versa. Hence answer is NO
Second:
ans is NO because snake('c') cannot bend
But the second test case output is
YES
3
1 1 1 2
1 1 1 2
2 1 2 2
... I realy didnt get this one suppose (A) overwrite (B) and then (B) overwrite (A) but then why we overwrite (C) with itself when (C) was there on that position???
'a' cannot overwrite 'b'
In question snakes are in order that first 'a' is written then 'b' then 'c', which implies a character can only be overwritten by a character after it. i.e 'e' can be over written by any character from 'f' to 'z' and cannot be overwritten by character 'a' to 'd'. Also there is only one snake of a character, so it cannot possibly overwrite itself as it cannot bend .
But the second test case output is
YES.....
i guess you wanted to paste the sample test case
b c
b c ( which has the the above solution of 'YES') but you pasted
b c
c c
(whose solution is 'NO')
when will the editorials come?
[deleted]
Now editorials are available.
I think the solution which Radewoosh wrote for problem D is incorrect. It is showing -1 for this case: 5 2 4 5 6 8 The answer should be 3. :/
Yes the answer is 3. Earlier I thought that the array consists of 6 elements.
How? If we delete 3rd element, it's a arithmetic sequence.
System tests for task D are so weak...
This submission is AC: 55860779
But it couldn't pass a few different tests:
1)
4
3 5 5 7
2)
5
2 3 4 6 8
3)
5
2 5 8 10 13