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(aliasadiiii) 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.
Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).
came @ right time :) awesome idea
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
I think he mean copying the whole old solution
Yes! I meant the whole old code.
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?
Yeah, exactly as mentioned in above comments "copying codes is forbidden(even copying your own old code) " <- this is lame.
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
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 :)
That seems nice! :)
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.
"May the odds be ever in your fever." I hope not :D. Did you mean favor*?
I think it is better to take separated div tournoment
will you put the problems in persian language too?
Idea is awesome but please, think about "copying your own code is forbidden" part. It's so ambiguous and hard to check.
He said that it's only forbidden to copy a whole solution.
Name of array changed and everything is ok? Can I copy all functions and rewrite short main?
:)
Will there be the onsite for top contestants just like in the movie? :D
Don't copy yourself idea kinda sucks :\
why is there a tag "killing" ? :D
First coding survival game on the world! I'm really excited to participate.
By the way, when will the game begin?
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.
Well, when I am on the onsite contest and can't copy I am angry too.
Does it (that you are angry) help you?)
Have you seen me winning smth?
https://official.contest.yandex.ru/contest/1211/standings/
Ok, maybe it was the case when it helped:)
Didn't expect you to find something
We've played this contest as a training and then find official results, so I've just remember (:
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 :)
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.
is addressed in:
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.
Red coders don't copy
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 :)
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... ;)
Some one should make The Goblet of Fire contest
Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).
Hunger games is for stupid little girls
Happy Hunger games then !
Just wish God will help you...
I like the way you dislike me. Filling myself so important! Thank you, guys
So u were useless before getting dislikes right ?
He's like that now too...
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?
of course
BOTTOM-25notTOP-25:DAuto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).
5 Minutes
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.
As I know, ACM rules is the only avaliable type of gym contests
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 :)
Could you please answer the clarification requests?
very nice problemset ,when we will able to discuss problems ?
Shouldn't the output for test case #2 be 2 1 2?
Nevermind, i misunderstood the problem's statement.
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.
Quote from blog:
I'm afraid that "Denial of judgement" might have done intentionally
Edit: Nevermind my stupid comment. I got AC now.
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?
They can be negative. And you should forget about 109 restriction, output large values if you need. Also, I think, all ai should be integer.
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.
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
That's one of the best insults I've ever heard.
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
But if a[i] is negative, is a[i]%n still non-negative or is it like in c++ that (-4)%3 == -1?
The mod is non-negative and it says a[i%n], not a[i]%n, look at the font very carefully.
"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 ?
(min lcm) % mod
Can anyone please explain me the 2nd statement for the F problem? Thx.
Interesting question!
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.
So, formally you copied your own code you used on the same problem in other place? :)
I've written the code for problem E, but submit it somewhere else :)
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.
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).
Can you please send a notification when you add new problems ?
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)
for C++ just if you want to query for node v then write this line:
cout<<v<<endl;then read the answer like this:
cin>>v;it's very simple
Will I have to write something like this?
No, it's more like
while(v != 0)thenNo you don't read the graph again
I finally got it. Thanks a lot!
In problem J, if I ask more than 33 questions, what will the verdict be?
WA
It's not WA, it's TLE, thank you....
If you take too long to ask them, it's obviously TLE...
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.
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.
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.
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?
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
deleted
I think you should be removed from contest :)
Why? I just wanted to ask how to input/output values with scanf/printf
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?
noooooo...why i can't solve that? :|
He really wanted to play with her Pepsi Cola...
I really want it too but I just have been removed from contest cause I registered as a team...:/
Fuuuuu..
WTF is with you internet? -_-
Why??
Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).
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?
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!)
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.
Will be the editorial of the problems after the tournament? It is very interested to know how to solve some of the problems
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
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) ? =)
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.
I'm struggling with "Pepsi cola" for quite a while now, you guys sadden me :D
I think allowing teams would have made this more exciting
Well in case they actually plan to provide some rewards for top20 it would've been unfair to allow teams :)
One can always make an announcement that there has been a slight change in the rules at then end ;)
jk, you're right. :D
Please add more problems.
Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).
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?
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?
It looks like I was removed from contest because I reimplemented that in less than 10 mins.
Hamro and TheVampireDiaries — How can we do this in c++ since the limits are beyond even long long?
Actually, most of the people who solved it used c++
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?
You should print any of them.
Just print any correct set. If there is any solution it's guaranteed that all ai would fit in long long, at least that's what got AC for me, because it isn't very clear from the statement :)
Thanks everyone. Just got AC and passed the 69 mark.
It would be bad if problem O happen with you in real life. Imagine that 50000 people want to kill you :P
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
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?
It should be "some of its edges", I suppose, since there's "each edge" afterwards.
Will editorials be posted after the contest?
I don't think so, similiar question has already been asked by someone and still got no official response. But,.I. 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...
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 :)
Can you please extend the duration of contest by 2-3 days?
What? Why should the competition be extended because someone asks for it? Is that not completely unfair to other competitors?
Why the fuck its unfair when duration is equal for all participants :||
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.
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.
I agree, that sounds like a great idea, and I will be glad to help
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!
that awkward moment when you realize you have solved as much as 20th participant and you are 21st :((
Apologies mate.
No Problem ;) Congratulation!:D
Woohooo! Editorial :3
http://mirror.codeforces.com/blog/entry/19987
This 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 :)
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.
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 X1 = [a1, b1], call it excluded and compute the probability it's k-th (first, second, ..., n - 1st) in order under the assumption that X1 = 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 xk - 1 coefficient hides the probability of X1 being k-th when s is fixed.
What if s is uniformly distributed over [a1, b1]? X1 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 [a1, b1] 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 Θ(n2)), get the polynomial describing the xk - 1 coefficient, integrate it in s over that interval. Everything should be doable in Θ(n5).
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 Xi 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 Xj, j < i and proper intervals partitioning [ai, bi] and second with variables Xj, j > i and same proper intervals. Probably with some voodoo magic with 2D segment trees it can be done in Θ(n4) or even in 
.
Isn't it... uhm, quite overcomplicated?
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.
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 + 1th, S + 2th, ..., S + Kth.
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(N3) with DP). However, this is overall O(N5) 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(N4). Theoretically this is possible but in practice it is too inaccurate.
Instead we can calculate this with divide and conquer (overall O(N4lgN), 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 ¯\_(ツ)_/¯)
How to solve T?
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)
I'm curious to know how many people solved problem U (Godzilla and Chess) in O(N2), because both people that I talked to afterwards solved it in O(N3) which I assumed would be too slow.
Mine is N^3/32. Does N^2 solution exist?
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(N2) solution that I missed...
Wow, that's actually quite nice. Another great problem ruined by constant factors.
Please note, that both editorials, written by kpw29 (short and full version; the later is not finished yet) were added to 1st Hunger Games group blog
What about the prizes?
Eagerly waiting for the 2nd hunger games. 1st one was a very good collection.