| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 166 |
| 2 | maomao90 | 163 |
| 2 | Um_nik | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
Let's discuss the solutions of all the problems. I would like to know other peoples approaches for the problems. This time I am only able to solve Problem A. What are your views about the problems ?
Here are the problem statements.
Final Round on Sunday, November 6, 2016 13:00 CST
how did u solve A ?
I didnt solve it through the contest because I had some troubles, but I submited now and got AC to both, small and large. Large run in 6sec, so I think is a good solution. Complexity is O((N+M)*N) I keep a dp[i][j] with size [4000][2000] where i is the position and j is how much 'A' voters I have until that position. Dp itself keeps the ways we can achieve that with the rules that statements says. So dp[i][j] = dp[i-1][j] * max(0, M — (k-1)), for the case that we want to add in ith position an 'B', and dp[i][j] += dp_solve[i-1][j-1] in case we want to add an 'A'. Finally you will print dp_solve[N+M][N] / factorial(N+M). In large that will overflow, so we can keep a clever division in each for loop, something like that-> dp[i][j] /= i, because we want dp[i][N] to be divided by i!, so dp[i-1][N] will be divided by (i-1)! so new dp[i][N] can be equal to (i-1)!*i, so you see that you can just divide by i in each loop.
What is the variable k and dp_solve?
dp_solve is the dp. I write it differently by accident. k is the variable that keeps the 'B' voters we can have at current state. It is caclulated as i-j.
sanket407 Read the problem statement carefully and Just see the sample inputs. The ans will be (n-m)/(n+m). You can get this by writing all the permutations as explained in problem. Check this for more details : Bertrand's ballot theorem
A: Simple DP with state as (N, M) denoting number of people of first kind and second kind left. Transitions are easy, just check if second kind person votes now, then first person should be still winning.
B: I'm not sure, but I think I got AC on large by fluke, just submitted some random greedy solution. Any ideas on proof or your solution? Solution for small: DP with state (current Index, mask of row[currentIndex-1], mask of row[currentIndex-2]). Transitions are easy, check all possible masks for the current row which satisfy all conditions.
C: Again DP in O(N2 logN) per test case. State is (Current Index). From the current index, start iterating forward keeping an array of frequencies. At each position, check if we have the same frequency of characters as in any one of the strings using a map(which is computed previously).
D: Small: Brute force, try out all 210 combinations. No idea how to solve large. Anyone?
D: DP[x][i] stores the minimum cost required for formation of length exactly x using some rubber bands upto i. Transitions are pretty straight forward. One can use segment tree or sparse table to speed up the same.
Thanks a lot! :)
Can you explain a bit more on how segment table or sparse table can be used to speed up transitions
please state the recurrences for A
P(A) = Probability to select a person that votes for A from remaining voters
Similarly for P(B). These could be find out from initial, n, m, noOfPeopleVoted, noOfVotesforA
Answer is in find(0, 0)
How did u bitmask on large dataset ? R,c<100
Only for the small dataset. For large I used a greedy approach that I don't have a proof of.
can you explain how to use greedy approach to solve the problem? I think the method is like this:
so I get the answer:
N = 15,M = 15
but it's wrong!!! I don't know how to solve it. thanks a lot
I had a shitty greedy, this is what I did:
Every time if the previous column in the same row is blank, and the same column in above 2 rows both are not filled, I fill this current cell.
If the previous column is filled:
1) If the above top 2 rows of current column is filled, do nothing.
2) Else if the above row is not filled, fill this cell.
3) Now if the above cell is filled, we check the previous column. If the row above in previous column is also filled, we don't fill the current cell(if it is the last row, we fill it), else we fill it.
When I did this, it didn't pass the small dataset.
Then I did the same thing for both, the given matrix, and transpose of the matrix because answer won't change since we have started filling in another way.
Now I took max of both, and it passed the large data set too.
thank you for you reply, but I have some doubts. I default the cells above the first row are all blank.
Every time if the previous column in the same row is blank, and the same column in above 2 rows both are not filled, I fill this current cell.and
2) Else if the above row is not filled, fill this cell.so the first row will be filled like this:
Maybe I have some misunderstanding, very thanks
I'm sorry for the confusion, you also have to check at each time that there isn't any consecutive 3 cells. So first row is filled like this -xxoxxoxxoxxo...
How did you create a map of character frequencies for the dictionary words in C?
Used C++ and a map that maps vector to int.
A: well-known problem, answer is (n-m)/(n+m).
B: I don't know the right way but I made a few observations and with a little help from oeis, I guessed the answer. Answer for (r,c) is same as (c,r). Assume r<=c. If r=1 or r=2, answer is r*(c-floor(c/3)). If r is a multiple of 3, answer is (2*r/3)*c, else the answer is r*c-floor((r*c)/3).
C: DP. Dp[i] is the number of ways to form the string till i. To find this, select some j<i and consider the string between these two indices. Check for how many words in the vocabulary, this string is an anagram of. Call that number X, then dp[i]=dp[i]+x*dp[j-1].
D: Did the small dataset only by checking all the subsets.
How to prove answer for A is (n-m)/(n+m) ?
Bertrand's ballot theorem
nice !
Could u please tell me how did u get this formula about r and c in problem B. Thanks a lot!
When r = 1:
xxo xxo xxo ...
When r = 2:
xxo xxo xxo ...
xxo xxo xxo ...
When r > 3 and r % 3 == 0 or 1:
Consider the following method:
xxo xxo xxo ...
oxx oxx oxx ...
xox xox xox ...
xxo xxo xxo ...
When r > 3 and r % 3 == 2:
xox xox xox ...
xxo xxo xxo ...
oxx oxx oxx ...
xox xox xox ...
xxo xxo xxo ...
Here we permute the lines to assure that the leading columns filled with 'x' as many as possible.
Then you can get the above formula.To prove the correctness,
For every continous 3 grids we need to fill at least 1 'o',
while the method we suggested can do exactly 1 'o' every 3 grids.
Thank u very much! I have got your idea,but one question here is.
If i keep every 3 seats must have one 'o' in a line,and permute the 'o's position in different lines, why when r > 3 and r % 3 == 2 is:
xox xox xox ...
xxo xxo xxo ...
oxx oxx oxx ...
xox xox xox ...
xxo xxo xxo ...
Is it the same with?:
xxo xxo xxo ...
oxx oxx oxx ...
xox xox xox ...
xxo xxo xxo ...
oxx oxx oxx ...
which means does the first line can be xxo xxo ... form? they all have 15 'o'
Take your same examples and take C = 10 (instead of 9 above) Then couunt the no. of X in both cases U will get the difference
"Here we permute the lines to ensure that the leading columns filled with as many 'x' as possible."
When r % 3 == 2, we only consider the last 2 lines. When the column number increase, we want to keep as many 'x's as possible.
(i)
xxo
oxx
when c = 1, number of 'x' is 1. when c = 2, 'x' is 3, c = 3, 'x' is 4.
(ii)
xox
xxo
when c = 1, number of 'x' is 2. when c = 2, 'x' is 3, c = 3, 'x' is 4.
You can see when c = 1, the second one is better.
Can somebody tell me of how much order pass in Apac or Codejam. In Codeforces solution of 10^8 pass. However, I am not sure about how much complexity Apac allows. Please guide me in this as I thought my A would not pass large test cases but however it did.
So please tell me is it 10^8 computations in Apac too.
There's nothing like that in code jam or apac as you have to post the output file rather than code. Your code will not be run by server like in CF. So basically it comes down to generating the output file on your pc using your code within the time limit ( 4 minutes from time of downloading input file to time of submitting i guess )
No, they take the source code so obviously they check the code on their cases too. Else 4 minutes is too much I guess. It may happen that many TLE solution may pass.
Plz someone help over here.
They check any similar codes to avoid copying. TL is dependent on your computer and 4min is very lenient but still enough to kill most suboptimal solutions.
Thanks a lot. And so Facebook Hacker Cup follows same procedure( of just checking output files ) or do they have limit on computation. Can you please tell this too?
source code is just for plaigarism check i or some other reason They dont run it themselves https://code.google.com/codejam/apactest/terms.html check rules 3-4-5-6 under 4.PROBLEMS section
Thanks :)
Is there any other way to solve B-large , apart from formula ?
Problem D. large test case in detail anybody please
Let's dp[n][L] = the least money to create a rope of exactly size L
then dp[n][L] = min(dp[n — 1][L — b[n]] -> dp[n — 1][L — a[n]] you can find the answer by using dequeue,
Code