| # | User | Rating |
|---|---|---|
| 1 | ecnerwala | 3648 |
| 2 | Benq | 3580 |
| 3 | orzdevinwang | 3570 |
| 4 | cnnfls_csy | 3569 |
| 5 | Geothermal | 3568 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3530 |
| 8 | Radewoosh | 3520 |
| 9 | Um_nik | 3481 |
| 10 | jiangly | 3467 |
| # | User | Contrib. |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | adamant | 164 |
| 2 | awoo | 164 |
| 4 | TheScrasse | 160 |
| 5 | nor | 159 |
| 6 | maroonrk | 156 |
| 7 | SecondThread | 150 |
| 8 | -is-this-fft- | 148 |
| 9 | pajenegod | 146 |
| 10 | BledDest | 144 |
is chrome ok? no posts of SRM by him since long time :/
I miss him :(
Can someone please explain the solution to Div1 Level 3?
Solution to the 800: If S % K = 0, then write S/K on both sides of the coin and we are always done.
If S % K is not 0, then first notice that we can only win if there is at least one head and one tail. WLOG the first flip is heads, and consider the position of the first tail.
If there are A heads and K-A tails in the end, we must have AX + (N-A)Y = S for X on the heads side and Y on the tails side. Note that if gcd(A,N-A) does not divide S, we cannot win in this case.
Otherwise, pick X so that for each A with gcd(A,N-A) dividng S, there exists integer Y with AX + (N-A)Y = S. (This can be done by the Chinese Remainder Theorem, as we need A | S-NX for each of these A)
Write X on the head of the coin. Once the first tails appears, we need to decide what to write. If there are C coin flips left, pick the A closest to (C/2) such that gcd(A,N-A) divides S. Then write the Y with AX + (N-A)Y = S. The probability of this scenario is (C choose A) / 2^K.
I have question about this solution.
In Chinese Remainder Theorem, the dividers need to be co-prime to each other, which is not ensured in this problem. How could we ensure we can find such X?
Ok, we need to find integer X so that lcm(all possible A) | S-NX. The greatest common divisor of this LCM and N must divide S since gcd(A,N-A) divides S, which means that you can find such an integer X by Bezout.
Reads a statement about bears/Limak
Immediately realises it's an Errichto's Round.
Can someone please explain some deterministic solution to div1 500? I didn't manage to use the fact about degree<=3 somehow so I just coded local optimization desperately.
Upd. I've just read in chat room, picking an edge decreases cost of at most 5 edges, so there is no need to try something except of 35 best edges in our brute force solution. Got it :(
Each edge you pick diminishes value of at most 4 of the other edges, so take only 35 biggest edges and do brute force.
I had this idea also. It reminds me of a COCI problem that appeared at some point.
http://hsin.hr/coci/contest3_tasks.pdf
Problem DOMINO
That was my first time in a SRM! :D The experience was awesome. ^_^
I've a question though. Is there any editorial for today's contest?
Don't expect the editorial to come out soon. They haven't published the editorial to SRM 694 yet. :(
But you can ask the problems here. :)
How to solve div1 300 ??
I will split the answer string into maximal constant substrings and store them in some container. (eg. abbaab has 4 components a, bb, aa, b). Once you have the sizes of all these components, you can assign 'a' and 'b' greedily. Keep assigning 'a' to the largest component, 'b' to the smallest, then 'a' to the largest and so on.
Now to get these components. Iterate from n to 1 (assume x[] is 1-indexed). Store the components you have already found in some container. If you are at position i, decrease the value required by the number already contributed by all the components you've found already. If this value goes below zero, answer is not possible. Otherwise if remaining value is r, create r components of size i.
Let's take a small example. Consider the vector {4, 2, 1}. At position 3, you create a component of size 3. At position 2, you get the new value as (2-(3-2+1)), which is 0. So you move on. Then at position 1, you get the new value as (4-(3-1+1)), which is 1. So you add 1 component of size 1. You have 2 components now, one of size 3 and one of size 1. Assign 'a' to the largest and 'b' to the smallest, to get the answer "aaab".
Hope this helped. :)
Yeah, it helped, thanx a lot :) ...
Thanks for describing your solution satyaki3794. Unfortunately I feel like I'm missing something. What do you do if you have something like this
{0, 0, 2, 0}. From my understanding you create 2 components of size 3, but this doesn't seem right since then your final string will have length of 6 chars while one with 4 chars is needed.Furthermore, how exactly do you decrease the value of all the components found already. E.g., what exactly are the numbers in your calculations:
(2-(3-2+1))and(4-(3-1+1))?Please refer to my code.
Also, I have added a check for ans.length() == n at the end, to take care of the problem you mentioned.
As regards to the value (2-(3-2+1)) at pos 2 (1-indexed array), 2 is the required number of constant substrings of length 2 and (3-2+1) is the number contributed by some constant substring already found (in my above example, there is only one of length 3).
My solution was: the final string will be made of various segments of 'a's and 'b's. Let ai be the number of these segments of length i.
Then ai satisfy a system of linear equations that involve xi. They also all need to be non negative and the sum of i * ai needs to sum to N.
I solve that system, verify the solution and generate the output string.
My codes in Java. There are two approaches for div1-med. Mine was "choose some K of the initially-best 5*(K-1)+1 edges, in complexity C(5·(K - 1) + 1, K)". The other one was resursive "find the best edge and either take it or take some two neighbours".
could you please elaborate a bit on div2-hard?
Every valid subtree has a unique diameter. The main idea is to iterate over O(n2) possible diameters. For a fixed pair of vertices (a, b) we are interested in the number of subtrees with the following properties:
You should mark some vertices v as forbidden and on the remaining vertices run an O(n) dynamic programming solution. Check my code for details.
Could you explain Div2-Med a bit please? Esp. this part: ~~~~~ for(int j = i — 1; j >= 0; --j) x[j] -= val * (i — j + 1); ~~~~~ Why do we reduce the values and then check if x[j] going < 0 will return an invalid password. Am not able to get the intuition behind this. Seems like something to do with combinations.
Let's say the input says that there are no intervals of length bigger than 5. But it says that there are two intervals of length 5. Each of those two intervals generate some smaller intervals. In an interval of length 5 there are:
The solution is to subtract those and then move on — check if the input says something about some smaller intervals that weren't simply generated by bigger intervals (here: intervals of length 5).
Could please explain where number "5 * (K — 1) + 1" in your Div1-medium solution come from? I know picking 1 edge will affect cost of at most 5 other edges, but it doesn't seem obvious.
Let's say that we already know k - 1 edges from some optimal solution. These edges affect at most 5(k - 1) edges in total. So, at the beginning you can sort edges by "the-sum-of-values-of-two-connected-vertices" and right now the best k-th edge to add is for sure one of 5(k - 1) + 1 best ones from the beginning. Because at least one of first 5(k - 1) + 1 edges isn't affected by already chosen k - 1 edges. And that "at least one" edge isn't worse that edges outside the set of first 5(k - 1) + 1 edges.
Using the logic above, one can prove that there exists an optimal solution using edges only from the set of first 5(k - 1) + 1 edges.
can you explain solution for div 1 easy
can someone explain div2 medium?
You can think about the problem in this way:
Let S be the answer we returned, and it can always be split into a consecutive sequence of 'a', then 'b', alternatively, etc. Let L[1], L[2], ..., L[t] be the length of each consecutive sequence of same character.
For x[i], if L[j] >= i, then it will contribute L[j]-i+1 to x[i]. So x[i + 1] can be computed from x[i] in the following way: x[i+1] = x[i]-(# of L[j] >= i + 1)-(# of L[j] == i), this is equivalent to x[i+1]-x[i] = # of L[j] >= i
Since we know how many L[j] has length at least i, we can thus construct an answer.
div2 medium not able to get solution?
Here is my source: http://pastebin.com/N2TNgWD8
The logic I follow is from biggests to smallests because biggests contains smallests. So lets say if x = {4, 2, 1, 0}. We check x[3] it is zero so we have nothing to do. We check x[2] = 1. Also we calculate how many 3-length substrs there are already. There are zero, so we need to construct one. The resulting string is res = "aaa" Next time we will start with the letter 'b'. x[1] = 2, we have already two substrs of length 2, so we dont add anything. Finally x[0] = 4, so because we have already three we just need to add one new, so resulting res = "aaab". I hope it helps.