Hello Codeforces Community!
I invite you to December Clash 2015. It will take place on Dec, 19-th at 9:30 MSK. Duration is 24 hours and submitting time doesn't matter so you can start whenever you want.
You will be given 5 algorithmic problems and one approximate (optimization) one. Some problems should be hard even for very strong competitors. All problems will have partial scoring (points for each test passed) and easier subtasks. Thus, everybody should find something for themselves.
EDIT — Problems are not necessarily sorted by the difficulty! Each problem is worth 100 points but scoring is partial so try to pass as many tests as possible! There is no penalty for incorrect submissions.
In my opinion problems are interesting and I hope you will have nice time solving them. It shouldn't be a typing competition for anybody. I'm very curious about the number of people with all 5 problems solved and about your scores in an approximate problem. We'll see.
I want to thank Akul Sareen (akulsareen) for his amazing help as a tester. He will also provide you editorials after a contest. And big thanks to HackerEarth admins — Arjit Srivastava (belowthebelt) and Ravi Ojha (raviojha2105).
Enjoy problems!
Oh, and there prizes. 5 T-shirts and 3 Amazon gift cards for the best participants. I guess it will make a fight for top spots a bit more interesting.
The contest is over! I hope you enjoyed it. Congratulations for top5, good job.
- mugurelionut
- Marcin_smu
- LayCurse
- zeliboba
- Carsten Eilks (HE account)
Is it a coincidence that top6 has nicely distributed scores? Roughly, the i-th place has score 510 - 10i.
Hackerearth staff* :P
Thanks, changed.
funny typo (it was "stuff" instead of "staff")
UPD: wrong comment
Problems are NOT necessarily sorted by the difficulty.
And sorry for the delay — missing problems will be added asap.
Should I expect one more problem? There are just 4 algorithmic ones so far.
Nope. There will be only 4 algorithmic problems and 1 approximate one.
How to solve Bear and Immugene for large tests?My solution is M*O(n^(1/2))*16 using blocks,but TLE for large tests.
Yeah, that's what I also had initially and tried really hard to optimize it to run in time — I could only make it score 80 points (the last 2 test cases still got TLE). But if you take a closer look, you'll see that when computing the answer, this looks a lot like multiplying some matrices together (e.g. you have one matrix for each block). So you can build a segment tree over the blocks, which is updated whenever each block is updated. This way, the answer will be found using the data stored in the root of the segment tree. Of course, at this point you don't really need blocks anymore — you could make each block equal to one character :) But that exceeded the memory for me, so in the end I used blocks of 16 characters and a segment tree over them.
As mugurelionut said, matrix exponentiation. We need to formulate dp in some way allowing us to move to the next letter by multiplying our matrix by some other matrix (defined by a letter).
Editorial is 100% ready but there are some technical issues. It should be visible soon. Now, I can give you my code — link. Complexity is
but matrices of sizes 5x5 were meant to get AC too.
The matrices of sizes 5x5 is easy to understand,however the 4x4 is a bit harder for me.
When will the tutorials be published?
There are some technical issues. I don't know when it will be resolved.
my codes: Immugene, Bowling, Roads, GCD Sum.
It was my first challenge/approximate problem. What do you guys think about "Bear and Equality"?
What should be changed and why?
There were two groups (types) of tests, each group with 10 tests. Would you prefer more groups? Or maybe only one? Would it be better to have more tests in a group?
And I encourage you to share your approaches to solving it ;)
I would've preferred if it was easier to find a solution at all. Some simple approaches (keep picking ranges based on some max. difference) totally TLE'd and would probably spend more than 106 operations.
The main problem seems to be that a lot of operations are needed to go from almost equal to equal. In that case, I'd introduce a penalty for not making all numbers perfectly equal; see the latest Codechef challenge problem (TANKS).
I really liked the fact that the process of generating the test data was properly described. This way we could generate local tests which had similar structure as the official tests, making local testing meaningful. In my case, most improvements on the local tests were also improvements on the official test cases, which was really good.
As Xellos said, it would have been nice if finding a solution was easier. Initially I tried various approaches and almost none of them worked (i.e. they couldn't find a solution in <= 10^6 steps). The first approach that was actually able to find solutions for all test cases was also at the core of my best submission :) [ this first solution scored 80.57 in the end, so even if I had stopped competing then, I would have got at least 3rd place, which is not bad :) ]. I will mention this first approach now and I will provide details on the improvements and what I have in my best submission later. Basically, the first approach tried at each step to select a move which:
is a maximal interval (in terms of sum)
has maximum "score": where the score of a move is equal to the absolute sum of differences between the elements in the interval and their average (i.e. the value with which they are replaced after the move) — for instance, if the interval consists of the elements [1,7,5], their average is (1+7+5)/3=4 and the score of this move is: |1-4|+|7-4|+|5-4|=3+3+1=7.
I don't exactly know why this approach finds relatively good solutions, though :)
I used DSU for Roads I maintain as many sets as the number of connected components initially calculated.In each set I store a pair of form <degree(v),v>(v is a vertex of that connected component).I also maintain a 'master' set which stores pair of form<degree of smallest vertex of connected component, smallest degree vertex of that component>. Now while the number of elements in master set are not one(till we form a tree) , I take the first two elements of the master set and merge the sets containing these two vertices(equivalent to merging the 2 components),remove these two elements from the master and insert the smallest vertex of the newly formed combined set(connected component). Sadly ,this solution fails on three test cases . Code. Any assistance will be highly appreciated.Thanks.
Have a look at this.
In this case your method might end up merging nodes 5 and 10 in which case you will never be able to get the actual answer of max degree = 3.
Thanks for taking the time to look into the code,but the hyperlink you provided isn't working.
Fixed.