Блог пользователя Killever

Google Code Jam Round 1A 2014
Автор Killever, 11 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

»
11 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

I got the qualification mail result 6 days ago

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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

    → Ответить
»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится +49 Проголосовать: не нравится

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!

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится +39 Проголосовать: не нравится

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

→ Ответить
»
11 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

What is the approach to solve C?

→ Ответить
  • »
    »
    11 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится 
    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.

    → Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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 :)

    → Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

    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;
}
    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится +13 Проголосовать: не нравится

        Can you explain how to calculate prBad with DP?

        → Ответить
        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
          ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          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 :)

          → Ответить
        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          → Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
»
11 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Can someone explain their solution to problem A?

→ Ответить
  • »
    »
    11 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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!

      → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +18 Проголосовать: не нравится

      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

      → Ответить
      • »
        »
        »
        »
        11 лет назад, # ^ |
        ← Rev. 4   Проголосовать: нравится +13 Проголосовать: не нравится

        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

        → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

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

      → Ответить
»
11 лет назад, # |
← Rev. 3   Проголосовать: нравится +41 Проголосовать: не нравится

Т.к. случайно прошел на онсайт Kotlin и решил туда поехать, писал GCJ на этом языке.

Обнаружил вот какую особенность:

/**
 * Sorts array or range in array inplace
 */
public fun <T> Array<out T>.sort(fromIndex : Int = 0, toIndex : Int = size - 1) : Unit {
    Arrays.sort(this, fromIndex, toIndex)
}

А теперь внимание: Arrays.sort в джаве принимает второй индекс не включительно! Т.е. должно быть в заголовке функции toIndex : Int = size. Не сдал из-за этого первую задачу. Придется писать еще один раунд.

Вот бага: http://youtrack.jetbrains.com/issue/KT-4963

Решил, что надо дописать, откуда у меня там сортировка. Вначале я не придумал решение для Large, поэтому написал Small максимально втупую, в частности там было что-то вроде такого:

var used = BooleanArray(n);
for (i in 0 .. n-1) {
    for (j in 0 .. n-1) {
        if (used[j])
            continue;
        if (after[i] == required[j])
            used[j] = true;
    }
}

То есть я втупую преобразовал каждую строчку инпута, сохранил это в массив after, а потом сравнивал с тем, что надо получить. Дальше я написал Large, но этот кусок кода от Small остался жив. Я запустил программу и понял, что работает все очень медленно — не успею за 8 минут. Ну я сообразил, где самое узкое место — вон оно чуть выше написано. Как это быстро пофиксить? Да посортить просто массивы after и required. Посортил. Потом увидел output, охренел слегка и за оставшееся время не разобрался, в чем причина.

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    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.

    → Ответить
»
11 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

→ Ответить
  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Can you explain the formula?

    → Ответить
    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

      → Ответить