Monday, January 06, 2014

SRM 603: uncertainty

What a match to be tainted by uncertainty. I have no idea if my 250 is correct and for a while I had no idea if my 500 was correct. Starting to write before the challenge phase and now I know that my 500 is at least correct in theory. I could have made an implementation mistake.

Div1 250

Two players have a tree. They play alternating turns. In a turn, a player must pick an edge and destroy the edge. This splits the tree into two components (also trees). The player then chooses a component to keep, the rest is discarded. The game ends when only one node remains. The nodes have some costs written on them. The first player wants to maximize this value, the other player wants to minimize it. Return the cost of the node if both players play optimally.

I had absolutely no idea what to do. I tried everything and couldn't think of a non-clever way to solve it. Eventually, I thought that since it is a div1 250, it shouldn't be so hard. It probably has a very easy solution that I am missing. Maybe a super easy solution that is, however, difficult to prove... I checked the example cases and noticed that they were all very simple... maek you think... Then I noticed that in all those cases, the returned value was the maximum cost node with degree equal to 1. After drawing in paper it sort of makes sense. I was late so I made a submission. Right now it seems that just about everybody is doing this. So maybe it is correct?

int findend(vector<int> edges, vector<int> costs)
{
int n = edges.size() + 1;
vector<int> degree(n, 0);
for (int i = 0; i < edges.size(); i++) {
// edge between i+1 and edges[i]
degree[ edges[i] ]++;
degree[i+1]++;
}
int best = 0;
for (int i = 0; i < n; i++) {
if (degree[i] == 1) {
best = std::max(best, costs[i] );
}
}
return best;
}

Div1 500

Given n count the number of pairs of two strings such that the second string is a rotation of the first string and the strings use only the first k letters of the English alphabet.

The number of rotations depends on the number of repetitions in the first string. If the string contains 2 repetitions (eg: abab), then the number of rotations is n/2. For each number of repetitions r, calculate the number of ways to have exactly that number of repetitions and multiply by n/r.

So in order to have r repetitions, n must be a multiple of r. So we are interested in all divisors d of n. With n <= 1000000000, we can find all the divisors in O(sqrt(n)).

The difficult part is to count the number of strings with an exact number of repetitions. Note that "aaaa" contains "a" repeated 4 times, "aa" repeated two times and "aaaa" "repeated" 1 time. We should only consider it as 4 repetitions. So if we calculate the number of strings with 2 repetitions as K ^ (n / r), we have to subtract the strings with smaller repetitions that divide r... I couldn't think of a way to do this fast. I could only do it in O(d^2) where d is the number of divisors of n. At first I had no idea what an upper bound for the number of divisors is. We know we need an O(sqrt(n)) algorithm to find them. But what about the actual number of divisors?

In my first excursions, I tried many numbers composed of the first few primes raised to some exponents. My best was 729.

Eventually though, I coded a bruteforce. It appears 1344 is the maximum number of divisors for n <= 1000000000. Let's see...

const int MOD = 1000000007;
vector<int> getDivisors(int n)
{
vector<int> div;
for (int i = 1; i*i <= n; i++) {
if (n % i == 0) {
div.push_back(i);
if (n / i != i) {
div.push_back(n / i);
}
}
}
sort(div.begin(), div.end());
return div;
}
long modPow(long x, int y)
{
long r = 1;
while (y > 0) {
if (y & 1) {
r = (r * x) % MOD;
}
x = (x * x) % MOD;
y /= 2;
}
return r;
}
long best = 1;
vector<int> primes = {2,3,5,7,11,13,17,19,23};

void backtrack(int p, long x, long divs)
{
if (divs > best) {
best = divs;
cout << x <<" has "<<divs<<endl;
}
long y = x;
int i = 0;
if (p == primes.size()) {
return;
}
while (y * primes[p] <= 1000000000LL) {
y *= primes[p];
i++;
}
//cout << "}" << endl;
for (int j = i; j >= 0; j--) {
backtrack(p+1, y, divs * (j+1) );
y /= primes[p];
}

}

int getNumber(int n, int k)
{
// The bruteforce to find the maximum number of divisors
//backtrack(0, 1, 1);

vector<int> d = getDivisors(n);
long total[d.size()];
long res = 0;
cout << d.size() << " divisors found"<<endl;
for (int i = 0; i < d.size(); i++) {
long x = modPow(k , d[i]);
for (int j = 0; j < i; j++) {
if (d[i] % d[j] == 0) {
x = (x - total[j] + MOD) % MOD;
}
}
total[i] = x;
//cout << "for "<<d[i]<<" = "<<total[i]<<endl;
res += (total[i] * d[i]) % MOD;
}
return (int)( res % MOD );
}

So?

The challenge phase is about to end and my solutions are standing. Let's see what happens

I don't really like 250s that have solutions that are easy but difficult to prove. How many people are getting points like me, coding it on a hunch? Well... maybe the solution is wrong,but Petr agrees, so... I gues it is right. I don't whether the way I proved my 250 is correct or not but here it is. The 2nd player always has the option to cut one of the leaves with the minimum cost and choose to continue with it which ends the game. Since the two players are playing optimally so if the 2nd player knows that somehow the 1st player can make a profit larger than one of the leaves then he can end the came in his turn. So the upper bound of the cost the first player can have is the largest cost of all leaves .So the 1st player ends the game in the first turn cutting the edge connecting the leaf with the maximum cost. vexorian said...

This is useful because I have to write the editorial and thus prove this. JOmegaCV said...

I thought of it this way: Player 1 knows that if he wants to guarantee a score greater than the max leaf, he has to remove all leaves as ending options for player 2. So the the proof I assumed was: it is impossible to remove a single edge in a tree, keep one subtree, and not have an original leaf exist in the subtree. Not sure how useful that fact would be in the future.

Also, for a tree with two nodes, is it correct to say they are both leaves? dvdreddy said...

Hi vexorian, my code for Div 1 250has the same logic as yours and code is also very similar but mine failed system tests
can you please suggest where it is wrong

http://community.topcoder.com/stat?c=problem_solution&rm=320049&rd=15836&pm=12946&cr=22889193

Thank you vexorian said...

n is equal to costs.size() + 1, not just costs.size() JOmegaCV said...

I think n=costs.size() is ok, It passed sample tests for me by changing the edges loop to loop over n-1 edges instead of n. dvdreddy said...

costs contain the same number of elements as the tree right? and hence n is costs.size() dvdreddy said...

Thanks got the mistake Sai said...

Hi vexorian,
I was just trying to solve the problem after the contest has ended and I was wondering why 5 is returned in the last case(4th) instead of 3, since if both players play optimally the {3,2,5} will become {3,5}(edge between 3,2 is removed) and in the 2nd turn becomes {3} since player 2 wants to minimize the result he selects the edge between and 5 and 3 and removes 5, so shouldn't 3 be returned?
Thanks. Sai said...

Sorry, I forgot to mention. I was talking about Div1(250)