Kniaz's blog

By Kniaz, history, 6 years ago, translation,

Hello!

Next Codeforces round #378 for participants from the second division will take place on October 31, 2016 at 17:05 MSK(Moscow time). Traditionally, participants from the first division are able to participate out of the contest.

This round will be unusual:participants will be given six problems and two and a half hours to solve these problems. Pay attention to the unusual time of the beginning of a round!

I want to thank Nikolay Kalinin (KAN) for help with preparation of this round, Tatiana Semenova (Tatiana_S) for translation of statements and Mike Mirzayanov (MikeMirzayanov) for great Codeforces and Polygon systems and also for the help in preparation of a contest and the ideas for several tasks.

It is my first round and I hope you will appreciate it.

The scoring is 500-1000-2000-2000-2750-3000.

Congrats to the winners!

Div. 2

Div. 1

Editorial

• +251

 » 6 years ago, # |   +40 So, Delinur is back as a translator at Codeforces :D
•  » » 6 years ago, # ^ |   +174 OK, yesterday in the announcement it was mentioned that Delinur translated the problems, today it is written that Tatiana_S did the translation, I want my up-votes back, it's not my mistake :(
•  » » » 6 years ago, # ^ |   -15 XD
 » 6 years ago, # |   -15 I hope your first round will be a great round.Good luck
 » 6 years ago, # |   +8 Unusual rounds.. unusual rounds everywhere
 » 6 years ago, # |   -56 I'm sure It'll be a very beautiful round <3 _ <3
•  » » 6 years ago, # ^ |   -85 how you are sure? have you got the question paper in advance?
•  » » 6 years ago, # ^ |   -10 Solved A,B,C,D :3 Told you it's a beautiful round :D :D although i was late a bit :3
•  » » » 6 years ago, # ^ |   0 same room :)
 » 6 years ago, # |   +9 I hope you make next contests on sundays, since most people can't participate on mondays.
•  » » 6 years ago, # ^ |   -28 I wonder if anyone is going to get raided by treat or trick while competing.Anyways, Sunday round should be much more better, and I am pretty sure that many people are going to hang out on Hallo... Wait...
•  » » 6 years ago, # ^ |   0 I agree, Sunday is the safest option.
 » 6 years ago, # |   -25 Hope we will find new charm from new problem setter :) Waiting for it eagerly :)
 » 6 years ago, # | ← Rev. 2 →   +29 I was hoping for special Halloween round, but it seems in vain
 » 6 years ago, # |   +9 I like six-problem rounds, my top 3 best rounds are all six-problem rounds :D
 » 6 years ago, # |   -21 If it's unusual time contest , then it should be unusual rate for all ,, i wanna +200 for this contest and i'll be happy :)
 » 6 years ago, # |   -14 A bad time for the Chinese...QAQQQ However, happy Halloween!
•  » » 6 years ago, # ^ |   +6 I believe it's much better than the usual time for the Chinese:)
•  » » » 6 years ago, # ^ |   0 oh, bl!
 » 6 years ago, # |   0 Can't play 'trick or treat' on the Halloween EVE.. So sad! :(
•  » » 6 years ago, # ^ |   +20 Only treat you will get is negative change
 » 6 years ago, # |   -6 i hope it will be a beautiful round
 » 6 years ago, # |   -23 I hope problem difficulties are gradual.
 » 6 years ago, # | ← Rev. 2 →   +13 I am interested about your handle. Can somebody pronounce it to me? I have not seen this type of names earlier. Finally, Happy Halloween contest to all! Hope to see some scary hard easy problems :D
 » 6 years ago, # |   -83 Damn!!where is the CF rounds for div1 onlyabout 40 days since last div1 round
•  » » 6 years ago, # ^ |   +43 Canada cup was for DIV.1 and DIV.2.
•  » » » 6 years ago, # ^ |   +18 Which part of "div1 only" you didn't understand :\
 » 6 years ago, # |   +14 Finally a regular codeforces round after two weeks. Thanks Kniaz for preparing this round. Hopefully everything will be fine :D
 » 6 years ago, # |   +10 but i dont think it unusual .. because the current three contests are similarly : six problems with two and a half hours .. but i hope i can do better than my previous contests..
•  » » 6 years ago, # ^ |   0 the gold shang, you must comeback now and open the Codeblocks, otherwise you maybe miss the contest.
 » 6 years ago, # |   +6 Good Luck!
 » 6 years ago, # | ← Rev. 2 →   -21 Thanks for this contest!
 » 6 years ago, # |   +8 Does Codeforces plan to change its format (or it has already changed it)? All recent contests have 6 problems and 2.5 hours.
•  » » 6 years ago, # ^ |   +3 I think it is just a coincidence that recently the problemsetters have sets of 6 problems :)
•  » » » 6 years ago, # ^ |   +6 Possible, but with this one it's 5 Div2 rounds in a row (counting Technocup too) with 6 problems.
•  » » » » 6 years ago, # ^ |   +5 Technocup 2017 — Elimination Round 2 after three weeks is just two hours length...
 » 6 years ago, # |   +6 Thank this unusual time i can go to sleep early
 » 6 years ago, # |   +6 Score distribution ?
•  » » 6 years ago, # ^ |   +3 updated
 » 6 years ago, # |   0 In Problem A the statement says that the grasshopper can jump on vowels of English alphabet, yet the image and the paragraph below the image feature letter Y among as a vowel. AFAIK, Y is not a vowel, but a consonant.
•  » » 6 years ago, # ^ |   0 I am not sure if this incorrect translation can be remedied at this point, but please consider any possible steps you may take in order to prevent quite a few people like myself being victims to errors in translation. (there are 4 people in my room who considered the phrase "English vowels" to only mean 'A', 'E', 'I', 'O', 'U')
•  » » » 6 years ago, # ^ |   -10 Did the pretests not cover Y being a vowel? Were you able to hack them?
•  » » » » 6 years ago, # ^ |   +1 Yes. Pretests were not having Y. I hacked one such solution.
•  » » » » » 6 years ago, # ^ |   +1 Yeah, I hacked 3.
•  » » » » » » 6 years ago, # ^ |   -10 I just realised you can continue hacking the same person's solution as long as they're uploading new submissions :(
•  » » » » » 6 years ago, # ^ |   0 I was hacked because of 'Y'...
•  » » » » » » 6 years ago, # ^ |   0 Me too
•  » » » 6 years ago, # ^ |   +5 It said "The following letters are vowels: 'A', 'E', 'I', 'O', 'U' and 'Y'." right below the picture in Problem A. In this https://simple.wikipedia.org/wiki/Vowel wikipedia page it says that vowels can be: "A, E, I, O, U, and sometimes Y".
•  » » » » 6 years ago, # ^ |   0 Actually, wikipedia is unreliable source of information. That's why do not believe wikipedia (-_-)
•  » » 6 years ago, # ^ |   +21 As it's explicitly written in the statement which characters are vowels as you said, there's no point of arguing about it, everyone should follow the statement in order to solve the problem. Also https://en.oxforddictionaries.com/explore/is-the-letter-y-a-vowel-or-a-consonant.
 » 6 years ago, # |   +72
•  » » 6 years ago, # ^ |   +7 Dang, I knew I'd seen a similar problem before! I guess that's why you should always upsolve...
•  » » » 6 years ago, # ^ |   0 Which problem above link refers to in todays contest?
•  » » » » 6 years ago, # ^ |   0 F.
 » 6 years ago, # |   0 How to solve C?
•  » » 6 years ago, # ^ |   0 I use greedy and prefix sums!
•  » » » 6 years ago, # ^ |   +12 I divided A into contiguous blocks mapped to each index of B, such that sum of the block is equal to element at that index in B. Then picked the largest element in the block such that at least left or right of it has a smaller value and then made this monster eat all monsters to its left followed by all monsters to its right, or vice versa depending on which side has a smaller value than the largest element.
•  » » » » 6 years ago, # ^ |   0 I think exactly the same thing that you, sadly I didn't code it well. Still looking for my error :( However good to know that my idea wasn't in the wrong path
•  » » » » 6 years ago, # ^ |   0 ACCEPTED ?
•  » » » » » 6 years ago, # ^ |   0 Actually, I didn't finish it in time during contest. I submitted in practice, and I was printing it wrong. Logic is correct though.
•  » » » » » » 6 years ago, # ^ |   0 Yes your logic is correct.I implemented the same logic during the contest.
•  » » 6 years ago, # ^ |   0 You should choose m segments such that i-th segments sum is equal to b[i].
•  » » 6 years ago, # ^ |   0 Consider first element of ending array. It must be formed by first elements of original array (else where does first monster go?). So it suffices to solve the problem in the case of ending state a single monster (then apply this to each range by precalculating partial sums). This can be done by identifying a monster of maximum size that is bigger than at least one of its neighbors (if none exists, then solution does not exist), and having it eat everything.
•  » » 6 years ago, # ^ |   +7 Notice that you can only convert the initial array into arrays which contain elements which are contiguous sums of elements of the first array. Now, in order to generate the procedure, all you have to do is in every subsequence, find the largest element and go left and right to consume all the others (as it will only become larger, it will not create problems). You also have to take care of cases when the largest cannot go either left or right.
 » 6 years ago, # |   0 PLease tell me how to solve C and D!! I only solved A and B I tried to solve D in O(n^2) bruteforce but it got tle of course....
•  » » 6 years ago, # ^ |   0 D is enough to maintain hash of (pairs -> list of third dimension) for all 3 possible pairs (first sort the dimensions for each brick).
•  » » » 6 years ago, # ^ |   +1 Why hash, you need no hash, sort the array and check neighour bricks.
•  » » » » 6 years ago, # ^ |   +1 Of course other solutions may exist. Hashing is simply the most natural one.
•  » » 6 years ago, # ^ | ← Rev. 3 →   +4 DImagine the shape described by the problem. It becomes obvious that the sphere is limited by the edge that has minimum length. You have block A that you are considering. To use A and B (another block) the value of some area must be the same (both in size of the area and shape). But there's something more: if you put A and B together, you are basically increasing the length of the edge that you didn't use to get the area. So this length that you are increasing needs to be the minimum length of block A and B, otherwise some length you used on the common intersection is already limiting the volume of the sphere and you already have the maximum volume you could get using this union. The max volume in this case will be limited by the minimum between the sum of the edges that A and B aren't using and the minimum edge of the intersecting area (because if the sum is greater than this, now this is the limiting factor of the volume of the sphere).Now, to get the answer from this you have a vector of (max_area, minimum side of area, side not used in area) and sort it. The blocks that you can glue together are next to each other, so you can easily consider all the unions.edit: now that I think about it, you just need the dimensions sorted and check if the 2 maximum sides match, but the thinking process is the same.
•  » » 6 years ago, # ^ |   +8 For problem D: Basic observation is that if you have parallelepiped (lol I copyed it from statement :D) of size a * b * c, then the radius of the inner sphere is min(a, b, c) / 2. Also you can glue two parallelepipeds together only and only if they have two common edges of the same length. After that you should use a data structure like std::map, pair>. In this DS you keep the maximum possible 3rd edge length for given a and b edge lengths, after filling this DS you can use a simple loop to get the answer. Complexity is
•  » » » 6 years ago, # ^ |   0 This is what I did. Failed the system tests. Must have missed something. Did it work out for you?
•  » » » » 6 years ago, # ^ |   0 Failed test case 15.
•  » » » » 6 years ago, # ^ |   0 Did you check if any element in the pair which acts as key for the map is less than the glued dimension's measure?
•  » » » 6 years ago, # ^ |   0 Pretty much exactly what I did, but got TLE on Test case 32 :(
 » 6 years ago, # |   0 how to calculate max volume for k=1 in D
•  » » 6 years ago, # ^ |   -10 For a rectangular parallelepiped of dimensions a×b×c, the radius of the inscribed sphere is min(a, b, c) / 2.
 » 6 years ago, # |   +9 How to solve problem E? Any small hints?
•  » » 6 years ago, # ^ |   +1 The jumping root is regular, consider current step is right, so we jump right until reaching the first left step(now all the steps we have visited is left), then we jump left until reaching the first right(now all the steps we have visited is right), and so on until jump out, the answer has two parts, here consider the left part(distance we go at left side of current step), (curIndex — leftIndex1) + (curIndex — leftIndex2) + ...= totLeftNum*curIndex — (leftIndex1 + leftIndex2 + ...) To calculate the answer in O(nlog(n)), precalculate several arrays, lcntUp(number of up steps from left), lsumUp(the sum of every up index from left) and rcntDown, rSumDown. for every step there are 4 cases. Sorry for my poor English.
•  » » » 6 years ago, # ^ |   0 I used the same approach and I just wanted to add that the answer can also be calculated in O(n).My code
•  » » » » 6 years ago, # ^ |   +10 Is this you? link
•  » » » » » 6 years ago, # ^ |   +1 Yes, that would be me :)
•  » » » » » » 6 years ago, # ^ |   0 Well that's interesting!
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Consider position i. Let char be 'U' there. The movement will be oscillatory. You will move to first 'D' above i, then to first 'U' below i, then to second 'D' above i, then to second 'U' below i and so on. I advise just running through an example on paper to see this. So, if you know the count of Us below and Ds above, you get to know whether you will exit from top or bottom. Then just calculate the total distance travelled. The case for when str[i] = 'D' is analogous. So each i can be dealt with in O(1). :)Code
 » 6 years ago, # | ← Rev. 2 →   +2 Tried to hack this solution for Problem B with the following test case. No initialization done whatsoever in the code. Still no hack :(
•  » » 6 years ago, # ^ |   +10 The variables are global, so initialized to 0
 » 6 years ago, # | ← Rev. 2 →   0 Typed if (t&(1>>k)) instead of if (t&(1<
•  » » 6 years ago, # ^ |   +19 WOW , how could that pass the pretests ? it should completely change the answer
•  » » » 6 years ago, # ^ |   +5 He didn't pass the pretests. He meant that fixing the line helped him get AC verdict.
 » 6 years ago, # |   +2 Solved D but Just fell short of 2 minutes from submitting C.Need to boost my speed.
 » 6 years ago, # |   -6 only two minutes before the end of the round I realized that o(n^2) solution can pass the pretest for problem D I could have hacked a lot of participants BTW, problem C is sucks
•  » » 6 years ago, # ^ |   +1 However my O(n^2) solution submitted and the result is TLE in pretest 7.
•  » » » 6 years ago, # ^ |   0 Yeah, my O(n^2) solution also failed on pretest 7. Managed to get it to O(N*log N) but it took another 20 minutes to complete it.
•  » » » » 6 years ago, # ^ |   0 Yeah, I use std::sort for 3 times but also failed on pretest 7 (Wrong Answer).........
•  » » 6 years ago, # ^ |   0 However, my O(n^2) solution submitted and the result is TLE in pretest 7.
 » 6 years ago, # |   0 To include Hacks like in problem A IMO should be controversial.Well I don't know but hacks do change the contest for me so in my selfish opinion hacks should test algorithmic incorrectness . Any other views?
•  » » 6 years ago, # ^ |   0 yup,i agree with u.
•  » » 6 years ago, # ^ |   0 I agree. It is more of a problem of one's familiarity with English language.
•  » » » 6 years ago, # ^ |   +51 Why would you say that? The statement isn't clear or what? It clearly says which letters are considered to be vowels.
•  » » » 6 years ago, # ^ |   +19 so you have read "and" as "not" ?
•  » » 6 years ago, # ^ |   +4 I think that on the one hand, the current hacking system is not fair. According to who is in your room, you may hack between 0 and n >> 1 solutions. Getting 0 hacking point or 1000 hacking points may be the result of your luck, more than of your hacking skills.On the other hand, I'm not sure letting everyone hack anyone would be a great idea. Indeed, we may see one day someone winning the contest with one problem solved and 70 hacks.
 » 6 years ago, # |   +1 What is test 68 on D? I wish I hadn't missed it!
 » 6 years ago, # |   +1 I failed system test on D(test case 14).Any boundary case?
 » 6 years ago, # |   +1 Is there a problem with Codeforces servers? I was repeatedly getting 504 gateway timeout error while trying to submit my solutions during the contest. I was submitting my solutions by uploading the code file. Did not try submitting the code directly though.
 » 6 years ago, # |   0 Finished C just 2 minutes after contest ended ;_;I badly needed rating rise
 » 6 years ago, # |   +243 Revenge is a dish best served in the same contest. :)
•  » » 6 years ago, # ^ |   +120 Good job!
•  » » 6 years ago, # ^ |   +1 Good for you I wish someday I can get this feeling
•  » » 6 years ago, # ^ |   0 And in the same problem too...
•  » » 6 years ago, # ^ |   +1 BOOOM The deep meaning of THUG LIFE , BRO :)
 » 6 years ago, # |   +18 It would be very interesting if Div. 1 could have joined this contest officially.
 » 6 years ago, # |   +116
 » 6 years ago, # |   +39 waiting for the result of your submission for problem C is harder than waiting for GOT season 7
 » 6 years ago, # |   0 How to solve C ?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 I use DP to solve it. DP[i][j] = if i ~ j's number can merge then DP[i][j] = sum( i ~ j ) else -1 if( DP[i][k] != DP[k+1][j] ) DP[i][j] = merge(DP[i][k], DP[k+1][j])time complexity is O(N^3)... little tight
•  » » » 6 years ago, # ^ |   0 There's a O(N) solution:To get the first wanted weight you need to make some combination using the initial values from the first to some where the sum of all the weights in this interval is the value wanted.You do the same for the other wanted weights. If in this process the sum is different than the one you want when it ends (when your interval reaches the end or when the sum is greater or equal to the one wanted), there's no answer. If this process ends and there's not enough groups there's no answer as well.
•  » » » » 6 years ago, # ^ |   0 Oh, I read it after solve it O(N), :) I tried O(N) solution using stack, and solve it. (source : http://codeforces.com/contest/733/submission/21955664)
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 pl0892029 your solution looks very interesting....can you explain your print function ?
•  » » » » 6 years ago, # ^ |   0 plzz explain your code
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Hmm... I can't explain well, but try it.Let's begin. testcase is here. 5 3 3 1 2 2 3 3 3 5 I intend DP's value is it. DP[1][1] = 3 DP[2][2] = 3 DP[3][5] = 5 focusly, DP[3][5] is derived it's sub-DP value. DP[3][5] = DP[3][4] + DP[5][5] why not DP[3][3] + DP[4][5], because V[4] and V[5] is same value 2.In this context, let's calculate DP[3][4]'s value. DP[3][4] = DP[3][3] + DP[4][4] so generally dynamic formula is if (DP[i][k] != DP[k+1][j]) then DP[i][j] = (DP[i][k] + DP[k+1][j]) print function is similar binary tree's postorder traversal.while calculate DP, we save it's k value. my variable name is PATH.and call print. print is trace it using PATH.I think it's solution is Unintuitive. other's solution is more helpful. :) ... Haha..
 » 6 years ago, # |   0 In D, for the second sample case, I printed25 1and got WA. Why? The statement mentions I can print in any order.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 It might be an issue with spacing, for example writing "2 \n" instead of "2\n"
•  » » » 6 years ago, # ^ |   0 I do that all the time. This is the first time I got WA.Then I changed 5 1 to 1 5 and got pretests passed. Took me 10-15 minutes, because I thought it's some other serious bug, and test case 2 is different from the second sample case.It costed me C.
•  » » 6 years ago, # ^ |   +4 simple rule can help you in all your life : you're always wrong and the statement is always right
•  » » » 6 years ago, # ^ |   0 I agree with you. But life's a little difficult when the checker doesn't agree with the statement.
•  » » 6 years ago, # ^ |   0 http://codeforces.com/contest/733/submission/21938356 looks like you didn't print 5 1 huh
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Which is funny, because it prints 5 1 when I tested it.You can test it on ideone or your local compiler. You'll see 5 1
 » 6 years ago, # | ← Rev. 3 →   +19 Exiting moment for me ! Waiting eagerly to see the final verdict of my submission on D. Because, after a long time I am able to solve D !! If it got AC, it will be my 2nd time to be able to solve D in contest duration !!Update: My solution for D is Accepted finally !! I am so much happy and excited that I can't express it !!!Update2: After rating change done, I became Cyan(Specialist) from green(pupil) ! Exitement overflowed !
•  » » 6 years ago, # ^ |   0 Congratulations!
 » 6 years ago, # | ← Rev. 4 →   +9 This is my room: I'm not very optimistic on passing the system tests on problem C :((EDIT: I became a victim of test 13 too :(
•  » » 6 years ago, # ^ |   +1 Yeah same, it's kinda nerve wracking.
•  » » 6 years ago, # ^ |   0 test case 13 is killing everyone !!
•  » » » 6 years ago, # ^ |   0 Am I the only one here who is dying to know what is test 13? (Didn't take part in the contest, but read it and assumed there it should be something really obscure)
•  » » » 6 years ago, # ^ |   +1 I've seen a lot killed by test 11 too
•  » » » 6 years ago, # ^ |   0 Good from tester perspective to have tricky test cases just in the beginning so that if some solution fails it will fail immediately and don't waste time on server by passing 90 cases and then failing on 91st test case.
•  » » » 6 years ago, # ^ |   0 Unlucky 13
 » 6 years ago, # |   0 [submission:http://codeforces.com/contest/733/submission/21935362] why did this fail ? :/
•  » » 6 years ago, # ^ | ← Rev. 2 →   +4 Ignore
•  » » » 6 years ago, # ^ |   0 What ?
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +5 Ignore
•  » » » » » 6 years ago, # ^ |   0 shouldnt answer be 1\n 1
•  » » » » » » 6 years ago, # ^ | ← Rev. 5 →   0 Yes you are right, both answer are correct
•  » » » » » » » 6 years ago, # ^ |   0 yes but radius of inscribe sphere will be 1 which is also for 2 2 2
•  » » » 6 years ago, # ^ |   0 http://codeforces.com/contest/733/submission/21931658 can u tell where i am wrong. i failed system test on case 14
 » 6 years ago, # |   +27 Codeforces users now : I think they wait something
 » 6 years ago, # |   +23 WOW!! actually the first official participant in the contest is Abdelfatah_Elsisi the president of Egypt :V :V
•  » » 6 years ago, # ^ |   +2 i think he's a cheater .. he got WA on D after 1 min of solving Ci think they are two or three people solving on the same handle
•  » » » 6 years ago, # ^ |   +76 Give me your full name and we'll see about that.
•  » » » » 6 years ago, # ^ |   -17 you can find it by reading my handle smart
•  » » » » » 6 years ago, # ^ |   +42
•  » » » » » » 6 years ago, # ^ |   +7 It's
•  » » » 6 years ago, # ^ |   +28 I think all the government are solving on the same handle :V
•  » » » » 6 years ago, # ^ |   0 Man , this comment made my day :D
•  » » 6 years ago, # ^ |   +15 Thanks fady for your support, I'll make sure to visit Syria soon to meet my fans there.
•  » » » 6 years ago, # ^ |   +6 You welcome man !! You have many fans here of syria :D P.S. it's fadi not fady -_- smart president
•  » » 6 years ago, # ^ | ← Rev. 3 →   -16 .
•  » » » 6 years ago, # ^ |   +14 I add a define only when I need it :)
•  » » » » 6 years ago, # ^ |   +7 and you solve problem c in 1 minute too ??
•  » » » » 6 years ago, # ^ |   +1
•  » » » 6 years ago, # ^ |   +4 I use predefined 'mp' and 'make_pair' in same code sometimes,am i a schizophrenic now? same with 'pb' and push_back
•  » » » 6 years ago, # ^ |   -6 define mp make_pair — I use it too.
•  » » » » 6 years ago, # ^ |   +18
 » 6 years ago, # |   +35 should I be very optimistic ??
 » 6 years ago, # |   +38 For those who failed problem C: I guess 13th test must be something like 7 1 2 2 2 1 2 179 2 5 5 i. e. some valid yes-case with extra monsters appended to a, so you also need to check whether sum of a equals sum of b (or do some other validity check). Pretests didn't cover it.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +1 In my room 3 participants failed on test 11, including meUPDATE: My C failed just because I forgot to reset a varialbe ...
•  » » 6 years ago, # ^ |   +15 During the contest I was like "Oh, these guys don't check if the current index is still less than or equal to N, let's hack them" (3 successful hacks). And after getting WA #13, I saw that my code checks if the index is less than or equal to M, not N (in array B instead of A) :D
 » 6 years ago, # |   +96 Some scary idea for Halloween costume:
 » 6 years ago, # |   +27 Wake me up when systest ends.
•  » » 6 years ago, # ^ |   +11 Wake up
•  » » » 6 years ago, # ^ |   0 Thanks bro. Wake me up when ratings change :)
•  » » » » 6 years ago, # ^ |   0 Wake up
•  » » » » 6 years ago, # ^ |   0 Wake up! It's happens! )))
•  » » » » » 6 years ago, # ^ |   +3 Thanks Bro for waking me up.
 » 6 years ago, # | ← Rev. 2 →   +5 For problem C you can check this hack test:41 2 3 431 2 3Answer should be "NO"
•  » » 6 years ago, # ^ |   -12 LOL. Thank god I first checked if sum of array a and b are equal. I still can't say it will pass. :/
•  » » 6 years ago, # ^ |   0 My solution fails this. :( Thanks by the way. Now I don't need to wait for the system testing.
•  » » 6 years ago, # ^ |   0 After seeing this test case I got AC now. Just had to add one line that sum(A)== sum(B)
 » 6 years ago, # |   +29 I am feeling that MikeMirzayanov turned the last 20% of automatic system test to manual system test :\
 » 6 years ago, # |   +8 Submitted solution for problem C at 2:29:59..now just hoping it passes the system tests. :)
•  » » 6 years ago, # ^ |   0 Happy Halloween ? Test 13 Again :/
•  » » » 6 years ago, # ^ |   0 Both C and D failed on test 13.Such a Halloween theme round for me. :D
 » 6 years ago, # | ← Rev. 3 →   +19 That feel when in the phrase Help Zahar choose such a present so that Kostya can carve a sphere of the maximum possible volume and present it to Zahar. you took attention only to words maximum possible volume and present it and decided that goal is to maximaze volume of parallelepiped, not sphere... =(
 » 6 years ago, # |   +65
•  » » 6 years ago, # ^ |   0 Bro! plz don't wait for the rating change :P
 » 6 years ago, # | ← Rev. 2 →   +5 How does this solution pass for problem C? Shouldn't variable sum2 be of type long long as elements in B are ~ 5*10^8 and maximum 500 in number .
•  » » 6 years ago, # ^ |   +1 Elements in B are 5*10^8. These elements are sums of elements in A that are 10^6.
•  » » » 6 years ago, # ^ |   +3 You didn't get me. number of elements in B are maximum 500 , maximum value of these can be 5*10^8 . maximum value variable sum2 can get is 25*10^9 =2.5 *10^10. which overflows integer range. ( Look at variable sum2 in the code )
•  » » » » 6 years ago, # ^ |   0 Indeed, interesting http://codeforces.com/contest/733/submission/21947301It doesn't pass without sum2 but it would need an incredibly specific test in order to make the overflowed sum match sum1 in order to make a difference.
•  » » 6 years ago, # ^ |   +6 I think it passes because he checks for !=If sumof A != sumof B, then it doesn't really matter that one of them overflows, because if they are indeed equal, they won't overflow.
 » 6 years ago, # |   0 Waiting for rating change.....
 » 6 years ago, # |   0 how to solve c ??
•  » » 6 years ago, # ^ |   +1 Watch first number in array b, say it's 10. Iterate over array a elements until their sum is 10. If their sum is less or more then it's not possible. If it's 10 then you need to find an element in array a among those you checked that will eat all the other elements. It's one of the maximal elements, consider some tests on a paper to understand which one you have to pick. Once you are done with first number in array b, watch the second number and do the same stuff...
 » 6 years ago, # |   -9 That feel when you solve C and D and get a wrong answer at problem B.
•  » » 6 years ago, # ^ |   0 Butthurt noobs who didn't solve C downvote this.
 » 6 years ago, # | ← Rev. 3 →   0 Any idea why this fails for F? http://codeforces.com/contest/733/submission/21947192 The value of minimum sum matches, but it says "wrong answer lyamzikov shortage" i also checked that it is printing n-1 edges...}Edit: NVM, Got it! I forgot that there could be multiple edges b/w same pair of vertex in graph too
•  » » 6 years ago, # ^ |   0 I think "lyamzikov shortage" means that you use more coins than you're given while lowering drivers' dissatisfaction :)
 » 6 years ago, # |   -8 WOW!!Abdelfatah_Elsisi submit problem D at 17:30 and submit problem C after exact one minute :|
•  » » 6 years ago, # ^ |   0 It's called cheating.:)
•  » » » 6 years ago, # ^ |   0 Maybe he wrote two programs, checked them and then sent?
•  » » » » 6 years ago, # ^ |   +16 really nigga !?
•  » » » » 6 years ago, # ^ |   0 So he wrote C and D in less time than dreamoon_love_AA and uwi? seems logical.
•  » » » » 6 years ago, # ^ |   +3 and maybe he is the flash and he accidentally forget to pretend that he is normal ?
•  » » » 6 years ago, # ^ |   0 احلوف!!!
•  » » 6 years ago, # ^ |   +3 In fact,he might meet the following condition. In a contest,I wrote the code of problem C first but I failed to debug the code. Then I gave it up and wrote the code of problem D. After I sent the code of D,I continued to debug the code of C and sent the code of C after debugging in little time.
 » 6 years ago, # |   0 For Problem C On testcase 1 : Why this is considered as invalid? Input : 6 1 2 2 2 1 2 2 5 5My output : YES 4 2 L 1 R 2 R 2 R
•  » » 6 years ago, # ^ |   0 You don't have to print the "4".
•  » » » 6 years ago, # ^ |   0 Ouch, i just realized that. Thanks for answering! It's a funny mistake though
 » 6 years ago, # |   0 When will be editorial?
 » 6 years ago, # |   +3 Got C and D wrong by two very small and silly mistakes.... :( Got them ACed just after the contest ended :P
•  » » 6 years ago, # ^ |   0 Same here. :)
 » 6 years ago, # |   0 Can I download the test cases for a problem, because my solution is failing on a test case which very large and is not displayed completely in the browser ?
 » 6 years ago, # | ← Rev. 2 →   +1 Why rating change is so delayed ?Update: I just commented and reloaded the page and saw that rating change is published... !
•  » » 6 years ago, # ^ |   +1 Rating change done :)
•  » » » 6 years ago, # ^ |   0 As soon as I completed commenting, rating change is done !!
 » 6 years ago, # | ← Rev. 2 →   0 Good
 » 6 years ago, # |   +5 I heard that 2Pac didn't come back in 2014 because he was waiting for ratings to be updated.
 » 6 years ago, # |   0 In Problem C, Print only "Yes" without moves if the array and the new array are exactly the same or not?.
 » 6 years ago, # | ← Rev. 2 →   0 In problem E, why am I getting RTE on CF, while its working fine on ideone?
•  » » 6 years ago, # ^ |   0 There are various types of RE. It'd be good if the judge can tell us which RE it is.
 » 6 years ago, # |   0 Any idea to solve the problem E ??? some editorial published ???
 » 6 years ago, # |   +15 what's the procedure of the check against repetitive code？ one of my friend Hu_huhuhuhuhuhu used other's code on problem D(despise him!),but after systest his score was still less than me. but i got -8 on this round(now my rating is less than him), he escaped from decreasing！ it seems if someone's rating will decrease in a round，copy other's code can avoid it. that's rediculous!
 » 6 years ago, # |   0 My rate is progressive from right to left and descending from left to right :789 & 987 I hope it becomes a lucky number 4774
 » 6 years ago, # |   0 Something fishy going on with the judge/checker for D. The output is different when tested and submitted for same test case. Output differs on different runs of (almost) the same code! I had to make small change between two submissions.
 » 6 years ago, # |   +4 For D, what can we do if we are asked to find out the maximum volume? As a * b * c may be as large as 10^27, how can we compare two volumes without BigInt?p.s. I didn't work out D during the contest because I didn't read the problem carefully and thought it was finding greatest volume. Don't be like me.
•  » » 6 years ago, # ^ |   +1 the answer can be simple as the min(a, b, c) / 2
•  » » 6 years ago, # ^ |   0 You can use log values for comparison
•  » » » 6 years ago, # ^ |   0 Thanks, maybe, I've tried, but consider this: 999,999,999 ^ 3 and 1,000,000,000 * 999,999,999, 999,999,998. It seems that even using log will return the latter is bigger.
•  » » 6 years ago, # ^ |   +3 Although this isn't what was required in this problem, but you can simply use double for comparing huge numbers like this. if((double) a1 * b1 * c1 < (double) a2 * b2 * c2) { // my code }
•  » » » 6 years ago, # ^ |   0 Thanks for your attention.According to the following code, with given a1, b1, c1 and a2, b2, c2, it gives a1*b1*c1 == a2*b2*c2. #include using namespace std; typedef long long ll; int main() { ll a1 = 999999999LL; ll b1 = a1, c1 = a1; // all same ll a2 =1000000000LL; ll b2 = a2 - 1LL, // 999999999 c2 = a2 - 2LL; // 999999998 bool res = (double) a1 * b1 * c1 < (double) a2 * b2 * c2; cout<
•  » » » » 6 years ago, # ^ |   0 Notice that a1 * b1 * c1 == a2 * b2 * c2` won't cause you any problems even if they overflow because the overflowed values will probably be equaled if the real values of the multiplications are equaled. But to be on the safe side, use doubles.
 » 6 years ago, # | ← Rev. 2 →   0 Orz hahaha
•  » » 6 years ago, # ^ |   +8 ;|
 » 6 years ago, # |   0 any hints about problem E?
•  » » 6 years ago, # ^ |   0 Can you determine the which side will you fall off in O(1) with preprocessing? If you can, then can you use this observation tell how many "cycles" you have to go through before falling off?
 » 6 years ago, # |   +3 Somebody please compare these two submissions and tell me wtf is going on!!!! One is failing on test case2, other at test case 36.21957079 21957040spoiler : they're EXACTLY the same!!!
 » 6 years ago, # |   +8 For Problem D,First of all, for a parallelepiped with sides say l,b and h ,the radius of sphere inscribed in it will be r = min(l,b,h)/2 . So here, to maximize the volume, we need to maximize the radius r. That is we need to maximize the minimum side of parallelepiped.Now, two parallelepipeds should have atleast two sides identical in order to join them. Lets sort the sides for a parallelepiped in increasing order and do this for all parallelepipeds. After sorting, lets say the sides of a parallelepiped are l,b,h such that l<=b<=h . Now the observation is we need to match only the larger sides i.e. 'b' and 'h' of this parallelepiped with larger sides of other parallelepipeds so that the minimum side of the resulting parallelepiped can be maximum. Why? Because , lets assume we match 'l' and 'b' values of two parallelepipeds then for the resulting parallelepiped the minimum side will remain 'l' . The same thing happens when we match 'l' and 'h' values of two parallelepipeds. But when we match 'b' and 'h' then there is a chance that now the 'l' side of resulting parallelepiped will be greater than 'b' or 'h' as a result our minimum side will become 'b' now.For help refer to my solution, 21956827Hope this helps :)And sorry for my bad English!
 » 6 years ago, # |   +9 When will be the editorials published??? Nice problemset Hope they publish it ASAP
 » 6 years ago, # | ← Rev. 2 →   +11 For problem F, after viewing some other's code. I think I understand it. First, we are actually finding a spanning tree of the graph and are decreasing weights of some of the edges of the tree to get the answer.Suppose now we happen to know the spanning tree, we can simply invest all of our money into only one edge, whose C is the smallest among edges of the tree, to reduce total 'disatisfaction' as large as possible. Note that we may not be able to invest in any other edge by doing so.But how can we find the spanning tree — we only know minimal spanning tree algorithm.Well, let's turn our attention to another point. I mentioned that what you have to do is just to reduce the weight of only ONE edge. So what about enumerate through edges we are going to reduce! Actually, the final spanning tree may be very similar to the minimal spanning tree — intuitively, apart from the edges to reduce, other weights of edges of the spanning tree must be as small as possible. So, suppose we now have the minimal spanning tree T.And now we want to plug an edge (u, v), which may or may not be in the tree, into T. The only block, if (u, v) is not in the T, is the only path from u to v in T. And if we remove one of the edge of the path from T and plug (u, v) into T, we'll got another spanning tree.So, you may just remove the edge with the largest weight on path from u to v and plug E into it you will get the answer. But how to find the path from u, v and find the maximal weight along the path? You'll need LCA(Lowest Common Ancester) algorithm, which preprocess the minimal spanning tree.Sorry for my poor English. But typing solution out really helps me organize my thought.
•  » » 6 years ago, # ^ |   0 I was wondering why we just need to reduce the weight of only ONE edge. As you mentioned "what you have to do is just to reduce the weight of only ONE edge".Thanks.
•  » » » 6 years ago, # ^ |   0 Because the weight can be negative
•  » » » 6 years ago, # ^ |   0 Suppose you want to reduce weight of m edges of a spanning tree, let's number them 1, 2...m, you wan to reduce each edge by ui times, and each edge costs you Ci for reducing once. Then, the result you get is tot - u1 - u2 - ... - um, where u1 * C1 + u2 * C2 + ... + um * Cm ≤ S. Suppose now you select an edge with minimal C, and you can at least reduce u1 + u2 + ... + um times, because: C ≤ Ci and u1 * C + u2 * C + ... + um * C ≤ u1 * C1 + u2 * C2 + ... + um * Cm ≤ S. So reducing only one edge is at least as good as reduce many edges. And intuitively, for a fixed spanning tree, you can find the edge with minimal C, then you can reduce the 'dissatisfaction' of the whole tree by S / C. If you select edges with bigger C, you may not be able to reduce the 'dissatisfaction' that much.As we don't know whether the edge we are working with is the edge with minimal C, we want the w of remaining edges to be as small as possible, that's why we are replacing edges in MST.
 » 6 years ago, # | ← Rev. 4 →   +10 For the problem C733C - Epidemic in Monstropolis Although my code is Accepted, but if use this data will wrong answer233 2 1 3 3 3 1 1 2 1 2 1 1 1 2 2 3 1 2 3 3 3 356 16 5 5 15 Because my answer is NO and the right answer should be "YES" So is the data have BUG? Hope a reply!Thank you!@Kniaz
•  » » 6 years ago, # ^ |   0 Same happened with me, i wrote a wrong solution using linked-lists and it failed at ~110th test which was probably a hack, if that person didnt hack someone with that test i probably would pass it.. :/
•  » » 6 years ago, # ^ |   0 The answer my program gives is YES 1 R 1 R 4 R 4 L 3 L 2 R 2 R 2 R 2 R 6 L 5 L 4 L 5 L 7 L 6 L 5 R 5 R 5 R You can try it. And my code
•  » » 6 years ago, # ^ |   0 I ran this testcase and my AC solution gave NO. I freaked out until I realize the testcase lacks number K (number of elements in B). You scared me :(
•  » » » 6 years ago, # ^ |   0 I am so sorry! Just now surely lack a "k", you can try again. For this data my accepted program gives "NO"　but I think should be "YES"...
 » 6 years ago, # |   +3 wait for my online judge
•  » » 6 years ago, # ^ |   0 I wonder who you are ! Because I don't think that you're a single person .Because a good DIV1 programmer wouldn't waste their time using such a fake account .
 » 6 years ago, # |   0 Hi! Can you give me a test example where this does not work:https://gist.github.com/Vitosh/01e3ce215de5ecb70b42cafc2dd2b8d0Its from http://codeforces.com/contest/733/problem/B and I think it should be working. However it breaks on test 10 and I cannot see it. Thanks!
•  » » 6 years ago, # ^ |   0 You are missing out so many things: why the "&&(long_left>long_right)" conditions? Sometimes there are more right legs and you need to reduce them to achieve max beauty. maximising the delta of legs do not guarantee maximum beauty, think about it.
•  » » » 6 years ago, # ^ |   0 Yup, thanks, I was thinking something else. My initial idea was that the beauty is only if they start with left foot. Just I was reading things which were not there. And the fact, that the first 9 tests were correct has only put me into this direction. :) Cheers!