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
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 ?
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)
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..
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.
Yeah, the third problem, thanks for pointing it.
Do you know how can I submit problems after the contest? Added your idea to my solution and want to see how much points can it get.
http://www.hackerearth.com/august-clash/
Contest has been added to practice section.
This problem is no longer available for practice. Apology for any inconvenience!
:(
Last problem also added to practice :)
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
Can you describe your idea? It's not really clear from the code above :p
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
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
Editorial — http://www.hackerearth.com/problem/algorithm/building-the-wall-2/editorial/
I gave up this idea after I didn't find the sequence at oeis.org :(
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
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.