GCJ 2019 – round 1A

6 years ago, # |

Is it possible to see country-wise standings?

→ Reply

6 years ago, # |

← Rev. 2 →

My solutions to first two:

Pylons

Golf Gophers

Alien Rhyme (why greedy passed the first set didn't the second?)

→ Reply

JustInCase

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

→ Reply

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

→ Reply

6 years ago, # ^ |

← Rev. 2 →

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

→ Reply

6 years ago, # ^ |

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.

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

The nearest.

→ Reply

6 years ago, # ^ |

And somehow, it worked in given TL?

→ Reply

6 years ago, # ^ |

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

→ Reply

kessido

6 years ago, # ^ |

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

auto 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);
}

→ Reply

SlavaSSU

6 years ago, # ^ |

← Rev. 2 →

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

→ Reply

6 years ago, # ^ |

can u share ur alien rhyme solution ?

→ Reply

SlavaSSU

6 years ago, # ^ |

Yes

→ Reply

6 years ago, # ^ |

This link is broken

→ Reply

SlavaSSU

6 years ago, # ^ |

It worked yesterday. New link

→ Reply

6 years ago, # ^ |

← Rev. 2 →

Yes now working :) Maybe some server issues yesterday

→ Reply

usernameson

6 years ago, # ^ |

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.

→ Reply

KhaleD_

6 years ago, # ^ |

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

→ Reply

6 years 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!

→ Reply

nanobyte

6 years ago, # ^ |

← Rev. 4 →

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

→ Reply

6 years ago, # ^ |

Thanks a lot i was missing this point

→ Reply

computerbox

6 years ago, # ^ |

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 ?

→ Reply

6 years ago, # ^ |

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

→ Reply

6 years 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

→ Reply

Jakube

6 years ago, # ^ |

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

→ Reply

6 years ago, # ^ |

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

→ Reply

Jakube

6 years ago, # ^ |

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.

→ Reply

vamaddur

6 years ago, # |

← Rev. 2 →

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

C++ Code

→ Reply

adhoc_king

6 years ago, # |

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

→ Reply

WhaleVomit

6 years ago, # |

← Rev. 4 →

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

→ Reply

https://rextester.com/WCVI57759

6 years ago, # ^ |

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.

→ Reply

anjn98

6 years ago, # ^ |

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

→ Reply

Mindjolt

6 years ago, # |

← Rev. 2 →

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

→ Reply

kronos

6 years ago, # |

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.

→ Reply

dalex

6 years ago, # ^ |

+13

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

→ Reply

P___

6 years ago, # ^ |

← Rev. 2 →

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.

→ Reply

kronos

6 years ago, # ^ |

12 and 13 on the same diagonal, thanks.

→ Reply

P___

6 years ago, # ^ |

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.

→ Reply

kronos

6 years ago, # ^ |

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

→ Reply

fikr

6 years ago, # |

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

→ Reply

kumarpratyush4

6 years ago, # |

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

→ Reply

pk842

6 years ago, # |

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

→ Reply

pleasant

6 years ago, # ^ |

Fails on this case

Spoiler

mentioned by nanobyte above

→ Reply

pk842

6 years ago, # ^ |

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

→ Reply

Usagi.K

6 years ago, # ^ |

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

→ Reply

pk842

6 years ago, # ^ |

Thanks a lot :)

→ Reply

samarth1402

6 years ago, # |

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.

→ Reply

zed_b

6 years ago, # |

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.

→ Reply

6 years ago, # ^ |

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

→ Reply

zed_b

6 years ago, # ^ |

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

C++

#include <bits/stdc++.h>
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<string> words(M);;
        for(int m=0;m<M;m++) {
            cin>>words[m];
            reverse(words[m].begin(),words[m].end());
        }
        sort(words.begin(),words.end());
        list<string> 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;l<len;l++) if((*w1)[l]!=(*w2)[l]) {
                        same_start = false;
                        break;
                    }
                    if(same_start && w1->find(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 #"<<n<<": "<<res<<endl;
    }
    return 0;
}

→ Reply