### Lewin's blog

By Lewin, history, 6 years ago,

Hello everyone!

Codeforces round #385 will take place at the unusual usual time of Saturday, 17 December 19:35 MSK.

Thanks to the following people for making this round possible.

As usual, contestants will have 2 hours to solve 5 problems. Hope you will enjoy the problems!

Scoring will be announced closer before the round.

EDIT: It may be helpful to read the Interactive Problem Guide before the round for both divisions.

EDIT 2: The scoring distribution will be unusual:

Div2: 500-1000-1500-2250-2750

Div1: 500-1250-1750-2250-2500

EDIT 3: While you wait for system testing, here is a quick editorial: http://codeforces.com/blog/entry/49126

EDIT 4: Congratulations to the winners!

Div1:

Div2:

• +477

 » 6 years ago, # |   +17 Interesting problem setters. Now, i'm more eager to participate :)
 » 6 years ago, # | ← Rev. 8 →   -50 Deleted...
 » 6 years ago, # |   -62 I am sure that this round by Lewin will contain interesting problems(not as previous two rounds).
 » 6 years ago, # |   +40 Clashes with COCI #4. It would be awesome to move it to 20:xx MSK (a hour later).
 » 6 years ago, # |   +434 ** ** *****?
•  » » 6 years ago, # ^ |   -26 yes ! :D
•  » » 6 years ago, # ^ |   +293 ***
•  » » » 6 years ago, # ^ |   0
 » 6 years ago, # |   -124 hope not to see comments like "is it rated?" or "usual time"
•  » » 6 years ago, # ^ | ← Rev. 2 →   -25 up-and-down : ** ** *****?
•  » » 6 years ago, # ^ |   -69 Is it rated ?
 » 6 years ago, # |   -36 Found it funny:"unusual usual time"..:)
 » 6 years ago, # |   +1 nice tags
 » 6 years ago, # |   +22 Till now I found out that Lewin is fantastic setter. I hope another , balanced problemset !When I see interactive task I know my rating will go down :D It would be nice to say before contest which task is interactive, for you it is not big deal for me and probably fot many users it is very important.
•  » » 6 years ago, # ^ |   +6 it's ( div2-C/div1-A ) or ( div2-D/div1-B ) we will need less than 2 minutes to find out :D
•  » » » 6 years ago, # ^ |   +4 Why not div1C?
 » 6 years ago, # |   +11 Again interactive! every time I see and I think- well! I can solve it :D but then- I say — Sorry me! :(
•  » » 6 years ago, # ^ |   0 So you saw a lot of interactive problems. Interesting :)
 » 6 years ago, # |   +36 After seeing the tags and round description, I'm wondering, if we will have to interact with cows...
•  » » 6 years ago, # ^ |   +91 moo?
 » 6 years ago, # |   +5 Wondering how to hack the interactive problem?
•  » » 6 years ago, # ^ |   +6 The statement always explains how to.
•  » » » 6 years ago, # ^ |   +3 sometimes source code can't be seen by double click or ctrl+clik after lock my submission, it shows only submission history. why?
 » 6 years ago, # | ← Rev. 2 →   -39 -
 » 6 years ago, # |   +20 thanks Lewin for suggesting to read the interactive problem guide. i would have wasted some time in the contest to learn how to solve interactive problems. i never solved an interactive problem.
 » 6 years ago, # |   -12 This contest seems to be better one.
 » 6 years ago, # |   +56 It seems that codeforces is cleaning up its inventory of problems before Christmas...
 » 6 years ago, # | ← Rev. 2 →   -49 Today Petr is participating :) ,any guesses in which language(Java/C++/both) he will code in todays contest ?
 » 6 years ago, # |   -13 Hope the interactive problem will be interesting.:)
 » 6 years ago, # |   +37
•  » » 6 years ago, # ^ |   +138
•  » » » 6 years ago, # ^ |   +41 I bet on allllekssssa
•  » » » » 6 years ago, # ^ |   +35 At least I have the biggest opportunity to change color :D
•  » » » » » 6 years ago, # ^ |   +32 to blue ? :D
•  » » » » » » 6 years ago, # ^ |   +4 Yeah :) it is relly bad to do following three rounds unofficial :D
•  » » 6 years ago, # ^ |   0 Clash of titans xD
•  » » 6 years ago, # ^ |   0 Finally... =)
•  » » 6 years ago, # ^ |   +29
•  » » 6 years ago, # ^ |   0 aka "how the heck did he lost rating as a rank2/3"
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 vs jcvb vs Um_nik
 » 6 years ago, # |   -6 Do we need to flush cin? Like not using cin.tie(NULL);
 » 6 years ago, # |   +23 Four contests in a row) Four contests in 3 days) Real happiness...
•  » » 6 years ago, # ^ | ← Rev. 2 →   +21 And all of them are Rated :D
 » 6 years ago, # |   +13 Good luck! I hope more Experts will be Candidate Master!
 » 6 years ago, # |   -17 *** ****** ** ?
 » 6 years ago, # |   +2 Is Codeforces trying to implement "Boxing Day" algorithm from the England Premier League? Xp 4 Codeforces round in 3 days. That's something worth living for...
•  » » 6 years ago, # ^ |   +14 4 Codeforces !! are u arsenal fan :v
 » 6 years ago, # |   0 Excited for interactive problem!Hope i could solve it. Thanks lewin.
 » 6 years ago, # |   +4 I have registered for the div-2 contest but I am not able to see the problems. What should I do.
•  » » 6 years ago, # ^ |   +1 Contest has not started yet! its about 1 hour 44 minutes to go.All the best!!
•  » » » 6 years ago, # ^ |   0 I did realize that later, I actually thought that contest was supposed to start at 8:05.
 » 6 years ago, # |   +3 Hope to provide a grader for the interactive problem :/
 » 6 years ago, # |   0 ICPC REGIONALS ON 22ND, UNIVERSITY PRACTICALS ON 22nd Onwards.Ladies and Gentlemen . Codeforces will always be there, when you need to get high.!Thank you codeforces for the contest series this week.
 » 6 years ago, # |   0 Bad timing for manchester united fan.
 » 6 years ago, # | ← Rev. 2 →   0 ‌
 » 6 years ago, # |   +5 Considering the amount of people who are trying to find out how interactive problems works and sending submissions and how hard it works right now on problem "Guess The Number" do you think it will be ok during the contest?
 » 6 years ago, # | ← Rev. 2 →   +42 Deep♂Dark♂Fantasy (MiracleFaFa, jcvb, YuukaKazami) in this round they will decide who will be the captain
•  » » 6 years ago, # ^ |   0 Deep♂Dark♂Fantasy(MiracleFaFa, jcvb, YuukaKazami) and they still have the same number of legendarys
 » 6 years ago, # |   +6 I hate registering using the lower bottom, hope in this round I can reach Div1 and use the upper one
•  » » 6 years ago, # ^ |   0 I guess I'll cheer you on since I like the problems you write :D
 » 6 years ago, # |   +5 Hi I new to this platform. Today I will be solved by second contest.I was wondering why the newer comments go to the bottom rather than addition of comments to the top.Thank You . Jai Babe di.
•  » » 6 years ago, # ^ |   +20 You are going to be solved? XD
•  » » » 6 years ago, # ^ |   +4 He is the problem, you know... =)
•  » » » » 6 years ago, # ^ |   0 When You Write Problem statements like Div2 B . at least I can make you understand what I mean.And also Don't Worry Be ruski
 » 6 years ago, # |   +10 Good luck everyone! Lewin always writes interesting problems.
 » 6 years ago, # | ← Rev. 2 →   0 I hope there will be lots of math questions!
 » 6 years ago, # |   +3 Explain B problem in Div2
 » 6 years ago, # |   +10 DIV2 B problem statement :(
 » 6 years ago, # |   +6 what is the explanation DIV 2 B means? How can by one movement to right ..... XX... ..... ..... .....be formed ??
•  » » 6 years ago, # ^ |   0 they said two identical copies. I think that's your ans. although I couldn't solve the problem!
 » 6 years ago, # |   +21 Div2 Problem B ..So unclear problem statement. It does not even make sense to me :(
•  » » 6 years ago, # ^ |   +3 Damn right!
•  » » » 6 years ago, # ^ |   +3 I am done with this contest. I am either really stupid or other people who are solving this fast are really geniuses.
 » 6 years ago, # |   0 I just love Ruski English.GGWP ;)
 » 6 years ago, # |   -6 In Problem C Div2 "There is at most one edge connecting any two nodes " and the graph is undirected :/ How is that possible if graph is undirected?
•  » » 6 years ago, # ^ |   +5 I think it means that there is at most one undirected edge connecting two nodes i.e no parallel edges.
 » 6 years ago, # |   0 In DIV 2 B , is it 'x' or 'X' ?
•  » » 6 years ago, # ^ |   0 X
•  » » » 6 years ago, # ^ |   0 thanks pretest passed !!
 » 6 years ago, # | ← Rev. 2 →   -8 in problem B DIV 2 why this test outputs no? 3 3.XXXX.XX.
•  » » 6 years ago, # ^ |   +1 I will get my eye sight tested I cannot understand what was meant by their problem statement. But interesting problems though. ;) Especially D.
•  » » 6 years ago, # ^ |   +4 I guess we cannot move the individual "X"s. I first submitted the solution based on checking whether "X"s form a rectangle or not. Then thought we can move individual "X"s so checked if there exists a,b such that # of "X"s = a*b. If a<=n and b<=m, said YES else said NO. Then decided to hack solutions and then realised after unsuccessful hacking attempt that we are wrong. We have lost this round brother!
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 yes i was hacked on this case . you cannot move the X's which is poorly phrased on the statement .
•  » » » 6 years ago, # ^ |   +1 But then how 5 5.......X.................This outputs YES?
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   +1 Because here the single X is the complete puzzle. I failed in English and not code skills. Sad life. Wish I hadnt submitted it again.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 .XXXX XXXX. XXXX. or .XX XX. XX. .XX XX. XX. It can't be rectangle
•  » » 6 years ago, # ^ |   0 How can you make a rectangle using two such pieces?
•  » » 6 years ago, # ^ |   0 say why yes -> know why no
 » 6 years ago, # |   0 Can I delete my last accepted solution? I only need another one to be verified...
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Only last successful submit will go to system testing.
 » 6 years ago, # |   +16 the problem statement on B is extremely weird !
 » 6 years ago, # |   0 Hacking, hacking everywhere!
 » 6 years ago, # |   0 Ok, it was really great contest))
 » 6 years ago, # |   0 Does anyone have a hack case for Div. 2 B?
•  » » 6 years ago, # ^ |   +3 2 3 XX. .XX Answer is NO.
•  » » » 6 years ago, # ^ |   0 There goes my B solution...Could you please explain why its NO?I'm not sure if I understood properly but why cant you arrange it like this:- .XXYY. .XXYY.(Rearranging the tiles in the puzzles and putting them next to each other. Y are the tiles from identical board)
•  » » » 6 years ago, # ^ |   0 Why is it no? Can't you slide all pieces to the right on the first piece and then slide all to the left on the second piece so that it looks like:.XXXX. .XXXX.
•  » » 6 years ago, # ^ |   0 2 3 .XX XX. 
•  » » » 6 years ago, # ^ |   +4 Why is the answer NO? Cannot we make it as.XX.XX and the other one as XX.XX.and combine two pieces
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 It mustn't intersect and you can't change the figure.
•  » » » » » 6 years ago, # ^ |   0 How do they intersect?
•  » » » » » » 6 years ago, # ^ |   +4 We cannot change individual X positions within one piece. I misunderstood the question :(
•  » » » » » » » 6 years ago, # ^ |   0 "The puzzle pieces are very heavy, so Hongcow cannot rotate or flip the puzzle pieces. However, he is allowed to move them in any directions. The puzzle pieces also cannot overlap."Doesn't this mean you can change individual x positions?
•  » » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 You can move only puzzle pieces not the part of the puzzle pieces. I think it sounds confusing, but russian version is ok.
•  » » » » » » » » » 6 years ago, # ^ |   0 Yeah my bad. I should've asked for a clarification but the other way of understanding it didn't even cross my mind in contest lol.
•  » » » » 6 years ago, # ^ |   0 .XX XX.XX and XX form a single piece(4 connected).
•  » » » » 6 years ago, # ^ |   0 No, you can move only a whole puzze piece, not parts of them
•  » » 6 years ago, # ^ | ← Rev. 2 →   +1 The puzzle piece has to be one of the following types:1. Rectangle2. Horizontal segment3. Vertical segment If the figure formed by 'X' symbols does not belong to one of these 3 types — the answer is NO. Otherwise, the answer is YES.
 » 6 years ago, # | ← Rev. 2 →   0 Petr may reclaim his second rank today.
•  » » 6 years ago, # ^ |   0 and he has done.
 » 6 years ago, # |   +5 How to solve Div2D and Div2E?
 » 6 years ago, # |   0 How to solve the problem about the table game?
 » 6 years ago, # | ← Rev. 5 →   +3 If I pass system testing this will be my best contest ever...fingers crossed wish me good luck.btw what was the hack for DIV 2B ???:)UPD: It passed.:) UPD2:finally blue...here I come Div 1...
•  » » 6 years ago, # ^ |   0 I don't know if it was the hack case but my first submission passed pretests and failed for this case:3 3 .X. XXX XX.Answer is yes. My first submission was awfully written though (so was my second lol) so maybe it was just me that was wrong on this.
•  » » » 6 years ago, # ^ |   0 How is it yes?
•  » » » » 6 years ago, # ^ |   0 I think I may have misunderstood the problem.
•  » » 6 years ago, # ^ |   0 4 4 .... XXX. ..X. .... I did like 4 hacks :)
•  » » » 6 years ago, # ^ |   0 Answer is yes right?
•  » » » 6 years ago, # ^ |   0 what should the answer be ???
•  » » » » 6 years ago, # ^ |   0 No
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 I hacked a solution using this test case 4 4 .... .X.X .X.X .XXX The answer should be NO
 » 6 years ago, # |   +6 Statement for DIV2 B could have been better.
 » 6 years ago, # | ← Rev. 2 →   +1 How to solve Div 1 B / Div 2 D? I kept dividing intervals in n/2 and asking for 2 questions each. For n = 1000, it asked 21 questions somehow :\Edit: it seems the approach was correct as in editorial. However the last question was redundant and trying to find values on the main diagnol only
•  » » 6 years ago, # ^ |   0 Please explain your solution.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +5 Suppose you want answer on a table NxN. Then lets query n/2 numbers twice, the first query questions indices 0, 1...n / 2 - 1, and the second query questions indices n / 2...n - 1. Graphically, this means you know all information for the bottomleft and topright of the current table(verify this with a picture). Now recurse on the topleft and botright, notice that they still have the diagonal with 0's.I think this is what he meant.
•  » » » » 6 years ago, # ^ |   0 I don't see why this is right. I thought the same thing. Obviously, binary division was involved, given the constraints, but I couldn't prove it's correctness.
•  » » » » » 6 years ago, # ^ |   +2 Yes exactly, this was what i was doing. For the topleft and bottomright, part you can divide them into 2 new sub matrix and solve for them too. However direct implementation of this will lead to no of steps as f(x) = 2 + 2*f(x/2). However each of the queries on the leftside and rightside are disjoint and one could merge it into a single query too. That would make f(x) = 2 + f(x/2)As for why its right, it is effectively searching all the matrix values
•  » » » » » » 6 years ago, # ^ |   0 Your implementation sounds exactly like what I tried as well, unfortunately it seems I had a flaw in implementation.
•  » » » » » » 6 years ago, # ^ |   0 I finally understand :) So, its 2*log(n) .
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +3 for each bit i, do 2 query, one for all the index whose ith bit is 0, one for all the index whose ith bit is 1.now for row k, we only check the reply which desn't contain M[k][k], that is, those query that checks ith bit different from k's ith bit. UPDATE: M[i][i]->M[k][k]
•  » » 6 years ago, # ^ |   +4 My approach was, first I split all N numbers in two queries by taking groups of 1:1 3 5 7 9... and 2 4 6 8 10...then I take groups of 2:1 2 5 6 9 10... and 3 4 7 8 11 12...then take groups of 4:1 2 3 4 9 10 11 12... and 5 6 7 8 13 14 15 16...and so on.With this queries you can test every element in the matrix, and get the minimums.
 » 6 years ago, # |   +9 Problem B pretest cases were extremely weak, I couldn't believe some of the passed solutions that I hacked. rankings in Div.2 are more influenced by number of guys with bad solution in your room than time penalty. I think pretests should be stronger, so hacking would be more challenging.
•  » » 6 years ago, # ^ |   0 I agree, one of the people I hacked just checked whether there exists a rectangle that has the area equal to the number of X's. No idea how that passed pretests.
•  » » » 6 years ago, # ^ |   0 I did the same, but I also checked that the number of X inside the rectangle is same as the area of rectangle.
•  » » 6 years ago, # ^ |   0 Agree, I hacked 8 submits with easy hacks like 3 3 ... XXX X.. 
 » 6 years ago, # |   +1 My first ever hack!
 » 6 years ago, # |   +32 Pretests passed in Div1-A by reading edges first then capitals — such strong pretests :( — http://codeforces.com/contest/744/submission/23053839
•  » » 6 years ago, # ^ |   0 riadwaw had the same problem :(
•  » » » 6 years ago, # ^ |   +5 I took revenge from the guy who hacked him and me: http://codeforces.com/contest/744/room/12 :D
•  » » » 6 years ago, # ^ |   +13 To be honest that was not the only my problem in A
•  » » 6 years ago, # ^ |   +16 Really sorry about this. This is definitely not intentional. I think the way to fix this would be to make sure to include more pretests in general (for this problem, we only had 7, which in hindsight is really small).
 » 6 years ago, # |   +1 Div 2B question should have had a clear statement."The puzzle pieces are very heavy, so Hongcow cannot rotate or flip the puzzle pieces. However, he is allowed to move them in any directions." is very confusing. I thought that the pieces could be moved independently of each other and only understood why my answer was wrong in the last 10 minutes.When the initial statement read "It is guaranteed that the puzzle pieces are one 4-connected piece", I thought that only referred to the input and not that the pieces had to remain connected throughout. Nice questions in Div 2 otherwise.
•  » » 6 years ago, # ^ |   0 Yeah I thought the same. It could've been a really nice problem if it wasn't for the unclear statement.
 » 6 years ago, # |   -8 I hacked 3 C solutions where their logic was as follows:ans=n-k+1;ans=(ans*(ans-1))/2;ans=ans-m;If any of you did this, it is wrong.Counter test case:6 2 21 31 23 4Correct answer is 5.
•  » » 6 years ago, # ^ |   0 LOL, this solution is really retarded. The pretests are really weak if it worked.
 » 6 years ago, # |   +5 Div2 B is the worst problem I have ever seen in CF
•  » » 6 years ago, # ^ |   +60 I'm sorry you feel that way :( I tried to balance a short statement versus a clear statement. It seemed it was too short on details.
•  » » » 6 years ago, # ^ |   +4 Thanks for your effort though! It was a good problem I think just very unclear (at least for me).
•  » » » 6 years ago, # ^ |   +3 It's alright, you tried your best. Other problems were very good. Just that this problems statement should've been a bit more clear :)
•  » » » 6 years ago, # ^ |   +3 Other problems were great...thank you very much for your effort..
•  » » » 6 years ago, # ^ |   0 I was sad too. But then I had a bhangra session to enjoy life.
 » 6 years ago, # |   0 DIV2 E test3?
 » 6 years ago, # |   +8 That moment when you discover your bug 30 seconds after the contest ends T_T.
 » 6 years ago, # |   0 can someone figure out why my code is giving Idleness limit exceeded on pretest 2 even though I am flushing many many times?(bug is probably in n<3 part since pretest 2 has n=2)http://codeforces.com/contest/744/submission/23071215I have tried finding the error for the past hour and have used 8 incorrect submissions on this problem :|
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 disclaimer: i am CPPershouldn't it be like this? (corrected n < 3 part)
 » 6 years ago, # |   0 I first submitted a correct submission on div2B and then got confused, changed the code so that it outputs wrong on some cases, and submitted it! :(
•  » » 6 years ago, # ^ |   +3 Similar thing happened to me, but I noticed in time and changed it back. Still lost 10 minutes :C
 » 6 years ago, # |   +16 I found 2 submissions with the same implemention http://codeforces.com/contest/745/submission/23067444 http://codeforces.com/contest/745/submission/23067030I just read the first one and i didt understand why he used big integer with this problem, but i think the cheating detector will find it soon :)) (hope so!!)
•  » » 6 years ago, # ^ |   +11 getting 3rd place with a stolen code, seems legit
 » 6 years ago, # | ← Rev. 2 →   +10 I have taken almost 20 minutes to understand the problem B in div2 :(
•  » » 6 years ago, # ^ |   0 Same here, the funny is I submit a solution without understanding the problem and got pretest passed !!
 » 6 years ago, # |   +5 I should practice more hard
 » 6 years ago, # |   0 So what's the right solution for B? Check whether it's a rectangle? Or what? Even C is easier than this.
•  » » 6 years ago, # ^ |   0 Yeah, I can't say with confidence that I know, even though I passed pretests... I just made sure the input was a rectangle, since you can always combine two rects to make another rect.
•  » » » 6 years ago, # ^ |   0 Then why there seems to be such a confusion about this problem? This was the most obvious thing to implement.
•  » » » » 6 years ago, # ^ |   0 Yeah, I guess a lot of people have confusion about what a 'piece' is. Many believe you can shift individual 'X' characters in any fashion you like, where the problem statement says that 'X' characters come together to form one connected piece which must be shifted as a whole. Many people don't quite understand the intent of the question, so hopefully we are not one of those people.
•  » » » 6 years ago, # ^ |   0 But didnt they say that you could move pieces in any direction?So technically even if the input is not a rectangle, it may form one on rearrangement.Did I miss understand?
•  » » » » 6 years ago, # ^ |   0 By puzzle pieces, they mean the big given grid, and not individual X's
•  » » » » » 6 years ago, # ^ |   +4 Oh my god....So basically you have to paste one grid on top of another and the resulting 'X's should be a rectangle(with no overlaps)?
•  » » » » » » 6 years ago, # ^ |   0 I hope so, because that's what I did. :)
•  » » » » » » 6 years ago, # ^ |   +4 You comment should be part of the problem statement ;)
•  » » 6 years ago, # ^ |   0 Yes, it has to be a rectangle. There's no other way.
•  » » 6 years ago, # ^ |   0 considering the problem conditions , main problem will be this : check if in the input exist only 1 rectangle or not ? if there exist exactly 1 rectangle without any 'X' more print "YES" otherwise print "NO"
 » 6 years ago, # |   0 is it even necessary to have govt nodes Number in Div 2 C ? if i iterate over all nodes to do the dfs anyway ?
•  » » 6 years ago, # ^ |   0 Of course they are needed, you can't put edges between vertices that are connected to some capitals. The example contains such a test.
•  » » » 6 years ago, # ^ |   -8 shit i am f*cked.
 » 6 years ago, # |   +10 Both problem statement & pretest cases of problem B were really very weak.
 » 6 years ago, # |   +25 That weird moment when you get pretest passed without understanding the problem at all and pray to get hacked before it's to late :P
•  » » 6 years ago, # ^ |   0 And when it get hacked...you start to read and understand the question again :(
•  » » 6 years ago, # ^ |   +7 That weirder moment if you get accepted instead without understanding the problem
 » 6 years ago, # |   0 This contest was nice but the pretest for Div 2 B sucked...like they weren't just bad they were the worst...my friend solved an entirly different problem and got pretest passed...but other than that it was great.:)
 » 6 years ago, # |   -9
 » 6 years ago, # |   0 in the problem B DIV2 it says in the statement " The puzzle pieces are very heavy, so Hongcow cannot rotate or flip the puzzle pieces. However, he is allowed to move them in any directions. The puzzle pieces also cannot overlap."and now you say i can't move peaces how is that ?
•  » » 6 years ago, # ^ |   0 Well...you actually can. But you'll get a rectangle only when the pieces are initially rectangles. I don't understand the confusion about this problem.
•  » » » 6 years ago, # ^ |   0 .XXXX.this is not a rectangle but if i moved each peace in the first row one step it will be rectangle
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 I don't understand you, how can you get a rectangle from to pieces that look like this?
•  » » » » 6 years ago, # ^ |   0 XX.XX. this one peace if i have two peaces it will be like this XXXX.. XXXX..
•  » » » » 6 years ago, # ^ |   0 there are two copies.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +1 The confusion is whether they meant the board as a whole is a 'piece' or do they mean the 'X's as the pieces?If we consider the latter, then the input does not have to be a rectangle originally.
 » 6 years ago, # |   0 Div2/B is just horrible, nice Div2/C BTW I got pretest passed in the last minute.
 » 6 years ago, # |   +50 Why Codeforces nowdays testing user's ability to understand problem statement???
•  » » 6 years ago, # ^ |   -29 Why not? ;)
•  » » » 6 years ago, # ^ |   +22 Because it's not an English language testing platform -_-
•  » » » » 6 years ago, # ^ |   0 Why did this guy _index solved the problem A in 2 minutes and problem B in 6 minutes?
•  » » » » » 6 years ago, # ^ |   +4 He said he read the statements in Russian where they were clearer (according to him).
•  » » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Ok, TheMaverick is definitely not russian (and has a badass toxedo) :)He solved B in 9 minutes. theodor.moroianu is from Romania and he solved B in 4 minutes!
•  » » » » » » » 6 years ago, # ^ | ← Rev. 2 →   +3 What are you trying to prove here saying "He" solved B in "T" minutes?
•  » » » » » » » » 6 years ago, # ^ |   +6 Do I really need to clarify?
•  » » » » » » » » » 6 years ago, # ^ |   +4 Did you see how many people failed in the system test in problem B?I don't think there is any corner case in this problem.So do you want us to believe that they all got the statement right and coded wrong?Seriously?
•  » » » » » » » » » 6 years ago, # ^ |   +22 "you want us to believe that they all got the statement right and coded wrong?"No, I wanted to say that 1240 people understood the problem and coded it correctly. And I wanted to say that for the people with enough experience B wasn't a problem at all. Understanding the problem correctly (however unclear it is) is, I believe, a part of the problem solving skills. If tourist or Petr participated in Div2, they would have solved A and B in no time =)
 » 6 years ago, # |   0 Div2 B, they said "It is guaranteed that the puzzle pieces are one 4-connected piece." and didn't accept rotate, flip and overlap. ==> only move. Because there are two copies of puzzle, only rectangular input is accepted. no stairs shaped, window shaped...
 » 6 years ago, # | ← Rev. 3 →   +9 Problem statements were really confusing -_-
 » 6 years ago, # |   +7 Problems were fine, statements were trash
•  » » 6 years ago, # ^ |   0 hahaha
 » 6 years ago, # |   0 Lets see how many solutions of B pass system test.As I understand now, the code I wrote is COMPLETELY wrong.Yet,it still passed pretests and a hack too...
 » 6 years ago, # |   -15 In Div2, Only a few could solve D or E. The gamechanger question was B whose problem statement was horrible. People have submitted considering individual "X"s can be moved. This round should be made unrated for Div2 as B has clearly caused complete turbulence.
•  » » 6 years ago, # ^ | ← Rev. 3 →   +6 I never saw weak pretests being reason for unrated contest.
•  » » » 6 years ago, # ^ |   -10 Weak pretests + confusing statements + D,E were very hard.
•  » » » » 6 years ago, # ^ |   +4 The only times I've seen contests be unrated are when the queue is bad. I think there was one contest where the judge solution for Div 2. D was actually wrong and they just removed the problem instead of making it unrated. So today will probably be rated.
•  » » 6 years ago, # ^ |   +1 Then how come some people understood the statement correctly? Have you ever played jigsaw puzzle? The question clearly stated two puzzle pieces. It should've occurred to you that 'X' != puzzle piece when you saw the first sample case.
•  » » 6 years ago, # ^ |   0 When people go undercover to make the contest unrated. The contest can not be unrated just because of a problem statement.Also many were not able to give time to D because they were stuck in B.
 » 6 years ago, # |   +19 I really liked Div1 B!
 » 6 years ago, # |   0 Problem B not passed — nooooooo! So it's actually wrong to output yes when the piece is a rectangle.
•  » » 6 years ago, # ^ |   0 Not true, mine passed. Probably a bug in implementation.
•  » » » 6 years ago, # ^ |   +3 Wow, that's even worse. The pretests are so weak.
 » 6 years ago, # |   0 I have a question. I wonder how people can solve Div2 B, though they are confused about it... Is it a gap between me and high ranks?
•  » » 6 years ago, # ^ |   +1 I'm definitely not a "high rank" but because of weak pretests, it's possible to "solve" the problem without actually understanding it. For parts that were unclear for me, I assumed parts of the problem that were actually incorrect but worked with the sample cases. And with passed pretests, it made me think it was actually correct (when it wasn't at all).
•  » » » 6 years ago, # ^ |   0 I agree with you. I had the same experience before.
 » 6 years ago, # |   -42 Is it rated ? :p
•  » » 6 years ago, # ^ |   0 downvotes coming .. Hell yeah 'B' is worst ever B of mine on CF. -_-
•  » » 6 years ago, # ^ |   +20 Before the contest : ** ** *****? After the contest : ** ** *****? xD
 » 6 years ago, # |   0 The pretests for Problem B DIV2 is very weal i got pretest passed and i don't know even what is the problem is .. and Now i got Wrong answer and i still don't know the problem .? could someone explain what the problem ?
•  » » 6 years ago, # ^ |   0 find out if the surface covered with 'X' forms a rectangle
•  » » » 6 years ago, # ^ |   0 It would've been Problem A with an understandable statement but they made the statement so confusing so that it would have the difficulty of a B problem..
•  » » » 6 years ago, # ^ |   0 3 3X.X XX. .XXi understand that we can make rectangle with this by shifting?
•  » » » » 6 years ago, # ^ |   +3 You're not allowed to shift 'X' You can only move left, right, up or down the whole matrix (the whole piece)You have to get a rectangle by appending two identical pieces. You can get that only if you have a rectangle in the given piece.
•  » » » » » 6 years ago, # ^ |   0 oh man thank you very much =D . i see it's easy now
•  » » » » » » 6 years ago, # ^ |   +3 You're welcome :)
 » 6 years ago, # |   +24 welp, this was unexpected
 » 6 years ago, # |   0 I take 'he is allowed to move them in any directions' as 'he is allowed to move X in any directions' in the statement of problem B. Actually i was solving a different problem and i got pretest passed.
 » 6 years ago, # |   0 Waiting for rating
 » 6 years ago, # |   +3 The statement for problem B (division 2) was very poor!
 » 6 years ago, # |   +1 whatever....what about ratings???
•  » » 6 years ago, # ^ |   +5 Div1 is still undergoing system testing.
 » 6 years ago, # |   0 system pending wasnt faster before ? :-"
 » 6 years ago, # |   +18 Let's hope rating will be updated in 25 minutes, otherwise there will be few lucky div1 participants who can participate officially in tomorrow's round. ;)
 » 6 years ago, # |   0 When can i up-solve problems? cant submit any solution now! there is no option ! if i click on 'submit code' tab, its shows 'contest is over'!
•  » » 6 years ago, # ^ |   +2 You have to wait until system testing is over and ratings get updated, then the problems will be available for practice.
 » 6 years ago, # |   +156
 » 6 years ago, # |   +4 Div.1A, test 15. Are you sure that given graph is stable?
•  » » 6 years ago, # ^ |   +24 You are reading capitals after the edges, but they are given before them.
•  » » » 6 years ago, # ^ |   0 Thanks!
•  » » 6 years ago, # ^ |   +23 Surprising part is that it passed 14 tests..
•  » » 6 years ago, # ^ |   +5 You should read capitals first, then edges, not vice versa.
 » 6 years ago, # |   0 Goodbye Expert...
 » 6 years ago, # |   0 Where is the new rating?
•  » » 6 years ago, # ^ |   0 div1 updated Div2 on queue
 » 6 years ago, # | ← Rev. 24 →   +8 C approach:let k be the number of governmentsMake k sub-graphs such that each of them contains one government node (k strongly connected components), so vi nodes with government.Note that there will be, let say p nodes in anarchy (no government) with pe edges between them. We will attach those nodes to some of the k sub-graphs and generate the maximum number of possible edges. (No node can be attached to two different sub-graphs)Let g1 be the edges generated by Two nodes with government Let g2 be the edges generated by Two nodes without government Let g3 be the edges generated by Nodes with government Nodes without government We agree g1 has a fixed amount, thus no decision with the anarchy nodes will influence its value.Then we need to see that g2 ≤ p * (p - 1) / 2 - pe. We can't have more edges between p nodes than the possible pairs of them. Any solution with g2 = p * (p - 1) / 2 - pe has an optimal value of g2. Any solution that set the p vertex in the same group has an optimal value of g2 (1)Note that adding one anarchy node to a group with government generate vi edges of type g3. (denote vi the original amount of nodes per group). If j is the sub-graph with more nodes then vi ≤ vj with any sub-graph i where ci is the amount of anarchy nodes that go to the sub-graph iAs ci * vi ≤ ci * vj this means adding all anarchy nodes to the group j implies an optimal g3 value, cause equality is obtained. But if we do so then all anarchy nodes will be in the same group, because of (1) g2 is optimal As g2 is optimal, g3 is optimal, and g1 is fixed, adding all vertex to greater group is the optimal solution.After doing so we count the amount of nodes and edges per group and solution will be where ei is the amount of edges that already exist per group Total complexity: O(n)
•  » » 6 years ago, # ^ |   +14 Tutorial on C — The simple made tough
•  » » » 6 years ago, # ^ |   +5 it's a simple problem and you can figure out the solution intuitively. This is not the solution, but the proof of it.
 » 6 years ago, # |   +6 Start the upsolving, please
 » 6 years ago, # |   +2 When can we submit for problems??
 » 6 years ago, # |   0 Well, just 1 far from expert :( Look at my graph
•  » » 6 years ago, # ^ |   0 Sleep well and tomorrow you'll have a chance to get blue :)
 » 6 years ago, # | ← Rev. 2 →   +1 I think something is wrong here one code with 2 different verdict (hack, accept) 23067626 , 23072618
 » 6 years ago, # |   +20 I think there is a problem on codeforces , i can't do anything on the site look here
•  » » 6 years ago, # ^ |   +17 I've been having such a problem for a couple of hours, though :/
•  » » 6 years ago, # ^ |   0 Me too. I can't see my own submissions, which is quite annoying.
 » 6 years ago, # |   0 is there any tutorial on C Div.2 ? i tried to solve it but i can't find out what's the problem :( i think the solution might be DFS , but i feel like i'm missing something ...
 » 6 years ago, # |   +3 When I go to any of the problems a message says "No such problem"and all my solutions in this contest disappearedand my graph is updated and the rating still the same ,does anyone have the same problem ?
•  » » 6 years ago, # ^ |   0 it seems like everyone is having this problem, idk why, the rating is still the same but the color doesn't change though.
•  » » » 6 years ago, # ^ |   0 I just fixed it , you have to change your ip address (by restarting your router or whatever)
 » 6 years ago, # |   +1 Anyone know what testcase 15 on Div1A/Div2C contains? I'm failing on it.
•  » » 6 years ago, # ^ |   0 Try this case; if you count this edge ?
•  » » » 6 years ago, # ^ |   0 It seems that your program can solve this case.Then i have no ideal what's wrong with your program.
•  » » 6 years ago, # ^ |   0 Even I am failing on that test case. The test case is large enough ! So no gain.
•  » » 6 years ago, # ^ |   0 You need to make all components cliques.Say capitals are 1 and 4. n m k 9 8 2 1 4 1 2 1 3 2 3 4 5 4 6 5 6 7 8 7 9  (1) - 2 (4) - 5 7 - 8 \ / \ / \ 3 6 9 you have to make an edge 8 - 9 and connect that component to any other, adding 3 * 3 = 9 edges, so total is 10 edges.
•  » » » 6 years ago, # ^ |   0 Damn, my code already passes your test case :( Still not sure why it's failing 15 because I can't see the whole input.
•  » » » » 6 years ago, # ^ |   0 did you completed linking the other governments, check this
 » 6 years ago, # |   0 I can't see test cases :(
 » 6 years ago, # |   0 Can someone please help me with Div2 C problem? I made disjoint sets of all the capital cities and the nodes connected to them directly or indirectly. Then I calculated the number of nodes who aren't connected to any of the capitals,I did this by calculating the sum of sizes of various disjoint sets and subtracting it from n. Then for every capital city I added (size*(size-1))/2 to my final answer.Finally I gave the output as this sum-m , the no of edges. My submission is http://codeforces.com/contest/745/submission/23076645 . Thanks in advance !
•  » » 6 years ago, # ^ |   0 Here's my approach. First of all, if you have make disjoint sets in such way, make each of those disjoint sets a complete subgraph (let's say the set contains x nodes, so the number of edges we can add to make it a complete subgraph with x nodes is x*(x-1)/2 — e where e is number of default edges on that sets).Then after we make each disjoint sets a complete graph, we search every disjoint sets who doesn't have a capital city (special node) as their member and do the following process : - since we want to add as many edges as possible, find the best disjoint set that have capital city as its member (e.g. the disjoint set who has the maximum number of nodes as its member) - add our variable answer with sum[x]*sum[y] (**_sum[x]_** is how many vertex in disjoint set x)
 » 6 years ago, # |   +60 Back to CF after 1.5 years...Looks like I have not completely forget all about algorithims :)
•  » » 6 years ago, # ^ |   +4 Now you can probably stop saying you were carried by team members. xDThey don't let you solve :P
 » 6 years ago, # |   0 Is it just me or rating is not updated yet?
 » 6 years ago, # |   0 Tough solutions of problem B(Div2) passed the main test , i tested some codes and they(main test passed solutions) gave different answers :( my test case 3 3 ... .X. ..X