### Batman's blog

By Batman, history, 4 years ago,

Hi!

I'd like to invite you to join in Codeforces Round #411 that will be held on May 4 at 17:35 MSK.

Actually I didn't do anything for this contest :) and most of the contest is prepared by my good friends saliii and MohammadJA. Also amsen, Navick, tundra, kastarika and I helped them in testing problems, writing statements and these sort of things. At the end, Thanks to KAN for his huge help in all of the contests and MikeMirzayanov for great Codeforces and Polygon platforms. (Sorry if there's someone I didn't mentioned, This is everything I know).

Each division contains 6 problems (4 common problems). Hope you enjoy them.

The round is rated and score distribution will be posted soon and good luck and have fun and hope you high ratings and all the other words that should be told.

UPD 1 Contest delayed by 10 minutes.

UPD 2 Contest delayed by 5 minutes. :)

UPD 3 We can see the scores now in contest page.

UPD 4 Contest is finally over, Hope you enjoyed the problems. Cause of technical issues editorial will be posted tomorrow.

UPD 5 And here are the top5 in each division:

Div1:

3-al13n

5-zeliboba

Div2:

2-_ISB_

3-Dipak

And also congratulation to hahaschool, MKyzy and shanin who solved problem F in div2.

UPD 6 Editorial is ready now.

• +346

 » 4 years ago, # |   +63 I hope the problem statements will be clear, short and easy to understand like this blog :'D
•  » » 4 years ago, # ^ |   +9 Me too XD
 » 4 years ago, # | ← Rev. 2 →   +8 How much will the round last? I see that it's a non-standard round (having 6 problems).L.E: oh, it's 2 hours. I didn't check out the contest tab
 » 4 years ago, # |   -9 "good luck and have fun and hope you high ratings and all the other words that should be told." is like saying "wish you all the best" in happy birthday
 » 4 years ago, # |   +21 A round at the beginning of the summer vacation, What's better than this :)
•  » » 4 years ago, # ^ |   +12 It's a round on the last day of high school for me :)
•  » » 4 years ago, # ^ |   +44 It's the beginning of our final exams, What's worse than this :)
•  » » 4 years ago, # ^ |   +1 begining of our 4th sem exams and my first codeforces round... fingers crossed!
 » 4 years ago, # |   -20 GOOD LUCK
 » 4 years ago, # | ← Rev. 2 →   +206 I was hoping for a Star Wars contest in the announcement.
 » 4 years ago, # | ← Rev. 4 →   -62 hi
 » 4 years ago, # | ← Rev. 7 →   -45 don't hate me
•  » » 4 years ago, # ^ |   -53 why? because you are a little boy?
•  » » » 4 years ago, # ^ |   -57 you are very funny that send message with my account and reply to it ...
•  » » 4 years ago, # ^ |   -27 see her interview
 » 4 years ago, # | ← Rev. 3 →   -10 Two Impressive Setter's Profile saliii & tundra from today's contest
 » 4 years ago, # |   -40 I hope problem statements won't say us to assume all other words that should be told :p
 » 4 years ago, # |   -40 Hope there won't be any other "HOS" in statments :D
•  » » 4 years ago, # ^ |   -29 Why did you think at this way?
•  » » » 4 years ago, # ^ |   -25 Already having a Hir in blog
•  » » » » 4 years ago, # ^ | ← Rev. 3 →   -24 So what is the common thing between "Hir" and "Hos" else 'H'?
•  » » » » » 4 years ago, # ^ |   -18 Ask Batman
•  » » » » » » 4 years ago, # ^ |   +5 I want test you!
 » 4 years ago, # |   +1 6 problems and 2 hours.WOW!
•  » » 4 years ago, # ^ |   +82 Maybe they are too easy...
•  » » » 4 years ago, # ^ |   0 hopefully the statements will be short !!
•  » » » 4 years ago, # ^ |   +28 Or you are too strong
•  » » » » 4 years ago, # ^ |   +42 Or I didn't even read the problems :)
•  » » » » » 4 years ago, # ^ |   0 Really ?
•  » » » » » » 4 years ago, # ^ |   +5 Some of them :)
 » 4 years ago, # |   +36 Actually I didn't do anything for this contest :)Sorry if there's someone I didn't mentioned, This is everything I knowall the other words that should be told.Wow... It's... Awesome..
•  » » 4 years ago, # ^ |   -8 great context of my Friend :)
 » 4 years ago, # | ← Rev. 2 →   +8 30 minutes before the beginning of the contest and score distribution hasn't been posted...
•  » » 4 years ago, # ^ |   +2 8 minutes remaining now
•  » » 4 years ago, # ^ |   +6 I asked them from saliii, But he didn't answer me...
•  » » 4 years ago, # ^ |   0 And the contest has been pushed by 10 minutes :)
 » 4 years ago, # |   0 good luck to everyone!
 » 4 years ago, # |   0 Hoping to solve some problems before exam..
 » 4 years ago, # | ← Rev. 2 →   +32 Maybe it will be good if CF implements a feature to reveal scoring distribution automatically, say 5 minutes before the round.
•  » » 4 years ago, # ^ |   +3 I prefer more than 5 minutes, but I'm agree with you.
•  » » » 4 years ago, # ^ |   +1 Well, the delays usually do the job :D
•  » » 4 years ago, # ^ |   +37 I've never understood why scoring distribution always has to be revealed at the last minute. I mean, why couldn't they reveal it when they first made this post?
•  » » » 4 years ago, # ^ |   0 may be it is something to do with the number of registered participants ... just a guess
•  » » » 4 years ago, # ^ |   +3 Don't worry. I'm aware that problem D is easier than C (for me at least), LOL.
•  » » » 4 years ago, # ^ |   0 My guess is, to prevent people from using well-thought-out strategies. Making you think which problem to start first, second, and so on right before the contest boosts your adrenaline :D
 » 4 years ago, # |   -8 Auto comment: topic has been updated by Batman (previous revision, new revision, compare).
 » 4 years ago, # |   +3 Good luck for all!
 » 4 years ago, # |   +10 Why the delay? I know I'll never get an answer.
 » 4 years ago, # |   +40 extension by 10 has become common
•  » » 4 years ago, # ^ |   +9 Agree, really disappointing.
 » 4 years ago, # |   +80 Thx for delay :) I'm in bus getting home right now
•  » » 4 years ago, # ^ |   +77 thanks again :D I even finished eating
 » 4 years ago, # |   +52 UPD 1 Contest delayed by 10 minutes. Probably, still not decided on score distribution
 » 4 years ago, # |   -10 late-10minutes.
•  » » 4 years ago, # ^ |   -8 one of the worst things about codeforces contest :(
 » 4 years ago, # |   +50 who's girlfriend missed the registration?
•  » » 4 years ago, # ^ |   0 checked yours? :P
•  » » » 4 years ago, # ^ |   +59 I have no girlfriend :'(
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   -7 so sad.
•  » » » » 4 years ago, # ^ |   -10 so sad, wish you have a girlfriend before the next contest. :D
•  » » » » » 3 years ago, # ^ |   0 Your pray is guaranteed. Still, have a girlfriend. Pray next for better thing.
•  » » » » 4 years ago, # ^ |   -10 Don't worry, She must waiting you to find her. just patient.
•  » » » » 4 years ago, # ^ |   +2 Then, we are two. I'm in the friend zone since past week :o
•  » » » » 4 years ago, # ^ |   0 Hey Mr, you trying to get some fake sympathy here dear?
•  » » 4 years ago, # ^ |   +73 A codeforces a day keeps girlfriend away.
 » 4 years ago, # |   0 GLHF
 » 4 years ago, # |   +107 Maybe server was unexpectedly fast, so they must make delay to see what is wrong :P
 » 4 years ago, # |   +13 UPD 1 Contest delayed by 10 minutes. We saw that, maybe we can see scoring distribution next?
•  » » 4 years ago, # ^ |   0 Yes maybe, that's not impossible.
•  » » » 4 years ago, # ^ |   +33 Also it is not possible.
 » 4 years ago, # |   +10 These numbers <3 :'D
 » 4 years ago, # |   0 Blin che za nesereznost'?
 » 4 years ago, # | ← Rev. 3 →   +6 Just 2 minutes till to learn scores of problems :PContest delayed 5 more minutes LOL :D
•  » » 4 years ago, # ^ |   0 and now 1 min !
•  » » » 4 years ago, # ^ |   +3 and 6!
•  » » » 4 years ago, # ^ |   +4 and now 6 min
•  » » » 4 years ago, # ^ |   0 U say what?
•  » » » » 4 years ago, # ^ |   0 WTF? :D Refreshed page 5 more minutes :(
•  » » » 4 years ago, # ^ |   +3 and now 5 minutes!!
•  » » » 4 years ago, # ^ |   0 And now 4!
•  » » 4 years ago, # ^ |   +1 Maybe it will be dynamic scoring :D
•  » » » 4 years ago, # ^ |   +10 While I am seeing just dynamic start time :)
•  » » 4 years ago, # ^ |   +5 Maybe 12 minutes or more.
•  » » » 4 years ago, # ^ |   0 Why need to delay? I mean I'm okay with seeing scoring when the contest starts
•  » » » » 4 years ago, # ^ |   0 I think there's another problem...
 » 4 years ago, # |   0 Again 5 minutes late.So sad:(
 » 4 years ago, # |   0 Contest delayed by 5 minutes.
 » 4 years ago, # |   0 Again Delay!! :(
 » 4 years ago, # |   +13 Delays ... Delays Everywhere
 » 4 years ago, # |   +2 I can only say: :|
 » 4 years ago, # |   +5 UPD 2 Contest delayed by 5 minutes.
•  » » 4 years ago, # ^ |   +2 How did you know that? :DDD
•  » » » 4 years ago, # ^ |   +3 he is GOD :)
 » 4 years ago, # |   0 Auto comment: topic has been updated by Batman (previous revision, new revision, compare).
•  » » 4 years ago, # ^ |   +31 The 7th problem is almost ready? :)
•  » » » 4 years ago, # ^ |   0 Laughing so hard at this!! =))))
 » 4 years ago, # |   +6 = ChamrAn what is the score distribution ? -read the problem statement
•  » » 4 years ago, # ^ |   0 hahahahhaAhaha
 » 4 years ago, # |   0 ffs we have finals
 » 4 years ago, # |   0 And again ... !!!
 » 4 years ago, # |   0 UPD 2 Contest delayed by 5 minutes
 » 4 years ago, # |   0 CF is delaying the contest little by little so we don't understand that thank you CF :|
 » 4 years ago, # |   0 If this contest gets pushed back any further I'll be late for work...
 » 4 years ago, # |   0 another 5 mins :)
 » 4 years ago, # |   +2 I hope this round wont cancel at the end of the delays
 » 4 years ago, # |   0 Can we have an announcement about these delays or not? :/
 » 4 years ago, # |   +14 2.5 mins next?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +18 No. That's too predictable. We'll make it 15 next time.
•  » » » 4 years ago, # ^ |   0 And here I was hoping for a GP.
•  » » 4 years ago, # ^ |   0 Therefore the total delay is 20 minutes? :P
 » 4 years ago, # |   +31 Please stop playing with my heart.
 » 4 years ago, # |   0 A first delay is ok, A second one? that's irritating
 » 4 years ago, # |   0 Why the contest is not starting?
 » 4 years ago, # |   +45 They are doing Binary search on delay . first 10 min, then 5 min... :|
•  » » 4 years ago, # ^ |   +1 In this way the contest will never start :)...paradox
•  » » » 4 years ago, # ^ |   0 Not in machinary computing case! >D
•  » » 4 years ago, # ^ |   0 Good point, hahaha
 » 4 years ago, # |   0 Why So Much Delay ? :(
 » 4 years ago, # |   0 Now i regret i upvoted the blog...
 » 4 years ago, # |   +36 Contest delayed by minutes
•  » » 4 years ago, # ^ |   +3 it shows that contest will starts at end!
•  » » 4 years ago, # ^ |   0 Accepted
 » 4 years ago, # |   -21 What the Fuck, Dude
 » 4 years ago, # |   +17 5 more Minutes please
 » 4 years ago, # |   0 Is it dalayed? Twice? Or have a bad computer?
•  » » 4 years ago, # ^ |   0 Oh sorry I didn't see the update announcement :P
•  » » 4 years ago, # ^ |   -10 dalayed...
 » 4 years ago, # |   +19 Annoying : delayMore annoying : second delayMost annoying : people complaining
•  » » 4 years ago, # ^ |   +15 Mostiest annoying: people complaining about people complaining
•  » » » 4 years ago, # ^ |   +15 Mostiest annoyingest: people complaining about people complaining about people complaining.
 » 4 years ago, # |   +22 Expecting: Due to the delays starting the contest. This contest will be unrated.
•  » » 4 years ago, # ^ |   0 breaks keyboard
•  » » 4 years ago, # ^ |   0 Haaaahaa
 » 4 years ago, # |   +9 Delays are for the people using Internet Explorer.
 » 4 years ago, # |   0 The scoring is going to be a surprise this time :p
 » 4 years ago, # |   0 Quite frustrating when you reschedule everything in your day so you can fit the codeforce's contest but it keeps delaying.
 » 4 years ago, # |   +77 So we have infinite geometry series, next delay will be 2.5 minutes, and 1.25 minutes, and so on, so total delay time will be 20 minutes to sum up. :)
•  » » 4 years ago, # ^ |   +27 Or they'll be like 10, 5, 10/3, 2.5, 2, etc st the contest will never start, how can we know?
 » 4 years ago, # |   0 Waiting for next delay.
•  » » 4 years ago, # ^ |   0 No delay :p
 » 4 years ago, # |   0 I'm sleepy...
 » 4 years ago, # |   +3 long time no cf :)
 » 4 years ago, # |   +1 You know what? 100 rating points on another 5 minutes. :)
 » 4 years ago, # |   0 Auto comment: topic has been updated by Batman (previous revision, new revision, compare).
 » 4 years ago, # |   0 Long queue :(
 » 4 years ago, # |   0 Hack page is not loading. :(
 » 4 years ago, # |   -11 Solved 2 cant submit any so quitting this round
 » 4 years ago, # | ← Rev. 4 →   +6 I waited 20 minutes for the page loading to hack a code, and then it tells that the code was hacked !!!!EDIT : 4 codes
 » 4 years ago, # |   +1 I dont like rounds where if you are put in a room where everyone solves the problem right you cant participate well :(
 » 4 years ago, # |   0 long queue :s
 » 4 years ago, # |   0 Queue is driving me MAD!
 » 4 years ago, # |   0 In queue :(
 » 4 years ago, # |   0 I think Div2 A, B, C, D are too easy. Most people solved them in < 1 hour. Maybe system test will prove me wrong.
 » 4 years ago, # | ← Rev. 3 →   +228 And at this moment Jackson knew... He f***ed up
 » 4 years ago, # |   +3 I've been waiting forever for the hack form to load.
 » 4 years ago, # |   0 What was approach to solve problem D?
•  » » 4 years ago, # ^ |   +3 Make a little observation and you will get it.result of aaab is same as result of aab+aab and you get 3 a's at the resultant string.So, the recurrence you get is R(n) = 2*R(n-1)Little bit more observation will show that taking R(0) = 1 works for all cases.And the initial sting aaab was available without any transformation. So the answer will be R(n)-1 for this case. Now, think about what you do for the case aabab, and you will know the solution.
•  » » 4 years ago, # ^ |   +1 "Bubble sort" all 'a' to right side of string, count all swaps. On every swap 'b' becomes doubled.
 » 4 years ago, # | ← Rev. 3 →   0 What is the hack for C (Div.2 E)?
•  » » 4 years ago, # ^ |   0 what the hell??? I hope this contest won't be rating
•  » » » 4 years ago, # ^ |   0 Why?
•  » » 4 years ago, # ^ |   +3 Maybe2 50 0 1 2Or something like this
•  » » 4 years ago, # ^ |   0 maybe each node has 0 element in their set?
•  » » 4 years ago, # ^ |   +5 I was hacked by the test where no ice creams are given in any set. So i was outputting total colors as 0 whereas it should be 1(color all of them the same).
•  » » » 4 years ago, # ^ |   +3 NOOOOOOOOOOOOO I'M SO DUMB
•  » » » 4 years ago, # ^ |   0 Great. That bull#&! testcase made the difference between ~+120 and ~-50 rating for me (according to rating estimator extension)
•  » » » » 4 years ago, # ^ |   +5 You're not the only one, buddy.
 » 4 years ago, # |   0 For me problemset was like AAACDE but still nice though. I think may have missed something in one of problems ABC, so are there any special cases except l == r in A?
 » 4 years ago, # |   +4 How to solve D?
•  » » 4 years ago, # ^ |   0 IF we have string with 'a' and n 'b'-s, it becomes 2*n 'b'-s and one 'a' after n operations. Then start from the end of the string and every time you will have string of this type, so you count operations you need and new number of 'b'-s
•  » » 4 years ago, # ^ |   0 Probably go from left to right and count 'a'. If encountered 'b', then ans=(ans+pow(2,count_of_a)-1)%(1e9+7) Because of my very stupid mistake I got AV test 13. I just precalculated powers for only first 32 arguments....
•  » » » 4 years ago, # ^ |   0 I did something like this before:count a from left to right and count a, if I encounter b then ans = (ans + (1 << count) — 1) % (1e9 + 7) but still not pass pre-test 6 Not sure why, then I tried going from right to left, also failGonna wait for the editorial then ..
•  » » » » 4 years ago, # ^ |   +3 Well 1 << count can easily overflow. You should use binary exponentiation instead.
•  » » 4 years ago, # ^ |   0 Think of it as sending every 'a' to the end of of the array, by operating it against all 'b' on it's right. If we start from the rightmost to leftmost 'a', there will be a contiguous (subarray) stream of 'b' for each 'a'. The number of 'b' will double for each 'a' that passes it.
 » 4 years ago, # | ← Rev. 3 →   0 Found this during the contest but couldn't figure out anything. Can these things actually help to solve E? How to solve E?
•  » » 4 years ago, # ^ |   +3 The graph class you should be looking for is chordal graphs.
 » 4 years ago, # | ← Rev. 4 →   0 .
 » 4 years ago, # | ← Rev. 2 →   0 It seems to be a happy hack round. :)
 » 4 years ago, # |   +6 How to solve Div1C/Div2E?
•  » » 4 years ago, # ^ |   +4 BTW, End sem aa rahe hain :P
 » 4 years ago, # | ← Rev. 2 →   +24 Very bad contest Problems are very bad and first 4 problems very easy to div 2 and hacks are overrrrrrrr
 » 4 years ago, # |   0 Does a character string (example char s[200000]) have junk value towards the end ??
 » 4 years ago, # | ← Rev. 2 →   +94 I'm just curious: is it so well-known that an empty graph is considered a connected subgraph? I've had this doubt during the contest, but somehow this phrasing got me thinking that it should have at least one vertex. Shouldn't this be an aspect worth clarifying in the statement?
•  » » 4 years ago, # ^ |   +18 Graph has non-empty set of vertices. So rejudge or unrate should be done.
•  » » » 4 years ago, # ^ |   +14 Many hacks have been done with empty subgraphs in the input, which is a bit unfortunate.
•  » » » 4 years ago, # ^ |   +40 Graph has non-empty set of vertices. Source?
•  » » » » 4 years ago, # ^ |   +37 Russian wikipedia, at least
•  » » » » 4 years ago, # ^ |   +25 English wikipedia suggests an ambiguity too:"Moreover, V is often assumed to be non-empty, but E is allowed to be the empty set."I would not assume any re-evals will occur though
•  » » » 4 years ago, # ^ |   +66 I don't think that round should be unrated. Seems that the best way is accept all hacks, but rejudge solutions without such tests.
•  » » » 4 years ago, # ^ |   0 Do authors and coordinator KAN even read the comments? Anyway it is a fault in statements, and we see no reaction.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +30 Yes, I read comments. We will think how to resolve the situation.
•  » » » » » 4 years ago, # ^ |   0 So, what was decided in the end? I am not insisting of anything, just asking out of curiosity :)
•  » » » » 4 years ago, # ^ |   -20 First, this test was indeed a hack test.Second, I think that in this particular problem the ambiguity was much less than in general question "is the empty graph a graph?". Of course, it would have been better if we had explicitly mentioned this in the statements. But now, I think the best option is to leave it as it is.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   +73 I think the ambiguity was exactly the same, which is also confirmed by the fact that authors haven't made such tests. If the problem was "count the number of connected subgraphs in the tree", no one would consider the empty graph. If not mentioned in the statements, it must have been tested by pretests, because it is clearly a matter of understanding the problem.Leaving it as it is is the most unfair for those who wasn't hacked. But I don't see the better option now too.
•  » » » » » 4 years ago, # ^ |   0 "First, this test was indeed a hack test." Does it mean that organizers didn't provide it or it wasn't added to systests?
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   +20 There were a lot of hacks added to systests, and there were no such tests in the testset provided by organizers.
•  » » » 4 years ago, # ^ |   -17 Yeah, and array has non-empty set of elements, and string has non-empty set of characters.
•  » » » » 4 years ago, # ^ |   +18 Source?
•  » » » 4 years ago, # ^ |   +16 Not exactly: https://en.wikipedia.org/wiki/Null_graph
•  » » » » 4 years ago, # ^ |   0 "Some authors exclude K_0 from consideration as a graph"Still debatable ...
•  » » » » » 4 years ago, # ^ |   0 If there are two valid interpretations, but the problem doesn't specify anything like "sum of si's must be positive", it seems like the problem setters want to allow null graphs.
•  » » » » » » 4 years ago, # ^ |   +8 If there are two valid interpretations, there is a serious issue with the problem statement.
•  » » » » » » » 4 years ago, # ^ | ← Rev. 4 →   -10 Well, the input criteria (all si are allowed to be 0) seemed to clear up the ambiguity.For instance, don't you sometimes see problems where the text says something like "subsequence" or "substring" and only later when you read the input specifications you figure out it is contiguous/nonempty/etc?
•  » » » » » » » » 4 years ago, # ^ |   +18 Actually si being equal to 0 is irrelevant to the problem of empty graph (because even if all vertices had sone color it is possible that some color is not present in the graph)E.g consider testcase 2 2 1 1 1 1 1 2 
•  » » » » » » » » » 4 years ago, # ^ |   0 Makes sense. I was thinking more in terms of the case when all si are 0.
•  » » » » » » 4 years ago, # ^ |   +15 But the problemsetters haven't made such tests, see my comment below.
•  » » » » » » » 4 years ago, # ^ |   0 Yes, I agree this is the real issue. Perhaps the authors aren't even aware of the ambiguity.
•  » » » » » » » » 4 years ago, # ^ |   +5 Note that even if the problem setters didn't add the ambiguity intentionally at the first, the problem setters could've announced a clarification during the contest. Certainly, there were questions about the ambiguity and author must have been aware of it. Therefore, I can say that the problem setters intentionally created the ambiguity in a sense.
•  » » » » » » 4 years ago, # ^ | ← Rev. 12 →   0 "Vertices which have the i-th (1 ≤ i ≤ m) type of ice cream form a connected subgraph." Misinterpretation can happen here if you do not consider null graph as graph .As cited: "To avoid the need for such exceptions, it is often assumed in literature that the term graph implies "graph with at least one vertex" unless context suggests otherwise."
•  » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 A null graph is connected. I agree that graphs generally have at least one vertex. The problem's context (it's possible that all si are 0) led me to believe otherwise.
•  » » » » » » » » 4 years ago, # ^ |   0 Actually I just saw this: "Please note that we consider that empty set of vertices form a connected subgraph in this problem."This does fix every issue I said. :D I don't think there is anything wrong with this problem (except checker issue discussed down in comments).
•  » » » » » » » » » 4 years ago, # ^ |   +13 This phrase was added just recently.
•  » » » » » » » » » 4 years ago, # ^ |   +22 To prevent confusion, I'm here to say that this part was added after the contest to make sure no one face this issue later.
•  » » » » 4 years ago, # ^ |   0 "To avoid the need for such exceptions, it is often assumed in literature that the term graph implies "graph with at least one vertex" unless context suggests otherwise."
•  » » » » » 4 years ago, # ^ | ← Rev. 3 →   0 I agree that graphs generally have at least one vertex. The problem's context (all si can be 0) led me to believe otherwise.
•  » » 4 years ago, # ^ |   +25 Well, if you consider empty graph a graph, it's obvious it's connected (I mean definition is that any pair of vertices is connected which is true)Whether it's a graph is a good question, though
•  » » 4 years ago, # ^ |   +5 But you can't say that an empty graph is not connected? Unless you can provide two vertexes, that aren't connected by any path.
•  » » » 4 years ago, # ^ |   +3 Definition of a path is a sequence of edges which connect a sequence of vertices. If you have a path containing no edges, then there is no path, correct? Therefore your empty graph is not connected.I agree that there are many interpretations, but I believe the problem was ambiguous enough to warrant a rejudge
•  » » » » 4 years ago, # ^ | ← Rev. 4 →   +49 The empty graph is definitely connected. "For every pair of vertices in the graph, there exists a path between the two vertices." is vacuously true, since the set of vertices is empty.
•  » » » » 4 years ago, # ^ |   +15 That is not entirely correct :). A graph with only one vertex and no edges is usually considered connected. But you have just proved that it isn't.My point was that an expression, opposite to graph being connected is "Exist u,v from V such that there is no path between u and v". You can't select anything from empty set thus it is not correct, thus empty graph (if it is really a graph) is connected.
•  » » 4 years ago, # ^ | ← Rev. 3 →   +5 Moreover, seems like all tests with empty subgraphs are actually hacks. So it's fault not in statements but in validator.
 » 4 years ago, # |   0 My solution for E is way too simple to be true. How to solve E?
 » 4 years ago, # |   +5 In Div1 E is the answer YES iff n=2^p, n!=2?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +10 No, the answer is YES iff n = 4k, 4k + 1. Proving that 4k + 2, 4k + 3 doesn't work can be done by looking at the parity of the number of cycles in the cycle representation but I couldn't find a construction for 4k, 4k + 1 in contest time.
•  » » 4 years ago, # ^ |   +8 answer is yes when n ≡ 0, 1mod4. For n ≡ 2, 3mod4 the answer is no. (which is clear, because trivial permutaiton is even so the number of transposition should be even and is even only when n ≡ 0, 1mod4.)Construction is harder. But I guess one should use the following identities: (12)(34)(13)(24)(14)(23) = e (1x)(xy)(y1) = (xy)
•  » » » 4 years ago, # ^ |   0 Yeah, I knew the parity argument. I could only come up with a construction for n=2^p so I kind of assumed that was the only case.
•  » » » » 4 years ago, # ^ |   +28 ok. The full solution is:when n = 4k + 1 construct first for 4k then using (nx)(xy)(ny) = (xy) plug inside all (n, 1), (n, 2), ..., (n, n - 1).when n = 4k + 4 then construct first for 4, 5, ..., 4k + 4 by induction. Put (12)(34)(13)(24)(14)(23) at the beginning. And plug inside all (1x), (2x), (3x), (4x) as we did in the first case.
 » 4 years ago, # |   0 DIV 2EI was thinking that each node will form a clique of size number of icecream in that node i.e if there are 3 icecream in a node in T, then there will be a clique of size 3 for that node in G. I found maximum size of clique and colored nodes such that no 2 items in a clique will have same color.It failed on pretest-3. Am I missing something?
•  » » 4 years ago, # ^ |   0 I think every vertex set will form a clique. And every clique will have colors = size of clique. I don't know what else to think.
 » 4 years ago, # |   +4 Why so much math and greedy? I don't know about E and F though. I solved E by greedy that i did't even understand why it passed the pretest ?_?
 » 4 years ago, # | ← Rev. 3 →   +16 Have I understood the problem E correctly? There is no meaning to use edges between vertices in the given graph T?
•  » » 4 years ago, # ^ |   0 agree with you
•  » » 4 years ago, # ^ |   0 Same. I do 2 clarifications and still don't understand what is the use of edges in the tree..
•  » » 4 years ago, # ^ |   0 Yes, it guarantees there won't be contradictions between nodes. Also you can fill the answer in the order of tree traversal.
•  » » » 4 years ago, # ^ |   +1 What's the point of tree?
•  » » » » 4 years ago, # ^ |   +5 So the new constructed graph will not have cycles.For example: {1,2}, {2,3}, {3,1} can't be nodes on a tree. (vertices which have the same type of ice cream form a connected subgraph)
•  » » » » » 4 years ago, # ^ |   0 Can you please explain with a sample case?
•  » » » » » » 4 years ago, # ^ |   +5 3 3 2 1 2 2 2 3 2 3 1 1 2 2 3 This is invalid.
•  » » » » » » » 4 years ago, # ^ |   0 can someone explain why this is invalid?? thanks 
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   +6 The new constructed graph will have cycles if vertex set size >= 3, right?I meant, vertex set of given tree, not the new one.
•  » » » » » » 4 years ago, # ^ |   0 No, maybe you missed this: Vertices which have the i-th (1 ≤ i ≤ m) type of ice cream form a connected subgraph.
•  » » » » » » » 4 years ago, # ^ |   0 Hmm, I think what you mean is, after compressing each clique to one node in the new graph, we have a new tree. Am I right?
•  » » » » » » » » 4 years ago, # ^ |   0 Yes, G was a "tree of cliques".You could use the tree to assign the colors greedily correctly :)
•  » » » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I now understand why input has to be a tree. Otherwise, we might have clique of cliques. The solution only works if G is a tree of cliques.
•  » » » » » » » » » 4 years ago, # ^ |   0 The "every ice cream forms a connected subgraph" condition means nothing, unless graph is specific. In case of a clique any pair of vertexes are connected. That means there are absolutely no restrictions. You can easily reduce any vertex coloring to it.
 » 4 years ago, # |   0 Auto comment: topic has been updated by Batman (previous revision, new revision, compare).
 » 4 years ago, # |   +39 When problem C is about finding yourself :D
 » 4 years ago, # |   0 I was sure my solution for C is correct, but obviously it is not :) Is asnwer always max(Si) ?
•  » » 4 years ago, # ^ |   0 Is it even a div2 E level problem!
•  » » » 4 years ago, # ^ |   0 When there are 6 problems? Yes.
•  » » » » 4 years ago, # ^ |   0 So the solution is the size of maximum clique size?
•  » » » » » 4 years ago, # ^ |   0 Yes
•  » » » 4 years ago, # ^ |   0 I didn't solve it :D I have no idea what is wrong , but possible I am a little stupid.
•  » » 4 years ago, # ^ | ← Rev. 4 →   0 Nope, look at this case: 4 43 1 2 32 1 42 2 42 3 41 2 1 31 4
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 [DELETED]
•  » » » 4 years ago, # ^ |   +9 This test case violates the fact that vertices with color 'i' form a connected subgraph. Consider color 2.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I edited the testcase. I think it is valid now..?UPD: Sorry, no, it is still wrong.
•  » » » » » 4 years ago, # ^ |   0 Again it is not valid.I was right. But I do not know how I missed implementation part.
•  » » » » » » 4 years ago, # ^ |   0 Yeah...I also thought the same thing as you did, but then I came up with invalid testcases like this one! -_-
•  » » 4 years ago, # ^ |   0 No, because all Si can be zero, but you should answer 1. XDAnd yeah, this test is used as a hacktest on the contest. Many contestants missed this including me at first.
 » 4 years ago, # |   +3 Div 2 A — D problems were almost two liners. xD
•  » » 4 years ago, # ^ | ← Rev. 2 →   +1 For me it's an advantage. I prefer enjoyable thinking to tons of coding (often frustrating).
•  » » » 4 years ago, # ^ |   +1 but there weren't much thinking either...
•  » » » » 4 years ago, # ^ |   +3 It depends on the skill level of participant.
•  » » » » » 4 years ago, # ^ |   +7 agreed, I personally find A-D too easy, while I can't understand what E is asking, so i give up. Anyone mind explaining what E is asking for?
 » 4 years ago, # |   0 In my Div2 Blink 1 — fails pretestslink 2 — passes pretestsAny help ??Does setting s[n]='\0' matter ??
•  » » 4 years ago, # ^ | ← Rev. 3 →   +1 Yes, it does. When you create an array inside a function it's allocated in the memory area called stack. It's randomized (filled with random numbers). When you create an array outside it's allocated in so-called global storage. It's filled with zeroes. '\0' marks the end of a word and on most systems numerically equals zero (i.e. '\0' == 0).
•  » » » 4 years ago, # ^ |   0 Thanks I got 2 wrong submissions because of that !!
•  » » 4 years ago, # ^ |   +1 when you're dealing with string as a char array, it does.
 » 4 years ago, # |   +6 500-500-500-1500-2500-3000
 » 4 years ago, # | ← Rev. 2 →   +13 In C (Div.2 E), not including a test where all vertexes have sets of size 0 is like purposely making a 'hack problem.' Shouldn't hacking not be about something like that? Nice contest overall though
 » 4 years ago, # |   +15 Did anyone have trouble understanding F? I still don't understand what the problem is asking for, and I wasn't even sure where to start in terms of clarifications. Maybe one question is, do the coin transfers happen all simultaneously at each hour? Is there a fixed number of hours? Usually, when I see 10^100, it suggests that we let a random process run until it converges, but I don't see any randomization here, so that's probably another reason I got confused.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +10 Here you can consider 10^100 inf.The problem ask for this:For each gang consider that after 10^100 hours it has a[I] billions at first and it has b[I] billions now.Each of them will have a number of accepted billions between a[I] and b[I].Police sort them in increasing order and choose a gangs from top and choose b of them.What is the number of choosing b gangs.
•  » » » 4 years ago, # ^ |   +5 Ok that makes a bit more sense. I guess my other question would be how exactly does the tranfer process work? It seems we have the i mod s_i thing which seems not to suggest splitting indices up by gcd. Also I guess you also split the gangsI into strongly connected components and solve those individually. I believe there is a cycle involving arbitrary gangs within the same strongly connected component. Can you check my understanding is correct?
•  » » » » 4 years ago, # ^ |   0 It works till they see a completely same state that they saw it before ( it happen before 10^100 hours)
•  » » » » » 4 years ago, # ^ |   0 Does the selling and trading happen in separate stages or can they be mixed together?
•  » » » » » 4 years ago, # ^ |   0 Ok, I think I finally figured it out. Here is what was confusing to me.There are two distinct parts to this problem: 1) Compute for each person, can they eventually receive a fake coin? 2) Afterwards, there is the math problem that you mentioned above.I was very confused about part 1, and was not sure how to interpret the statement. For example, a sample explanation explaining the process would have helped greatly in clearing up any confusion, and I don't think it would have made the problem easier. Because I wasn't able to figure out what part 1 was, I didn't even get a chance to think about part 2. It was only having the interpretation with part 2 in mind was I able to correctly decipher what the statement was asking. To be honest, I think statement is unambiguous, but I don't think it was clear or concise.Also, as a side note, my solution is O(sum s_i + n^2), but it takes 2.7s. Is there a faster solution in mind?
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 I'm happy that you understand this problem.I agree with you that the statement wasn't clear enough but it changed at the last moments, I read the last one and that was clear, for some changing in problem they change the statement.I was tester of the problem and my solution works in 700ms.
 » 4 years ago, # |   -20 Honestly , speaking , questions weren't clear . Some had multiple answers but there wasn't any clarifications regarding this. :(
•  » » 4 years ago, # ^ |   +2 well most of them informed that if there were multiple solutions you could print any.
 » 4 years ago, # |   0 How to solve Div2 F/Div 1D ?
•  » » 4 years ago, # ^ |   +10 You can find for each component its diameter and the distance from each node in that component to the furthest node.Now you need to find the average for combining two components.This can be done in O(n * m) time where n is the number of nodes in the first component and m is the number of nodes in the second. However, this obviously wouldn't run in time. We can speed it up greatly by knowing the average diameter will just be (avgA + avgB + 1) Where avgA is the average max distance of all nodes in the first component and avgB is the same for the second component. However, this isn't always true. In some cases, connecting two nodes will not extend the diameter further than it currently is in the two components.Thus, we need to count these cases where the diameter doesn't change. We can do this in O(n) time where n is the number of nodes in the first component.We will for each node, binary search which node we can connect it to such that the diameter doesn't change. (We will have all distances of each component in sorted order so we can binary search) Then we can do some math with cumulative sums and cumulative averages to subtract out the appropriate portion and add back what we need knowing that all of these pairs will result in an unchanged diameter.This brings our runtime down to O(n * q * log(n)). This is still far too much. However, we can do two speedups to get it to run in time. First, we can memoize the answers we find for each pair of components. Thus, we will never need to deal with the same query more than once. Second, we will always do the linear loop on the smaller component. This will bring our runtime down to O(q * sqrt(n) * log(n)) which is good enough for the time limit.
•  » » » 4 years ago, # ^ |   +5 Use 2-pointers will decrease the Time To : (n+q)*(sqrt(n))
•  » » » » 4 years ago, # ^ |   0 You have to be very careful doing a two point sweep there. If each pointer always gets to go its full distance, you don't get the sqrt(n) speedup and your runtime is O(n * q).
•  » » » 4 years ago, # ^ |   +5 Why after last optimization you do, complexity turns to O(q * sqrt(n) * log(n)) ?? Can you prove it please ?
•  » » » » 4 years ago, # ^ | ← Rev. 5 →   +6 Let a1  ≤  a2  ≤  ...  ≤  an be the sizes of the trees in the forest, and qi the number of times tree i is the smaller tree in a query. Also, let and The runtime is . We can forget about the term and multiply by it after we're done. Now, The second term in the inequality comes from the fact that if we must have (because the ai are sorted, so in the worst case every ai has elements greater than it.)Edit: lmn0x4F did this in an earlier comment below, sorry about that.
•  » » » 4 years ago, # ^ |   +5 Very nice explanation tbuzzelli, could you give some insight about the sqrt(n) in your complexity analysis?, I have some sign that could be like it, when the sizes of the each tree in the forest are: 1, 2, 3, ..., x and this sum is equal to n, for this x = sqrt(n), and now answer the querys is as you say O(q*sqrt(n)*log(n)), is it correct? What is a better analysis for it?
•  » » » » 4 years ago, # ^ |   +1 Because each component will only contribute it's size for all things larger than it, it is fairly easy to show that in order to maximize runtime, all the components should be the same size. Now the question is, how many components should we have.Let N equal the number of nodes in our graph and let X be the number of components. Our runtime would thus be q * (N / X). However, each query must be unique because we memoize. Thus q <= X^2. Therefore our runtime is actually max(q, X^2) * (N / X). Let's assume that q = X^2 because any excess queries would just be repeats and are trivial to handle. Now we have a runtime of X^2 * (N / X) = X * N. We want to maximize X. Because X^2 <= max number of queries, X should be sqrt(100,000) which is technically sqrt(N) in this case because I considered the variables for bounds on N, M, and Q to all be the same for Big-Oh runtime analysis.I hope this makes sense. It is a fairly common runtime as if X is too large, the pairs don't contribute much and as X gets too small there just aren't enough pairs to make a large runtime. Feel free to message me if you have any further questions.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +5 This is such a nice and simple speed up! Did you came up with this during contest or is this something somehow common?Also, could you elaborate on where did the sqrt came from? I thought something like:For each query we find U, V (connected components) with U ≤ V. then it's easy to see the . then each vertex in U gets visited at most times in total. This leads me to something like Is there other way to think about it?Thanks :)
•  » » » » 4 years ago, # ^ |   +1 So as long as we only loop through the smaller of the pair, we can show that our runtime will amoritize to q*sqrt(n) if we make sure to never repeat the same pairThis is a fairly common speedup. In order for us to get a bad case, we need the max of n and m to be as large as possible where m and n represent the sizes of our two components.Because no pair can be repeated (because we memoize) the worst case on queries will be if we get every pair of components given to us(this may not be possible if the number of components is large but we will assume we can have an infinite number of queries for now). Thus, if we query every pair of components, our runtime is the sum of min(n(i), n(j)) for all (i, j) pairs. Therefore, for each component it only contributes it's size to our runtime the amount of times equal to the number of components greater in size than it. If we have two components of size n/2 we will have O(n/2) just for that but then we have little to no nodes left. It turns out that the way to maximize this runtime would be to have sqrt(n) equal size components. This brings us to the sqrt(n)*q runtime. The log(n) part is because we binary search ontop of that.
•  » » » » 4 years ago, # ^ |   +9 This is a well known technique, introduced in IOI 2009
 » 4 years ago, # | ← Rev. 2 →   0 The first & the second of DIV 2 have never take part of any previous contest !? Congratulations every one and best of luck in the next contests :)
 » 4 years ago, # |   +19 That feel when you realized you did not fix your own bug before hacking others :(
 » 4 years ago, # | ← Rev. 2 →   0 How was DIV2C/DIV1A supposed to be solved? :c
•  » » 4 years ago, # ^ |   +4 (n — 1) / 2
•  » » » 4 years ago, # ^ |   0 Thanks
 » 4 years ago, # |   +73 When you are that one guy -_- (Div1 A, somehow thought that answer on 1 would be 1 :D and then locked it immediately) :D :D
•  » » 4 years ago, # ^ |   0 Today was not your day mate :(
 » 4 years ago, # | ← Rev. 2 →   0 The first & the second of DIV 2 have never take part of any previous contest !? Congratulations every one and best of luck in the next contests :)
 » 4 years ago, # |   +6 Will the system testing be today itself??
•  » » 4 years ago, # ^ |   +3 I believe it should start in less than an hour like normal.
 » 4 years ago, # |   +7 How to solve Div2 E?
 » 4 years ago, # |   0 What was pretest 3 for Div 2 E ? I used DSU for finding connected subgraphs and assigning colors incrementally to each node in each subgraph !! WA on pretest 3
 » 4 years ago, # | ← Rev. 2 →   -10 how this code get AC http://codeforces.com/contest/805/submission/26862337 and this get TLE ?!!!!!!!!! http://codeforces.com/contest/805/submission/26850899How ????????????????????????????????Edit this code get AC how !!http://codeforces.com/contest/805/submission/26864979
•  » » 4 years ago, # ^ |   0 They both rejected. Pretests are just pretests you know.
•  » » » 4 years ago, # ^ |   0 yeah! but see this one!http://codeforces.com/contest/805/submission/26850369
•  » »