### DarthKnight's blog

By DarthKnight, history, 5 years ago, ,

Hello Codeforces.

Hunger games is a programming tournament.

For participating in this tournament, you should join as a participant in this group until the deadline. After the deadline you'll be able to join only as spectator.

In some time after the deadline (exact time will be published) tournament starts as a long contest in the group. At first, there will be some problems. Each day, organizers will add a non-negative number of problems to the contest. Also, at the end of each day, a non-negative number of participants from the bottom of the scoreboard will be deleted from the contest (to practice) and become spectators (not able to submit any more). Also, people that don't submit any code in first two-three (exact time will be published) days will become spectators.

Finally, there will be 20 peoples remaining at the end. We're still deciding about their prizes.

Duration of the tournament is not known yet. It will be published (it may be several weeks!).

Problems of the tournament may be copied (borrowed) from Codeforces or any online judge but we'll do our best to put new problems that we wrote ourselves. Also you may find a classic problem. To sum up, anything may happen in this tournament. Don't be shocked even if you see some April-fools-day-contest-problem-style problem.

Cheating and copying codes is forbidden(even copying your own old code) and you'll be disqualified from the the tournament if we catch you.

I think this is a good opportunity to practice and compete for all Codeforces members, because there will be hard and easy problems and good for everybody.

After the tournament ends, you'll be able to submit its problems in practice.

Currently, organizers team consists of AmirMohammad Dehghan(PrinceOfPersia) and Keyvan Khademi(keyvankhademi) but of course some more people will join.

Stay tuned, all future news will be published in the group blogs.

May the odds be ever in your favor.

UPD: Ali Asadi(AliA) joined our team.

UPD1: Tournament starts at August 12.

UPD2: Tournament is starting in about 3 hours. Don't forget to participate. Initially there will be 5 easy problems; But get ready, cause this shit's about to get heavy (problems will be added one by one during the tournament).

Team are not allowed.

You can read the news in the Memorial service.

• +291

 » 5 years ago, # |   +1 Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).
 » 5 years ago, # |   0 came @ right time :) awesome idea
 » 5 years ago, # |   +50 copying codes is forbidden(even copying your own old code)Sorry, I am not keen to write all the standard algos once more, especcially rewriting fast I/O for every task
•  » » 5 years ago, # ^ |   +3 I think he mean copying the whole old solution
•  » » » 5 years ago, # ^ |   +1 Yes! I meant the whole old code.
 » 5 years ago, # |   +27 So if I have some data structure prewritten and I'll copy it I will be disqualified? And what if I write some algorithm in a same way every time I need it?
 » 5 years ago, # |   +8 Yeah, exactly as mentioned in above comments "copying codes is forbidden(even copying your own old code) " <- this is lame.
 » 5 years ago, # | ← Rev. 2 →   +67 What about using non-standard/new/unusual problems instead of inventing don't copy your own code rules?Anyway, if I'll write down a screencast to prove that I retyped my old code instead of copy-pasting it — does it count? :D
 » 5 years ago, # |   +15 Will time penalty matters? If it's a long contest then obviously people from some time zones will see the problems first, so what scoring will you use so that time-penalties are irrelevant? Awesome idea for a contest though :)
 » 5 years ago, # |   +16 That seems nice! :)
 » 5 years ago, # |   +25 How will you discern between situations "I copied my old code and made small changes in it" and "I looked at my old code and something with the same kind of implementation again"? The former is significantly faster, but since my coding style hasn't considerably changed, they'd be very similar.Protip: you can't, which either makes for an easy way to bypass the rule or you'll piss people off with false positives.
 » 5 years ago, # |   +2 "May the odds be ever in your fever." I hope not :D. Did you mean favor*?
 » 5 years ago, # | ← Rev. 2 →   0 I think it is better to take separated div tournoment
 » 5 years ago, # | ← Rev. 2 →   0 will you put the problems in persian language too?
 » 5 years ago, # |   -9 ... why you are cheating in contest i khnow all the detail about you
 » 5 years ago, # |   +21 Idea is awesome but please, think about "copying your own code is forbidden" part. It's so ambiguous and hard to check.
•  » » 5 years ago, # ^ |   +5 He said that it's only forbidden to copy a whole solution.
•  » » » 5 years ago, # ^ |   +2 Name of array changed and everything is ok? Can I copy all functions and rewrite short main?
•  » » » » 5 years ago, # ^ |   -14 :)
 » 5 years ago, # |   +84 Will there be the onsite for top contestants just like in the movie? :D
 » 5 years ago, # |   -8 Don't copy yourself idea kinda sucks :\
 » 5 years ago, # |   +18 why is there a tag "killing" ? :D
 » 5 years ago, # |   0 First coding survival game on the world! I'm really excited to participate.By the way, when will the game begin?
 » 5 years ago, # |   +22 Why are you guys so angry about not being able to copy your old codes? Just think about it as if it was an onsite contest where you start with a clear computer. Obviously, not being able to copy code you wrote during the contest would be kind of weird, but I guess that it's not what PrinceOfPersia meant.
•  » » 5 years ago, # ^ | ← Rev. 3 →   +78 Well, when I am on the onsite contest and can't copy I am angry too.
•  » » » 5 years ago, # ^ | ← Rev. 3 →   +16 Does it (that you are angry) help you?)
•  » » » » 5 years ago, # ^ |   +6 Have you seen me winning smth?
•  » » » » » 5 years ago, # ^ |   +23
•  » » » » » » 5 years ago, # ^ | ← Rev. 4 →   +5 Ok, maybe it was the case when it helped:)Didn't expect you to find something
•  » » » » » » » 5 years ago, # ^ |   -38 Let's watch The international 5 The international 5 is better than programming
•  » » » » » » » 5 years ago, # ^ |   0 We've played this contest as a training and then find official results, so I've just remember (:
•  » » 5 years ago, # ^ | ← Rev. 2 →   +8 The idea is fine, the execution will just be difficult. As Xellos mentioned above, how would you make difference between someone who copies old code and modifies it and someone who writes it from scratch? If it is some standard algorithm, say DFS/BFS/Dijkstra/Flow/Segment Trees/etc then my codes will look 95% identical even if I write them weeks apart because I have a specific style of writing them in my head.And of course, if it is impossible to guess which is a new code and which is an old code, it becomes useless to have such a rule as cheaters won't be effectively punished (without lots of false-positives for non-cheaters).Idea is fine, execution could be tough. If it is indeed a long contest and time penalty doesn't matter (obviously it shouldn't) allowing use of old codes (as long as they are your codes) should be fine.I personally rarely use old codes and have no templates at all, so I'm fine with whatever the rule is, but I see why people dislike it :)
•  » » » 5 years ago, # ^ |   +19 come on :| we didn't say don't copy your template code or your precoded algorithm. we mean if had ever solved the problems before (in other Online Judges for example) don't copy paste the raw code. Or don't copy anyone else solution.
•  » » » » 5 years ago, # ^ |   -14 we mean if had ever solved the problems before (in other Online Judges for example) don't copy paste the raw code is addressed in: how would you make difference between someone who copies old code and modifies it and someone who writes it from scratch?
•  » » » » » 5 years ago, # ^ |   +26 we will not check all the solutions, of course it's easy to cheat. but we respectfully ask not to cheat. but if we GET SURE that some body is cheating will disqualify him.
•  » » » 5 years ago, # ^ |   -19 Red coders don't copy
•  » » » » 5 years ago, # ^ |   +11 Lots of red coders have tons of templates and precoded algorithms for all kinds of stuff. I just dislike doing that because on onsite competition you can't really use any old codes and I want to keep myself in good coding shape :)
 » 5 years ago, # |   -17 I think it won't work...We have contests in our school that problems are from other judges, and ALWAYS we have a lot of cheaters...We know who are the cheaters in school cause we know students, but here you can't slander anybody...But nice idea at all...wish you use new problems in contests...at least in important ones... ;)
 » 5 years ago, # |   -14 Some one should make The Goblet of Fire contest
 » 5 years ago, # |   +8 Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).
 » 5 years ago, # |   -62 Hunger games is for stupid little girls
•  » » 5 years ago, # ^ |   +6 Happy Hunger games then !
•  » » » 5 years ago, # ^ |   -68 Nah. I better go and watch some mww porn
•  » » 5 years ago, # ^ |   -70 Jesus! Let's play "Twilight" too, why not! WFT guys?
•  » » 5 years ago, # ^ |   +6 Just wish God will help you...
•  » » » 5 years ago, # ^ |   -37 I like the way you dislike me. Filling myself so important! Thank you, guys
•  » » » » 5 years ago, # ^ |   +5 So u were useless before getting dislikes right ?
•  » » » » » 5 years ago, # ^ |   0 He's like that now too...
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 I don't know "useful" guy about you, but I am useless only during command contests. But thank you for your opinion anyway
 » 5 years ago, # | ← Rev. 2 →   +3 What if competitors are allowed to come back?A parallel contest may be held each time for anyone who out, and top-few competitors could qualify back. For example, BOTTOM-25 go out every round, and TOP-5 from parallel round rejoin. Relevant restrictions could still be applied — e.g. can't rejoin after only X members are remaining.This approach has pros and cons, which could be balanced by introducing some extra rules. What do you think?
•  » » 5 years ago, # ^ |   0 of course BOTTOM-25 not TOP-25 :D
 » 5 years ago, # |   0 Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).
 » 5 years ago, # |   0 5 Minutes
 » 5 years ago, # |   0 Don't you think it's a little bit unfair to have time penalty in a long contest? For example I can't solve the problems at the moment so I'll get bigger penalty on the initial set of five easy ones, and of course if it goes for weeks it will be very uncomfortable for some time zones.
•  » » 5 years ago, # ^ |   0 As I know, ACM rules is the only avaliable type of gym contests
•  » » » 5 years ago, # ^ |   +15 In that case I think a clarification should be added that penalty time should be ignored. That is, there shouldn't be two people with equal amount of problems solved and only one of them being removed after any day :)
 » 5 years ago, # |   +59 Could you please answer the clarification requests?
 » 5 years ago, # |   0 very nice problemset ,when we will able to discuss problems ?
 » 5 years ago, # | ← Rev. 2 →   0 Shouldn't the output for test case #2 be 2 1 2?Nevermind, i misunderstood the problem's statement.
 » 5 years ago, # |   +57 if(problemid=='C' && submission_verdict=="AC"){ submission_verdict="Denial of judgement"; } 
•  » » 5 years ago, # ^ |   +9 When writing checker to problem with "find any good/best answer", setter should consider his mistake and do some asserts (not exactly asserts but nvmd) in case of participant having better answer. Here I guess for some tests their program returns -1 (impossible) but there is a solution. So checker validates this solution and says "shit". I guess it is what happened here.What bothers me more is that there is no administrator (online) for more than 12 hours after start of a contest.
•  » » » 5 years ago, # ^ |   +22 Quote from blog: To sum up, anything may happen in this tournament. Don't be shocked I'm afraid that "Denial of judgement" might have done intentionally
•  » » » 5 years ago, # ^ | ← Rev. 3 →   +5 Edit: Nevermind my stupid comment. I got AC now.
 » 5 years ago, # |   +26 Since they are not answering clarification requests can someone help me out with the statement of problem C? Is it possible for ai to be negative? From constraints it seems possible but they're speaking of milliliters in a cup so it makes no sense in reality. And secondly if there is some solution but with ai out of the interval -10^9 ~ 10^9 then do we still print -1 even though there is some solution?
•  » » 5 years ago, # ^ |   +16 They can be negative. And you should forget about 109 restriction, output large values if you need. Also, I think, all a i should be integer.
•  » » » 5 years ago, # ^ | ← Rev. 4 →   +12 Well there goes my half code choosing appropriate values so that they fit in [-10^9 ; 10^9]...P.S.Thanks, AC now :)P.S.S.Funny enough they responded to my clarification that it's impossible for ai to be out of [-10^9; 10^9]. Yet I got WA#8 if I made sure ai is in that interval and AC without that.
•  » » » 5 years ago, # ^ |   +48 Thanks, further if I have any questions, I'll check them here and won't send any clars or PMs to authors. Great disrespect to people who made this statement
•  » » » » 5 years ago, # ^ |   +40 Great disrespect to people who made this statement That's one of the best insults I've ever heard.
•  » » » » 5 years ago, # ^ |   0 WDF!!!!!I feel the same as you men, I passed hours trying to figure out what could be wrong with my code, and trying to find a bug I remove the constraint checker and got AC.How can the statement say abs(ai) < 10^9, if it is BAD????Just FIX IT
•  » » » 5 years ago, # ^ |   0 But if a[i] is negative, is a[i]%n still non-negative or is it like in c++ that (-4)%3 == -1?
•  » » » » 5 years ago, # ^ |   +5 The mod is non-negative and it says a[i%n], not a[i]%n, look at the font very carefully.
 » 5 years ago, # |   +13 "Since they are not answering clarification requests" (c), can anyone explain to me statement of problem E? Whe should output min (lcm % mod), or (min lcm) % mod ?
•  » » 5 years ago, # ^ |   +11 (min lcm) % mod
 » 5 years ago, # |   0 Can anyone please explain me the 2nd statement for the F problem? Thx.
•  » » 5 years ago, # ^ |   +8 Interesting question!
 » 5 years ago, # |   +22 Question about rules:If I have noticed that there is a problem in this contest which I can find in another judge or/and in another contest, may I debug my code on that problem first to decrease my penalty time?I've already did it with problem E. I cannot find anything in rules about this situation (except 'cheating', but who knows what do you mean by 'cheating').Request: publish updates to this blog (or create new blog) when you add new problems.
•  » » 5 years ago, # ^ |   0 Cheating and copying codes is forbidden(even copying your own old code) and you'll be disqualified from the the tournament if we catch you. So, formally you copied your own code you used on the same problem in other place? :)
•  » » » 5 years ago, # ^ |   0 I've written the code for problem E, but submit it somewhere else :)
•  » » 5 years ago, # ^ |   0 I think it is considered cheating cause u r having an advantage over other contestants who don't know where to find the other version of the problem.
•  » » 5 years ago, # ^ |   0 If penalty time doesn't matter in this contest, I think it's OK for you to do it (but of course they might have a different opinion).
 » 5 years ago, # |   +12 Can you please send a notification when you add new problems ?
 » 5 years ago, # | ← Rev. 2 →   0 Can anyone tell me more clearly about how will participant's solution and judge's checker interect with each other in problem J? (Sorry, this is the first time I meet interactive problem in an online judge)
•  » » 5 years ago, # ^ |   +5 for C++ just if you want to query for node v then write this line:cout<>v;it's very simple
•  » » » 5 years ago, # ^ | ← Rev. 4 →   0 Will I have to write something like this? int main () { while (true) { //Read the graph cin >> v; if (v == 0) return 0; //Processing cout << v << endl; } return 0; } 
•  » » » » 5 years ago, # ^ |   +8 No, it's more like int main() { //read graph while (true) { //do smth cout << v << endl; cin >> v; if (v == 0) return 0; } } 
•  » » » » » 5 years ago, # ^ |   0 while(v != 0) then
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +11 No you don't read the graph again int main(){ //read graph while(true){ int v; // decide which node you want to query cout<>ans; // this is the answer from judge if(ans==0)break; } } 
•  » » » » » 5 years ago, # ^ |   0 I finally got it. Thanks a lot!
 » 5 years ago, # |   +8 In problem J, if I ask more than 33 questions, what will the verdict be?
•  » » 5 years ago, # ^ |   +8 WA
•  » » » 5 years ago, # ^ |   0 It's not WA, it's TLE, thank you....
•  » » » » 5 years ago, # ^ |   +5 If you take too long to ask them, it's obviously TLE...
•  » » » » » 5 years ago, # ^ |   +5 No I think he's saying that asking more than 33 questions gives TLE even though PrinceOfPersia said it gives WA. This guy said the same thing. I'm not sure whether it actually does give TLE but if it does then it is really disappointing since the only clarification than has been answered would have been answered incorrectly.
•  » » » » » » 5 years ago, # ^ | ← Rev. 2 →   +23 I just tested this: I added the following code into my AC solution, after reading the tree and before making any other queries. So, it gives the correct answer after making at least 34 queries. The verdict was WA.  int junk; forn(i,34){ cout<<1<>junk; } I also submitted code which first asks 34 queries and then waits for timeout. The verdict is TLE. So, the clarification isn't wrong, but the question was worded ambiguously.
•  » » » 5 years ago, # ^ |   0 Other than exceeding the number of moves, what could another reason be for getting an WA?In my solution, I made sure that I am making valid queries and they are under 33 queries. Also I am exiting the program only when I get a 0.I still get WA on 14, what might be the reason for this?
 » 5 years ago, # | ← Rev. 2 →   0 I think it's not really justly...Someone like me started contest from second day and solved some problems without any wrong submit but someone with lots of wrong submits is better than me in the ranking...If it's possible I think better to make the negative point of a wrong submission at least equal to 2 hours...(or more :/)And something else... In 14 days why the colors don't change?I'm still blue in the contest
 » 5 years ago, # | ← Rev. 2 →   -18 deleted
•  » » 5 years ago, # ^ |   -13 I think you should be removed from contest :)
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Why? I just wanted to ask how to input/output values with scanf/printf
 » 5 years ago, # |   +4 she lets you play with her Pepsi Cola. Do you want it ?Nice :D...But could you please give us a picture of her in the problem statement to decide of the problem have value to solve?
•  » » 5 years ago, # ^ |   +50
•  » » » 5 years ago, # ^ |   +1 noooooo...why i can't solve that? :|
•  » » 5 years ago, # ^ |   +55 He really wanted to play with her Pepsi Cola...
•  » » » 5 years ago, # ^ |   0 I really want it too but I just have been removed from contest cause I registered as a team...:/ Fuuuuu..
 » 5 years ago, # | ← Rev. 2 →   0 WTF is with you internet? -_-
 » 5 years ago, # | ← Rev. 3 →   -17 Why??
 » 5 years ago, # |   0 Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).
 » 5 years ago, # |   +5 Did anyone notice that in problem J, all solution that ask more 33 questions or has running time exceed limit will get the same verdict TLE?
 » 5 years ago, # |   +56 When will be "bottom" people knocked out of the contest? Will it be announced who was? (like "Bottom 10 have just won a magical trip to graveyard. Beware!)
•  » » 5 years ago, # ^ |   +6 How do we know that people are knocked out of contest? In standing, on 1st day I see around 140 people, couple of days ago it was around 160-170, right now it is 178.
 » 5 years ago, # |   +5 Will be the editorial of the problems after the tournament? It is very interested to know how to solve some of the problems
•  » » 5 years ago, # ^ |   +17 I don't think it will. But I think we, participants, could after the end prepare a community editorial, as some problems are quite hard for less skilled participants, but also interesting and worth upsolving
 » 5 years ago, # |   +53 But get ready, cause this shit's about to get heavyWhen will this day became? =) Because now there are near 20 peoples with full score.Maybe, it's time to cut "bottom" and add some extra-hard problems (and the decent amount of them, not just 1-2) ? =)
•  » » 5 years ago, # ^ |   +10 You're totally right. But also, it would be a nice idea to add more problems with more difference in difficulties, cause in last 3 days there were only 3 new medium problems and none of them is really hard or easy.
•  » » » 5 years ago, # ^ |   +24 I'm struggling with "Pepsi cola" for quite a while now, you guys sadden me :D
 » 5 years ago, # |   0 I think allowing teams would have made this more exciting
•  » » 5 years ago, # ^ | ← Rev. 3 →   +5 Well in case they actually plan to provide some rewards for top20 it would've been unfair to allow teams :)
•  » » » 5 years ago, # ^ |   0 One can always make an announcement that there has been a slight change in the rules at then end ;)jk, you're right. :D
 » 5 years ago, # |   0 Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).
 » 5 years ago, # |   0 I'm out of contest, but I can register again. What if I register again and just solve as a practice? Is it ok for you? Or, Do I have to wait until the end?
 » 5 years ago, # |   +15 So I can't submit my old code on this problem, but I can read it, refresh the idea and write almost the same code again, am I right?
•  » » 5 years ago, # ^ |   +5 It looks like I was removed from contest because I reimplemented that in less than 10 mins.
 » 5 years ago, # |   0 Hamro and TheVampireDiaries — How can we do this in c++ since the limits are beyond even long long?
•  » » 5 years ago, # ^ |   +4 Actually, most of the people who solved it used c++
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 I think I've figured it out now, but thanks! I have one more question about it, though. -If there are multiple sets (a1,a2,..,an) that work, should we print any of them or print -1 because it would be impossible to guess?
•  » » » » 5 years ago, # ^ |   0 You should print any of them.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Just print any correct set. If there is any solution it's guaranteed that all a i would fit in long long, at least that's what got AC for me, because it isn't very clear from the statement :)
•  » » » » » 5 years ago, # ^ |   +3 Thanks everyone. Just got AC and passed the 69 mark.
 » 5 years ago, # |   +13 It would be bad if problem O happen with you in real life. Imagine that 50000 people want to kill you :P
 » 5 years ago, # |   +13 Are participants allowed to discuss ACCEPTED problems in private? Of course it doesn't matter when they both got AC and future submits won't count, and it would be nice to be able to exchange solutions with friends
 » 5 years ago, # |   0 I have a question about problem R."We all a graph adorable if and only if we can increase the weight of some of its edge (increase each edge by a non-negative number)" I can't understand this sentence. Are we allowed to change the weight of exactly one edge or of any subset of the edges?
•  » » 5 years ago, # ^ |   +5 It should be "some of its edges", I suppose, since there's "each edge" afterwards.
 » 5 years ago, # |   +3 Will editorials be posted after the contest?
•  » » 5 years ago, # ^ |   +11 I don't think so, similiar question has already been asked by someone and still got no official response. But,Andres_Unt and me are going to prepare one, along with small hints editorial. However, there's no need to do this if there'll be an official editorial, so I encourage contest hosts to finally answer this question...
•  » » » 5 years ago, # ^ |   +25 I think user-prepared editorial should be pretty nice, we can all contribute to it in order to get the cleanest and most efficient solutions :)
 » 5 years ago, # |   0 Can you please extend the duration of contest by 2-3 days?
•  » » 5 years ago, # ^ |   0 What? Why should the competition be extended because someone asks for it? Is that not completely unfair to other competitors?
•  » » » 5 years ago, # ^ |   -38 Why the fuck its unfair when duration is equal for all participants :||
•  » » 5 years ago, # ^ |   +5 But why stop there? This contest is so awesome it should be extended at least until New Year! Just need a way to "resurrect" the "dead" and lots of problems.
 » 5 years ago, # |   +12 Add some people (including me) to contest managers after the contest and make an blog that'd serve as "write editorials of everything here" — that'd be probably the best way to make an official editorial by contestants, and definitely better than just comments.
•  » » 5 years ago, # ^ |   +5 I agree, that sounds like a great idea, and I will be glad to help
 » 5 years ago, # |   0 I've only looked at A-N,but my favorite problem in this set has to be problem L :)Thank you for an interesting contest!
 » 5 years ago, # | ← Rev. 2 →   +6 that awkward moment when you realize you have solved as much as 20th participant and you are 21st :((
•  » » 5 years ago, # ^ |   +8 Apologies mate.
•  » » » 5 years ago, # ^ |   0 No Problem ;) Congratulation!:D
 » 5 years ago, # |   0 Woohooo! Editorial :3http://codeforces.com/blog/entry/19987This is only hint-editorial, I'll write a similar blog with detailed explanations. Ofc it's impossible to finish it in one person so I deeply encourage you to help and share your solutions :)
 » 5 years ago, # |   -6 So what about the prizes? :)And how to solve problem T? I know it was taken from the one of the previous Codeforces rounds, but it seems that there is no editorial for this problem.
•  » » 5 years ago, # ^ | ← Rev. 3 →   +21 I was only a spectator, so I had no way to check if my solution is right.First of all, we need to come up with any solution. Let's fix a variable X 1 = [a 1, b 1], call it excluded and compute the probability it's k-th (first, second, ..., n - 1 st) in order under the assumption that X 1 = s for some fixed .Everything can be described by the generating function where t is number of variables whose intervals are strictly left to s and J contains all the intervals such that . We can see that the x k - 1 coefficient hides the probability of X 1 being k-th when s is fixed.What if s is uniformly distributed over [a 1, b 1]? X 1 has a probability density function equal to inside its interval and 0 otherwise, so the overall probability is . Only note that the definition of w may change for different values of s (if we move s to the right, some intervals may begin lying strictly to the left of s or contain s). However, such changes are not too frequent (there are only Θ(n) stars/ends of intervals, so there may be only that many changes).So: for each of n variables with associated interval [a 1, b 1] we find all the intervals where w doesn't change its definition (Θ(n) of them). Then for each of these intervals: compute w for each of them (do Θ(n) multiplications, each of them can be done in Θ(n 2)), get the polynomial describing the x k - 1 coefficient, integrate it in s over that interval. Everything should be doable in Θ(n 5).This will probably not be enough, so we need to speed it up. For example, we could probably somehow use multidimensional FFT for multiplication (however, I'm not sure how it works XD). We could also probably avoid so many multiplications and merge some steps. One way is to think that each polynomial behaves properly in intervals between variables starts/ends (call such intervals proper and order them from left to right) computed for each excluded variable. We can then create a matrix M of generating functions; cell in i-th row, j-th columns contains the generating function for excluded variable X i and in j-th proper interval in order.Then a factor has to be multiplied with all the generating functions inside either of two rectangles: the first with variables X j, j < i and proper intervals partitioning [a i, b i] and second with variables X j, j > i and same proper intervals. Probably with some voodoo magic with 2D segment trees it can be done in Θ(n 4) or even in .Isn't it... uhm, quite overcomplicated?
•  » » » 5 years ago, # ^ |   +13 That algorithm is numerically extremely bad due to the cancellations, you'll get WA for n>=40. A better way is to not bother calculating the polynomial in s explicitly. Just evaluate it for some fixed values of s and integrate using Newton-Cotes. Considering each interval individually is still useful, since the function you're integrating is somewhat smooth inside each interval but not across them.
•  » » 5 years ago, # ^ | ← Rev. 3 →   +19 Here is a solution that doesn't require knowledge of integration (or integration algorithms).Consider the simplified case where we know that, for some interval, every competitor is either before the interval (say there are S of these competitors), after the interval, or somewhere inside the interval with uniform probability over the whole interval (say there are K of these). Then if this arrangement happens, each of the K competitors then has a chance to come each of S + 1 th, S + 2 th, ..., S + K th.Note also that if we consider all endpoints together and then take the intervals between consecutive endpoints: then for each interval, every competitor will either not cover that interval at all, or will completely cover that interval (and thus if they are in it, they will have a uniform probability of being anywhere in that interval). Also, there are O(N) of these intervals.This gives us the simple algorithm: for each interval ( O(N)), for each competitor i, ( O(N)), calculate dp[S][K] = the probability of S other competitors appearing before this interval and K other competitors appearing inside this interval (which we can do in O(N 3) with DP). However, this is overall O(N 5) which is too slow.So we need to try and calculate " dp[S][K] for all competitors except i", for every i. One idea is to calculate dp[S][K] for all competitors, and then "subtract" each competitor with some maths. Overall this would be O(N 4). Theoretically this is possible but in practice it is too inaccurate.Instead we can calculate this with divide and conquer (overall O(N 4 lgN), or buckets . For example, for divide and conquer we can calculate f(l, r) = the dp[S][K] for all competitors outside of the range [l, r), and then recurse on f(l, mid) and f(mid, r). (or maybe my understanding of the divide and conquer method is completely wrong because I did sqrt N buckets and was only told about the divide and conquer method afterwards ¯\_(ツ)_/¯)
 » 5 years ago, # |   +10 How to solve T?
•  » » 5 years ago, # ^ |   0 Suppose the function F(i, x, r) = probability that the ith player scores exactly x points, and finishes at the rth rank.Function F can be easily computed by dp in O(n^2) for all values of r fixing i and x.We can integrate this function for fixed i and r, from x = L[i] to x = R[i] using efficient integration method. (I used simpon's rule but it was very hard adjusting accuracy to pass the time limit)
 » 5 years ago, # | ← Rev. 2 →   +8 I'm curious to know how many people solved problem U (Godzilla and Chess) in O(N 2), because both people that I talked to afterwards solved it in O(N 3) which I assumed would be too slow.
•  » » 5 years ago, # ^ |   +8 Mine is N^3/32. Does N^2 solution exist?
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +24 Yes.Consider the graph of players where an edge goes from A to B iff A beats B.Now suppose we have some subset of the players such that for every player P in the set and every player S that is not in the set: P beats S or P beats some R that beats S. (Basically, the set must have the property that we can ignore things outside the set, because they will not make anyone inside the set not a winner.) Also, only consider the edges between players in the set (essentially we treat the subset as a smaller version of original problem). Observe that a player P in the set who has a minimal number of incoming edges (remembering to ignore edges to and from players outside of the set), must be a winner. Helpful paint:Note that any player a in A has at least as many incoming edges as P (since P has a minimal number of edges), so a must be beaten by something in B.Of course, the whole group is a subset fulfilling the requirements so we can simply do this to get our first winner P. Now if the set A of players that beat P is empty, we're done. Otherwise everything in A beats P and A beats everything in B so therefore A is a subset fulfilling the requirements. Thus we can repeat the procedure on A to get our second winner Q.Now if, the set of players in A that also beat Q is not empty, we can recurse again on that set. However, if there is nothing in A that beats Q, we cannot just stop like at the last time (when there was nothing that beat P).Slightly less helpful paint:Players in B that beat Q are red, players in B that are beaten by Q are green.Alright, now we know that Q beats everything in A, and also beats P, and also beats any green players. Meanwhile, it is also beaten by at least one player in B (since P has a minimal number of incoming edges, and P has an incoming edge from Q, and we just checked that Q has no incoming edges from other players in A, so Q must have at least one incoming edge from B). Therefore, red is a non-empty subset that satisfies the requirements (since everything in red beats Q and Q beats everything else that is not red). So we can recurse on red to find our third winner.Hopefully there isn't a way simpler O(N 2) solution that I missed...
•  » » » » 5 years ago, # ^ |   0 Wow, that's actually quite nice. Another great problem ruined by constant factors.
 » 5 years ago, # |   0 Please note, that both editorials, written by Miyukine (short and full version; the later is not finished yet) were added to 1st Hunger Games group blog
 » 5 years ago, # |   +15 What about the prizes?
 » 4 years ago, # |   +35 Eagerly waiting for the 2nd hunger games. 1st one was a very good collection.
 » 3 years ago, # |   -26 nice way to post i am visiting first time Angry Birds 2 Game Download