We hope you participated and enjoyed the changes made to monthly Long Contests. We had made some changes to the long contest format to make it more exciting. 10 problems for 10 days! It now has everything for everyone, be it a newbie or a veteran You can read more about it in here.
Continuing from there, we bring you the CodeChef July 2012 Long Challenge. The July 2012 Algorithm Challenge is taking place on http://www.codechef.com/JULY12.
Here are the details:
Date: 1st July 2012 to 11th July 2012
Duration: 10 days
Problems: 9 binary problems of varying difficulty levels + 1 challenge problem.
Problem Setters :
- Namit Shetty (shettynamit),
- Shanjingbo,
- Kamran maharov (kamran_maharov),
- Vitaliy Herasymiv (witua),
- Nikhil Garg (Nikhil),
- Sergey Kulik (cherrytree304),
- Kaushik Iska (cauchyk),
- Gennady Korotkevich (tourist ),
- Vamsi Kavala,
- Anton Lunyov (Anton_Lunyov).
Problem Tester: Hiroto Sekido (LayCurse),
It promises to deliver on an interesting set of algorithmic problems with prizes up for grabs.
The contest is open for all and those, who are interested, are requested to register in order to participate.
Check out the local time in your City/Time Zone here. Do share your feedback on what you feel about the new long contest format at [email protected]
Good Luck! Hope to see you participating.
The contest has ended, let's discuss problems here. Please, tell how to find chain with length less than 325 in ADDCHAIN? Also, how to solve EST?
In EST I proved the following strange thing.
Notice that "remapping" characters (like swapping 'a' and 'b' values) doesn't affect unlabeled suffix trie. Let a normalized string be a string that is lexicographically smaller than any string produced by "remapping" its characters. We can normalize input string, count normalized strings with equal suffix trie and multiply the answer by 26 * 25 * ... * (27-A), where A is the number of different characters in input string.
Let S[1..n] be the input string, T — another string with isomorphic suffix trie. Let's call a range Z[i..j] of a string Z nice if i..j is not the first occurrence of substring Z[i..j] in Z (i.e. if there exists k>0 Z[i-k..j-k]=Z[i..j]). Ley's find the longest nice suffix of S and call it S[p..n]. In suffix trie it corresponds to the longest "hidden" suffix, i.e. a suffix that ends not in a leaf. It's not hard to prove that T[1..p-1]=S[1..p-1], i.e. we can't change first p-1 characters. So we can only change S[p..n] to something nice. There are p-1 candidates for T[p..n]: for any i<p we can assume T[i..i+n-p]=T[p..n], which uniquely defines T. Now the problem is to check if a candidate T has the same suffix trie as S. That's when the voodoo begins. If S[p-1..p-1] is not nice (i.e. if p-1 is the first occurrence of some character), then all candidates are valid. Otherwise, let's find the biggest q such that S[p-1..q] is nice. Now the candidate is valid iff T[1..q]=S[1..q] and T[p-1..q+1] is not nice. Proving it took me some insight about how suffixes are "hiding" and "unhiding" in suffix trie as we add characters to the end of the string. This condition can be checked with hashes in a bit tricky way.
Please find the editorials here: http://discuss.codechef.com/tags/july12/
You may discuss all your issues on individual problems there.
Here is my ADDCHAIN
This is much shorter, and got 9.7+
Well, I think mixed function may be easily removed (as it could not benefited from last optimization) and then basic solution is pretty short
@Egor: Can you please explain your approach briefly. The code is too long!
I still think that my code tells my approach better that I can express it in English
ADDCHAIN is a well studied problem and it's very easy to google many articles about it. What's the reason of including this problem into the problemset? Can we expect a travelling salesman problem on the next contest?
Well, considering I have not used any web resources while solving it... It seems Google was not that much help this time
I've implemented an algorithm from one article and even without optimizations it was scoring around 325 points.
Interesting, could you please give a link to the article?
Here it is. I was talking about the adaptive window method.
Thank you!
Reading a few pages of Art of Computer Programming Vol 2 about Addition Chains was enough to get about 324. Also there was another problem about Addition Chains recently in Codility, backtracking was enough though.