Killever's blog

Google Code Jam Round 1A 2014
By Killever, 11 years ago, In English

First don't miss this round will be hold after one day Time HERE
Second any one got Qualification mail Result ,Till now I didn't get it.
UPD: I got TCO'14 Algorithm Round 1B official results while Writing this post.

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I got the qualification mail result 6 days ago

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Thanks ,
    I login to gmail using my ymail "my main mail" so most of time I open ymail (yahoo) rather than gmail(google) and I register using gmail not ymail ,that's the reason that I thought they didn't send it. but I opened gmail and I found You have advanced mail which I didn't receive on ymail .
    Thanks for your reply

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +49 Vote: I do not like it

That's bad idea to post such topics two days before the competition starts, because it won't be on the top helping everyone who possibly forgot about the contest.

I even accidentally duplicated this notification few minutes ago. So let's make this topic up!

→ Reply
»
11 years ago, # |
  Vote: I like it +39 Vote: I do not like it

It seems I can guess the author of the problem C. Am I right, Petr?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +48 Vote: I do not like it

    Yeah, I'm too predictable. Did you like it?

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      At least for me it was "Hey, let's try some random statistics and calculate mu and sigma for both types"

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    :O How did you know??

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

What is the approach to solve C?

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it 
    const string res[] = {"BAD", "GOOD"};

void solve(){
	int n;
	scanf("%d",&n);
	vector<int> p(n);
	for (int i = 0; i < n; i++){
		scanf("%d",&p[i]);
	}
	int cnt = 0;
	for (int i = 0; i < n; i++)
		cnt += p[i] < i;
	bool ok = cnt >= 485;
	printf("%s\n", res[ok].c_str());
}

    Error is about 6% in both sides. I don't know how to think about it. Just try different ideas, and check. This was third or fourth.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it +4 Vote: I do not like it

      You can think about this by plotting probabilities for a small n, say 7:

      You can clearly see that the probabilities are heavily biased towards points lower than main diagonal.

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I guessed BAD if atleast 55% of positions satisfies a[i]>i.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I've computed the following sum for each permutation:

    VI inv = get_inv(perm);
long double sum = 0.0;
rept(i, L(perm)) {
	sum += pow((long double)abs(i - inv[i]), 1.5) * (i + 1);
}

    Then I sorted all 120 permutations by the value of sum and claimed that the first 60 of them are BAD and the rest of them are GOOD. This approach was guessing 109 out of 120 permutations in 12% of test cases on my local computer. In the first 3 tries I've submitted during the competition I mixed up GOOD and BAD and I've got AC in the fourth one, which means I was very lucky :)

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Another version (I got AC only after the end):

    //precalc
int IT = 1000 * 1000;
forn (it, IT) {
    forn (i, n) {
    	p[i] = i;
    }
    forn (i, n) {
    	int r = rand() % (n - i) + i;
    	swap(p[i], p[r]);
    }
    forn (i, n) {
    	prGood[p[i]][i] += 1.0 / IT;
    }
    forn (i, n) {
    	p[i] = i;
    }
    forn (i, n) {
    	int r = rand() % n;
    	swap(p[i], p[r]);
    }
    forn (i, n) {
    	prBad[p[i]][i] += 1.0 / IT;
    }
}

//for each test case
ld good = 1.0;
ld bad = 1.0;
forn (i, n) {
	good *= prGood[a[i]][i];
	bad *= prBad[a[i]][i];
}
if (good > bad) {
	cout << "GOOD" << endl;
} else {
	cout << "BAD" << endl;
}
    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      Same solution, but prBad calculated with DP (prGood[i][j] == 1/n). Local run shows >96% probability of guessing single testcase (>99.7% probability of guessing 109 out of 120).

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        Can you explain how to calculate prBad with DP?

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          It's not DP, it's just running 1M iterations of the algorithm and noting down the final position of each element

          EDIT What was I thinking, ignore my comment :)

          → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          dp[i][j][k] = Probability that i ends up in position j after k swaps

          When calculating dp[i][j][k], you will swap the position k-1 with someone.

          if k-1 == j: dp[i][j][k] = 1/N (you have to choose the exact position i is in to swap with j)

          if k-1 != j: dp[i][j][k] = dp[i][j][k-1] * (1-1/N) + dp[i][k-1][k-1] * 1/N (either i was already in position j, and not swapped, or i was in position k-1 and got swapped to position j).

          As you only need dp[x][y][k-1] to calculate dp[i][j][k], you can do it in O(n²) memory.

          → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    (in practice) I tried running the bad algorithm many times and computing the probabilities p[i][j] of π[i] being j. For a given permutation π, I computed the product of p[i][π[i]] and said that if it's  > k, then the answer's BAD.

    I made my own inputs using the 2 algorithms, sorted the computed products for all permutations of each input, looked at the numbers, and said that k = 1. First submit AC.

    → Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain their solution to problem A?

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    Try matching the first outlet with each device. There are only N different configurations of switches worth looking at.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot. MikeMirzayanov's solution was easy to read and I got to learn that we can check equality of two C++ sets. Doing that, reduces some complexity in implementation. Thanks Mike!

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What is the time complexity of comparing two stl sets?

        → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      I spent over 1.5 hours on this problem. Thought of everything, matching, dp, bitmasking, etc, but I couldn't solve it. When I saw this solution, I was like

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 4   Vote: I like it +13 Vote: I do not like it

        Exact same thing for me. Fortunately it struck me at about 2:15 into the contest.

        There's something about this task that makes one think it's really hard :D A friend of mine wrote me in Facebook that he used bipartite matching to solve the set equality part :P

        → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I did the same :D :D for large input but in small input I did O(2^N)

      → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the complexity of checking equality of two set containers in C++?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Linear in the size of the container.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain how to solve problem B? Thank in advance!

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Assume the tree is rooted and the root is r. Also suppose that the tree is now directed with respect to the root. Now you can calculate dp[r] which represents the minimum removal of nodes to make the subtree rooted at r a full binary tree.

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried to calculate the probability of a[i]<i for the bad algorithm. For the good algorithm it is obviously i/n.

P(a[i]<i) = x^(n-i) — x^n + (x^(n-1))*(i/n)

where x = (n-1)/n = 0.999

Am I correct?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain the formula?

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I'll try.

      the probability that k is displaced from a[k] in the first k iterations of the algorithm is

      P(E1) = 1/n + ((n-1)/n)(1/n) + (((n-1)/n)^2)(1/n) + ...

      this is a GP and its sum will be P(E1) = 1-(0.999^k).

      The probability that it stays at the kth position(E2) is P(E2) = 0.999^k.

      Now in the kth iteration, assuming E2 E3 = it is swapped with arr[i] , i<k E4 = it is swapped with arr[i] , i>=k

      For E4 now k will remain in arr[k,k+1,...n-1] , so this is not required.

      P(E2 and E3) = (0.999^k)*(k/n)

      Now assuming E1 E5 = k does not get swapped with arr[k].

      P(E1 and E5) = (1-(0.999^k))*((n-1)/n)

      E6 = k is currently in arr[0,1,2...k-1] after kth iteration (total k+1 iterations).

      P(E6) = (1-(0.999^k))*((n-1)/n) + (0.999^k)*(k/n)

      Now the probability that it does not get selected in the further iterations is

      P = P(E6)*(((n-1)/n)^(n-k-1))

      P = (1-(0.999^k))*(0.999^(n-k)) + ((0.999^(n-1))*(k/n))

      P = 0.999^(n-k) — 0.999^n + ((0.999^(n-1))*(k/n))

      What do you think?

      → Reply