GCJ 2019 – round 1A

6 лет назад, # |

Is it possible to see country-wise standings?

→ Ответить

6 лет назад, # |

← Rev. 2 →

My solutions to first two:

Pylons

Golf Gophers

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

→ Ответить

JustInCase

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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.

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

The nearest.

→ Ответить

6 лет назад, # ^ |

And somehow, it worked in given TL?

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

kessido

6 лет назад, # ^ |

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

→ Ответить

SlavaSSU

6 лет назад, # ^ |

← 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

→ Ответить

6 лет назад, # ^ |

can u share ur alien rhyme solution ?

→ Ответить

SlavaSSU

6 лет назад, # ^ |

Yes

→ Ответить

6 лет назад, # ^ |

This link is broken

→ Ответить

SlavaSSU

6 лет назад, # ^ |

It worked yesterday. New link

→ Ответить

6 лет назад, # ^ |

← Rev. 2 →

Yes now working :) Maybe some server issues yesterday

→ Ответить

usernameson

6 лет назад, # ^ |

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.

→ Ответить

KhaleD_

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

← 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!

→ Ответить

nanobyte

6 лет назад, # ^ |

← 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

→ Ответить

6 лет назад, # ^ |

Thanks a lot i was missing this point

→ Ответить

computerbox

6 лет назад, # ^ |

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 ?

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # |

← 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

→ Ответить

Jakube

6 лет назад, # ^ |

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

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

Jakube

6 лет назад, # ^ |

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.

→ Ответить

vamaddur

6 лет назад, # |

← Rev. 2 →

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

C++ Code

→ Ответить

adhoc_king

6 лет назад, # |

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

→ Ответить

WhaleVomit

6 лет назад, # |

← 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

→ Ответить

https://rextester.com/WCVI57759

6 лет назад, # ^ |

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.

→ Ответить

anjn98

6 лет назад, # ^ |

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

→ Ответить

Mindjolt

6 лет назад, # |

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

→ Ответить

kronos

6 лет назад, # |

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.

→ Ответить

dalex

6 лет назад, # ^ |

+13

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

→ Ответить

P___

6 лет назад, # ^ |

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

→ Ответить

kronos

6 лет назад, # ^ |

12 and 13 on the same diagonal, thanks.

→ Ответить

P___

6 лет назад, # ^ |

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.

→ Ответить

kronos

6 лет назад, # ^ |

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

→ Ответить

fikr

6 лет назад, # |

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

→ Ответить

kumarpratyush4

6 лет назад, # |

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

→ Ответить

pk842

6 лет назад, # |

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

→ Ответить

pleasant

6 лет назад, # ^ |

Fails on this case

Spoiler

mentioned by nanobyte above

→ Ответить

pk842

6 лет назад, # ^ |

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

→ Ответить

Usagi.K

6 лет назад, # ^ |

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

→ Ответить

pk842

6 лет назад, # ^ |

Thanks a lot :)

→ Ответить

samarth1402

6 лет назад, # |

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.

→ Ответить

zed_b

6 лет назад, # |

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.

→ Ответить

6 лет назад, # ^ |

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

→ Ответить

zed_b

6 лет назад, # ^ |

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

→ Ответить