Блог пользователя Errichto

Автор Errichto, 7 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +90
  • Проголосовать: не нравится

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

can one miss one round and participate in other??

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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... :'-(

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

where can we find link to the dashboard?

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +48 Проголосовать: не нравится

is it only me unable to see the problems??

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +15 Проголосовать: не нравится

Are the questions loading for anyone?

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +110 Проголосовать: не нравится

somehow i am tired of their Shakespeare language

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

Is it possible to see country-wise standings?

»
7 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +8 Проголосовать: не нравится

My solutions to first two:

Pylons
Golf Gophers
Alien Rhyme (why greedy passed the first set didn't the second?)
»
7 лет назад, скрыть # |
Rev. 3  
Проголосовать: нравится +18 Проголосовать: не нравится

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
  • »
    »
    7 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, скрыть # ^ |
       
      Проголосовать: нравится +3 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        7 лет назад, скрыть # ^ |
         
        Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
7 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

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

C++ Code

»
7 лет назад, скрыть # |
Rev. 4  
Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +5 Проголосовать: не нравится

    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.

»
7 лет назад, скрыть # |
Rev. 2  
Проголосовать: нравится +6 Проголосовать: не нравится

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]$$$ $$$- \gt $$$ $$$mat[1]$$$ $$$[$$$$$$(i+3)mod\ m$$$$$$]$$$ $$$- \gt $$$ $$$mat[0][i+1]$$$.

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

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

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

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.

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, скрыть # ^ |
       
      Проголосовать: нравится 0 Проголосовать: не нравится

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

      C++
»
7 лет назад, скрыть # |
Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, скрыть # ^ |
    Rev. 3  
    Проголосовать: нравится 0 Проголосовать: не нравится

    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
  • »
    »
    7 лет назад, скрыть # ^ |
    Rev. 2  
    Проголосовать: нравится 0 Проголосовать: не нравится
  • »
    »
    7 лет назад, скрыть # ^ |
     
    Проголосовать: нравится +1 Проголосовать: не нравится

    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
»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

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/

»
7 лет назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

can someone find a error in my solutions for pylons

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