shigule's blog

By shigule, 4 years ago, ,

Hello, Codeforces!

Codeforces Round #278 will be held at Nov/21/2014 20:00 MSK for both divisions. Note that the time is 30 minutes later than regular Codeforces time, and Moscow is currently UTC+3.

The problem setters are taorunz and me. This is our first Codeforces round!

We'd like to thank Maxim Akhmedov (Zlobober), who helped us prepare the problems very much; also to thank MikeMirzayanov for Codeforces and Polygon platforms.

This round is involved in MIPT Fall Programming Training Camp, and top-20 of contestants from the camp will be rewarded with Codeforces T-shirts. For other contestants it will be regular Codeforces round.

Hope you enjoy the round, and wish you high rating.

UPD: Score distribution:

Div. 2: 500 — 1500 — 1500 — 2500 — 2500

Div. 1: 500 — 1500 — 1500 — 2000 — 2500

It's not for everyone that the optimal strategy is solving tasks in order. Make sure you've read all problems before the contest ends.

UPD: Very sorry that the round will be moved 20 forward due to technical reasons.

UPD: Top 5 participants:

Div.1

Div.2

Honorable mentioned:

anta, who solved Div.1 E!

CKYang, who solved Div.2 E!

UPD: Editorial is here!

UPD: hack statistics (Div.1 and Div.2) by illi!

•
• +225
•

 » 4 years ago, # |   +48 > "top 20 contestants blablabla CF T-shirts" > reads it again
•  » » 4 years ago, # ^ |   +4 "from the camp"
•  » » » 4 years ago, # ^ |   +13 Yes, that's what I found out when I read it again.
•  » » » » 4 years ago, # ^ |   +61 I agree, this valuable information could be spread among participants attending the camp.No necessity to write to others about t-shirts which could not be received by them :D
•  » » » » » 4 years ago, # ^ |   +72 It gives additional motivation to visit this camp in future:)
 » 4 years ago, # |   +19 Oh maaan , the time is too late for me.
•  » » 4 years ago, # ^ |   +17 Its never too late for a Codeforces Contest!!!!!
•  » » » 4 years ago, # ^ |   +7 Only too early :-D
•  » » » » 4 years ago, # ^ |   +5 i guess codeforces took me seriously another 20 minutes delay
 » 4 years ago, # |   +19 Codeforces Round #278 will be held at Nov/11/2014 20:00 MSK for both divisions Today is Nov/20/2014 — are you really writing about the date in past?
•  » » 4 years ago, # ^ |   +3 I think he want to express Nov/21/2014.... Because the url is http://www.timeanddate.com/worldclock/fixedtime.html?day=21&month=11&year=2014&hour=20&min=0&sec=0&p1=166
•  » » 4 years ago, # ^ |   +33 Very sorry that the round will be moved 20 forward due to technical reasons.
 » 4 years ago, # | ← Rev. 5 →   +9 Two amazing events in one day : 1.A (maybe ;) ) rated Codeforces Div.2 + Div.1 round after a long time.2.Hunger Games Mockingjay part I release.
 » 4 years ago, # |   +6 Oh my god, the time is unscientific， it's toooooooooo late
 » 4 years ago, # |   0 I want a T-shirt..... I haven't get the T-shirt of Codeforces! What a pity!
 » 4 years ago, # |   +26 Omgone contest after anotherreally cool...if you start ten contests on a week i will join all of them...
•  » » 4 years ago, # ^ | ← Rev. 2 →   +8 ツ
 » 4 years ago, # |   +4 top-20 of contestants from the camp will be rewarded with Codeforces T-shirtsThere's no chance for usIt's all decided for usThis world has only one sweet moment set aside for us...
•  » » 4 years ago, # ^ |   0 Here's a problem you may enjoy: http://cerc.tcs.uj.edu.pl/2012/data/b.pdf :). (In fact with really cool solution!)
 » 4 years ago, # |   0 Really do not like that time.
 » 4 years ago, # |   +3 First contest that forces me to participate until 24:00 :) And this comes in a day that tomorrow i have region olympiad :( I think i will not wait for system checking and updating ratings today.
 » 4 years ago, # | ← Rev. 2 →   +28 The contest is prepared by Chinese but I really don't think it is prepared for Chinese because it will start at 1:00 am UTC+8.
•  » » 4 years ago, # ^ |   +16 Maybe we want to make something different from previous Chinese rounds. As you can see, no one is here saying anything like "yet another Chinese round, huh?"
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +8 So ? You do not want the Chinese coder's to do this Chinese round?
•  » » » » 4 years ago, # ^ |   +12 I think it should be a Codeforces round first.
•  » » » 4 years ago, # ^ |   0 yet another Chinese round, huh?
 » 4 years ago, # |   0 Please consider Chinese coders' sleeping time. Contests starting time has been moved from 23:30pm to 01:00am now, so sleeping time of Chinese coders moved from 01:30am to 03:30am.
•  » » 4 years ago, # ^ |   +5 my mistake: 03:30am -- > 03:00am
•  » » 4 years ago, # ^ |   +47 Why do the Chinese have so much problem with staying up late ?
 » 4 years ago, # |   +1 Late night contest is great adventure
 » 4 years ago, # |   +31 This unusual start time is good for me. I can start contest after taking my dinner :D
 » 4 years ago, # |   -8 I want to take part in this contest because of the e-mail says: Attention! Unusual start time: the round starts on Friday, November, 21, 2014 17:00 (UTC). However , this time changes. I cannot do it now. Chinese people don't want to the Chinese one's to take part in? OK . OK.
•  » » 4 years ago, # ^ |   0 It is 17:00 UTC, isn't it?
•  » » » 4 years ago, # ^ |   0 Yep. 20:00 (UTC+3) == 17:00 (UTC).
•  » » 4 years ago, # ^ |   +3 the later 2 days is one of China Regional Contest....SO, most of coders will decide to have a good sleep.
•  » » » 4 years ago, # ^ |   0 So why you not?
•  » » » » 4 years ago, # ^ |   0 Because mathlover like codeforces very much.
 » 4 years ago, # |   -54 我是来测试一下能不能发中文的
•  » » 4 years ago, # ^ |   +3 wat?english pls
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0
•  » » » 4 years ago, # ^ |   +7 He said:"I just come here and test if it can post Chinese."
•  » » 4 years ago, # ^ |   0 (sigh)
 » 4 years ago, # |   +5 For Japanese, it starts in 2:00 AM and too hard to participate...
 » 4 years ago, # |   +67 In Arabic, "saffah" means a murderer! i hope this has nothing to do with today's contest :D :D. No hard feelings bro :D
•  » » 4 years ago, # ^ |   +53 Okay this name is randomly typed when I was 9 years old and needed a nickname......
•  » » » 4 years ago, # ^ |   +1 Just like WJMZBMR... randomly nickname.
•  » » » 4 years ago, # ^ |   +3 In what place have you used this nickname first time? (just curious :D )
•  » » » » 4 years ago, # ^ |   0
•  » » » 4 years ago, # ^ |   +3 Well I guess it had many things to do with the contest xD. It was a MASSACRE! :D :D.
 » 4 years ago, # |   0 It seems so late, maybe I will be hungry at half.
 » 4 years ago, # |   0 oh my god! 1:00 am! I have a class tomorrow morning ==
 » 4 years ago, # | ← Rev. 2 →   +4 I bet there will be at least 1 pure math problem! :D Because it's a Chinese round...
•  » » 4 years ago, # ^ |   0 Close condition?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 It's not a typical Chinese round. (At least the time is unusual, isn't it?^_^) We hope to break the stereotype about Chinese rounds.
 » 4 years ago, # |   -44 hey guys plz unlike me
 » 4 years ago, # |   0 hope for some dp!!!
 » 4 years ago, # |   0 Loving this series of CodeForces Rounds :) ..
 » 4 years ago, # | ← Rev. 3 →   -34
 » 4 years ago, # | ← Rev. 3 →   -62 playing clash of clans and coding and coding and coding in CF.
•  » » 4 years ago, # ^ |   -6 thanks MikeMirzayanov
•  » » 4 years ago, # ^ | ← Rev. 2 →   -21
•  » » » 4 years ago, # ^ |   0 I love codeforces and Google too:)
•  » » » 4 years ago, # ^ |   +2 The links now work as "No such blog entry" = "No such blog entry". You need to start links with http://, or they'll be considered internal.
•  » » » 4 years ago, # ^ |   0 I also think :)
 » 4 years ago, # |   +1 Too late for Chinese.T_T
 » 4 years ago, # |   0 Interesting score distribution!
 » 4 years ago, # |   +12 can't wait. want to see new winners and at first get in div.1 :D good luck everybody
 » 4 years ago, # |   0 a3333333... why :'( !!
 » 4 years ago, # |   +3 Is B harder than usual?Please don't delay the contest! I have to go to school tomorrow and now the contest will finish at 11:00 PM in my country! :D
•  » » 4 years ago, # ^ |   0 Me too...Contest will finish 00:20 in my country :)
 » 4 years ago, # |   0 20 mins delayed?!
 » 4 years ago, # |   0 Why delay the contest...
•  » » 4 years ago, # ^ |   +35 If you were here in MIPT Fall Training Camp, you wouldn't even ask :)
 » 4 years ago, # |   0 What!! It's been put off...Oh no, i must go to sleep
 » 4 years ago, # |   0 20:20?
 » 4 years ago, # |   0 very bad :(
 » 4 years ago, # | ← Rev. 2 →   +21 So for this time does "technical reasons" mean "dinner on training camp" again? :D
•  » » 4 years ago, # ^ |   0 so we are waiting for them to finalize their dinner :D
•  » » 4 years ago, # ^ |   +2 I know nothing about their dinner, but i was able to finish my dinner thanks to this delay :Ъ
•  » » » 4 years ago, # ^ |   0 well atleast somebody's happy for the delay!!
 » 4 years ago, # |   0 good rating 500 — 1500 — 1500 — 2500 — 2500
•  » » 4 years ago, # ^ |   0 Seriously O_o
 » 4 years ago, # |   +88 Moved is always better than unrated ;-)
•  » » 4 years ago, # ^ |   +30 Better hope it won't be unrated in the end, then :D
•  » » » 4 years ago, # ^ |   0 You are right, hopefully the'll fix the problem completely not partially, we will see...
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 [Deleted]
 » 4 years ago, # | ← Rev. 2 →   -16 А нельзя уже сделать как на топкодере, контесты в разное время? Я, конечно, понимаю, что основной контингент хороших программеров России обитает в Питере, Москве, Саратове и им удобно, когда контест начинается в 19-30, 20-00 и т.д., но чем восточнее город, тем решать становится сложнее, и реально не прет решать задачи на ночь глядя после рабочего дня и ещё 4-5 часов ожидания. Просто сложно нормально выступить, даже если ты неплохо кодишь.
 » 4 years ago, # | ← Rev. 2 →   +2 "Note that the time is 50 minutes later than regular Codeforces time, and Moscow is currently UTC+3."
 » 4 years ago, # |   +1 Why profiles are locked?!
•  » » 4 years ago, # ^ | ← Rev. 4 →   +3 I can't even open my own profile.UPD- Now Everything looks ok.
•  » » 4 years ago, # ^ |   +1 For no chitting mb=)
•  » » 4 years ago, # ^ |   +4 to reduce the load I think
•  » » 4 years ago, # ^ |   +6 Yeah, that's to prevent cheating and begging solutions during contest.That has already happened during last 3(/4?) contests.
 » 4 years ago, # |   +9 it seems we should expect so many "Codeforces is temporary unavailable" during the contest !!
•  » » 4 years ago, # ^ |   0 Is it unrated again?
 » 4 years ago, # |   +2 Its really disheartening and frustrating when you cant submit a code for like half and hour just because servers are not working.. :\
 » 4 years ago, # |   +1 Keep getting "Server down" errors for the last 15-20 minutes. Need to cancel this round for sure.
 » 4 years ago, # |   +4 I don't know if It happened only for me (!) , but CF kept "Connecting ..." for me half of the contest, and was "Temporary Unavailable" for another 15 minutes! Couldn't even submit ...
•  » » 4 years ago, # ^ |   +4 Guess It wasn't only you ... :|
•  » » 4 years ago, # ^ |   +3 I left the contest ~1 h ago
 » 4 years ago, # |   +67 Nice contest ^_^
•  » » 4 years ago, # ^ |   +3 When I saw so many people were getting extra points by hacking A, I thought to give it a try myself. Then I found that almost all the hacks in my room has already been taken by someone. Not to mention, I couldn't think of any tricky case either. What case did you use?
•  » » » 4 years ago, # ^ | ← Rev. 3 →   +5 I tried to find minimal test case to let people do the same mistake again =) Most of all can beat with follow test case:1 2 12 100 11 100 100And second test (for those who tried to fix solution but failed):1 2 130 100 11 100 100
•  » » » » 4 years ago, # ^ |   0 What should these test cases return?
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   +3 first: 198second: 994
•  » » » » » » 4 years ago, # ^ |   0 Ehooo, i hope i'll get AC
•  » » 4 years ago, # ^ |   +1 True rampage! You are amazing!!!
•  » » 4 years ago, # ^ |   +4 Your room mates hate you, I'm pretty sure :-D
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +9 To tell the truth I have found mistake in my own solution. =)
•  » » » 4 years ago, # ^ |   +3 Actually he is doing them a favor. It is better to know that your solution is wrong earlier in the contest than towards the end, or not know it at all. :)
•  » » 4 years ago, # ^ |   +4 Did you add your profile pic now to go with the picture? :D
•  » » » 4 years ago, # ^ |   0 No. But it fits perfectly :)
•  » » 4 years ago, # ^ |   0 poor people. :D
•  » » 4 years ago, # ^ |   0 забавно, что на тесте1 1 1100 100 1001 100 100у тебя падает)))
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Your profile pic + the image = perfection =))
 » 4 years ago, # | ← Rev. 3 →   -13 Very nice problems. Can't wait for the system test to end so I can submit solutions at C.
 » 4 years ago, # |   -14 was hard problems mostly mathematic so i couldn't write good. but i love math and hard problems really waiting for editorial(tutorial).
 » 4 years ago, # |   +8 ...yet another chinese round...
 » 4 years ago, # | ← Rev. 3 →   +15
•  » » 4 years ago, # ^ |   0 and also +198 rating point :v :v
 » 4 years ago, # |   0 Is that enough to check attack decrease up to 100?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 1 1 1100 100 1001 100 100answer is 11890(i hope xD).
•  » » » 4 years ago, # ^ |   0 Thanks,
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 No, for example2 1 1 100 2 100 100 1 100 requires increase attack by 199
•  » » 4 years ago, # ^ |   0 Attack decrease (that is, increasing defense) is enough to 100; once your defense is more than the opponent's attack, you won't be harmed. But attack increase must be checked up to 200, an HP increase must be checked up to 10000. (Someone in my room used 1000 and passed, but 10000 is easier to prove.)
•  » » 4 years ago, # ^ |   +3 No. There is a easy test when you need 199 100 1 50 100 100 100 100 1 100 
 » 4 years ago, # |   +33 Solution to C:n must be prime or 1 or 4 (trivial), so let n be prime numbera1 = 1, an = n and ai = i / (i - 1) :>>
•  » » 4 years ago, # ^ |   0 i/(i-1) = 1 (i >= 3)
•  » » » 4 years ago, # ^ |   +13 Division is handled in Zp field. In other words, i / (i - 1) = i·(i - 1)p - 2 mod p.
•  » » 4 years ago, # ^ |   0 ...I tried to figure out whether 9 is possible or not, since I saw that the primes and 1 and 4 worked. I should have just hardcoded the solution for 4...
•  » » 4 years ago, # ^ |   0 Why cannot n be a degree of a prime?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Because we have p and 2p, if p > 2, so for p2 number 0 will occur too early.If n = pk, k > 2, then we have p and pk - 1.
•  » » » 4 years ago, # ^ |   +5 Because for non-prime N, (N-1)! mod N = 0, since N has to be last, we'll get two 0.Except for 4, which I forgot. I can prove it for all non-primes except perfect squares — you just decompose the number into prime multipliers and then get rid of powers — all of numbers are distinct from 1 to N-1.
•  » » » » 4 years ago, # ^ |   -13 Same here, forgot 4 and will get 0 for this apparently =( Hate these rules, why can't we get partial scores or see the results right away.
•  » » » » » 4 years ago, # ^ |   0 4 should be in pretests... You would force people who didn't see it to lose points, but they wouldn't get 0.
•  » » » » » » 4 years ago, # ^ |   +10 No, 4 should not be in pretests. It makes good hacks. (And 1 too.) That makes people need to figure out all corner cases.
•  » » » » » » » 4 years ago, # ^ |   +3 It also disbalances the contest completely. Someone with a guy in the room that knows that corner case has a huge advantage, because they will get hacked and fix their code (for instance Swistakk). The person that doesn't notice the corner case gets zero points, i.e. the exact same as someone who didn't think of the solution to the problem at all. Someone who notices a corner case can get more points for noticing it than for solving a problem (especially true if the corner case is in problem A).
•  » » » » » » » » 4 years ago, # ^ |   +5 This one I agree somewhat. Although the only plausible alternative is to get everyone into a single, large room, and that's just plain impossible. They have failed to solve the problem, and thus I say 0 is deserved. This is Codeforces, not ACM-ICPC; you should adapt your strategy to the Codeforces platform. If you know hacking might potentially yield plenty of points and you refuse to hack, that's your problem.
•  » » » » » » » » » 4 years ago, # ^ |   0 Your argument that the contestants should adapt to the rules applies to any system, good or bad, so it's not relevant here. You can have all the codes in your room hacked by someone in your room who saw the corner case 5 minutes earlier, and therefore has 700 points more than you do now. In that case hacking was never an option for you. Ideally, the system should be as little luck-dependent as possible and as fair as possible, in that it allows for people who performed similarly in a contest to be placed in similar positions. What I mentioned above is an example of that not happening.
•  » » » » » » » » » 4 years ago, # ^ |   +5 Which simply means you need to practice to find corner cases faster?I don't see any luck involved among contestants in a single room (barring server problems and so). Which means I should suggest that rating updates only see people inside a room, but that will make a single position up or down to have a major effect in rating, in which those unexpected troubles (server problems) will now have big effects.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +18 Wow, it's much easyer, than I have.I found generator, and set ak = r(k - 1) * ( - 1)k.
•  » » 4 years ago, # ^ | ← Rev. 3 →   +12 My solution is more sophisticated :| Let n = p be a prime number, We find generator g mod p. Let a be the sequence 1,  - 2, 3,  - 4, ..., (p - 1) / 2, ...,  - 3, 2,  - 1 mod p - 1. The answer is 1, ga[0], ga[1], ..., ga[p - 2], p. Oh, it's the same as PavelKunyavskiy's solution.
•  » » » 4 years ago, # ^ |   0 Hah, I alredy knew this problem, it was posed on PMO 8 years ago and I have solved it using generators, but later I read that solution: http://archom.ptm.org.pl/?q=node/105 :).
•  » » 4 years ago, # ^ |   +8 How do you know that ai = i/(i-1) is unique for each i? Is this a known theorem or something?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +5 i / (i - 1) = j / (j - 1) implies i·j - i = j·i - j, so i = j.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   -8 Leti * k = (i + 1)j * k = (j + 1)then(j — i) * k = j — ithen k = 1
•  » » » 4 years ago, # ^ |   -16 1/i is a unique reciprocal of i in Zp field. This is such a number k that . There is exactly one such number and it can be computed as
•  » » 4 years ago, # ^ |   +3 You got lucky you were hacked with 4... I didn't share the same happy ending :)
•  » » » 4 years ago, # ^ |   0 Haha, yes, indeed I'm lucky :).
•  » » 4 years ago, # ^ |   0 I forgot to print "YES" , if n < 5 :(
•  » » 4 years ago, # ^ |   0 Used the same approach, can you prove that a will contain distinct numbers only?
•  » » » 4 years ago, # ^ |   0 i / (i - 1) = 1 + 1 / (i - 1)
•  » » » 4 years ago, # ^ |   0 Yes. x / (x - 1) = y / (y - 1)(modn) if and only if x = y(modn)
•  » » » 4 years ago, # ^ |   0 Suppose you have i! = j so that i / (i - 1) = j / (j - 1) <  =  > i(j - 1) = j(i - 1) <  =  > ij - i = ij - j <  =  > i = j, so it contradicts the hypothesis.
 » 4 years ago, # | ← Rev. 2 →   0 Got around 12 WAs on Problem B inspite of checking all possible permutations of the given numbers. Can someone point out certain corner cases?
•  » » 4 years ago, # ^ |   0 well, for me I got 6 WAs, re-wrote the code 3 times, and in the last 2 mins, I found that I accidentally wrote 2 instead of 3 xD, (though I still don't know if it'll pass system test or not)
 » 4 years ago, # |   +17 div1, I'll be back!
 » 4 years ago, # |   0 thanks saffah for nice problem
•  » » 4 years ago, # ^ |   -7 really !! :D
•  » » 4 years ago, # ^ |   0 nice??? :|
•  » » » 4 years ago, # ^ |   0 nice and very hard :)
 » 4 years ago, # |   -8 Seeing so many people harvesting points through hacks, I got impatient and lost 100 points :p Never doing such a silly act again! Not gonna unless I am sure of what I am doing.
 » 4 years ago, # |   0 How I can solve problem B?
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 Div2 B For n=0 :Print 1 1 3 3 or any other satisfying numbers For n=1 :x2=2*x1, x3=2*x1, x4=3*x1 For n=2 :Sort the given numbers. x3=4*x1-x2, x4=3*x1 For n=3 :Sort the numbers. And check if (2*x1+x2+x3)/2 == (5*x1+x2+x3)/3 If true,then print anyone of these. For n=4: Sort the numbers and check them. Take float datatype here as integer may give wrong answer(Hacked 1 solution on this)I hope it passes final test. I am not sure if it is right.
•  » » » 4 years ago, # ^ |   0 what about this test? 1 1000000 u forgot that Bi must me non-negative and <=10^6
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Problem statement: "The next n lines contain integers ai, denoting the number of candies in the i-th box (1 ≤ ai ≤ 500)."Candies wont be more than 500 so no need to check for <=10^6. I forgot to include Bi condition. Thanks. I have included it in my solution though.
 » 4 years ago, # |   +1 Nice contest, but I can't pass B problem's 5-th pretest, so good bye blue colour(((
•  » » 4 years ago, # ^ |   0 Yes I also get too many WA on pretest 5 of problem B
•  » » 4 years ago, # ^ |   0 I passed 5th pretest but not 6th. Don't even know what's wrong with my method. Hoping that the editorial comes out soon :)
•  » » » 4 years ago, # ^ |   0 Hope so!
•  » » 4 years ago, # ^ |   0 small bug( YES 125 375 375NO forgot return 0 (((
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 OMG pretty much similar to mine error
 » 4 years ago, # |   +8 Why B was worth more points than usual? I think it was straitghforward, easier than usual... By the way I really enjoyed problem D, I'm fond of interval trees composing funny things :).
 » 4 years ago, # |   -18 В задаче А див.1 есть тесты, на которых нам будет выгодно брать больше 100 какого-то итема?
•  » » 4 years ago, # ^ |   -15 2 1 1 10 2 100 100 1 100 109 раз Attack
•  » » 4 years ago, # ^ |   -10 как минимум 100500 взломов!
•  » » 4 years ago, # ^ |   0 Да. 1 1 1 100 100 100 1 100 100
•  » » 4 years ago, # ^ | ← Rev. 2 →   -12 В теории:Защиты нам не нужно более 100, ибо имея 100 мы сможем отразить любой удар.Атака нужна максимум 200, ибо в худшем случае, чтобы убить монстра одним ударом, нам нужно пробить 100 защиты и 100 ХП.На счет количества ХП трудно что-то точно сказать, но рассмотрим вот такую ситуацию: у нас защита 1, чтобы убить монстра когда-либо нам нужно наносить 1 хп, а так как у монстра максимум 100 ХП, значит нам максимум понадобится 100 ходов, чтобы убить монстра. Следовательно, нам нужно, чтобы монстр убил нас более чем за 100 ходов. Допустим, монстр бьёт на 100, значит нам нужно (100-1)*100 + 1 = 9901 хп, чтобы монстр не убил нас до того, как его убьём мы. Но вряд ли в действительности нам когда-нибудь понадобится такое количество ХП, потому что, скорее всего, нам будет выгоднее купить атаку (и ускорить победу), нежели ХП.Поэтому могу предположить, что достаточным было сделать перебор ХП до 1000, атаку до 200, защиту до 100.UPD: Нашелся тест, где перебирать ХП нужно до 2000. Возможно, есть и хуже, поэтому лучше вообще отказаться от перебора и вывести формулу необходимого количества ХП при данной атаке и защите.
•  » » » 4 years ago, # ^ |   -10 Можно перебирать до 1e4, т.к мы в ход теряем не больше 100hp и нам нужно не более 100 ходов(иначе мы вообще не убьем). Если добавить break, то это успевает отработать за секунду.
•  » » » » 4 years ago, # ^ |   -11 Я по-тестил, тупой перебор 10000 x 200 x 100 не работает, а вот перебор 10000 x HPm + DEFm x ATKm заходит.87928228792817
•  » » » » » 4 years ago, # ^ |   0 Достаточно в ваше первое решение добавить бряк, как только мы нашли что-то (если мы выигрываем из состояния (h,a,d) нет смысла смотреть на (h+1, a, d), (h, a + 1, d) или (h,a,d + 1).Добавил break — все залетает. 8796090
•  » » 4 years ago, # ^ | ← Rev. 3 →   -9 1 1 1 100 2 100 100 1 100 UPD 1 x defence and 100 x attack = 200Sorry for mistake
•  » » » 4 years ago, # ^ |   0 why not 100 atk?
•  » » » » 4 years ago, # ^ |   0 yes, 100 atk, my bad
 » 4 years ago, # |   -8 This platform is always crashing during competitions and I can not submit another try during last minute as it keeps crashing. Really think you need to spin up some extra servers for this platform.
•  » » 4 years ago, # ^ |   +12 in what time it was not working?
•  » » » 4 years ago, # ^ |   0 during last few minutes
•  » » » 4 years ago, # ^ |   0 During the previous 3 competetions(including today's) it has been crashing constantly .
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Yea i know. Same was happening pretty much since every contest I have participated since starting about 3 contests ago. Idk if my solution was correct that I was trying to put foward in last 5 minutes but it didnt even get submitted at all because it kept crashing.
•  » » 4 years ago, # ^ |   0 It was quite rare for me. ( twice at the middle ) Also you can save the statements locally...
•  » » » 4 years ago, # ^ |   0 Save the statements locally does not help for submissions
 » 4 years ago, # |   +23 The contest was like "Lets hack as much submissions before I get hacked myself xD ".
•  » » 4 years ago, # ^ |   0 it was really like this specially problem B...
 » 4 years ago, # |   0 let me say the realityThis problems was worst problems that i have seen in contests :(But like other times thank u that try to make this site better and better
•  » » 4 years ago, # ^ |   +3 Worst problems because they allow many hacks? I call those challenging problems. Although why do you think they are "worst"? I think they are nice.
 » 4 years ago, # |   +2 Man I'm so slow, I can barely handle Div 2 questions, I have no idea what kind of mindset other experts pack, its like I'm from a different planet, it really hurts my feelings when I'm incapable of solving these supposed to be easy problems x_X
•  » » 4 years ago, # ^ |   +9 Think about guys who don't even try! You are at-least trying to solve questions and slowly you will be able to solve these questions! I joined CodeChef 4 months ago and I wasn't able to solve even a single question untill my 5th competition and here in codeforces I have not solved more then 1 question! So never lose hope!
•  » » » 4 years ago, # ^ |   +9 Thanks, I been here for 11 months but did not participate much due college and other things however I solved so far over a hundred problems, yet when it comes to real time events, I'm incapable of thinking clearly that it becomes frustrating, I guess its just a matter of time until I get the hang of it, tomorrow is my birthday Q-q , I'll make a wish to break this infernal limit!
•  » » » » 4 years ago, # ^ |   +1 Best of luck and Happy Birthday in advance! :)
•  » » » » 4 years ago, # ^ |   0 It is probably psychological then. Just try to approach it as a nice game. Do not treat it as a duty to perform well. Because as A. Einstein said, "Love is a better teacher than duty". I had the same problem for a long time (3 years), I was solving problems on USACO gold and solved some not so small portion of it, I was able to think of algorithms and code it when there was no pressure. However, I was making too much of a deal when it would come to real contests. Just let it flow, try to approach it with love and passion and you will be getting better :) Have fun!
•  » » 4 years ago, # ^ | ← Rev. 2 →   +8 I think your rating will be increase today... 1 problem solved.
•  » » 4 years ago, # ^ |   +8 Man, Don't feel bad, keep trying and practicing!
•  » » 4 years ago, # ^ |   0 You got your Birthday gift one day before see you ratings! :) :)Hope you will do much better tomorrow or the day after tomorrow contest! :)
•  » » » 4 years ago, # ^ |   +3 Unbelievable, I actually got points UP and saw a new message for the first time haha!!!! My jaws almost broke from over smiling - This is definitely the best thing happen to me over the past few months, even just for once seeing points going up is miraculous, I will no longer feel down, I will keep coding, I will code....FOR THE GLORY! - Thank you all for the encouragement!!! :D
•  » » » » 4 years ago, # ^ |   0 Even you got 145 points and I got 66 feeling jealous! ;) ;) (just kidding)
 » 4 years ago, # |   0 It was difficult to read solutions of guys from room, because they usually didn't appear, because of lagging, or appeared after a time.
 » 4 years ago, # |   +8 Test for A, where you need to get more than 1000 HP: 1 10 1 99 100 1 1 100 100 
•  » » 4 years ago, # ^ | ← Rev. 2 →   +5 Your test upgrade :)) 1 2 1 99 100 1 1 100 100 
•  » » » 4 years ago, # ^ |   0 Yeah, I stopped as soon as I got over 1000, because that was a constant in the code. I've also seen 2000 as a constant, but I don't think it's possible to create such a test.
•  » » » » 4 years ago, # ^ |   +3 I was too lazy to think tonight, so I checked hit points up to 100000000 using binary search:)
 » 4 years ago, # |   +23 first time ever I see myself on the first ranking page during the contestprobaly means that my solutions are wrong
 » 4 years ago, # | ← Rev. 2 →   +16 Oh man. Don't tell me everything is going to be delayed today. The contest started late. Now, the system test is pending. Later rating update will be slow. And finally we will see analysis after a week? lol. Feel like going to sleep (already 2 AM), but can't beat the curiosity to see what will happen to my rating. What a dilemma.
 » 4 years ago, # |   0 Why it didnt start evaluation?
 » 4 years ago, # | ← Rev. 2 →   0 Awesome problem set! I'm so gonna be red after this <3Edit: 2179 ._.
 » 4 years ago, # |   -21 It was very bad contest. CF was not available. It's better to unrated this contest
•  » » 4 years ago, # ^ |   -21 totally agree :)
•  » » » 4 years ago, # ^ |   0 I had a bad day, but this contest was good!! I'll never use printf, I promise :/!
 » 4 years ago, # | ← Rev. 5 →   -17 Too much Waiting for the system test.....
 » 4 years ago, # |   +4 But where is 277.75?.. :D
 » 4 years ago, # | ← Rev. 2 →   0 I have a doubt in problem A Div 2 what should be the answer of -5?? 3 or 13if you say 3 then why the answer of -1 is 9 and if you say 15 then OMG OMG I left more then 5 hacks and what I thought is that my solution is wrong which is giving me 13 on -5
•  » » 4 years ago, # ^ |   0 of course it's 13, it says such that, if he walks b floors ""higher"".
•  » » 4 years ago, # ^ |   0 For -5, its 13. You can only take "positive" steps. That means you can move forward and not backward.
•  » » » 4 years ago, # ^ |   0 but what about -11 when I solved it with 19 get a WA while solving this with 3 I got accepted! Wasn't it confusing?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 -11 + 3 (minimum) positive steps = -8-11 + 19 (not minimum anymore) positive steps = +8I hope its clear now.
•  » » » » 4 years ago, # ^ |   0 Look at 19 numbers starting -11.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 ok ok ok I got it! ;) :) :)Thanks for the help! :)
 » 4 years ago, # |   -9 Problem B: DIV2: I wrote my solution assuming that the inputs are ordered! After getting update, I had to come up with a complete new solution.The update came after almost one hour. Which means I took part in the round for only one hour instead of two! Will it be fair that the contest is rated for them who faced the same problem (Who misunderstood B and had to re think the problem for a while and rewrite the entire code)?
•  » » 4 years ago, # ^ |   +3 Same here! It was a completely new problem when they updated and my this round (which could really go well) went too bad! :(
•  » » » 4 years ago, # ^ |   +1 yea agree +1
•  » » » 4 years ago, # ^ |   0 the is are ordered but not the ai s
•  » » 4 years ago, # ^ |   +21 Well, that's not right. You weren't promised that inputs are ordered, so you're the only one to blame for that. The autor actually helped you (and me aswell :P), but honestly he didn't have to.
•  » » 4 years ago, # ^ |   +2 It is always advisable to not make assumptions until explicitly mentioned.
•  » » » 4 years ago, # ^ |   0 The description told that x1<=x2<=x3<=x4, missing some integers does not change the order! does it? Leave all other cases, my first solution was like : if a valid set(1,1,3,3) is shuffled(3,3,1,1) I as giving NO O.o . I thought they had to be satisfied x1<=x2<=x3<=x4 as well as other three conditions. Anyway , leave it. Those who has experienced problem setting knows that how difficult it is to make statement clear for all. But, I am a bit upset because the clarification took a long time to come, and the contest could be extended for 5-10 minutes.
•  » » » » 4 years ago, # ^ |   0 I could figure out that we would have to order the input in such a case as otherwise a median or range would not even exist if it was not ordered.
 » 4 years ago, # |   +5 How long it takes in system testings ?
 » 4 years ago, # |   0 Hello Everyone can anyone help on this ....http://codeforces.com/blog/entry/14789
 » 4 years ago, # |   +28 Time Limit Exceeded for System Testing :D
 » 4 years ago, # | ← Rev. 6 →   +37 Height of Revenge : akashdeep :D :D
•  » » 4 years ago, # ^ |   +15 Maybe you're wondering why your picture doesn't show. That's because you don't link to the picture itself, but a page that shows the picture. You need to link directly to the picture, or it won't work.
•  » » » 4 years ago, # ^ |   +1 Thanks :)
 » 4 years ago, # | ← Rev. 2 →   -7 .
 » 4 years ago, # |   0 Can't believe missed an endl in problem B when only 6 people solved it, and took me 1:53 to find the problem at last :(
 » 4 years ago, # |   +1 finally the system testing is started!!
•  » » 4 years ago, # ^ |   +21 and suddenly finished :D
•  » » 4 years ago, # ^ |   +2 It's time to change the color :D
•  » » » 4 years ago, # ^ |   +1 I hope I change mine too.
•  » » 4 years ago, # ^ |   0 and completed :D
 » 4 years ago, # |   -8 IMHO n=4 for C should have been in pretests. After all, it is just an ugly corner case with with hardcoded answer:(
 » 4 years ago, # |   +1 A contest full of hacks and failed system tests.
•  » » 4 years ago, # ^ |   +1 Indeed! Never seen another similar to this one
 » 4 years ago, # |   0 Why did D have a special limit of 10000 change queries? It can be solved in n*log(n), which works fine with 100000.
•  » » 4 years ago, # ^ |   0 Could you tell this solution?
•  » » » 4 years ago, # ^ |   +8 Segment tree with mappings. To answer a query, we go up the tree until the left node brings us to an edge or cycle, then down until we reach the bottom of the tree.
•  » » » » 4 years ago, # ^ |   0 Could you kindly give more detailed explanation about your solution? Thanks.
•  » » » » » 4 years ago, # ^ |   +3 We can express every row as a mapping from 0..9 to either a column 0..9, Left, Right or Cycle. Then we can build a segment tree on these mappings, where each node stores the composition of all mappings in the subtree (from right to left). After updating a row we simply need to update nodes on the path to the root (log(n) operations). To get the answer, we start in the leaf node corresponding to our row, then go up the tree, changing the current column whenever we go left. If we get Cycle, we output immediately. If we get Left or Right, we need to go down the tree to find the exact row where we left the table.
•  » » » » » » 4 years ago, # ^ |   0 Thanks, I got this idea already by scanning your code. I like idea of Segment Tree with mappings. Could you recommend other problems with this idea?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I misread the task and thought that all "<>^v" are possible and solved that version, 10000 constraint helped a lot.
•  » » » 4 years ago, # ^ |   0 Wouldn't that make it a lot more complex than simple sqrt decomposition, since you can go back and forth between chunks?
•  » » » » 4 years ago, # ^ |   0 You can do (maybe not so simple) sqrt decomposition on C type queries. For each 100 C type queries mark those cells as important and for each other cell calculate first important cell on it's way. Now when you have A type query you can just traverse through important cells (at most 100 steps, each time you move from important cell to it's successor (probably unimportant cell) and use precalculated data to go to next important cell) and when having C type just change corresponding char.
•  » » » » » 4 years ago, # ^ |   0 "for each other cell calculate first important cell on it's way" — how do you exactly handle that thing?
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Every 100 queries do a DFS, for every cell follow links until you hit an important cell or a cell you visited before.
 » 4 years ago, # |   0 Such a bloody Div.2 Contest! Congratulations to those who were able to correctly solve Div2 C :) And thanks for the nice problemset
 » 4 years ago, # |   +13 O(n) div. 1 B solution: 8791632
 » 4 years ago, # | ← Rev. 2 →   0 In Div #2 Problem B Candy Boxes it was mentioned "All your numbers b must satisfy inequality 1 ≤ b ≤ 10^6....."but the system doesnt check for 10^6 condition Example: the case1 999999the ans should beYES 333333 333333 999999but it also passess the solutionYES 999999 2999997 2999997
•  » » 4 years ago, # ^ |   +1 1 999999 isn't even a valid input! "(1 ≤ ai ≤ 500)"
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 1 <= ai <= 500
•  » » 4 years ago, # ^ |   0 yup... my bad
 » 4 years ago, # |   0 Got a rank of 185 by solving only Div2 A! 5 Hacks saved my day .
•  » » 4 years ago, # ^ |   0 And I left 5 hacks just because I thought my answer is wrong! :( :(
•  » » 4 years ago, # ^ |   0 158 place "A" and "C" ... "B" hacked :( Next time I'll take purple :D
 » 4 years ago, # |   0 Where can we obtain the editorial?
•  » » 4 years ago, # ^ |   0 Editorials has not been published yet. Once they are published, it will be updated in the main page
•  » » » 4 years ago, # ^ |   0 thanks
 » 4 years ago, # |   +3 Please explain why my solution get ML ? http://codeforces.ru/contest/487/submission/8791889
•  » » 4 years ago, # ^ |   0 You don't call "build" anywhere.. not sure why the ML though.
 » 4 years ago, # |   +5 Problems were very interesting, thanks!
 » 4 years ago, # |   -22 Despite my rating increased by 82 but I think this round has to be unrated I left the contest after about 45 min every time I make refresh I found no response I tried a lot of times to submit A but no response also at a moment I make refresh I submitted an old code for C and didn't manage to submit it again about 15 min. so I think it's unfair to make it rated unless it's a problem of mine Thanks
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 I didn't really face any problems during the contest, other than the contest problems of course :)
 » 4 years ago, # |   0 How to solve 487B - Strip?
 » 4 years ago, # | ← Rev. 2 →   0 After contest i got AC in B (div.2) despite my program would incorrectly print a solution for such corner case: 2 n n*3`(separated by newlines), but tests doesn't included it.
 » 4 years ago, # |   +3 already orange ))
 » 4 years ago, # |   +16 Why the author's solution produces different output in these two hacks: 125341 and 125632
•  » » 4 years ago, # ^ |   0 What is even funnier is that checker didn't accept lac of EOLNs (-_- ...) : 8783190, so that second answer of author's solution won't be accepted :pp.
 » 4 years ago, # |   0 Can anyone explaine me what is a monotonic queue (editorial)? Thanks x_x
 » 4 years ago, # |   +22 Country wise standings has been updated. Also I want to ask a question that how much beneficial is it to the community now and should I continue with it ? I ask this because I have to pay for the hosting from my pocket and it becomes a bit expensive to do it every month and it is going to end pretty soon.
•  » » 4 years ago, # ^ |   0 publish (user-friendly) ads through adsense or some other ad network
•  » » 4 years ago, # ^ |   0 I think it's really useful, thanks for the effort!
 » 4 years ago, # |   0 captain my captaini wonderwhy do you prefer this round to be at midnight? @saffah