### Errichto's blog

By Errichto, 2 weeks ago, ,

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.

•
• +108
•

 » 13 days ago, # |   0 can one miss one round and participate in other??
•  » » 13 days ago, # ^ |   +3 Yes you have to be in top 1500 of any of 1A, 1B, 1C in order to pass to round 2.
 » 13 days ago, # |   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... :'-(
•  » » 13 days ago, # ^ |   +1
•  » » » 13 days ago, # ^ |   0 Thanks. Yeah, that's where I am waiting . . .
 » 13 days ago, # |   +3 where can we find link to the dashboard?
•  » » 13 days ago, # ^ |   +1
 » 13 days ago, # |   +48 is it only me unable to see the problems??
•  » » 13 days ago, # ^ | ← Rev. 2 →   0 Me too Edit: seen it.
•  » » 13 days ago, # ^ | ← Rev. 2 →   0 no : working now
•  » » 13 days ago, # ^ |   +2 Its working now
 » 13 days ago, # |   +15 Are the questions loading for anyone?
 » 13 days ago, # |   +110 somehow i am tired of their Shakespeare language
 » 13 days ago, # |   0 Why my rank is decreased from 200+ to 180+？
•  » » 13 days ago, # ^ |   0 Oh,i think somebody submits again.
 » 13 days ago, # |   +5 Is it possible to see country-wise standings?
 » 13 days ago, # | ← Rev. 2 →   +8 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?
•  » » 13 days ago, # ^ | ← Rev. 3 →   +23 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, # ^ |   +19 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 →   +9 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, # ^ |   0 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, # ^ |   0 So you decided which cell to search first (the nearest or furthest one) by random?
•  » » » » » 13 days ago, # ^ |   0 The nearest.
•  » » » » » » 13 days ago, # ^ |   0 And somehow, it worked in given TL?
•  » » » » » » » 13 days ago, # ^ |   0 It works really fast. You can check the code: https://pastebin.com/LsB8vA2t
•  » » » 13 days ago, # ^ |   0 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): Codeauto solve = [&](int r, int c, bool swaped) { int i = 1; while (i < r) { int line_cnt = 2; if (i + 2 == r) line_cnt = 3; fori(j, c) { for (int i1 = i; i1 < i + line_cnt; i1++) { int j1 = j; if (i1 & 1) j1 = (j + 2) % c; j1++; if (swaped) out << j1 << " " << i1 << '\n'; else out << i1 << " " << j1 << '\n'; } } i += line_cnt; } }; if (c > 4 || r > 4) { out << possible << '\n'; if (r > 4) solve(c, r, true); else solve(r, c, false); } 
•  » » 13 days ago, # ^ | ← Rev. 2 →   0 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
•  » » » 11 days ago, # ^ |   0 can u share ur alien rhyme solution ?
•  » » » » 11 days ago, # ^ |   +8
•  » » » » » 11 days ago, # ^ |   0 This link is broken
•  » » » » » » 10 days ago, # ^ |   +8 It worked yesterday. New link
•  » » » » » » » 10 days ago, # ^ | ← Rev. 2 →   +5 Yes now working :) Maybe some server issues yesterday
•  » » 13 days ago, # ^ |   0 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, # ^ |   +3 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 →   +11 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 →   0 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 →   +9 Problem: Alien RhymeI did the same as you and it failed the large set. This approach will fail in the following test case: SpoilerT = 11DBCDEBCDFBCDGBCDIn 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.
•  » » » 11 days ago, # ^ |   +3 Thanks a lot i was missing this point
•  » » 13 days ago, # ^ |   0 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, # ^ |   0 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 →   +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
•  » » 13 days ago, # ^ |   0 For what do you need the steps 4 to 7? Randomized recursive brute-force will get accepted.
•  » » » 13 days ago, # ^ |   +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
•  » » » » 13 days ago, # ^ |   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.
 » 13 days ago, # | ← Rev. 2 →   0 I tried using the method described here with a Knight's Tour, why does my large for Pylons fail???C++ Code
 » 13 days ago, # |   +5
 » 13 days ago, # | ← 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
•  » » 13 days ago, # ^ |   +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.
•  » » » 13 days ago, # ^ |   0 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
 » 13 days ago, # | ← 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]$ $->$ $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, # |   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.
•  » » 13 days ago, # ^ |   +13 Just write checker and check all possible tests, it is very easy in this problem
•  » » 13 days ago, # ^ | ← Rev. 2 →   +3 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, # ^ |   0 12 and 13 on the same diagonal, thanks.
•  » » » » 13 days ago, # ^ |   0 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, # ^ |   0 I situation (2,x) is handled already in the source I posted
 » 13 days ago, # |   0 Good hacks for Alien Rhyme? I solved the visible but got WA for hidden and don't know what to do
 » 13 days ago, # |   0 https://ideone.com/e.js/mKXWib i cant find a mistake-pylons
 » 13 days ago, # |   0 can someone give a counter-case for my solution to third problem?
•  » » 13 days ago, # ^ |   +4 Fails on this case Spoiler1 4 DBCD EBCD FBCD GBCDmentioned by nanobyte above
•  » » » 13 days ago, # ^ |   0 thanks but can u help me once more? It is failing on small test even :(https://rextester.com/WCVI57759
•  » » » » 13 days ago, # ^ |   +1 1 6 AA AAA AAAA AAAAA AAAAAA AAAAAAA easy to miss (including me...)
•  » » » » » 13 days ago, # ^ |   0 Thanks a lot :)
 » 13 days ago, # |   +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.
 » 13 days ago, # |   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.
•  » » 13 days ago, # ^ |   0 U deleted the two adjacent words even if their prefix length was not greatest ?
•  » » » 13 days ago, # ^ |   0 Maybe I didn't explain myself well, here is the code C++#include using namespace std; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N;cin>>N; for(int n=1;n<=N;n++) { int M;cin>>M; int res = 0; vector words(M);; for(int m=0;m>words[m]; reverse(words[m].begin(),words[m].end()); } sort(words.begin(),words.end()); list wlist; for(string& w:words)wlist.push_back(w); for(int len=50;len>0;len--) { string lastPrefix = "\$"; if(wlist.size()<2)break; auto w1 = wlist.begin(); auto w2 = w1; w2++; while(w1!=wlist.end() && w2!=wlist.end()) { if(w1->size()>=len && w2->size()>=len) { bool same_start = true; for(int l=0;lfind(lastPrefix)!=0) { lastPrefix = w1->substr(0,len); res+=2; w1 = wlist.erase(w1); w1 = wlist.erase(w1); if(w1==wlist.end()) { break; } else if(w1==wlist.begin()) { w2=w1; w2++; } else { w2=w1; w1--; } continue; } } w1=w2; w2++; } } cout<<"Case #"<
 » 13 days ago, # | ← Rev. 3 →   0 Can someone post solution for C where u dont use a trie ? (Actual Code)
•  » » 13 days ago, # ^ | ← 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. Codevoid solve() { static int t = 1; out << "Case #" << t++ << ": "; vector w; int n; in >> n; while (n--) { string s; in >> s; reverse(all(s)); w.pb(s); } sort(all(w)); int total = 0; function solve_1 = [&](int start, int end, int index) { if (end - start == 1) return 0; int res = 0; // group by this index and try to solve. for (int i = start; i < end;) { int j = i + 1; while (j < end && index < w[i].size() && index < w[j].size() && w[i][index] == w[j][index]) j++; res += solve_1(i, j, index + 1); i = j; } // if there are left over indexes in this group, choose to "have" 2 of them. if (res + 2 <= end - start) { res += 2; } return res; }; auto solve = [&](int start, int end) { int res = 0; for (int i = start; i < end;) { int j = i + 1; while (j < end && w[i][0] == w[j][0]) { j++; } res += solve_1(i, j, 1); i = j; } return res; }; total = solve(0, w.size()); out << total << '\n'; } 
•  » » » 13 days ago, # ^ |   0 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, # ^ |   +3 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 →   0
•  » » 13 days ago, # ^ |   +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#include using namespace std; #define all(x) begin(x), end(x) using ll = long long; using ld = long double; using pii = pair; using vi = vector; int main() { ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T; cin >> T; int tc = 1; auto comp = [](const string& a, const string& b) { if (a.size() == b.size()) { return a < b; } return a.size() > b.size(); }; while (T-- > 0) { int n; cin >> n; vector words(n); map, decltype(comp)> tot(comp); for (int i = 0; i < n; ++i) { cin >> words[i]; for (int j = 0; j < words[i].size(); ++j) { string t = words[i].substr(j); tot[t].push_back(i); } } vector vis(n, false); int ans = 0; for (auto& p : tot) { int x = -1; int y = -1; for (auto& idx : p.second) { if (vis[idx]) continue; if (x == -1) { x = idx; } else { y = idx; break; } } if (x != -1 and y != -1) { vis[x] = true; vis[y] = true; ans += 2; } } cout << "Case #" << tc++ << ": " << ans << '\n'; } return 0; } 
•  » » » 11 days ago, # ^ |   0 Neatest implementation for C i have seen till now. Thnx
 » 13 days ago, # |   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/
 » 13 days ago, # |   0 can someone find a error in my solutions for pylons [Link]-(https://pastebin.com/1UWXk9GA)
•  » » 13 days ago, # ^ |   0 yours is showing impossible for 4x3,5x2,5x3 use r*c<=9 impossible as condition
 » 12 days ago, # | ← Rev. 2 →   0 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)
 » 11 days ago, # |   -20 GCJ 2019 Round 1A PylonsI tried backtracking, but got stuck in time limit.