anup.kalbalia's blog

Invitation to the September 2013 Cook-off on CodeChef
By anup.kalbalia, 11 years ago, In English

CodeChef invites you to participate in the September CookOff 2013 at http://www.codechef.com/COOK38.

Time: 22nd September 2013 (2130 hrs) to 23rd September 2013 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: http://www.codechef.com/COOK38/

Registration: Just need to have a CodeChef user id to participate.

New users please register here

It promises to deliver on an interesting set of algorithmic problems with something for all.
The contest is open for all and those, who are interested, are requested to have a CodeChef userid, in order to participate.

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

Comments Comments (15)
| Write comment?
»
11 years ago, # |
  Vote: I like it +39 Vote: I do not like it

I would like to say that we did our best to make statements as short as possible and thank the tester.

It's the first contest that all five problems are prepaired by myself and I am pretty excited :) I would like everybody to share your impressions after the contest.

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

    I am satisfied. Not with my performance (too many WAs due to stress, I got 9th place in the last contest and tried hard to defend it), but the problems were quite good. I especially like BIGNUM.

    BTW it's kind of an honor for you to have your initials at the start of every tasks's short name :D

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

      Thanks a lot. I had to put my initials just because problem code should be unique :)

      → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Why modulo was required in problem RRGAME?

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

    It wasn't really required, since the answer is clearly no more than M. I just computed the answer as long long and printed it modulated :D

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

    What is your approach on Tree problem ?

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 4   Vote: I like it +8 Vote: I do not like it

      There is some known way how to calculate diameter. Find the most distant vertex from root (denote it v), and than the most distant from v. That distance will be the diameter.

      Using this fact you can easily keep track on diameters. When you add vertex i, if it's parent is one of the most distant vertices from root (by the moment), then you say that the current result is increased by 1 and there is new most distant vertex from root. If not, than the answer can only be increased by the path from current most distant vertex (from root) and vertex i. You can calculate that path using LCA.

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

        Thanks :)

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

        Well done! Neither me, nor tester invented such a neat solution. Mine uses divide&conquer and tester's appraoch requires hldot :)

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

          Can you write in short divide&conquer solution ?

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

            Sure: We are to find the most distant vertex U for every Vertex V such that U<V. Let's call such vertex U F[V].

            Let's fix a vertex R. We can count all answer for V if path from V to F[V] goes through R using a lot of data structues, even Segment Tree will do. So, let's take a look at our tree, choose R and update F[]. Then we delete vertex R and do the same for new connected components because if some path V->F[V] does not go through the vertex R it will lay in one of these connected components.

            Feel free to ask for details, because my explanation does not seems pretty clear :)

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

              thank you , nice solution :)

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

    It was like a reverse engineering hack.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      I think so :)

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

      this is something very similar to what was used in the model solution of IOI 2011 Race. This divide and conquer approach on trees is a useful trick.

      → Reply