memset0's blog

Topcoder Single Round Match 700
By memset0, history, 8 years ago, In English

Hi All,

Topcoder SRM 700 will be held 13 October 07:00 AM BDT

Let's discuss the problems after the contest.

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

Comments Comments (35)
| Write comment?
»
8 years ago, # |
  Vote: I like it +51 Vote: I do not like it

An important piece of information omitted from the blog post but present in match reminder: Booz Allen Hamilton will be sponsoring the SRM and giving out t-shirts to the winner of each room.

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

    US defense contractors in programming contests? This is new.

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

      NSA was sponsoring TopCoder Open in 2005-2010.

      DARPA ran a CS-STEM program with TopCoder (though that one was more noticeable for software and Studio competitors than for Algo participants).

      There is nothing new under the sun :-)

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

    I haven't received my T-shirt for 600.5 yet T_T

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

    Isn't it unfair for Div1 participants who might have easily won in a room in Div2? Just wondering if there will be many fake accounts due to this :|

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

Hello sir, I have two questions:

Is it rated? Can a former employee of Booz Allen take part on it?

Have a good day,

Ed.

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

I just created an account on TC. When can i register for the contest ?

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

Do I know you?

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

Can someone please guide through the approach for Div2 C?

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it +1 Vote: I do not like it

    Dp[i][j]= How many ways do you arrange the contestants , skipping at most j contestants. This DP assumes that the the first contestant of group 1 has a smaller rank that the first contest of group 2 and so on... Then you have to multiply the answer by fat[group] to cover all possibilities: DP[i][j]=DP[i+1][j+size-1]+DP[i][j-1]; sorry for my bad english ;/

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

      dp[i][j] = dp[i + 1][j + size — 1] + dp[i][j — 1], in the second dp (dp[i][j — 1]) why do we have to go back to when j > 0 ?

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

      What do you mean by skipping? Could you please elaborate it a bit more, specially the transition and the base case? Thanks

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

        Suppose that we have the rank of the first place of each group. R1 is the greatest rank of group 1 , R2 is the greatest rank of group 2 and so on. Now, we will suppose that R1<R2<R3<R4 and so on. Now, suppose that we have M contestants on each room. We can mantain a DP , that the state is I (the player we are) and J (how players we can skip). The dp count HOW many manners we can arrange the players in each room such that the rank of the first contestant on room 1 is smaller than the rank of the first contestant on room 2 and so on.. On state DP[I][J] -> WE HAVE TO POSSIBILITIES FOR THE PLAYER I: HE IS THE FIRST OF HIS ROOM , and he is not the first of his room; WHEN j is 0 , the i-th contestant MAY be the first of his room. Then: DP[I][J]=DP[I+1][J+SIZE-1] ( THE player I is the first of his room) + DP[i][j+1] ( THE PLAYER I IS the first of his room) ; The base case is: dp[1][0] = > the first player may be the first of his room. DP[lastplayer][anything] = 1; HOW WE assume that R1<R2<R3<R4<Rgroup. we may multiply this answer by fatorial[group].

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

Can someone please tell from where can I get editorial of this round ???

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

How to form dp in Div1 medium?

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

    Answer = . First multiple is the number of ways to choose k numbers, second is number of bijections for these k numbers. The remaining multiple is the number of ways to construct a rooted tree with n-k+1 vertices where degree of the root is i (imagine that k vertices are merged to the root) and to assign that i subtrees to real k vertices.

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

      I solved this until here but tried to form dp because I saw some users do that. I would love if they can share their solution too.

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

      Can you explain why we power n to number of vertices, what I thought was factorial of (number of vertices left -1)

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

        Which power of n do you mean? If nn - k - 1 it's only because of binomial formula.

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

      Can you explain me why the last multiple is C(n — k — 1, i — 1). I think it must be C(n — k, i) the number of ways to chose i root ?

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

        Let a be the number of vertices in a tree (a = n - k + 1). The number of trees where degree of the root is i is equal to the number of Prufer codes (Wiki) with exactly i - 1 values equal to a. There are a - 2 numbers in any Prufer code, Ci - 1a - 2 ways to choose positions for a-values and (a - 1)a - 2 - (i - 1) ways to set values for the other numbers.

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

      Hi! Can you please explain why this problem reduces to a graph theory problem?

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

        You can consider graph with edges between vertices i and j if f(i) = j.

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

Can anyone please explain the approach of div2 450?

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

    you just have to check all subset of the '?' in the board. You can do this as, at first check all them as '.'. Then for each subset you say that this will include 'O'. Then check that by including this as 'O' .After making as 'O' ,you now check what is the current min of row or column and max of row or column . Then simply add to variable (max row-min row+1)*(max column -min column +1).

    You can check all subset by bitmask or recursion.

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

I was hacked in the Div2 450 problem. I submit the same code after the SRM and got "Successful for XXX.XX points". Is there any way to see the test case that hacked my code? First round there, thanks.

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

I have trouble understanding dev1 B. Some help would be great!

What's the Z(f) for the below graph?

1->2
2->1
3->4
4->3
5->6
6->5
7->8
8->7

What's the relevance of the condition Z(f) will be the minimum of S(f,w), taken over all nonnegative w. I think S(f,0) would give the minimum value we are looking. Is there a case where S(f,1) is lesser then S(f,0)?

Edit: link to problem statement for quick access: https://community.topcoder.com/stat?c=problem_statement&pm=14266

→ Reply