anup.kalbalia's blog

Invitation to the July 2012 Cook-off on CodeChef

By anup.kalbalia, 12 years ago, In English

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

Time: 2130 hrs 22nd July 2012 to 0000 hrs, 23rd July 2012 (Indian Standard Time — +5:30 GMT) — Check your timezone.
Details: http://www.codechef.com/COOK24/
Registration: Just need to have a CodeChef user id to participate. New users please register here
Problem Setter: Hiroto Sekido
Problem Tester: Maxim Kolosovskiy / Anton_Lunyov.
Problem Editorialist: Anton_Lunyov.

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.

Tags: algorithms codechef recent contest

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

»
12 years ago, # |
← Rev. 2   Vote: I like it -15 Vote: I do not like it

Вопрос, я смогу сделать пару задач?Данным вопросом я прошу рассказать мне об уровне сложности задач!

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

Can i see the number of wrong test&

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

    If you mean whether you can see the test data or not, then the answer is no. We will make all solutions public at the end of the contest and also publish editorials. You can then ask your doubts from our problem setters on our editorial pages.

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

Very hard contest (2 last problems) ...

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

I got wrong answer in CEILTOMY.(number of shortest paths) ... I tried for over 1 hour but could not find the mistake in my code...Because of this my correct sub to CEILMAP was also delayed..Please somebody see my code and tell me where is it wrong...I am very anxious to know it..link

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

Well, that's unbalanced contest. 106 participants with three solved problems and only one with four. But I enjoyed the last two ones, thanks.

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

You can check the editorials here: http://discuss.codechef.com/tags/cook24/. Please feel free to ask your questions and discuss your doubts there.

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

Who have ideas to "Ciel Numbers III" ?

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

    I had some and I really want to upsolve it. I thought that the answer should be the same length as the input =)

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

My approach for CIELMAP: "Find the convex hull of set of points and then iterate over every pair of point on the convex hull to find max length segment such that number of points on any one of the side of the segment is greater than 1"

O(nlogn) + O(n^2) : worst case

I got WA, why this approach is not correct ? Code

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

    Your approach is wrong for the case N=4. Try test 0 0 2 0 1 2 1 1 With your approach you did not find the answer at all. But the correct answer is sqrt(5) since (0,0), (2,0), (1,1), (1,2) is a simple tetragon having side (1,2)-(0,0) of length sqrt(5).

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

      Oh, that was a terrible mistake :(, need to improve a lot.

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

    There are exist testcases that two farthest points doesn't lie in convex hull, but if n>=5 the answer is maximum distance.

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

      That's impossible — two farthest points always lay on the convex hull

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

    Described approach (I didn't read the code) should fail on this test (even if you count non-hull points as well):

    4

    0 0

    0 4

    1 4

    2 5

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

    Perhaps it would work if, when calculating npa and npb, you counted all points, not just points on the convex hull.

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

      With 1250 test cases, it would have TLE'd.

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

        The sum of N over all test cases is no more than 5000, so it would be OK.

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

          I think it won't work for concave polygon.

          → Reply