Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### Monyura's blog

By Monyura, history, 5 years ago, translation, ,

Hi, Codeforces!

I am glad to announce Looksery Cup 2015, that is prepared by our developers, each one of them has made a great impact: Sfairat, olpetOdessaONU, Sklyack, MrDindows, Rubanenko, Krasnokutskiy, 2222, MaximM, Avalanche, Igor_Kudryashov, Kepnu4 and I. Special thank to coordinator Zlobober for the help with problems and advices and to Delinur for the translation.

We've prepared 8 problems for you, that will have random order at the contest. Round will last 2 hours 30 minutes under the standard Codeforces rules with smooth dynamic scoring. We hope, that you will enjoy competition, and we will receive small amount of clars :)

Top-200 competitors will get t-shirts with the handle at Codeforces:

Winner will get opportunity to have a prepaid trip to San-Francisco.

Besides, top-15 competitors will get Oculus Development Kit 2.

And competitors from 16 to 50 — gadget Ollie.

Also I would like to thank MikeMirzayanov and everybody, who works on Codeforces and Polygon — your contribution in education and IT is hard to be overestimated.

UPD. Round will be rated for both divisions.

Looking forward to seeing you tomorrow,

Looksery Inc.

UPD3. Editorial

UPD2. Rating will be recalculated today, but it could be changed a little till final results.

UPD. Round is over. Thank to everybody, who took part. Congratulations to winners! The final results will be announced in a day, after catching all cheaters. Current top-15:

Announcement of Looksery Cup 2015

• +1426

 » 5 years ago, # |   -269 Just a Suggestion :: Keeping say 150 Tshirts for top 150 Performers and 50 for the randomly selected ones from top 500 might be more ATTRACTIVE .
•  » » 5 years ago, # ^ | ← Rev. 2 →   +62 you got nailed dude..stop beleiving in luck :P
•  » » 5 years ago, # ^ | ← Rev. 2 →   -52 maybe randomly select one from top 500 for trip to San-Francisco. xDD LOL
•  » » 5 years ago, # ^ |   +250 Top-200 competitors will get t-shirts with the handle at Codeforces. Winner will get opportunity to have a prepaid trip to San-Francisco. Besides, top-15 competitors will get Oculus Development Kit 2. And competitors from 16 to 50 — gadget Ollie. Will you participate in this contest?!!
•  » » » 5 years ago, # ^ |   +9 very nice ;) I am with you
•  » » » 5 years ago, # ^ |   +12 What Do We Want?? Premium Rating System ... Premium Rating System ...
•  » » » 5 years ago, # ^ |   0 lol
•  » » 5 years ago, # ^ |   0 i'm agree with you . why minus?
 » 5 years ago, # |   +276 Can I ask for other words to be print .___.
•  » » 5 years ago, # ^ |   +7 You want "Sand Bag"?
•  » » 5 years ago, # ^ |   -10 Last thing we want to happen is people creating fake accounts to get T-shirts name of their choice
•  » » » 5 years ago, # ^ | ← Rev. 3 →   0 Please ignore this comment. It initially contained an incorrect argument. I thank kingofnumbers for correcting me.
•  » » » » 5 years ago, # ^ |   0 However, here if someone takes a top 200 place(or any other place for that matter) then had they participated with their official account they would have taken the same place so it should't really have any affect on anyone else. Well, you forgot that if they taken part with fake account then the rating of that account will increase more than if they taken part with their real accounts and this will make others get less higher ratings
•  » » » » » 5 years ago, # ^ |   0 Hmm. I was under the impression that ones rating change was only a function of ones position and ones initial rating but it turns out that was incorrect.Sorry about that.It would still be nice if people were allowed to have a choice in the text that got printed though.
•  » » » » » » 5 years ago, # ^ |   0 Nooo. Imagine two Div1 contests. One where 500 violets take part and one where 500 reds take part. Your possibility wouldn't make sense :P.
•  » » » » » » » 5 years ago, # ^ |   +1 Even though this comment is not relevant to the discussion but I would like to inform you that The rating calculation for unrated people is a little different . Unrated contestants have an initial expected rank of n / 2 where n is the number of people taking part in the contest. So in a contest consisting of 499 red coders and 1 unrated coder if the unrated coder gets a rank worse than 250 then his rating would drop.
•  » » » 5 years ago, # ^ |   +8 I guess here he was not referring to rating or anything.He just mentioned "to get T-shirts name of their choice"
 » 5 years ago, # |   +171 nice t-shirts !!
 » 5 years ago, # |   -90 Can you please give me the t-shirt for nothing :(
•  » » 5 years ago, # ^ |   +62 stop begging...start winning :P
•  » » » 5 years ago, # ^ | ← Rev. 2 →   -36 I am just trying to comment something funny but alas it becomes too funny to give up vote :D Thanx to Looksery and Codeforces team for that opportunity and prizes are very much tempting . Hope to have a great round with high rating everyone :) May the best win :)
 » 5 years ago, # |   0 MaximM is not orange anymore!
•  » » 5 years ago, # ^ |   0 That's probably because this blog was written a few days ago as a draft when he was orange. For example for round #299, I wrote the announcement blog as a draft when I was red and I remembered to fix it just when I was publishing it.
•  » » » 5 years ago, # ^ |   0 so the draft was made before round #300 (i.e before about 40 days) , why would one write the announcement before 40 days of publishing it?
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +3 Well, the announcement that the round was going to be held was made around 3 months ago so it is plausible that the draft for this post was written long ago too.
•  » » » » » 5 years ago, # ^ |   0 that blog wasn't an announcement , it was the reward of those who donate to CF with at least 450\$ (publishing a blog on the main page)
•  » » » » 5 years ago, # ^ |   +38 Or, Monyura did this to make this blog prettier and only use orange and red colors in it.
•  » » » » » 5 years ago, # ^ |   +10 I agree , the list of coders looks really pretty :)
•  » » » 5 years ago, # ^ |   +5 But Rubanenko was not red for quite some time, so it is in fact pretty old :P.
•  » » » » 5 years ago, # ^ |   +3 Perhaps that part was just copied and pasted from the original announcement, with the dates when they had such colors, and then edited a bit.
•  » » » » 5 years ago, # ^ |   +27 Didn't think I'll have to say it again :)
 » 5 years ago, # | ← Rev. 2 →   +96 Btw — 8 tasks and 2h 30 min :o? Overwhelming a bit. Either most of them will be very easy or people will not solve too many of them :P.
•  » » 5 years ago, # ^ | ← Rev. 2 →   -8 Just like round 300 and people managed to solve a lot of problems in it. Since it has problems for both divisions you need 7-8 problems to get a good spread.
•  » » » 5 years ago, # ^ |   +6 ... which definitely was not properly balanced...
•  » » » » 5 years ago, # ^ |   -8 Why? As long as you solve the first three problems in less than 30 minutes (most did) you got more time for the last five than in a normal div 1 round.
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   +16 That's not what "balanced" means. The gap in number of solutions between F and G was huge in comparison to all the remaining gaps between successive problems. That means clogging up of the many people who solved A-F.When there's a huge jump in difficulties, more time doesn't help at all. It just means much more people will solve F, while not so many more will also solve G.
•  » » » » » » 5 years ago, # ^ |   -8 How would removing problems help with that?
•  » » » » » » » 5 years ago, # ^ |   +9 "... which definitely was not properly balanced...""Why?"Well I explained why that round wasn't properly balanced. I guess the point is that many problems aren't enough to get a good spread, you need problems with well-spread difficulties to get a good spread.
•  » » » » » » » » 5 years ago, # ^ |   -8 Ah well, but 8 problems isn't too much for 2.5 hours at least since it would have been fine if G were like a normal D instead of a normal E.
•  » » 5 years ago, # ^ |   +5 See, there were no problem at all with this contest, most reds solved between 5-7 problems and the balance weren't poor either.
•  » » » 5 years ago, # ^ |   -7 "balance weren't poor either", hahahaha, very funny xD. All problem beside E and F were really simple. They took me all <=16 mins, while I couldn't get AC on F for 1,5h >_>. There was no typical "C" problem.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Even F wasn't that difficult, though it was one of those problems in which if you approached it the wrong way you'd have a lot of trouble, so it fit as the "slightly harder" problem.(Hint: it's easy to count how many valid (l, r) intervals cross a certain point M)
•  » » » » » 5 years ago, # ^ |   0 I know how to solve it, but couldn't code it properly :/.
•  » » » » 5 years ago, # ^ |   +1 You can't really call B and C easy...
•  » » » » » 5 years ago, # ^ |   0 B is piece of cake , while you find an index i such that the guess is true then invite i.the same problem already exist on codeforces but I'm lazy to search for it
•  » » » » » » 5 years ago, # ^ |   +1 B is piece of cake Yet it took you over two hours to get it...
•  » » » » » » » 5 years ago, # ^ |   0 I didn't read B in early time because of the low number of who solved B. but when I did I solved it immediately the constrains which guarantee that f[i][i]=1 for all i is a very big hint
•  » » » » » » » » 5 years ago, # ^ |   0 Just look at how many solved it, just because it is easy to code doesn't mean that the problem is easy.
•  » » » » » » » » » 5 years ago, # ^ |   0 I didn't say easy to code, I said easy idea and that hint led me to that idea
•  » » » » » » » 5 years ago, # ^ |   0 BTW, here is the problem link, B already exist on codeforces as I told you.
•  » » » » » » » » 5 years ago, # ^ |   0 So the point is that it is easy since you have seen it before?
•  » » » » » » » » » 5 years ago, # ^ |   0 it's easy because it's easy , I only remembered that it already exist later after I solved it
•  » » » » » » » » 5 years ago, # ^ |   0 Can you provide a link to the problem in contest page? Problemset is currently blocked.
•  » » » » » » » » » 5 years ago, # ^ |   0 I didn't think the block will continue for that long , here is another link anyway
•  » » » » » » 5 years ago, # ^ |   0 How can you prove its correctness? What if you invite all of them, but still one of the guesses is still true? What is the correct order of processing the guests?
•  » » » » » » » 5 years ago, # ^ |   0 you only invite person i whenever the guess him is currently correct so when you invite person i the number of messages he will receive will be more by one than the guess so it will never happen again that the guess about him is correct.so if I had to invite all of them then I am sure that the number of messages each one of them have got is bigger than the guesses.also the order or inviting is not important
•  » » » » » » » 5 years ago, # ^ |   +3 For any set of invited people, among all people where Igor guessed correctly, call the one with the lowest ID as guilty.Now, start with the empty set of invited people; call this an invitation set. As long as there is a guilty person, invite that person as well, and call the resulting set of invited people as another invitation set. If there is nobody that's guilty, invite a random person. We keep doing this until all people are invited. This forms several invitation sets; to be precise, there are n + 1 of them, one of each of size 0, 1, 2, ..., n. We claim that at least one of these possible sets are free of guilty people.Note that each person A can only be guilty in one set; at the first moment A is guilty, A is immediately invited into the party, and thus the number of messages that A receives exceeds Igor's prediction. Since this number will never decrease (we never reject an invited person), A will always get more messages than Igor's prediction afterwards, so A will never be guilty any more.However, there are n + 1 invitation sets in total, but only n people that can be guilty. By (generalized?) Pigeonhole Principle, one of the sets will be free of guilty people. This is the set we want.To make it constructive, instead of picking a random person when there's no guilty people, stop and take that set instead; we are guaranteed to stop for the same reason as above. This is the basis of my submission.
 » 5 years ago, # |   0 combined division again, what are the chances to be one of the top 200 :P
•  » » 5 years ago, # ^ | ← Rev. 2 →   +6 I'm more interested in how high the chances to get +200 are. Also chances to get +400 and +600. With this number of participants and a combined round...
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +52 We have 737 red coders now, let's wait and see how will this number change tomorrow :)P.S. And also 46 people with IGM, let's also check this one after round.
•  » » » » 5 years ago, # ^ |   0 Opps, Red Alert!!
•  » » » » » 5 years ago, # ^ |   +8 743/48, not so bad. Did they finally resolved issues with inflation? :)
•  » » » » » » 5 years ago, # ^ |   +8 Oh, you made my day! I thought I had become red (for the first time) just because of rating inflation :')
 » 5 years ago, # |   -61 IS THE CONTEST RATED?
 » 5 years ago, # |   -6 Someday, I would try to win the 1st prize. Till then I would concentrate on improving
 » 5 years ago, # |   -62 The First Law of Online Judges :- For every problem there is a solution which is simple, fast, and wrong !! :D
 » 5 years ago, # |   +13 Wow, eight problems! I think many hacks will be in this contest.
•  » » 5 years ago, # ^ |   +4 unfortunately your comment has been hacked :D
•  » » » 5 years ago, # ^ |   +11 If I stay in the same room with you today, I will hack you :D
•  » » » » 5 years ago, # ^ |   -10 Unsuccessful hacking attempt :P
 » 5 years ago, # | ← Rev. 2 →   +1 I love green and also the codeforces logo :)
 » 5 years ago, # |   0 I don't love green T-shirts anyway .
•  » » 5 years ago, # ^ |   0 If you really don't like green then First change your rating color to some other color and that's depend on you which side u choose for changing color :P
•  » » » 5 years ago, # ^ |   0 I wish I could change it to anything other than grey. :D
 » 5 years ago, # | ← Rev. 3 →   +219 By the way, I have a feeling that this needs to be explicitly expressed by someone — I think that this contest has the best prizes on CF ever! There are 200 (!!) T-shirts and they are personally signed (!!). I don't know what these Oculus Development Kit do (and don't have time to delve into it), but they look cool and valuable. And these thingies to people from places 16-50 looks completely useless but amazingly funny, which makes me consider whether I should do some unsuccessful hacks if I will see that I have chances for being in TOP15 :3
•  » » 5 years ago, # ^ |   +127 "makes me consider whether I should do some unsuccessful hacks if I will see that I have chances for being in TOP15 :3" #justgrandmasterthings
•  » » 5 years ago, # ^ |   +27 Thanks for the clarification Swistakk – before reading your comment I thought that "competitors from 16 to 50" means people aged between 16 and 50, which raised a lot of questions :)
•  » » 5 years ago, # ^ |   -16 makes me consider whether I should do some unsuccessful hacks if I will see that I have chances for being in TOP15 :3Consider this case: You are in top 15, you attempt some unsuccessful hacks on purpose to be in 16-50. In system testing one of your solution fails and you are not in top 50 anymore. Then you notice without that unsuccessful hacks you would be in top 50.This case is very sad. And if something like this ever happens to me, I'll say goodbye to competitive programing for good.
•  » » » 5 years ago, # ^ |   +8 Yeah, that was rather just joking :P. Btw saying goodbye to CP because of such a reason would be pretty stupid xD.
•  » » » 5 years ago, # ^ |   0 If such case happens, CP would say good bye to you
 » 5 years ago, # |   -27 Can I ask how many problem in this contest ?
•  » » 5 years ago, # ^ |   +1 8
•  » » » 5 years ago, # ^ |   +5 Thank you ^^
 » 5 years ago, # | ← Rev. 2 →   +28 340 red coders registered to contest. No chance for experts
•  » » 5 years ago, # ^ | ← Rev. 2 →   +78 Never give up! Impossible is possible!!
•  » » 5 years ago, # ^ |   +8 If someone can win, then you can also win. Always be optimistic.
•  » » 5 years ago, # ^ |   +7 there was never
•  » » 5 years ago, # ^ |   +10 see there is an expert under 200 rank in final standings :)
 » 5 years ago, # |   +6 The time is rarely suitable for coders in China. :) PS. The College Entrance Examination will start tomorrow morning. Good luck! God bless us!
 » 5 years ago, # |   +7 Today's contest is a big opportunity for Div2 participants to become members of Div1.
•  » » 5 years ago, # ^ |   0 how ?
•  » » » 5 years ago, # ^ |   +5 If you do better than Div1 contestants, you'll get a lot of rating.
 » 5 years ago, # | ← Rev. 4 →   +3 So great t-shirts *-*
 » 5 years ago, # |   -10 expecting unusual rating changes in this contest like: Specialist -> Candidate Master; Expert -> Master ; Candidate Master -> International Master, etc.
•  » » 5 years ago, # ^ |   +7 And suddenly International Master -> Specialist. The most unusual, I think.
•  » » » 5 years ago, # ^ |   0 Generally in div 1 + div 2 contests maximum +ve rating change is around +400 but maximum -ve rating change is only around -135. So I don't think you are correct. :P
 » 5 years ago, # |   +10 I'm going to be on airplane during contest time..But airplane has (unstable) wifi..Not sure if I should participate..
•  » » 5 years ago, # ^ |   +3 You should try!
•  » » » 5 years ago, # ^ |   -13 You should catch!
•  » » 5 years ago, # ^ |   +4 Create fake account xD
•  » » » 5 years ago, # ^ |   -12 Well sure I could do that, but then how to avoid following conversation: GF: Wow, you won Looksery T-shirt Me: (put some cute sentence here) GF: Wait, where is "I love Hoang Yen"? :-O (of course there's option like creating account I_love_Hoang_Yen_2, but it would be too obvious :)))
•  » » » » 5 years ago, # ^ |   +36 You could have created an account "I_love_cutest_girl_in_world" and tell her that it is obvious that is about her, nobody will have strong suspicions about you and that T-shirt would be more 'universal' :pp. That means that it won't become out-of-date whatever the future will be xD.
•  » » » » » 5 years ago, # ^ |   +17 Do you think that such lame trick can not be seen through by the eye of a girl? :p
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 I_love_you written t-shirt would be nice present to your girlfriend...
 » 5 years ago, # |   +88 tourist began preparing to travel to San Fransisko. ;)
•  » » 5 years ago, # ^ |   +50 With his Tourist written t-shirt. He is really tourist in San-Francisco xD
 » 5 years ago, # |   0 The worst thing about random order is trying to find the "A" problem at the very beginning. But today I have a secret weapon: https://www.random.org/
•  » » 5 years ago, # ^ |   +18 Now it's not secret anymore :Pseriously speaking, I will tell you my strategy in such situation you might like it:I open all the problems, then I read shortest problem statement first then second-shortest and so on until 10 minutes after the starting time I open the dashboard to see if some problems are solved if yes I read them then I solve them until I finish solving them ,the difficulty of the problems will be revealed.
 » 5 years ago, # |   +3 that will have random order at the contestPainful :((
 » 5 years ago, # | ← Rev. 2 →   -11 scoring dynamic? ):random problems? ):I think that Problem D is the easiest problem in this contest (:
•  » » 5 years ago, # ^ |   0 And that's because... ?
•  » » » 5 years ago, # ^ |   0 because I am lucky (:
•  » » 5 years ago, # ^ |   +51 Oh, don't make us to reshuffle them again!
•  » » » 5 years ago, # ^ |   +5 Ok (: I'm sorry
 » 5 years ago, # |   +3 Hello everyone !!I hope high rating and good luck for everyone.I have a question .I have heard a lot of people said when the two division participate together is easier will have a high rating.Why ??? Anyway I thank for you answer in advance!!
•  » » 5 years ago, # ^ |   -8 We simply want more people to have high rating ;)
•  » » 5 years ago, # ^ |   +1 2 reason i think (at least for div2 participant) : 1. less "strong" unrated coder will participate (iykwim) 2. div2 participant can defeat div1 participant which can gain more rating
 » 5 years ago, # | ← Rev. 2 →   +11 Does random order mean that it is shuffled by a computer and is completely random or are they put in an order developers want them to be?
•  » » 5 years ago, # ^ |   +22 Sometimes developers' decisions are more random than the computer's ones
 » 5 years ago, # |   0 Random Order!! Sounds Fun 4 Div 2's!! Tnx Looksery :))
 » 5 years ago, # | ← Rev. 3 →   +4 some random t-shirts for us peasants would be much appreciated :)
 » 5 years ago, # |   0 finally 5808 registrants :)
 » 5 years ago, # |   0 Can you delay contest 5 min to allow for more registrants?
 » 5 years ago, # |   0 happy coding :)
 » 5 years ago, # |   +13 I love the prizes! GL & HF to everyone!
 » 5 years ago, # |   0 hey guys look at unknownuser96 in room 118 link
 » 5 years ago, # |   0 Iranian and North korean just used their nuclear weapons today , great preformance .
 » 5 years ago, # |   +46 (╯°□°)╯︵ ┻━┻
 » 5 years ago, # |   +1 D problem author,great problem, like!
 » 5 years ago, # |   +7 Hard would be an understatement , at least for poor coders like me
 » 5 years ago, # | ← Rev. 2 →   +6 How is C solved? I could only think of a O(N 2) DP solution with O(N) space complexity.
•  » » 5 years ago, # ^ |   +5 A lot of casework. Whoever goes last will generally win, unless it is possible for Daenerys to burn all the towns with odd number of residents, it is possible for Daenerys to burn all the towns with even number of residents and k is even, or it is possible for Stannis to burn all the towns with even number of residents and k is odd. Unfortunately, there is also the sad final case of n=k, in which case nobody gets a turn and so there is no "going last"; in this case answer simply depends on number of towns with odd number of residents.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +12 Do it in O(1). There's a categorization (although not really simple) based on the number of cities with odd/even populations (called odd, even respectively), something like this (not sure, though): If n = k, the game has ended, just count the number of cities with odd populations. If , Daenerys always wins; Daenerys always bombs an odd city. If (but not the above), the winner depends on (it's Stannis if odd, Daenerys if even); the winner always bombs an even city. If none of the above applies, the winner depends on (that is, the number of moves; again, Stannis if odd, Daenerys if even); the winner plays the city opposing the previous move, to guarantee that he has a choice for the final move.
•  » » » 5 years ago, # ^ |   +62 I hate the case n = k. Found it as challenging, killed two solutions, but mine is still wrong. Stupid problem, a lot of points and much more stupid bug. :(
•  » » » 5 years ago, # ^ |   +24 Unfortunately, there is also the sad final case of n=k"Sad" is very polite word for this case :)
•  » » » 5 years ago, # ^ |   0 Would you please explain your third case?How does it is depending on the pairity of k?
•  » » » » 5 years ago, # ^ |   0 If all even cities can be destroyed by one player, then all remaining cities are odd; there are exactly k of them. By checking the parity of k, we can check which player should destroy the even cities; if k is odd, then Stannis should destroy them (and Daenerys can't do anything to prevent that), while if k is even, it's the other way around.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +13 Just coded stupid O(n 2) solution to see patterns and then checked clever O(1) solution by the stupid one.upd. Too bad, it failed. But I think the right approach should be like this.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Call the number of odd houses is odd, and the number of even houses is evenIf Stannis can burn all the even houses before the game end, he can force Daenerys to burn only the odd houses in later move (after all even houses run out), and if the number of odd houses after the game is odd, he will win. The condition to do this is (n-k+1) div 2 >= even and odd-(n-k-even) mod 2 = 1.If Daenerys can burn all the odd houses before the game end, he will always win. The condition to do this is (n-k) div 2 >= odd.In all other case, the person who end the game is winner. Why? Because in all move (except the final), the players can make opposite move to each other (if Stannis burn odd house, Daenerys will burn even house and vice-versa). And the player who do the last move can just perform the move that give him victory.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +16 I solved that with DP , state is player , CitiesToBeDestroyed , RemainingOddCities Note that RemainingEvenCities can be omitted since it can be drived from the other parameters .Till now it is O(N*N) , since both players will play optimally and each one of them will try to cancel each other move , I removed x odd city & x even city & 2 * x CitiesToBeDestroyed before calling the DP ( left at most 128 for the DP to figure out a solution )Thus it will be O(N * 128)Take a look at my solution 11465922
•  » » » 5 years ago, # ^ |   0 BTW , I got WA on pretest because of a logical mistake , so I increased the factor when I was debugging . 128 is too much (8 is enough to get AC) ==> O(N*8)
•  » » » » 5 years ago, # ^ |   0 Can you please explain more on how you came to the intuition that you can remove x odd cities and x even cities before calling the DP(leaving at most 128 for the DP to figure out a solution) ?
 » 5 years ago, # |   +2 KareemMohsen and MG2033 submissions for last round look suspicious.P.S. It's impossible to view these submissions until the end of contest, but I was in the same room with them and
 » 5 years ago, # |   0 Anybody solved D with fenwick tree ? I couldn't.(
•  » » 5 years ago, # ^ |   +16 I don't understand problem D ! I work my tasks about 1 h ( first 10 minutes and last 50 ), all other time I spent for reading D.
•  » » 5 years ago, # ^ |   +5 Optimal solution is O(n * m)
•  » » » 5 years ago, # ^ |   0 I will cry now (. What was the solution for D?
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +8 Let b[x][y] be 1 if (x,y) is 'W', -1 if it is 'B', 0 if out of bounds.Increase answer by one for every (x, y) in board such that b[x][y] != b[x+1][y] + b[x][y+1] — b[x+1][y+1].
•  » » » » » 5 years ago, # ^ |   +3 why? please explain more ...
•  » » » » » » 5 years ago, # ^ |   +11 Every rectangle with bottom-right corner (x,y) is added a number of times R x, y to the final answer (it might be 0 if we never use it). Because you're only doing linear operations, the final answer for any sum of rectangles is C x, y * a x, y, where a x, y is the value on the board at position (x,y) and C x, y is the sum of R x, y for all rectangles that contain (x,y).But how can we calculate C x, y easily? Well, except for the rectangle with bottom-right corner (x,y), all rectangles that influenced (x,y) are the ones that influenced either (x+1,y) or (x,y+1). To eliminate double-counting, remove the ones that influenced both (x+1,y) and (y,x+1): the ones that influenced (x+1,y+1). Our final result is: C x, y = R x, y + C x + 1, y + C x, y + 1 - C x + 1, y + 1. To get the sum we're looking for, we want final C x, y to be equal to b x, y for every (x,y), so from the earlier equation R x, y =  - b x, y + b x + 1, y + b x, y + 1 - b x + 1, y + 1.After you calculate all R x, y, count the ones that are not zero, and that's your answer.
•  » » » » » » » 5 years ago, # ^ |   0 Is this based some kind of standard method? I'm trying to understand why this problem was solved by so many.
•  » » » » » » » » 5 years ago, # ^ |   0 O(n^2*m^2) algorithm was enough for this problem.
•  » » » » » » 5 years ago, # ^ | ← Rev. 3 →   0 I used a similar method. For cells not lying on the right or bottom border, I considered all cases in which that prefix rectangle would be used atleast once (how many times, does not matter as we can just multiply the required integer, after using it once). It will always be used unless its right, bottom and bottom-right cells are similar to it or exactly two of them are different and are adjacent.For the bordering cells (right or bottom border) they would be used if they are not equal to adjacent cell on the border.Please look at my submission for a better understanding. Solution complexity if O(n*m).11473484
•  » » » 5 years ago, # ^ |   +6 My solution is O(N 2 M 2). I think 2D Fenwick Tree is unnecessary since N 2 * M 2 ≤ 108
•  » » » » 5 years ago, # ^ |   +3 Please explain your approach.
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 The same here.Init sum for every pos as 0.Iterate for every cell from bottom-right corner to top left corner.If our mask at this pos == 'W' && sum for this pos != 1:sum of every pos from this to top left corner += 1 — d[i, j]result++If our mask at this pos == 'B' && sum for this pos != -1:sum of every pos from this to top left corner += — 1 — d[i, j]result++
•  » » 5 years ago, # ^ |   +3 i was unsure whether O(n^2*m^2) would pass. hence i implemented an O(n^2*m) solution.
 » 5 years ago, # | ← Rev. 2 →   0 Why O(255025000000) operation is not TL ? 11473557
 » 5 years ago, # | ← Rev. 3 →   +24 Was Problem E just this paper? Here
•  » » 5 years ago, # ^ |   +3 Your link seems to be broken.
•  » » » 5 years ago, # ^ |   +5
•  » » » 5 years ago, # ^ |   0 Oops, it converted one of the backslashes into 2 backslashes. Fixed.
•  » » » 5 years ago, # ^ |   0
•  » » 5 years ago, # ^ | ← Rev. 2 →   +29 That paper seems much stronger than what we need. Also, it seems it may be numerically instable, and also seems a bit hard to implement.I believe there's a way to do this using only integers, though the implementation is still very tricky since there a lot of special cases. My approach was to make the points (x,y,x*x+y*y), then find whether or not these two sets can be separated by a plane. This involves checking whether or not the two 3d convex hulls intersect. The implementation is made slightly simpler by allowing quadratic solutions. Unfortunately, there are a lot of degenerate cases when things are coplanar, and I wasn't able to deal with all of those in time. EDIT: Actually, the paper seems to talk about my approach in section 4. Should have read it a bit more carefully.
•  » » 5 years ago, # ^ |   0 I tried to compute the smallest enclosing circle for both sets and check if the other points lie outside this circle but I got wrong on #10. Is this even correct?
 » 5 years ago, # |   +6 Interesting problems . Thanks for good contest .
 » 5 years ago, # |   +150 I understand you want to introduce your company's work in the statements. But WTF was problem D's statement?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +31 I agree with you, THe problem D was very difficult understand I needed more than 45 min in order to understand MY english is bad I think that was that. but is the first time that happened this. did Someone have the same problem??
•  » » » 5 years ago, # ^ |   0 English does not matter, I understood the problem and sample test cases after reading for 30 mins, yet I could not solve it
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +1 I spent 30 min trying to understand the statement and the result I didn't , spent 2 mins to understand the problem from sample explanation .
 » 5 years ago, # |   0 Hoping for a systest miracle: for enough people to fail for 278th to get to top 200
 » 5 years ago, # |   +117 Winner is from North Korea. Hmmm... Congratulations to vepifanov with a trip to San-Francisco. :P
•  » » 5 years ago, # ^ |   +6 winner is tourist :D
•  » » 5 years ago, # ^ |   0 sure
 » 5 years ago, # |   +49 How to solve H? I've spent literally the whole contest on it :( Still getting WA#4, and I have no idea why.
•  » » 5 years ago, # ^ |   +11 overflow
•  » » 5 years ago, # ^ |   0 me too :(
•  » » 5 years ago, # ^ | ← Rev. 2 →   +17 Binary search; when you have fixed some answer, you have intervals of possible values for a,b,c,d in matrix B. From those invervals you can get invervals for values of ad and bc. Now you only need to check them for intersection.
•  » » » 5 years ago, # ^ |   0 Now you only need to check them for intersectionWould you please explain it?In this problem, how can I tell from the values of ad and cd that our current answer is valid? I don't understand it.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +8 Assuming answer is equal to X, you can pick any value in range [A-X,A+X] (I denote values of original matrix by A,B,C,D here) for a and any value in range [D-X,D+X] for d. This gives you some range [L1,R1] for possible values of product of a and d. By picking proper values for a and d in your new matrix you can reach any resulting product from that range. In the same way you can get range [L2,R2] of possible values for product of b and c. You are interested in picking such values for a,b,c,d that ac-bd=0, therefore ac=bd, which implies that [L1,R1] and [L2,R2] have a common point. I hope my code (11475874) is clear enough.
•  » » » » » 5 years ago, # ^ |   0 Yep got that. I was trying to make the matrix B. That was my mistake.Thanks.
•  » » 5 years ago, # ^ |   +3 Yup, same situation. I figured out how to solve it if (a+b+c+d)=/=0, but then got stuck. Really frustrating when you see the number of people that solved it...
•  » » 5 years ago, # ^ |   +5 I feel your pain... Spent whole contest on H, in the end I ended submitting random calculations until this passed pretests, but I have absolutely no idea why: for (int bs = -1; bs <= 1; bs += 2) { for (int cs = -1; cs <= 1; cs += 2) { for (int ds = -1; ds <= 1; ds += 2) { if (bs*cs == ds) { long long den = -a + bs*b + cs*c - ds*d; if (den != 0) k = min(k, fabs((a*d - b*c) / (double) den)); } 
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 I can't understand why this works. My solution had 8 cases:1) (a+x)(d+x)=(b+x)(c+x);2) (a+x)(d+x)=(b-x)(c-x);3) (a+x)(d-x)=(b+x)(c-x);4) (a+x)(d-x)=(b-x)(c+x);5) (a+x)(d-x)=(b+x)(c+x);6) (a-x)(d+x)=(b+x)(c+x);7) (a+x)(d-x)=(b-x)(c-x);8) (a-x)(d+x)=(b-x)(c-x);This solution don't work. But when i sent just first 4 cases have AC.Why?Example, 5th case: ad-bc=2*sqr(x)+x(b+c+a-d), when discriminant>=0 we can find new answer. If I am wrong please explain, all the time I spent on this task.UPD when Discriminant > 4*(10e18) my solution broked.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 My solution worked with above 8 cases.. I was trying to do the same during contest..but forgot to add the case of 0. After contest i added the case to handle 0 and got accepted.
•  » » 5 years ago, # ^ |   0 I am not positive this works but basically binary search. The truth condition is if by changing each of the elements by this much you can get the opposite sign of the determinant. Maybe this fails somewhere but I don't think so.
•  » » » 5 years ago, # ^ |   0 Idea was correct, but WA50 because of precision issues I think. Rewrote it with BigDecimal and now it works. Lesson learned I guess.
•  » » 5 years ago, # ^ |   0 Me too. ;-(
•  » » 5 years ago, # ^ |   +3 I suspect that there might actually be a simpler solution to this. Note that in the samples, for B each element differs by the same amount from its corresponding element in A (that is, |1.2 - 1| = |1.8 - 2| = |2.8 - 3| = |4.2 - 4|). I tried proving it, although I don't think it was rigorous or even worked. However, if it holds, then it's just checking 24 cases: add or subtract a number t to each element in A (that's where 24 comes from), compute its determinant (a quadratic expression in t), and find its solutions. Take the one with minimum magnitude among all found solutions.
•  » » » 5 years ago, # ^ |   0 I can't prove it, but I can say that (with this testset) it worked, since that's exactly the approach I took. See 11469632.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +3 Yes, I also used the same approach and passed.The idea is that if we fix the top row of the matrix B to be x, y, we know the bottom row is in the form xt, yt for some t; since the graph of is a polyline (several line segments/rays joined together), the minimum must be found at an intersection, where |c - xt| = |d - yt|. Generalizing that this must happen to all the elements at the same time is the shaky part.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Did it work?
•  » » 5 years ago, # ^ |   +9 Check my O(1) solution for H. I just tried all the possible combinations of +x or -x at all the places of the matrix. SOLUTION
•  » » » 5 years ago, # ^ |   +1 Can u plz explain ur solution in detail. Sorry for inconvenience.
•  » » » 5 years ago, # ^ |   0 explain plz?
•  » » » 5 years ago, # ^ |   0 For the record, here is another constant-time solution for H, except that it relies on arbitrary-precision arithmetic to get the accuracy to 1e-9: 11493234The explanation is based on similar thinking to the editorial, treating the matrix as two vectors. After drawing some pictures, we need to find a line passing through the origin (i.e. this is the degenerate matrix B) such that the distances along diagonal lines from the the vectors to this line are the smallest possible (i.e. the largest of them is minimised). Diagonals are usefully dealt with by rotating 1/8th turn, then it becomes a matter of dropping down vertical lines from the vectors onto a line of the form y = mx. And the rest are details.But I'd really like to know if there is a simple reason why prateek_jhunjhunwala's solution works, or is it just a coincidence?
 » 5 years ago, # | ← Rev. 2 →   +3 How to solve problem D? Is it possible to solve O(n*m) is the optimal solution?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +3 Yep it's possible to solve in O(n*m). Though I 've solved it after Contest. my O(n*m) solution 11478809 . you just do not need to update the whole prefix rectangle. :)
•  » » 5 years ago, # ^ |   +3 How did you came up with O(1) solution of pH ? will explain it for me ?
•  » » » 5 years ago, # ^ | ← Rev. 4 →   +27
•  » » » 5 years ago, # ^ | ← Rev. 7 →   +7 or here You can also see my code 11506983
 » 5 years ago, # |   +3 Congratulations I_love_you ! will be nice t-shirt with this handle ;)
 » 5 years ago, # |   +3 Test is ended. Please give me good score~~~
 » 5 years ago, # |   +90
 » 5 years ago, # | ← Rev. 2 →   +39 THe problem D was very difficult understand I needed more than 45 min in order to understand MY english is bad I think that was that. but is the first time that happened this. did Someone have the same problem??
•  » » 5 years ago, # ^ |   +4 I finished problem A then spent the rest of the contest trying to understand D, I jumped to some other problems as well but since so many people were finishing D I kept going back to it.Still don't know what it was asking for O_o
•  » » 5 years ago, # ^ |   +3 Now, I don't understand problem :)
 » 5 years ago, # |   +166 Seems like RNS hadn't even tried to pretend to be single person. 2 submits in the very same second, 2 accepted within 14 seconds of each other...
•  » » 5 years ago, # ^ |   +13 Also the two neighbours submissions have pretty different amount of includes...
•  » » 5 years ago, # ^ |   +20 I think I've read somewhere before that they are a team from Korea always participating together.I wonder what they are going to do with the tshirt. smh
•  » » » 5 years ago, # ^ |   +22 I do believe in integrity of Codeforces contests enough to be sure there would be no T-shirt for them
•  » » » » 5 years ago, # ^ |   +122 We're aware of this "user", this won't be left unpunished.
•  » » » » » 5 years ago, # ^ |   0 And his name is nowhere in the rank list. Faith in codeforces restored (not that it was ever shaken)!!
•  » » » » » » 5 years ago, # ^ |   0 it's because two of their solutions failed system test
•  » » » » » 5 years ago, # ^ |   +24 I feel like having a big banner on CF home page saying "NORTH KOREA DOES IT AGAIN: ANOTHER SHAMEFUL CHEATING ATTEMPT FROM NORTH KOREAN STUDENTS" would be a more appropriate punishment than hiding them from the leaderboard.
•  » » » » » » 5 years ago, # ^ | ← Rev. 3 →   +41 I think that that kind of generalization would be too racist.
•  » » » » » » » 5 years ago, # ^ |   +10 Suppose Brazil U20 wins the World Cup 3 times in a row. The day after the 3rd final you open the newspaper and it says "Brazil does it again: another amazing performance from Brazilian youth". Does it sound a racist generaliazation?
•  » » » » » » » » 5 years ago, # ^ |   +5 You can't say it's shame on all north korea coders just because one of them cheated
•  » » » » » » » » » 5 years ago, # ^ |   +13 It was definitely more than 1 though.
•  » » » » » » » » 5 years ago, # ^ | ← Rev. 4 →   0 Your example is just silly. It doesn't sound like a racist generalization because it isn't. One might claim that usage of "Brazil" and "Brazilian youth" is a generalization since it's actually only a team who've won the cup, not the whole country/nation. But it's wrong because that is their national team we're talking about. That sentence congratulates the whole country because the team that represents them have won. It's totally different than blaming a whole nation based on limited observation. I think you should consider what you've said before and try to be less offending.
•  » » » » » » » » » 5 years ago, # ^ |   0 I do not understand your argument. You were happy with Brazilian headline. Now I went ahead and replaced Brazil with NK, the phrasing referring to the act of stellar performance with the phrasing referring to the act of shameful cheating, and Brazilian youth, that represented the team, with NK students, that represented the NK lab behind the user.
•  » » » » » » » » » 5 years ago, # ^ |   +9 I still think that my argument is clear, but I will try to put it in other words just to be sure:There are 10 people in a room.First case: Some person steals something from me. Then, I come to conclusion of every person in that room is a thief.Second case: I want someone to play ping pong with me, that's why I go into that room and ask them to chose a representative player for their room. They choose the player. I play with that player. He wins. I congratulate the room.The important thing to notice is: I'm not saying everyone in this room can beat me. I'm just saying that this room has defeated me. In the second sentence, "the room" actually refers to the player that represents its room.First case is a generalization. Second one isn't. It's not related to action's morality or something. It's just that these examples are different. Trying to compare them is absurd.
•  » » » » » » » » » 5 years ago, # ^ |   +22 Now I realize you probably don't possess all the information. This is not the first or second case of a user claiming to be from North Korea being in the top through obvious cheating (code strongly resembling other NK user's code) or less obvious suspicions (submits for different problems within seconds of each other, different coding style, etc). Sometimes they get punished (like on Rockethon this year), sometimes they don't (there was a long discussion on Codechef sometime ago about a Long contest, not sure what happened in other Long contests). I haven't encountered a single case of NK user in the top that resembled an honest result. (I believe there are links pointing to some of these occasions in comments around here so you can check for yourself.)Hence analogy to your example would be -- every time I see a user from that room coming out, he is stealing something. And I come to conclusion that that room is full of thieves.
•  » » » » » » 5 years ago, # ^ |   +6 Hiding them from leaderboard doesn't prevent us from something like you've described. The cheating issue is much more general and complex than just punishing separate users that get too high in the leaderboard. Also that would be not fair to say that the worst cheaters are from North Korea, there are many other countries with high amount of cheaters...
•  » » » » » » » 5 years ago, # ^ |   0 North Korean cheaters are the only ones I've seen hailed in internet media (I am referring to NK press making news out of their 'victories' in online contests). I suspect they wouldn't continue this blatant cheating if they got publicly scolded once.
•  » » » » » » » » 5 years ago, # ^ |   0 I think they wouldn't care. It's like they're cheating for the sake of cheating, being that obvious.Not a big banner highlighting someone, but a Hall of Shame (in a sufficiently non-annoying manner) for all cheaters would be appropriate.
•  » » » » » » » » » 5 years ago, # ^ |   0 They were quite obvious at Codechef contests too, yet Codechef chose not to ban them. They are actually posting news about results of those contests to show how advanced their university is.
•  » » » » » » » » » 5 years ago, # ^ |   0 Mhm, I wonder why Codechef did what they did. My guess is negligence, but being threatened is also a possibility.You can't stop propaganda, anyway. If they didn't win any contests, they could outright lie.
•  » » » » » » 5 years ago, # ^ |   +19 I wonder if Korean students are really aware that they are participating not in a team competition?
•  » » 5 years ago, # ^ |   +28 Why should they ? The believe these are team contests.. :P Here Here
•  » » » 5 years ago, # ^ |   -6 That's hilarious! "Chinese team ACRush working for Google in Washington"
•  » » 5 years ago, # ^ |   +20 Is that all the proof you have?I'm pretty sure I've had 2 accepts in 14 seconds at some point in some contest. You give up on debugging a problem, do something else, go back to debugging the first one and find the bug immediately.Also, if the internet connection is down, you'd continue solving things and then submit 2-3 solved problems at the same time when you're able to submit.
•  » » » 5 years ago, # ^ |   +29 I do not want to go deeper into 14 seconds delta, but non trivial submits on different problems in the same second?
•  » » » » 5 years ago, # ^ |   0 I explained it. Connection comes back up, you submit 2 things you solved during downtime. Some random lag causes the first submission to delay by 2-3 seconds, so it looks like the same second instead of 5 seconds difference.
•  » » » » » 5 years ago, # ^ |   +24 While using different templates for different problems
•  » » » » » » 5 years ago, # ^ |   0 That is slightly strange, but still not proof. For example, when a problem requires maxflow, I copypaste some code that I wrote years ago, using a completely different coding style and different macros.
•  » » » » » » » 5 years ago, # ^ |   +66 There ought to be a moment when you stop multiply small probabilities and say that something that walks like a duck and quacks like a duck is a duck. Besides admins can check you theory about disconnect by looking into logs
•  » » » » » » » » 5 years ago, # ^ |   +6 Obviously it looks 99% like what you're saying, but you have to give an extreme amount of "innocent until proven guilty", since false positives are quite terrible.
•  » » » » » » » » » 5 years ago, # ^ |   +21 No, it looks maybe 99.9999% like what you're saying. The chances of getting 2 submits on the same second are already extremely low — it's never happened to me before, AFAIK, and I've made a LOT of submits. A few seconds are very, very rarely enough to fix a bug and submit. Especially if "you're on a slow connection".By quantum physics, there's non-zero probability of an event occurring (as long as it's in accordance with basic laws — causality comes to mind here). How low does the chance of being a false positive have to be for you to disregard it?
•  » » » » » » » » » 5 years ago, # ^ |   +8 to W4yneb0t:I don't know why are you arguing whether it's cheating or a rare cased happened. simply if it is really rare case happened at least RNS could say so,but even him didn't say that it's rare case happened and if he is banned from commenting then he could create new account to say so ,or he can ask a friend to use his account to comment.also if you're saying that those proofs are only 99% correct then could you give us example of how a 100% proof look like?
•  » » » » » » » » » 5 years ago, # ^ | ← Rev. 2 →   +8 As Xellos pointed out above, there's no such thing as a 100% proof. It's hard to say what's enough, but 99.999% definitely is and 90% definitely isn't. With only the info in Egor's original post (before he and Xellos responded with more info), I wouldn't even give it 90%.This is not another matter of two gray users submitting the exact same code with 1 character changed. Take it more seriously.
•  » » » » » » » » » 5 years ago, # ^ |   -11 if I was in RNS situation and I know that I'm not a cheater then I would post a comment with explanation to how is that these rare cases happened with me.
•  » » » » » » » 5 years ago, # ^ |   +18 While bragging about competing as a team.Anyway, which of these two options do you think is better?: skip solutions of suspected cheaters and give them a chance to appeal it nothing
•  » » » » » » » » 5 years ago, # ^ |   0 Bragging where?
•  » » » » » » » » » 5 years ago, # ^ |   +8 One link (Russian, Ctrl+F AcRush), evidence that at least one NK team considers individual participants "teams". Further links showing mugurelionut's digs into it: team rns4 (presumably this RNS) did cheat by using another account to submit.Just try googling for more. Okay, one more link, compare it with this situation.At this point, you're asking if it's "all the proof" that there's of NK sending teams into individual contests and publicly talking about winning them (hence "bragging"); repeatedly, NK "users" have successive submits with extremely small time gaps, different users had nearly identical codes (plus CC decided they didn't cheat, which is suspicious by itself), and individual users repeatedly send codes with completely different structures. Once again: extremely similar behaviour for different users. Yes, that's all the proof.Anyway, you haven't answered my question: which choice is better?
•  » » » » » » » » » 5 years ago, # ^ |   +16 Ok, I'm largely convinced. I'm not sure which is better — some people would just say "well fuck you then" instead of appealing, and even if they appeal successfully, there will be some damaging community drama.I suppose whoever made the decision to disqualify the offender has had access to all this info that you and Egor posted. This info wasn't shown anywhere to someone who is new to the discussion. In this case, it's fine to disqualify.
•  » » » » 5 years ago, # ^ |   +24 maybe he is multi-threading human? :D
•  » » 5 years ago, # ^ | ← Rev. 2 →   +132 tourist also should be punished... it's clearly impossible to solve 7 problems in 1:08 alone.
•  » » » 5 years ago, # ^ |   -6 He can :D
•  » » » 5 years ago, # ^ |   -23 He won two ICPC world finals and in the second one his team solved all 13 problems, are you still sure that it's impossible for him?
•  » » » » 5 years ago, # ^ |   +8 I was just kidding :)
•  » » » » » 5 years ago, # ^ |   -12 Ok I'm sorry, I didn't notice :)
•  » » » 5 years ago, # ^ |   +21 Wouldn't be the first time he single-handedly beat a whole North Korean class.
•  » » 5 years ago, # ^ |   +56 Maybe they don't know that contest for only one coder?)) Or maybe they need a good result to be not killed by their authorities?
•  » » » 5 years ago, # ^ |   0 Maybe :D
 » 5 years ago, # |   +37 I love this contest very nice problems.Hello div 2 again.
•  » » 5 years ago, # ^ |   +8 same here,especially problem D had nice statement.
 » 5 years ago, # |   +60 D was truly written in an AWFUL way, it took me around an hour to get the statement behind the simple problem :/
 » 5 years ago, # |   +172 k = n in C is so wrong in so many ways >_>... Who would want to play a game which is already ended? I think such tests should be excluded since we have "Stannis starts the game." and when it's already ended it's false xD.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +43 I'm also very disappointed about that.
•  » » 5 years ago, # ^ |   0 exactly! how could Stannis start the game if the game never starts!?
•  » » » 5 years ago, # ^ |   0 i just found out i got hacked cause of that and now i got accepted :|
•  » » » » 5 years ago, # ^ |   0 well I was in a really quiet room. No hacks in my room!
•  » » 5 years ago, # ^ |   +3 But sadly it was stated that K <= N. That was really tricky. What a sad story!
•  » » » 5 years ago, # ^ |   -14 If there would be a constraint that k ≤ n n then it would also be true — constraints given by inequalities in algo problems stay for conditions which are necessary for test to be correct — not sufficient ones.
•  » » 5 years ago, # ^ |   +1 Sounds similar to "stressful victory" in this years FBHC, doesn't it? :D
•  » » 5 years ago, # ^ |   0 Is there a chance they change the test cases and rejudge C solutions!?
•  » » » 5 years ago, # ^ |   0 Frankly saying — of course no. However I will stick to my understanding that k = n should be forbidden, but someone can always use some lame excuses like "statement was vague and since it wasn't excluded explicitly by constraints then you should consider this case" (which is not a valid reasoning of course :P).
•  » » » » 5 years ago, # ^ |   0 Can't agree.Formal > non-formal, so input > description.
•  » » » » » 5 years ago, # ^ |   -13 See my comment above: http://codeforces.com/blog/entry/18348?#comment-233274 Moreover, how "Stannis starts the game" is non-formal for you?There is no such thing like "input is more important than description" or other way round. All of them should be consistent and rules assured throughout whole statement are on the same level of importance.
•  » » » » » » 5 years ago, # ^ |   +5 Consider this version of actions during the game: on their turn a player checks if there are just k cities left; in such a case, the game ends and otherwise, that player makes a move. For-loops work this way: the ending condition is checked before the first iteration.
•  » » » » 5 years ago, # ^ |   0 Actually there's a lot of problems that have test cases where the game already ended before it starts
•  » » » » » 5 years ago, # ^ |   +6 How is that justifying anything :P?
•  » » » » » » 5 years ago, # ^ |   0 You said test cases such that the game is already ended should be forbidden when the problem statement says that "[name] starts first" , but a lot of game problems exist on codeforces or other OJ stated that "[name] starts first" and has test cases such that the game already ended before it start.so I meant to say that it's very normal thing to have test case k=n in this problem just like it's normal in other game problems
•  » » » » 5 years ago, # ^ |   0 It's a reasoning with which someone may disagree, but it is a valid reasoning. The statement may be considered vague (at least I needed to translate from Weird English to English sometimes in this contest) in such a way that the case k = n wasn't explicitly excluded. If a case isn't explicitly excluded by the statement, one should consider it (I didn't). Which part of this would be objectively invalid?
•  » » » » » 5 years ago, # ^ |   +3 "Which part of this would be objectively invalid?" — in an "ideal mathematical model of statements" there is no distinction between "explicitly excluded" and "implicitly excluded" and I consider(ed) that phrase as implicitly excluding, therefore excluding.
•  » » » » » » 5 years ago, # ^ |   0 "I consider(ed) that phrase as implicitly excluding"That's not objective.
•  » » » » » » » 5 years ago, # ^ |   +3 It is if we will assume that "starts the game" implies "first move exists". One may assume it, one may not, however there should be only one "true meaning" and what we can do now is to debate whether it is as I said or not.
•  » » » » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 "One may assume it, one may not"Yep, that's what "vague statement" means. To you, the statement means one thing, so you disgree with the reasoning you call invalid. To someone else, the statement may mean something else — not falsely — and that person would disagree with that same reasoning.You've made your point and I see your point, but I don't dismiss everything else. The important thing is: what to do next? There's nothing more to say. What there is to do: improve at reading statements, improve at problems of "UGH CASEWORK" type, lead by example by setting problems clearly, offer to review problems for future rounds (if you don't want to participate...) or find someone else who could do that. Path to perfection...
•  » » 5 years ago, # ^ |   0 The authors might say, "You know nothing(about Stannis's stubbornness)" ;-)
•  » » 5 years ago, # ^ |   +13 If it said "Stannis plays the first move", you would be right, but it doesn't. "Stannis starts the game", and the game immediately ends, no problem there.
•  » » » 5 years ago, # ^ |   0 Hmmm... Probbaly you're right, however whatever the "true meaning" is, I guess it would be best if I will just leave it as it is, stop complaining and be more careful next time :p.
•  » » » 5 years ago, # ^ |   +1 He has to make a move to start the game :|
 »