Hi All,
Topcoder SRM 700 will be held 13 October 07:00 AM BDT
Let's discuss the problems after the contest.
Hi All,
Topcoder SRM 700 will be held 13 October 07:00 AM BDT
Let's discuss the problems after the contest.
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3657 |
| 3 | jiangly | 3638 |
| 4 | turmax | 3442 |
| 5 | tourist | 3380 |
| 6 | Um_nik | 3353 |
| 7 | strapple | 3350 |
| 8 | squareOf105 | 3346 |
| 9 | heuristica | 3322 |
| 10 | maroonrk | 3310 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 158 |
| 2 | nik_exists | 150 |
| 2 | maspy | 150 |
| 4 | AmShZ | 144 |
| 5 | Um_nik | 143 |
| 6 | Errichto | 139 |
| 7 | adamant | 137 |
| 8 | BledDest | 135 |
| 9 | maroonrk | 133 |
| 10 | qwexd | 130 |
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.
US defense contractors in programming contests? This is new.
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 :-)
I haven't received my T-shirt for 600.5 yet T_T
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 :|
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.
I just created an account on TC. When can i register for the contest ?
Do I know you?
No... maybe you don't
Can someone please guide through the approach for Div2 C?
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 ;/
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 ?
If j==0, j-1 will access a invalid memory
What do you mean by skipping? Could you please elaborate it a bit more, specially the transition and the base case? Thanks
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].
Can someone please tell from where can I get editorial of this round ???
I put my solutions here: https://apps.topcoder.com/wiki/display/tc/SRM+700 as well as in the practice rooms. I'll try to add explanations later if I have time.
Thanks.
How to form dp in Div1 medium?
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.
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.
Can you explain why we power n to number of vertices, what I thought was factorial of (number of vertices left -1)
Which power of n do you mean? If nn - k - 1 it's only because of binomial formula.
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 ?
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.
Hi! Can you please explain why this problem reduces to a graph theory problem?
You can consider graph with edges between vertices i and j if f(i) = j.
Can anyone please explain the approach of div2 450?
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.
Thanks!
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.
When you are in practice, submitting the solution gives a pop-up that just displays "How many points you may get if u pass system testing". To see the actual results, go to practice options and click "Run System Test"
Got it. Thanks, sir!
These questions were somewhat answered on the following 2 Quora questions:
https://www.quora.com/If-on-TopCoder-I-submit-my-code-and-it-says-Submitted-with-x-points-does-it-mean-all-my-testcases-passed
https://www.quora.com/How-do-I-see-which-test-case-broke-my-code-in-Topcoders-Challenge-phase/answer/Dushyant-Singh?__snid3__=408977113&__nsrc__=1&__filter__=all
I have trouble understanding dev1 B. Some help would be great!
What's the
Z(f)for the below graph?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