MDCCXXIX's blog

Participate in HackerEarth's Monthly Hard Contest
By MDCCXXIX, 10 years ago, In English

Hello, everyone!

Check out August Clash, HackerEarth's first of a kind programming challenge for experienced programmers. Be assured to face some of the toughest problems and guaranteed fun. It will be a 12 hour contest, with 1 medium, 3 hard and a challenge problem to put your brain to the test! If you think you can win the clash, subscribe today and join the fun.

Problem Setter : Akashdeep Nain ,Lokesh Khandelwal,Prateek Gupta

Date: 16 August ,2014

Time : Check Time in your TimeZone

Link : August Clash

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

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

Wow. Such a long contest

What's the format of contest? Does it follow standard ICPC rules?

EDIT: sorry, I've got a problem registering. The website wants information of "college/university" but I'm not a university student now. So what should I fill in the chart ?

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

    You can fill your school/college/organisation name under "college/University".

    Contest Format: As given in post, — It will be a 12 hour contest — with 1 medium, 3 hard and a challenge problem.

    More info : — No penalty — partial marking is there (test file wise points) — can use almost all languages (C, C++, C#, Clojure, Haskell, Java, Perl, PHP, Python, Ruby, Objective-C, JavaScript)

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

Can anybody share the solution for the third problem? My O(N * 28) solution got TLE and I have no idea how to get rid of at least 27 factor.

Also I wonder what was the best solution for the last one? I believe that polynomial solution exists..

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

    I think you mean 3rd problem seeing as how you correctly solved the 4th problem.

    For the last problem my solution involved picking whichever was better: the set of the smallest n primes or the set of numbers from n to 2n-1 with numbers that were of the form 2x (where 3x>=2n) replaced by x instead.

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

    Well, my first submission for 30 points was an easy backtrack. Then I tried to optimalize it, which caused ~6 submissions, each of them for 30 points. So I realized two things: 1) I don't know how to write efficient codes and 2) the constant in backtrack is too big. So I decided to rewrite this backtrack as a plain dynamic programming. And it was the most stupid code I've ever written, but ~2 times faster. http://pastebin.com/QB9K2WMz

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

      Can you describe your idea? It's not really clear from the code above :p

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

        Let F(x,y,z) be a number of coverings of a board consisting of 3 strips of lengths x,y,z. We are looking for F(n,n,n).

        How does backtrack work? He takes triple (x,y,z), and goes to every possible triple that can be obtained from (x,y,z) via shortening of the longest strip. You just need to consider 3 cases (depending on position of the maximum) and in each case you consider all kinds of shortening (there at most 6 of them). Then you go to each triple (x', y', z') obtained by possible shortening and you have a (slow) solution.

        My dp solution is based on exactly the same idea. A[i][p][q] = F(i, i — p, i — q), B[i][p][q] = F(i — p, i, i — q). And I just consider all the cases (22 of them). Beautiful, isn't it? :D

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

      There is another dp solution. f(n, a, b, c) stores number of ways for a board of size 3 x (n-2) adjoined with another board of the form (a+b+c). We want f(n, 2, 2, 2). The recursion is straightforward but again, we have lots of case handling. It fetched me only 30 points and I had to use matrix exponentiation to make it pass. Code: http://pastebin.com/XnvFqRVg

      The contest is definitely not hard, it is rather very straightforward.

      By the way, JohnPaulII, nice code :D

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

    Editorial — http://www.hackerearth.com/problem/algorithm/building-the-wall-2/editorial/

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

      I gave up this idea after I didn't find the sequence at oeis.org :(

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

        Haha, I was looking there for it too. Now, when I have such a nice recursive formula, I can add this sequence to the oeis :D

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

Did anyone try to solve third problem with primary statement? We are looking for number of different coverings of wall 3xn, where 2 coverings are identical when COLOR of each cell is the same in both walls. I think that this problem is a bit harder, but I haven't tried to solve it yet.

→ Reply