Alwahsh's blog

TCO 2015 Round 1B (Topcoder Open) starts in under 4 hours
By Alwahsh, 9 years ago, In English

Hello all

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

For more info click here.

Enjoy!

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

Comments Comments (13)
| Write comment?
»
9 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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

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

    It seems that there is no parallel round.

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

Great performance! :) (in previous revision)

→ Reply
»
9 years ago, # |
← Rev. 6   Vote: I like it -19 Vote: I do not like it

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;
→ Reply
»
9 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can someone explain the solution for problem B?

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

    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.

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

      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?

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

        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.

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

          Ohh! Cool. thanks a lot. you are awesome.

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

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

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

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

      → Reply