anup.kalbalia's blog

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

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

Time: 2130 hrs 18th December 2011 to 0000 hrs, 19th December 2011 (Indian Standard Time - +5:30 GMT)
Details: http://www.codechef.com/COOK17/
Registration: Just need to have a CodeChef user id to participate. New users please register here
Problem Setter: Hiroto Sekido (LayCurse)
Problem Tester: Jingbo Shang (shangjingbo)

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
  • +29
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
13 years ago, # |
  Vote: I like it +19 Vote: I do not like it
All problem statements are empty =(
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +31 Vote: I do not like it
    Statements are for noobs
    → Reply
  • »
    »
    13 years ago, # ^ |
    ← Rev. 2   Vote: I like it -53 Vote: I do not like it

    с условиями и дурак сдать может, а без условий слабо?))

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

      1 min ago    shindann...    Ciel and A-B...    C++ 4.3.2

      вот парниша последовал моему совету

      → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    Not the first time when such things happen. Also, there is another bug - status of this contest is "Ended" at the home page .

    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      он был с самого начала
      → Reply
»
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Could you share the testcase my solution fails on Random Walk?
→ Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Never mind, I've read the editorial and the part that Gaussian elimination is not supposed to pass. It's strange that the assertions that verify that the Gaussian elimination error is not big do not fail in my solution, though.
    → Reply
    • »
      »
      »
      13 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Nevertheless, the only accepted solution for this problem uses Gaussian elimination.
      → Reply
      • »
        »
        »
        »
        13 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        I don't know how he avoids float point round-off errors, but this is not the weirdest part. With a simple idea(try to calculate answer for each node with flower, and reduce size of matrix to 2n), there is a O(n^4) approach, instead of his O(n^6) one.

        Anyway, since the writer's approach is iteration with O(n^5 logn) complexity, O(n^6) is not that bad. The weirdest part is that he solves such big matrix(500x500) correctly with double, but for 60x60 matrix all other participations get WA. It seems that he didn't use some particular technique to avoids errors.

        B.T.W. I think the gauss eliminations can be optimized further to an O(n^3) approach, with BigDecimal, it's solvable theorically.
        → Reply
        • »
          »
          »
          »
          »
          13 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it
          The solution I was trying to submit during the contest has the complexity O(N^3). It gets WA, as expected. However, I haven't tried to submit it with BigDecimals.
          → Reply
          • »
            »
            »
            »
            »
            »
            13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            I think maybe your method is what I'm considering: do gauss elimination twice, first time to remove all non-flowered nodes, right?

            I think with O(n^3) complexity, it's enough even to implements a Fraction class with BigInteger.
            → Reply
          • »
            »
            »
            »
            »
            »
            13 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            Yes, I do Gaussian elimination twice: on the initial graph and on the graph without flowered nodes.
            Maybe I should have tried to implement a Fraction class. 
            → Reply
  • »
    »
    13 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it
    I've uploaded a part of (not all) judge cases. http://ideone.com/wuXju

    → Reply