anup.kalbalia's blog

Invitation to the December 2012 Cook-off on CodeChef
By anup.kalbalia, 12 years ago, In English

CodeChef invites you to participate in the December CookOff 2012 at http://www.codechef.com/COOK29.

Time: 23rd December 2012 (2130 hrs) to 24th December 2012 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.
Details: http://www.codechef.com/COOK29/
Registration: Just need to have a CodeChef user id to participate. New users please register here
Problem Setter: David Stolp
Problem Tester: Anton Lunyov
Editorialist: Pradeep Mathias

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

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

"2130 hrs" is more than 88 days! I hope this is a typo! :D

→ Reply
»
12 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Thank you for the contest! I liked the problemset very much.

→ Reply
»
12 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Very interesting and balanced problemset! :)

→ Reply
»
12 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Thanks for the nice contest. How many non-indian participants will receive Codechef T-Shirt?

→ Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Oh, 5th problem! So simple solution! Really nice contest!

→ Reply
»
12 years ago, # |
  Vote: I like it +36 Vote: I do not like it

Finally, I've solved TREEROOT. Really nice constraints.

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Edit: Tutorial is now available!

Can someone explain the idea behind "Expected Greatest Common Divisor". Looks like the editorial for this problem is a bit delayed.

I couldn't find a solution to the main problem: what is the number of 5-tuples (x1,...,x5) s.t. ai<=xi<=bi and gcd(x1,...,x5)=1. There was a simpler problem discussed on TopCoder forums, where the constraint was 1<=xi<=n.

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

    Instead of directly answering your question, the solution (at least mine) first calculates the number of tuples where each element (and therefore GCD) is divisible by 1, 2, 3, ..., N = 200 000.

    After that, the number of tuples with GCD being exactly 1, 2, 3, ..., N can be found in an pass.

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

      Thanks a lot for your answer. I did the 1st step of your comment, however I assumed the 2nd step would take O(N*N) time (till I saw your code :) ).

      → Reply