anup.kalbalia's blog

Invitation to CodeChef’s July 2012 Algorithm Challenge
By anup.kalbalia, 12 years ago, In English

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 :

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.

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

»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

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

    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.

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

    Please find the editorials here: http://discuss.codechef.com/tags/july12/

    You may discuss all your issues on individual problems there.

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

    Here is my ADDCHAIN

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

      This is much shorter, and got 9.7+

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

        Well, I think mixed function may be easily removed (as it could not benefited from last optimization) and then basic solution is pretty short

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

      @Egor: Can you please explain your approach briefly. The code is too long!

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

        I still think that my code tells my approach better that I can express it in English

        → Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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?

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

    Well, considering I have not used any web resources while solving it... It seems Google was not that much help this time

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

      I've implemented an algorithm from one article and even without optimizations it was scoring around 325 points.

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

        Interesting, could you please give a link to the article?

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

          Here it is. I was talking about the adaptive window method.

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

      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.

      → Reply