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

TCO 2015 Round 1B (Topcoder Open) starts in under 4 hours
Автор Alwahsh, 11 лет назад, По-английски

Hello all

This is just a friendly reminder that TCO 2015 Round 1B starts soon.

For more info click here.

Enjoy!

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

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

Will there be a parallel round for ones who already advanced ?

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

Great performance! :) (in previous revision)

→ Ответить
»
11 лет назад, скрыть # |
← Rev. 6  
Проголосовать: нравится -19 Проголосовать: не нравится

I lost 20th place :\

My program fails when A contains one element

   int put=-1;
   for (int i=0;i<a.size();i++)
	  b.push_back(0);
    for (int v=2;v<=1000;v++)
     {
       for (int i=0;i<a.size();i++)
        if (a[i]%v == 0) b[i]=1; else b[i]=0;
       for (int i=1;i<a.size();i++)
        { b[i]+=b[i-1]; if (2*b[i] >= i+1) put=max(put,i); }
       for (int i=1;i<a.size();i++)
        for (int j=i+1;j<a.size();j++)
         if (2*(b[j]-b[i-1]) >= j-i+1) put=max(put,j-i);
     }
    return put;
→ Ответить
»
11 лет назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Can someone explain the solution for problem B?

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

    I can.

    First let's find p[i] — the probability that a clue with index i is not found. How can we calculate this probability? Let's define array can[i][j]: can[i][j] is true if we can find clue with index j when the clue with index i is already found; and false otherwise.

    This array can be calculated using Ford algorithm:


    Initially can[i][i] = true for all indices i,
and if clue[i][j] = 'Y' then can[i][j] = true

for(int k = 0; k < n; k++)
	for(int i = 0; i < n; i++)
		for(int j = 0; j < n; j++)
			if (can[i][k] && can[k][j])
				can[i][j] = true;

    So, if we find clue j, such that can[j][i], then we also find clue i. After that, it's clear that p[i] equals to the product of (100 — probability[j]) / 100. over all possible values of j, such that can[j][i] equals to true

    So, it can be calculated by the following code:

    p[i] = 1

for(int j = 0; j < n; j++)
	if (can[j][i])
		p[i] = p[i] * (100 - probability[j]) / 100.;

    After that, answer is the sum of (1 — p[i]) over all i. It's clear because of the linearity of expected value.

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

      Thank you for the explanation. I could not solve this question. Sorry my probability is really bad. Please clarify this doubt. "After that, it's clear that p[i] equals to the PRODUCT of (100 — probability[j]) / 100. over all possible values of j, such that can[j][i] equals to true."

      Aren't the events independent? If can[j][i] ==true and also can[k][i] == true, then shouldn't the probability of 'i' not happening,

      prob[i] = (1-prob[j]) + (1-prob[k]) ?

      Please clarify why should it be a product but not a sum?

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

        Yes, events are independent. We have 3 clues i, j, k. So, if you don't find clue i, and can[j][i] = true and can[k][i] = true, then you also should not find clue j and k both. So, p[i] = (1 — prob[i]) * (1 — prob[j]) * (1 — prob[k]).

        Also, answer can't be sum. For example, prob[i] = 0 for all clues, and can[j][i] = true; p[i] = (1 — prob[j]) + (1 — prob[i]) = 2. But probability can't be larger than 1.

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

      The answer would not be sum of (1-p[i]) over all i?

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

      Thankyou for solution :)
      Can you suggest some good sources to understand Probability and Expected Value topic and Questions to practice?

      → Ответить