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.

can one miss one round and participate in other??

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

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

Hope this help

Thanks. Yeah, that's where I am waiting . . .

where can we find link to the dashboard?

https://codingcompetitions.withgoogle.com/codejam/round/0000000000051635

is it only me unable to see the problems??

Me too Edit: seen it.

no : working now

Its working now

Are the questions loading for anyone?

somehow i am tired of their Shakespeare language

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

Oh,i think somebody submits again.

Is it possible to see country-wise standings?

My solutions to first two:

PylonsHandle easy impossible cases: n = 1 or m = 1 or (n, m) = (2, 3) or (n, m) = (2, 4) or (n, m) = (3, 3).

Then start from (1, 1) and each time go to the furthest point and nearest point by Manhattan distance in recursion.

Golf GophersWell, if we choose count of the blades in each windmill equally, summing up the numbers given by judge would yield answer modulo chosen number. So, we can use Chinese Remainder Theorem here. It is enough to choose 6 numbers to get product > $$$10^6$$$. I chose 5, 7, 11, 13, 17, 18.

Alien Rhyme (why greedy passed the first set didn't the second?)For each pair of words, find longest common suffix and store them. Then greedily select the words with sorting them in decreasing order of length of common suffix. It's $$$O(n^2*(|w_i|+log(n^2))$$$ (or at least I wrote this way), but 20 seconds does seem enough to pass all test-cases.

Is it correct?

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.

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...

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)$$$?

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.

So you decided which cell to search first (the nearest or furthest one) by random?

The nearest.

And somehow, it worked in given TL?

It works really fast. You can check the code: https://pastebin.com/LsB8vA2t

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:

here is the code (not including the dfs):

CodeFor 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

can u share ur alien rhyme solution ?

Yes

This link is broken

It worked yesterday. New link

Yes now working :) Maybe some server issues yesterday

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.

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

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!

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

I use python btw

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

SpoilerT = 1

1

DBCD

EBCD

FBCD

GBCD

In the above case, the longest common suffix with give ans as 2, whereas the correct ans is 4 since you can take pairs as (DBCD, EBCD) with B as pivot point and (FBCD, GBCD) with C as pivot point.

Just considering all common suffixes instead of the longest common suffix passes the large set.

Thanks a lot i was missing this point

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 ?

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

A lazy way:

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

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

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.

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

C++ Code

Editorial: https://codejam.withgoogle.com/2018/challenges/0000000000051635/analysis

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

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

EDIT: NVM I UNDERSTAND

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.I used the same approach as above(trie) but failed even in the small dataset, could someone please give a test case where my code fails. LINK:https://pastebin.com/JjRFMu8v

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$$$

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.

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

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.

12 and 13 on the same diagonal, thanks.

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.

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

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

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

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

Fails on this case

Spoiler1 4 DBCD EBCD FBCD GBCD

mentioned by nanobyte above

thanks but can u help me once more? It is failing on small test even :(

https://rextester.com/WCVI57759

1 6 AA AAA AAAA AAAAA AAAAAA AAAAAAA easy to miss (including me...)

Thanks a lot :)

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.

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.

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

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

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

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.

CodeYou 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 :)

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

https://ideone.com/W2Uyqv

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.

CodeNeatest implementation for C i have seen till now. Thnx

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/

can someone find a error in my solutions for

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

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

can someone find a error in my solutions for

alien poemIt can pass test case 1 but got WA in test case 2..

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

GCJ 2019 Round 1A Pylons

I tried backtracking, but got stuck in time limit.