PrinceOfPersia's blog

By PrinceOfPersia, history, 9 years ago, In English

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.

  • Vote: I like it
  • +291
  • Vote: I do not like it

| Write comment?
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

came @ right time :) awesome idea

»
9 years ago, # |
  Vote: I like it +50 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it +27 Vote: I do not like it

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?

»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Yeah, exactly as mentioned in above comments "copying codes is forbidden(even copying your own old code) " <- this is lame.

»
9 years ago, # |
Rev. 2   Vote: I like it +67 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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 :)

»
9 years ago, # |
  Vote: I like it +16 Vote: I do not like it

That seems nice! :)

»
9 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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.

»
9 years ago, # |
  Vote: I like it +2 Vote: I do not like it

"May the odds be ever in your fever." I hope not :D. Did you mean favor*?

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I think it is better to take separated div tournoment

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

will you put the problems in persian language too?

»
9 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Idea is awesome but please, think about "copying your own code is forbidden" part. It's so ambiguous and hard to check.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    He said that it's only forbidden to copy a whole solution.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Name of array changed and everything is ok? Can I copy all functions and rewrite short main?

»
9 years ago, # |
  Vote: I like it +84 Vote: I do not like it

Will there be the onsite for top contestants just like in the movie? :D

»
9 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Don't copy yourself idea kinda sucks :\

»
9 years ago, # |
  Vote: I like it +18 Vote: I do not like it

why is there a tag "killing" ? :D

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

First coding survival game on the world! I'm really excited to participate.

By the way, when will the game begin?

»
9 years ago, # |
  Vote: I like it +22 Vote: I do not like it

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.

  • »
    »
    9 years ago, # ^ |
    Rev. 3   Vote: I like it +78 Vote: I do not like it

    Well, when I am on the onsite contest and can't copy I am angry too.

  • »
    »
    9 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    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 :)

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like 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.

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it -14 Vote: I do not like it

        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?

        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +26 Vote: I do not like it

          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.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -19 Vote: I do not like it

      Red coders don't copy

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        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 :)

»
9 years ago, # |
  Vote: I like it -17 Vote: I do not like it

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... ;)

»
9 years ago, # |
  Vote: I like it -14 Vote: I do not like it

Some one should make The Goblet of Fire contest

»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).

»
9 years ago, # |
  Vote: I like it -62 Vote: I do not like it

Hunger games is for stupid little girls

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Happy Hunger games then !

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Just wish God will help you...

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -37 Vote: I do not like it

      I like the way you dislike me. Filling myself so important! Thank you, guys

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        So u were useless before getting dislikes right ?

»
9 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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?

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

5 Minutes

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    As I know, ACM rules is the only avaliable type of gym contests

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      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 :)

»
9 years ago, # |
  Vote: I like it +59 Vote: I do not like it

Could you please answer the clarification requests?

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

very nice problemset ,when we will able to discuss problems ?

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Shouldn't the output for test case #2 be 2 1 2?

Nevermind, i misunderstood the problem's statement.

»
9 years ago, # |
  Vote: I like it +57 Vote: I do not like it
if(problemid=='C' && submission_verdict=="AC"){
	submission_verdict="Denial of judgement";
}
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    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.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

      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

    • »
      »
      »
      9 years ago, # ^ |
      Rev. 3   Vote: I like it +5 Vote: I do not like it

      Edit: Nevermind my stupid comment. I got AC now.

»
9 years ago, # |
  Vote: I like it +26 Vote: I do not like it

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?

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    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.

    • »
      »
      »
      9 years ago, # ^ |
      Rev. 4   Vote: I like it +12 Vote: I do not like it

      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.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +48 Vote: I do not like it

      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

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +40 Vote: I do not like it

        Great disrespect to people who made this statement

        That's one of the best insults I've ever heard.

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But if a[i] is negative, is a[i]%n still non-negative or is it like in c++ that (-4)%3 == -1?

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        The mod is non-negative and it says a[i%n], not a[i]%n, look at the font very carefully.

»
9 years ago, # |
  Vote: I like it +13 Vote: I do not like it

"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 ?

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please explain me the 2nd statement for the F problem? Thx.

»
9 years ago, # |
  Vote: I like it +22 Vote: I do not like it

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.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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? :)

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I've written the code for problem E, but submit it somewhere else :)

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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).

»
9 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Can you please send a notification when you add new problems ?

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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)

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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

    • »
      »
      »
      9 years ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      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;
      }
      
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        No, it's more like

        int main()
        {
        	//read graph
        	while (true)
        	{
        		//do smth
        		cout << v << endl;
        		cin >> v;
        		if (v == 0) return 0;
        	}
        }
        
      • »
        »
        »
        »
        9 years ago, # ^ |
        Rev. 2   Vote: I like it +11 Vote: I do not like it

        No you don't read the graph again

        int main(){
            //read graph
            while(true){
                int v; // decide which node you want to query
                cout<<v<<endl; 
                int ans;
                cin>>ans; // this is the answer from judge
                if(ans==0)break;
            }
        }
        
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

In problem J, if I ask more than 33 questions, what will the verdict be?

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    WA

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's not WA, it's TLE, thank you....

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        If you take too long to ask them, it's obviously TLE...

        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            9 years ago, # ^ |
            Rev. 2   Vote: I like it +23 Vote: I do not like it

            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<<endl;
                cin>>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.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
9 years ago, # |
Rev. 2   Vote: I like it -18 Vote: I do not like it

deleted

»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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?

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +50 Vote: I do not like it

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      noooooo...why i can't solve that? :|

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +55 Vote: I do not like it

    He really wanted to play with her Pepsi Cola...

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I really want it too but I just have been removed from contest cause I registered as a team...:/

      Fuuuuu..

»
9 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

WTF is with you internet? -_-

»
9 years ago, # |
Rev. 3   Vote: I like it -17 Vote: I do not like it

Why??

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).

»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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?

»
9 years ago, # |
  Vote: I like it +56 Vote: I do not like it

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!)

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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.

»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Will be the editorial of the problems after the tournament? It is very interested to know how to solve some of the problems

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    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

»
9 years ago, # |
  Vote: I like it +53 Vote: I do not like it

But get ready, cause this shit's about to get heavy

When 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) ? =)

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    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.

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +24 Vote: I do not like it

      I'm struggling with "Pepsi cola" for quite a while now, you guys sadden me :D

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think allowing teams would have made this more exciting

  • »
    »
    9 years ago, # ^ |
    Rev. 3   Vote: I like it +5 Vote: I do not like it

    Well in case they actually plan to provide some rewards for top20 it would've been unfair to allow teams :)

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      One can always make an announcement that there has been a slight change in the rules at then end ;)

      jk, you're right. :D

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please add more problems.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by PrinceOfPersia (previous revision, new revision, compare).

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
9 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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?

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    It looks like I was removed from contest because I reimplemented that in less than 10 mins.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hamro and TheVampireDiaries — How can we do this in c++ since the limits are beyond even long long?

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    Actually, most of the people who solved it used c++

    • »
      »
      »
      9 years ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You should print any of them.

      • »
        »
        »
        »
        9 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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 :)

        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Thanks everyone. Just got AC and passed the 69 mark.

»
9 years ago, # |
  Vote: I like it +13 Vote: I do not like it

It would be bad if problem O happen with you in real life. Imagine that 50000 people want to kill you :P

»
9 years ago, # |
  Vote: I like it +13 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    It should be "some of its edges", I suppose, since there's "each edge" afterwards.

»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Will editorials be posted after the contest?

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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...

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +25 Vote: I do not like it

      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 :)

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you please extend the duration of contest by 2-3 days?

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What? Why should the competition be extended because someone asks for it? Is that not completely unfair to other competitors?

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it -38 Vote: I do not like it

      Why the fuck its unfair when duration is equal for all participants :||

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

»
9 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I agree, that sounds like a great idea, and I will be glad to help

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

»
9 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

that awkward moment when you realize you have solved as much as 20th participant and you are 21st :((

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Woohooo! Editorial :3

http://codeforces.net/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 :)

»
9 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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.

  • »
    »
    9 years ago, # ^ |
    Rev. 3   Vote: I like it +21 Vote: I do not like it

    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?

    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      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.

  • »
    »
    9 years ago, # ^ |
    Rev. 3   Vote: I like it +19 Vote: I do not like it

    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 ¯\_(ツ)_/¯)

»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

How to solve T?

  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

»
9 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

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.

  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Mine is N^3/32. Does N^2 solution exist?

    • »
      »
      »
      9 years ago, # ^ |
      Rev. 2   Vote: I like it +24 Vote: I do not like it

      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:

      I pRAY that people will understand this explanation

      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...

      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Wow, that's actually quite nice. Another great problem ruined by constant factors.

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
9 years ago, # |
  Vote: I like it +15 Vote: I do not like it

What about the prizes?

»
8 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Eagerly waiting for the 2nd hunger games. 1st one was a very good collection.