Errichto's blog

By Errichto, 2 weeks ago, In English,

Google Code Jam round 1A starts in less than 3 hours. https://codingcompetitions.withgoogle.com/codejam

In each of rounds 1A, 1B, 1C, top 1500 participants will advance to round 2 (4500 in total).

I'm not going to participate (because it's the middle of a night for me), but a reminder might help other people.

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

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can one miss one round and participate in other??

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Yes you have to be in top 1500 of any of 1A, 1B, 1C in order to pass to round 2.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

The page says "The countdown to Round 1A 2019 is on", but I can't find a countdown anywhere. Am I missing something? I hope I'm waiting in the right place, not that it would make any difference even if I was late, I just want to see the problems.

I know this is a new interface by Google, but I hope they make it a bit more exciting next year. One wouldn't know that an international event is shortly going to take place with thousands of programmers waiting anxiously to compete. Ten years ago, the Topcoder chatroom before a big event had a dynamic atmosphere and was a great place to meet programming friends and hang out. I miss that... :'-(

»
13 days ago, # |
  Vote: I like it +3 Vote: I do not like it

where can we find link to the dashboard?

»
13 days ago, # |
  Vote: I like it +48 Vote: I do not like it

is it only me unable to see the problems??

»
13 days ago, # |
  Vote: I like it +15 Vote: I do not like it

Are the questions loading for anyone?

»
13 days ago, # |
  Vote: I like it +110 Vote: I do not like it

somehow i am tired of their Shakespeare language

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Why my rank is decreased from 200+ to 180+?

»
13 days ago, # |
  Vote: I like it +5 Vote: I do not like it

Is it possible to see country-wise standings?

»
13 days ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

My solutions to first two:

Pylons
Golf Gophers
Alien Rhyme (why greedy passed the first set didn't the second?)
  • »
    »
    13 days ago, # ^ |
    Rev. 3   Vote: I like it +23 Vote: I do not like it

    You can easily implement the solution to Alien Rhyme by reversing the strings and then building a trie on them. After that each node in the trie can eliminate exactly two words so you can just run greedy on that trie and see how many words aren't matched at the end.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    One of my friend get AC on Pylons by random shuffle.

    Meanwhile, my code on this problem nearly reached 200 lines and still not get AC...

  • »
    »
    13 days ago, # ^ |
    Rev. 2   Vote: I like it +9 Vote: I do not like it

    Also, if we keep going to furthest point by Manhattan distance, for the case $$$n = 2$$$, $$$m = 5$$$, isn't it will go $$$(1, 1) \rightarrow (2, 5) \rightarrow (1, 2) \rightarrow (2, 4)$$$ and get stuck at $$$(2, 4)$$$?

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Whoops. Sorry about that. I go both nearest and furthest point in the recursion. I forgot to block the "going the nearest" line while thinking it was blocked. So, it seems more reasonable why randomized solution works.

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I did something completely different. I did DFS for small cases (r<5 || c<5) and then did a filling hueristic that's quite like the example solution for the other cases.

      assume c>4, then we can just do what they did in the example in 2 x 5, going down the rows 2 at a time. If we have 3 left, just do the last 3 together in a similar manner.

      for example for 3 x 5 this is the solution:

      10 13 1 4  7
      2  5  8 11 14
      12 15 3 6  9
      

      here is the code (not including the dfs):

      Code
  • »
    »
    13 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    For alien rhyme sort all suffixes by their lengths and choose any two not choosen words that have this suffix.

    For Pylons first i did random moves until there are 10 cells left, and then did bruteforce. But "furthest cell tactic" did't work for me Oo

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My randomised pylons solution that passed the large test case. Repeat the following process 1000 times or until we find a solution. Go to a random point. Take a random jump to another point that is unvisited and satisfies the row, column and diagonal conditions. Keep doing this until we run out of valid points. If we visited everything we have a solution.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I had the same solution for problem C and it failed the second test set. I also don't know why.

    • »
      »
      »
      13 days ago, # ^ |
      Rev. 2   Vote: I like it +11 Vote: I do not like it

      It should work I believe, as long as you’re extremely careful with implementation. For {aa, ba, ca, da} the answer is 2, since you can only take one pair with suffix a. But for {aaa, baa, caa, daa} the answer is 4, since you can take a pair with suffix a; and a pair with suffix aa. So the implementation of this approach has to essentially realize that because you can no longer take this pair with suffix of length x, you could still take it potentially with a suffix of length x-1. I suspect you might be missing that.

      Too late, nanobyte got it first!

      • »
        »
        »
        »
        3 days ago, # ^ |
        Rev. 3   Vote: I like it 0 Vote: I do not like it

        hi could you help me, i use dictionary to list all the possible suffix as a key and put the numbers of suffix as the values. i can't find where my program fail

        ulang = int(input())
        for u in range (1,ulang+1):
            word = {}
            N = int(input())
            for i in range (0,N):
                temp = input()
                for j in range (0,len(temp)):
        
                    if temp[j:] in word:
                        word[temp[j:]] += 1
                    else:
                        word[temp[j:]]=1
            
           
            doneKey= []
            ryhme = 0
            ListOfKeys = []
            alreadyIn = False
        
            for k in word:
                ListOfKeys.append(k)
            ListOfKeys.sort(key = lambda s:len(s),reverse=True)
            
            
            for i in ListOfKeys:
                
                if word[i] > 1:
                    for j in range (0,len(doneKey)):
                        
                        if i == doneKey[j]:
                            alreadyIn = True
                            break
                    
                    if alreadyIn== True :
                        continue
                    else:
                        for l in word:
                            if l in i:
                                word[l] -= 2
                        ryhme += 2
                        doneKey.append(i)
            
            
            print ("Case #{}: {}".format(u,ryhme))
        

        I use python btw

  • »
    »
    13 days ago, # ^ |
    Rev. 4   Vote: I like it +9 Vote: I do not like it

    Problem: Alien Rhyme

    I did the same as you and it failed the large set. This approach will fail in the following test case:

    Spoiler
  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    TooNewbie , why is better to go first to the farthest one , then to the nearest ? When i wrote first to the nearest one ,then to the farthest , it gives TLE . Maybe ,the best do it random ?

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Your solution shouldn't exceed the TL. Keeping priority on the nearest point works well and fast (somehow). Check my code above.

»
13 days ago, # |
Rev. 3   Vote: I like it +18 Vote: I do not like it

A lazy way:

  • I'm too sleepy to try to construct an approach.
  • Would random work well here?
  • Write a fully recursive brute-force, where on every step we try every possible move in a random order.
  • Try to find solutions for all cases.
  • Switch seeds until all cases pass (too lazy to do it separately) -- 4th attempt works.
  • Now we precomputed all the answers.
  • Encode it so that it fits in 100KB (using 2 letters A-T for coordinates just about works).
  • PROFIT
  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For what do you need the steps 4 to 7? Randomized recursive brute-force will get accepted.

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      On my PC some samples got stuck using randomized recursive brute-force, which led me to believe that you can make a very poor choice early on, that will make the solution impossible. I understand from analysis, that if you get stuck, you can abandon everything and try again -- and that works; but once again, if you can pre-compute (and too lazy to estimate probabilities), why worry at all :D

      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah, I tested all possible inputs locally right now. Most of the time it can solve all test cases in less then 1 second total, but sometimes it takes more than half a minute or even longer. Guess I've been lucky during the contest.

»
13 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I tried using the method described here with a Knight's Tour, why does my large for Pylons fail???

C++ Code

»
13 days ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

For C I first constructed a trie of all of the strings reversed and then calculated the answer based on this dfs:

int getans(tnode* t) {
    int rem = t->cnt; // cnt is number of strings that pass through this node
    int res = 0;
    M00(i, 26) if(t->next[i] != nullptr) {
        int k = getans(t->next[i]);
        rem -= k;
        res += k;
    }
    if(rem >= 2 && t->c != ' ') res+=2; // second condition makes sure this is not the root node (which means common suffix has length 0)
    return res;
}

I'm not sure why this solution works. Can anyone tell me?

EDIT: NVM I UNDERSTAND

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Every string you can match with a suffix of length x, you can also match with any suffix of smaller length. As such, the greedy approach of matching the strings from the longest suffixes, which you have implemented, works. You're matching everything with the longer suffixes first, and then if you have at least 2 more strings with the current suffix remaining, there is no difference between any of them, so you can just take 2 at random.

»
13 days ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

My solution for PYLONS was to divide the matrix into steps of 2s and 3(if odd). We can start at $$$mat[0][0]$$$ and follow a pattern.

The pattern for $$$2*m$$$ is $$$mat[0][i]$$$ $$$->$$$ $$$mat[1]$$$ $$$[$$$$$$(i+3)mod\ m$$$$$$]$$$ $$$->$$$ $$$mat[0][i+1]$$$.

For $$$3*m$$$, you can do $$$mat[0][i] -> mat[1][(i+3)mod\ m] -> mat[2][i] -> mat[0][i+1]$$$.

You'll have to take care of some corner cases, like when $$$max(n,m)<=4$$$

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I can't find any counter example for my solution for Pylons (simple test case). https://gist.github.com/kronos/d8ccb2941cd057c28d9bc0192b9a6652 if you see any issues in my solution — please, let me know.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Just write checker and check all possible tests, it is very easy in this problem

  • »
    »
    13 days ago, # ^ |
    Rev. 2   Vote: I like it +3 Vote: I do not like it

    I had the same problem. Every case with N == M is bad (basically you should do jump 3 in case N == M) + there is no regular pattern for 4 4 -> you should choose a correct permutation for the last 4 elements.

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      12 and 13 on the same diagonal, thanks.

      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        This is for 4x4 case — you can just switch the order of 13,14,15 and 16. For all other cases (2,x) and (N,N) jump 3 will do the job.

        • »
          »
          »
          »
          »
          13 days ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I situation (2,x) is handled already in the source I posted

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Good hacks for Alien Rhyme? I solved the visible but got WA for hidden and don't know what to do

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

https://ideone.com/e.js/mKXWib i cant find a mistake-pylons

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone give a counter-case for my solution to third problem?

»
13 days ago, # |
  Vote: I like it +1 Vote: I do not like it

Solution for alien rhyme:

  • Make an unordered_map, where key is all possible suffix for each of the word and value is a vector that stores the words for which we got that suffix

  • iterate through the map, and for all keys(suffixes) that have more than 1 element in their vector (i.e. there are more than 1 word that have that suffix), push those keys in a new vector.

  • This new vector would be sorted by length of string in decreasing order

  • for each of suffix in vector, choose 2 words from map that are not yet used.

  • Finally print the count of all chosen words.

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

On C, I didn't do trie/hashmap, just reversed and sorted the words and put in a linked list, and then from len 50 to 1 deleted adjacent words if they shared the same prefix length len, and that prefix wasn't the previously deleted words one.

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    U deleted the two adjacent words even if their prefix length was not greatest ?

    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Maybe I didn't explain myself well, here is the code

      C++
»
13 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Can someone post solution for C where u dont use a trie ? (Actual Code)

  • »
    »
    13 days ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Sure: it's quite the same, but this is how I thought about it.

    Used recursion going from the last to the first index, and trying to pair together strings that match each other far as I can, and then going down the recursion at each phase trying to pair 2 string that are still unpaired.

    Code
    • »
      »
      »
      13 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You do like to have functions named "solve". You have two in your code and the inner one doesn't need to be a function, I think :)

      • »
        »
        »
        »
        13 days ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        yup you are right :) Coding this also yield a lot of bugs, so it's probably have been better to work differently.

  • »
    »
    13 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
  • »
    »
    13 days ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Sure, here's the brute force implementation of the greedy algorithm:

    Make a list of all of the suffixes. Process them in order of longest to shortest. If there are at least two words with this suffix that haven't been paired, pair any two of them.

    My straightforward implementation of this with a map is $$$O(n w^2 \log(n w))$$$, which is fast enough in C++. It's not too hard to optimize this with a trie or hashing, but given the low bounds this was sufficient.

    Code
»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

pylon can be solved in two ways. O(r*c) make 2*n,3*n split few case will fail have to hard code them in my case 4*4,4*6,6*4,6*6 https://shashankmishracoder.wordpress.com/2019/04/13/google-code-jam-2019-round1a-pylon/

another way is to use dfs and backtracks for depth r*c https://shashankmishracoder.wordpress.com/2019/04/13/google-code-jam-2019-round-1a-pylon-dfs-and-backtracking-approach/

»
13 days ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone find a error in my solutions for pylons

[Link]-(https://pastebin.com/1UWXk9GA)

  • »
    »
    13 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yours is showing impossible for 4x3,5x2,5x3 use r*c<=9 impossible as condition

»
12 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

can someone find a error in my solutions for alien poem

It can pass test case 1 but got WA in test case 2..

[Link]-(https://pastebin.com/4i1Erkdy)

»
11 days ago, # |
  Vote: I like it -20 Vote: I do not like it

GCJ 2019 Round 1A Pylons

I tried backtracking, but got stuck in time limit.