Codeforces Round #568 (Div. 2)

5 years ago, # ^ |

it was a really big scar );

→ Reply

5 years ago, # ^ |

← Rev. 2 →

+17

try python. Some problems are easy if implemented in python. Especially problems does not constrain strictly on complexity.

→ Reply

5 years ago, # |

+22

Wish you the best of luck for organising your first contest

→ Reply

5 years ago, # ^ |

+24

Thanks!

→ Reply

GrandDaddy

5 years ago, # |

+63

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.

→ Reply

doped.silicon

5 years ago, # |

-6

Good luck and have fun everyone! :)

→ Reply

akidiekatze

5 years ago, # |

-14

lol

→ Reply

Wesam

5 years ago, # |

+82

Div(2.5) XD

→ Reply

kocko

5 years ago, # ^ |

+44

It's a Div.3, but rated for blue and purple ones. Doesn't happen every day :)

→ Reply

5 years ago, # ^ |

+64

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.

→ Reply

scauweng

5 years ago, # ^ |

I love interesting problems

→ Reply

LALKaIFIDIESAVEMYLIFE

5 years ago, # ^ |

+16

→ Reply

atriwal

5 years ago, # |

+20

Congrats for your first rated round.Hopes your hard work pays off and we can get many more round in future. Good Luck!!

→ Reply

5 years ago, # ^ |

+19

Thanks a lot! Wish you high scores on the contest! :)

→ Reply

sirish_kp

5 years ago, # |

← Rev. 2 →

Is div2 contest rated for div3 (<1600) participants? Can someone explain the rules.

PS: i googled it, but couldn't find the answer.

→ Reply

ForeverBrick

5 years ago, # ^ |

Yes.

→ Reply

sirish_kp

5 years ago, # ^ |

Thanks for your reply, but any idea on why it is mentioned "it will be rated for div2 participants" in above contest description?

→ Reply

fried-chicken

5 years ago, # ^ |

div_x_participants = ∑( i=x -> i=3 ) div_i_participants

→ Reply

securityViolation

5 years ago, # ^ |

+55

Wrong answer on test 1

Input
x = 1
Output
1 + 2 + 3
Answer
1

→ Reply

ankur314

5 years ago, # ^ |

+62

Successful hacking attempt!

→ Reply

fried-chicken

5 years ago, # ^ |

My fault, since I'm just a poor div2 participants, this is totally extracurricular knowledge for me QAQ

→ Reply

ChthollyTree

5 years ago, # ^ |

So if x = 1 + 2(div1 + div2)?

→ Reply

fugazi

5 years ago, # |

+10

Initially, we had prepared the round for Div. 3, but after testing, it became clear that this round is harder than usual such rounds

My prediction : A, B, C, D, E are easy problems with some implementation. F is of level div2 D, and G is hard.

→ Reply

5 years ago, # |

+35

hope it will not be hard code as the last div 2

→ Reply

smallguoguo

5 years ago, # |

Codeforces Round #568 (Div. 2.5)

→ Reply

McDic

5 years ago, # |

← Rev. 3 →

+27

Notable points on distribution

750 gap in BC
CDE are in similar level
G has 3500 points

By the way, 2 hour 15 minutes for 7 problems.. Our hands will not be able to stop during contest :(

→ Reply

subash23

5 years ago, # |

Back to back rounds...yeahhhh!!!...Thanks for the effort..

→ Reply

no_ath

5 years ago, # |

← Rev. 2 →

+28

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"

→ Reply

Vergara

5 years ago, # |

+13

We need more problems!

→ Reply

MagicSpark

5 years ago, # |

Now there are more and more subtasks in the problems.

→ Reply

AjaySabarish

5 years ago, # |

+13

Hope pretests pass=>system test pass,becomes true in this contest.

→ Reply

TheOneYouWant

5 years ago, # |

+11

Can the contest be longer? That seems like a lot of problems for 135 minutes..

→ Reply

5 years ago, # ^ |

-8

it seems it is not a bad contest with lots of implementations because its 9 problems :)

→ Reply

Jaidhunibavsi

5 years ago, # |

contest is going to be interesting.i hope more 10000 people will do participate.

→ Reply

soul_voyage

5 years ago, # |

-9

Is it a wise idea to write contest on mobile and not using paper-pencil due to power-cut?

→ Reply

AcceptedIsRealAbility

5 years ago, # |

+28

It can be true that the number of participators will be greater than 10000.

→ Reply

G.E.M.

5 years ago, # |

+31

Why was the game delayed by 10 minutes?

→ Reply

5 years ago, # |

Delayed for 10 minutes!!

→ Reply

5 years ago, # |

+162

Hi. Sorry, the delay is my fault. I forgot to change the contest type from ICPC to CODEFORCES. Now it is fixed.

→ Reply

5 years ago, # ^ |

Never mind :)

→ Reply

sapphire

5 years ago, # ^ |

Anybody helpful enough to tell the difference between the two types? :)

→ Reply

5 years ago, # ^ |

ICPC -> Educational + Div3

Codeforces -> Score Based. 500 -> 1000 -> .....

→ Reply

burt_macklin_

5 years ago, # ^ |

I thought it was delayed to reach the 10k mark. Is it happening for the first time though?

→ Reply

praeda_est_supra

5 years ago, # ^ |

was and 11k

→ Reply

AmanGupta_

5 years ago, # ^ |

11,769 is highest registration in any Codeforces Round (Hello 2019), It looks highest registration for any division 2 Round.

→ Reply

IIIIIIIIIIIIIIIIIIIII

5 years ago, # ^ |

← Rev. 3 →

+22

~~come on, you just wanted 10k+ registrants~~

→ Reply

gjaiswal108

5 years ago, # |

+15

First time I have seen more than 10k participants.

→ Reply

5 years ago, # |

+23

This is the biggest contest I've ever seen on Codeforces, both tasks wise and participants wise.

→ Reply

http://m2.codeforces.com/

5 years ago, # |

for any one have trouble use

→ Reply

yogahmad77

5 years ago, # |

+24

I think it is bad to give 2750 points for problem G1

→ Reply

5 years ago, # ^ |

+213

I think it is bad to write anything about problems during a round.

→ Reply

LOVE_BELUGAS

5 years ago, # ^ |

Maybe people learn to read all problems :D

→ Reply

aryanc403

5 years ago, # ^ |

+1
As soon as I solved G1. I wasn't motivated to think about G2.

→ Reply

Leonardo_Paes

5 years ago, # |

OMG this was the BEST contest ever! Incredible one!

→ Reply

Jhin

5 years ago, # |

← Rev. 2 →

Daaaaamn if just 2 minutes I could've tried D

edit : Nevermind it was wrong XD

→ Reply

wery0

5 years ago, # |

+11

Great round, thank you a lot!

→ Reply

GreenGrape

5 years ago, # |

+235

You should've left it as Div 3.

→ Reply

LOVE_BELUGAS

5 years ago, # ^ |

-21

2 hours would have been enough too

→ Reply

5 years ago, # ^ |

+11

at least it doesn't contain a lot of hacks like your rounds

→ Reply

GreenGrape

5 years ago, # ^ |

-36

Ye, ofc it's much better to have 6 dummy problems without hacks than nice problems with hacks

→ Reply

5 years ago, # ^ |

-36

yes it is better, because what is the point of solving great problem and then get hacked because of silly bug ?

→ Reply

Redux

5 years ago, # ^ |

-9

Maybe you shouldn't write code with bugs. (:

→ Reply

5 years ago, # ^ |

-12

i think even tourist sometime writes code with bugs

→ Reply

Redux

5 years ago, # ^ |

← Rev. 2 →

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, ¯\_(ツ)_/¯)

→ Reply

5 years ago, # ^ |

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

→ Reply

Charis02

5 years ago, # ^ |

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).

→ Reply

ameykudari05

5 years ago, # |

How to solve D?

→ Reply

xuanquang1999

5 years ago, # ^ |

← Rev. 3 →

+63

There are three cases:

Remove maximum element
Remove minimum element
Remove an element that is not maximum nor minimum

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.

→ Reply

brehze

5 years ago, # ^ |

Please don't put it like this. You make me sound so stupid for not being able to solve it. (pun intended) (T_T)

→ Reply

rupav

5 years ago, # ^ |

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 :)

→ Reply

xuanquang1999

5 years ago, # ^ |

My mistake. Fixed.

→ Reply

5 years ago, # |

+26

What was the shit about TC21 in D?

→ Reply

nonatomicgames

5 years ago, # ^ |

same question...

→ Reply

5 years ago, # ^ |

→ Reply

mohamedeltair

5 years ago, # ^ |

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.

→ Reply

5 years ago, # ^ |

I don't think so.

→ Reply

mohamedeltair

5 years ago, # ^ |

+55

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).

→ Reply

TaTaPiH

5 years ago, # ^ |

+13

Wasted an hour on this bug, thank you for explanation :)

→ Reply

5 years ago, # ^ |

+13

Ohhh. Same mistake.

Thanks.

→ Reply

5 years ago, # ^ |

I was printing 1.

→ Reply

aarcee

5 years ago, # ^ |

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.

→ Reply

Superuzir

5 years ago, # ^ |

← Rev. 2 →

Try this

5
3 4 1 5 2

→ Reply

SHA-256

5 years ago, # ^ |

Thanx man :)

→ Reply

SHA-256

5 years ago, # ^ |

exactly ???

→ Reply

intruder_p

5 years ago, # |

what is the pretest 21 of problem D :(

→ Reply

Screencast with commentary

5 years ago, # ^ |

It was the first test with big n.

→ Reply

Um_nik

5 years ago, # |

+19

→ Reply

manish_joshi

5 years ago, # ^ |

Ah, here lies the Gold among so much Clutter.

→ Reply

Jefe

5 years ago, # |

+41

That moment when you read G1 when 10 minutes remain and realize your strategy for the contest sucked.

→ Reply

njrafi

5 years ago, # ^ |

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

→ Reply

aqibm

5 years ago, # |

A person who solved all the problem has lesser score than some people who solved 8 problems ...well played Codeforces!

→ Reply

Ant_Man

5 years ago, # |

+11

So doing G2 first and submitting both is way less fruitful than quickly submitting G1 and then coding G2 again? That sucks!

→ Reply

Um_nik

5 years ago, # |

+188

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.

→ Reply

SoMuchDrama

5 years ago, # |

+205

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.

→ Reply

5 years ago, # ^ |

+55

Yes, I agree. It will be fixed somehow.

→ Reply

Geothermal

5 years ago, # ^ |

-17

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.)

→ Reply

coderanant

5 years ago, # ^ |

+22

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.

→ Reply

skyscraper

5 years ago, # |

+21

Problem D is similar to this problem from cookoff: link

→ Reply

Leonardo_Paes

5 years ago, # ^ |

← Rev. 2 →

Yeah, D is a very known problem

→ Reply

gjaiswal108

5 years ago, # ^ |

But they were different. I can tell you one more similar (but that too differs from the problem D). https://codeforces.me/problemset/problem/382/C

→ Reply

PinkRabbitAFO

5 years ago, # |

+103

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!

→ Reply

5 years ago, # ^ |

← Rev. 2 →

+12

what if, G2 Pass, G1 Fail.

Like jtnydv25 solutions.

→ Reply

Geothermal

5 years ago, # ^ |

+34

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).

→ Reply

9646516

5 years ago, # |

← Rev. 2 →

+40

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 ...

→ Reply

5 years ago, # ^ |

Lol, what's your problem, start reading with G1 too ....

→ Reply

5 years ago, # ^ |

I had really easy dp With O(n^4*m) Witch has also had c=1/16

→ Reply

-sh

5 years ago, # |

I solved C1 using multiset, but unable to see the pattern for C2. Any hint ?

→ Reply

Pj18

5 years ago, # ^ |

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

→ Reply

aditya_sheth

5 years ago, # |

How to solve G2??

→ Reply

QAQT

5 years ago, # |

← Rev. 2 →

+42

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.

→ Reply

jtnydv25

5 years ago, # |

+37

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.

→ Reply

Um_nik

5 years ago, # ^ |

-21

Well, your situation has nothing to do with point distribution or anything. You just did something stupid :)

→ Reply

jtnydv25

5 years ago, # ^ |

← Rev. 2 →

+24

Thank you for opening my eyes :)

→ Reply

tzc_wk

5 years ago, # ^ |

→ Reply

DomiKo

5 years ago, # |

← Rev. 3 →

+37

F tests are so weak.

Can kill many solutions.

→ Reply

hielitos

5 years ago, # |

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

→ Reply

5 years ago, # ^ |

I solved it with a treap: 55768688

→ Reply

hielitos

5 years ago, # ^ |

Interesting, the way you generate the random numbers is better somehow?

→ Reply

5 years ago, # ^ |

It shouldn't be that much better. I'm just directly using the output of an std::mt19937_64 seeded from a bunch of sources while you're using std::mt19937 and std::uniform_int_distribution. It could be that std::uniform_int_distribution is slow or that Visual C++ is faster than G++.

→ Reply

hielitos

5 years ago, # ^ |

Mmmm, I will try it with this. But i was expecting solved the problem with Treap :c

Anyway, thank you so much!

→ Reply

VadymKa

5 years ago, # |

+82

Wow, another implementationforces round, so cool (no).

→ Reply

izanbf

5 years ago, # |

← Rev. 3 →

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...

→ Reply

https://youtu.be/HDDgJPKuSf0

5 years ago, # ^ |

I implemented an O(n^2) solution for small values of n and a different solution for larger values of n (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.

→ Reply

LOVE_BELUGAS

5 years ago, # |

→ Reply

abhigyan10

5 years ago, # |

← Rev. 3 →

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.me/contest/1185/submission/55757491 I don't know whether I should feel amused or sorry for myself :( I need to indent my code properly.

→ Reply

5 years ago, # ^ |

← Rev. 3 →

-13

Какой же ты быдло кодер

→ Reply

5 years ago, # ^ |

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?

→ Reply

abhigyan10

5 years ago, # ^ |

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.

→ Reply

5 years ago, # |

Давайте поговорим серьезно ( я не хотел никого обидеть не надо минусить) раунд состоял из достаточно легких задач для див 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 ???

→ Reply

5 years ago, # ^ |

Do you mean we should give more or less time?

→ Reply

5 years ago, # ^ |

Less time )

→ Reply

Ankit211999

5 years ago, # |

-34

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!

→ Reply

AaronSwartz

5 years ago, # ^ |

-24

Well, since you said it will not happen again, we'll reconsider.

→ Reply

AaronSwartz

5 years ago, # |

-20

C2 was more difficult than D,E,G1

→ Reply

ZahinAwosaf

5 years ago, # |

-50

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.

→ Reply

5 years ago, # ^ |

+90

It is not a style, it is the copied code:

→ Reply

Shadow_Dragoon

5 years ago, # ^ |

-80

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.

→ Reply

prakhar17252

5 years ago, # ^ |

+27

How did the variable names change then? xD

→ Reply

adhoc_king

5 years ago, # ^ |

+12

Wouldn't it make more sense to keep them in the contest and let their rating drop

→ Reply

AaronSwartz

5 years ago, # ^ |

-123

Indians!

→ Reply

aryanc403

5 years ago, # ^ |

+64

Dude his profile say he is from Bangladesh.
Get your facts corrected before making any assumption.

→ Reply

silent__killer1

5 years ago, # ^ |

Trump Supporter btw you are from Mexico strangeee....

→ Reply

DC-HITMAN

5 years ago, # ^ |

Firstly look at your self dude

→ Reply

prakhar17252

5 years ago, # |

← Rev. 2 →

Is there a simpler solution than treap for C2 if $$$t_i \leq 100$$$ condition is not present?

→ Reply

SebaMarin

5 years ago, # ^ |

+25

I used binary search on Segment Tree (works for any ti). Wouldn't say its a simple one though.

→ Reply

gupta_shvm

5 years ago, # ^ |

I think you can use a BIT

→ Reply

Riolku

5 years ago, # ^ |

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).

→ Reply

undefined_error_

5 years ago, # ^ |

Can you please explain your solution. It will be helpful for me. Though treap is new for me. Btw Thanks in advance xD. :)

→ Reply

Riolku

5 years ago, # ^ |

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 parameter k, 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.

→ Reply

Grapeee

5 years ago, # |

← Rev. 2 →

+25

Div.3 Rated for Blue and Purple ! very good contest .

→ Reply

Nightmare05

5 years ago, # |

Editorials?

→ Reply

gupta_shvm

5 years ago, # |

What is test case 30 for C2?

→ Reply

P___

5 years ago, # |

← Rev. 2 →

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.

→ Reply

undefined_error_

5 years ago, # |

Can anyone please explain how to solve c2? It will be helpful for me. Thanks in advance xD. :)

→ Reply

https://codeforces.me/contest/1185/submission/55759892

5 years ago, # ^ |

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.me/contest/1185/submission/55785240

But it worked for Radewoosh: https://codeforces.me/contest/1185/submission/55759936

Probably because he deletes something from his multiset, I'll debug it tomorrow.

→ Reply

5 years ago, # ^ |

In the worse case, t[i] == M for all i which 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.

→ Reply

5 years ago, # ^ |

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 ?

→ Reply

5 years ago, # ^ |

← Rev. 2 →

setel.end() points to the imaginary element right after the last element in the set, so decrementing it results in the largest element.

→ Reply

5 years ago, # ^ |

it=setel.rbegin() is the same as it=setel.end() it-- ?

→ Reply

5 years ago, # ^ |

← Rev. 2 →

Yes, except that setel.rbegin() is a reverse iterator which I didn't previously know can't be easily converted into a forward iterator that std::set::erase accepts. So I was wrong and the easiest way here is to decrement setel.end().

→ Reply

Hazyknight

5 years ago, # |

Can anyone tell me how to solve G2?

→ Reply

Jefe

5 years ago, # ^ |

← Rev. 4 →

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.

→ Reply

AsleepAdhyyan

5 years ago, # ^ |

How do you calculate the H values while also making sure that you don't chose the same element more than once.

→ Reply

Jefe

5 years ago, # ^ |

To do this transverse over the values i,j,k in decreasing order instead of increasing order.

→ Reply

baIuteshih

5 years ago, # ^ |

← Rev. 2 →

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

$$$\sum _{i+j+k=T} dp(cnt1)(i)(0)*dp(cnt2)(j)(1)*dp(cnt3)(k)(2)$$$

, 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.

→ Reply

wucstdio

5 years ago, # ^ |

-8

Well, to be honest, the complexity of my solution is $$$O(n^3T^2)$$$, but my solution suns in 733ms.

55809647

→ Reply

tinca_matei

5 years ago, # ^ |

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.

→ Reply

YoshinoTomotake

5 years ago, # |

When you realized that C2 had a low score after you solved it, even D had a higher score.

→ Reply

wucstdio

5 years ago, # |

← Rev. 2 →

-31

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

→ Reply

huuduy16

5 years ago, # ^ |

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)

→ Reply

wucstdio

5 years ago, # ^ |

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:

if(f1[i][t1]==0)continue;
...
if(f2[j][t2]==0)continue;

And also, the complexity of "%" is only $$$O\left(\dfrac{T^2n^2}{18}\right)$$$

→ Reply

aswwwanth

5 years ago, # |

-8

Can someone help me with my solution. 55778971 I am getting a Wrong Answer on Test 13.

→ Reply

tubelight

5 years ago, # |

← Rev. 3 →

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.me/contest/1185/submission/55793048]

→ Reply

arman.t

5 years ago, # |

My submission for B in Python WA-d during contest but got accepted after the contest.

During contest: https://codeforces.me/contest/1185/submission/55760801 After the contest: https://codeforces.me/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.me/contest/1185/submission/55812449

→ Reply

5 years ago, # ^ |

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.

→ Reply

arman.t

5 years ago, # ^ |

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.

→ Reply

5 years ago, # ^ |

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.

→ Reply

arman.t

5 years ago, # ^ |

This is a pretty simple problem and my solution is linear. It seems like the platform should support it.

→ Reply

vikas_404

5 years ago, # |

How to solve G1?

→ Reply

moidda

5 years ago, # ^ |

← Rev. 2 →

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)$$$

→ Reply