Блог пользователя PrinceOfPersia

Автор PrinceOfPersia, история, 9 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +291
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

came @ right time :) awesome idea

»
9 лет назад, # |
  Проголосовать: нравится +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

»
9 лет назад, # |
  Проголосовать: нравится +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?

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
9 лет назад, # |
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

»
9 лет назад, # |
  Проголосовать: нравится +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 :)

»
9 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

That seems nice! :)

»
9 лет назад, # |
  Проголосовать: нравится +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.

»
9 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I think it is better to take separated div tournoment

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

will you put the problems in persian language too?

»
9 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +84 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Don't copy yourself idea kinda sucks :\

»
9 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

why is there a tag "killing" ? :D

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

By the way, when will the game begin?

»
9 лет назад, # |
  Проголосовать: нравится +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.

  • »
    »
    9 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +78 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
    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 :)

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +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.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится -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?

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится +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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится -19 Проголосовать: не нравится

      Red coders don't copy

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +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 :)

»
9 лет назад, # |
  Проголосовать: нравится -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... ;)

»
9 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

Some one should make The Goblet of Fire contest

»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится -62 Проголосовать: не нравится

Hunger games is for stupid little girls

»
9 лет назад, # |
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?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

5 Minutes

»
9 лет назад, # |
  Проголосовать: нравится 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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +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 :)

»
9 лет назад, # |
  Проголосовать: нравится +59 Проголосовать: не нравится

Could you please answer the clarification requests?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

Nevermind, i misunderstood the problem's statement.

»
9 лет назад, # |
  Проголосовать: нравится +57 Проголосовать: не нравится
if(problemid=='C' && submission_verdict=="AC"){
	submission_verdict="Denial of judgement";
}
  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +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.

»
9 лет назад, # |
  Проголосовать: нравится +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?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    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 лет назад, # ^ |
      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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +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

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +40 Проголосовать: не нравится

        Great disrespect to people who made this statement

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

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +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 ?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 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? :)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 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).

»
9 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

»
9 лет назад, # |
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)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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 лет назад, # ^ |
      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;
      }
      
      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        No, it's more like

        int main()
        {
        	//read graph
        	while (true)
        	{
        		//do smth
        		cout << v << endl;
        		cin >> v;
        		if (v == 0) return 0;
        	}
        }
        
      • »
        »
        »
        »
        9 лет назад, # ^ |
        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<<v<<endl; 
                int ans;
                cin>>ans; // this is the answer from judge
                if(ans==0)break;
            }
        }
        
»
9 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    WA

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится +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.

          • »
            »
            »
            »
            »
            »
            9 лет назад, # ^ |
            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<<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 лет назад, # ^ |
        Проголосовать: нравится 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?

»
9 лет назад, # |
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

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится -18 Проголосовать: не нравится

deleted

»
9 лет назад, # |
  Проголосовать: нравится +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?

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

WTF is with you internet? -_-

»
9 лет назад, # |
Rev. 3   Проголосовать: нравится -17 Проголосовать: не нравится

Why??

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +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?

»
9 лет назад, # |
  Проголосовать: нравится +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!)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +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.

»
9 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +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

»
9 лет назад, # |
  Проголосовать: нравится +53 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +24 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think allowing teams would have made this more exciting

  • »
    »
    9 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

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

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please add more problems.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 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?

»
9 лет назад, # |
  Проголосовать: нравится +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?

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

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

    • »
      »
      »
      9 лет назад, # ^ |
      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?

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        You should print any of them.

      • »
        »
        »
        »
        9 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +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

»
9 лет назад, # |
  Проголосовать: нравится 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?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Will editorials be posted after the contest?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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 лет назад, # ^ |
        Проголосовать: нравится +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 :)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +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.

»
9 лет назад, # |
  Проголосовать: нравится +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.

»
9 лет назад, # |
  Проголосовать: нравится 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!

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Woohooo! Editorial :3

http://codeforces.me/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 лет назад, # |
  Проголосовать: нравится -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.

  • »
    »
    9 лет назад, # ^ |
    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 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 лет назад, # ^ |
        Проголосовать: нравится +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.

  • »
    »
    9 лет назад, # ^ |
    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 + 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 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

How to solve T?

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 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)

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

    • »
      »
      »
      9 лет назад, # ^ |
      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:

      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 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

What about the prizes?

»
8 лет назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

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