Comments
|
+27
The situation is somewhat similar to the one after the SRM 539 at TopCoder. Model solution for 500 points problem was wrong, although 112 submissions passed system test with wrong test data. |
|
-1
Да нет, просто в посылках maxscore обновляется не часто. Отсюда и высчитывает баллы оно там неправильно, на основании устаревшего результата. А в монитор выводит реальное значение. По крайней мере, это то что я заметил за время написания контеста. |
|
-1
Судя по всему, берется максимум. P.S. коммент написан в английской ветке. |
|
+27
I think its time to make a decision. |
|
+5
Seems some of the AC solutions are getting “Internal Error” now. |
|
+26
Here is a link to the contest page in case if someone is still looking for it. |
|
+8
Is it possible to view the problems at least now? |
|
0
Do I understand correctly that C++ programs will be compiled without -O2 flag? |
|
0
The number of ones is x + a. The number of zeroes is b + (c - x). As it was said in the editorial, the answer is 01 or 10 iff the number of ones = the number of zeroes or the number of ones = the number of zeroes + 1 (depends on parity of n). It means that x + a = b + (c - x) + (n mod 2) which is the same as x + a = b + (c - x) + ((a + b + c) mod 2).
|
|
0
Yes, I do Gaussian elimination twice: on the initial graph and on the graph without flowered nodes.
Maybe I should have tried to implement a Fraction class. |
|
+5
The solution I was trying to submit during the contest has the complexity O(N^3). It gets WA, as expected. However, I haven't tried to submit it with BigDecimals.
|
|
0
Nevertheless, the only accepted solution for this problem uses Gaussian elimination.
|
|
0
>Also, isn't the complexity is more like O( (NM)^1.x ), because each '1' may bound more than one of each set of connected 0s?
The complexity is still O(NM). One can notice that each '1' can be adjacent to not more than 4 connected components of zeroes. It means that in total we'll process all '1's not more than 4NM times, which is O(NM). |
|
0
Russian version of the editorial is already published. I'll translate it today or tomorrow.
|
|
+10
Most of the successful hacks were also added to the final testset.
|
|
+17
You can open the "Status" tab and watch it there.
|
|
0
Well, I'm not sure about all of them, but most of them are added to the final testset.
|
|
+10
There were a few successful hacks made with antiquicksort and they were added to the final testset.
|
|
0
Yes, they know the digits. One need to find the outcomes for all possible replacements of '?' with '0' and '1'.
|
|
+3
Pretest #1 is always the first example case.
|
|
0
It can be solved in O(max * log(max) + n). First, for each number we can find the smallest prime number which divides it. It can be done in O(max * log(max)) using the Eratosthenes sieve.
The answer is c(1) * m(1) + c(2) * m(2) + ... + c(max) * m(max), where c(i) is the number of elements from the input which are divisible by i. m(i) is the Mobius function. Both values can be easily calculated in O(max * log(max)). It works 0.5s on my computer on maxtest. |
|
0
Isn't it the same which is currently implemented? The only difference now is that the virtual contest is being run by ACM rules instead of Codeforces rules. I hope it will be changed soon.
|
|
0
I've used exactly the same trick, i.e. 400*0.29 (my test case is #40). To find it I've ran a brute-force over all A and K and tried to round A*K with and without eps. If those two numbers are different, then there was a rounding error. The first such test case is 100 * 0.29, but 100* 0.29 is less than 100, which is not what we want. The next one is 400 * 0.29 and it is fine for us.
|
|
0
Nope.
|
|
0
In my solution most significant digits are at the right side. However, I'm using base 5 instead of base two.
|
|
+10
Can you fit it into 30 instructions and 150000 steps for N=5000?
|
|
+8
Problem C is brilliant! I think it is the best Code Jam problem I ever seen. The idea is original and fresh and the code is quite short, however it requires careful implementation. Quite strange that only one person has tried to submit it.
|
|
+3
Thank you. I've fixed this in the post, though for some reason it was correct in the Russian version.
|
|
0
Sorry, my reply was to the post in the Russian interface, so you probably didn't see it. Here is an article in which O(N2logN) solution is described. There is also O(N3) solution in this article and I think it is sufficient for the given constraints.
|
|
+7
Yeah, I have the same situation. And even if sometimes I can afford writing a contest at 17:00 on weekday, than it definitely won't be a Friday.
It would be really nice to have at least 1 round on weekend each month. Probably someone won't be able to compete in it, but I think that writing 3 out of 4 monthly contests is a good price to give someone a chance to compete in at least one of them. |
|
+1
Yes, standart keyboards have unique keys. But it was stated in the statement that the keyboard is "unusual", that is it can't be called "standart".
Moreover, there is a sample test case with duplicate keys, so there can't be any misunderstanding regarding this. |
|
0
If it is implemented optimally, then the complexity is O(N).
|
|
0
=============================================
Suppose that after some step the set S is equal to {1...X}. You want to add a new coin with the value of C. If C<=X+1, then it can be proven that after adding this coin the set S becomes {1...X+C}, otherwise the number X+1 is not representable so the algorithm outputs it and stops. You don't need to maintain the whole set, it is sufficient to remember only one number X. |
|
0
Actually the algorithm described above finds exactly what you need, i.e. maximum matching.
|
|
0
If you have coins "1 2 2 5 5 100", then what happens to the set of representable numbers after adding each coin? Here C is the current set of coins and S is the current set of representable numbers. 1) C={1}, S={1} 2) C={1,2}, S={1,2,3} 3) C={1,2,2}, S={1,2,3,4,5} 4) C={1,2,2,5}, S={1,...,10} 5) C={1,2,2,5,5}, S={1,...,15} After adding the last coin set S stops being consecutive, so the answer is 16. |
|
+6
Partially true. It may happen that after adding some number set stops being a consecutive sequence and this case is the most important in this problem.
|
|
0
It won't work for 10000 machines, that's why I told you about O(NlogN) solution. After figuring out how to solve it in O(NlogN) for one machine, you'll be able to solve the whole problem in O(P*N*logN).
Btw, it is better to continue the discussion in private messages. |
|
0
It is not a good idea to add something new to the comment after it has been answered. You don't need to store the whole set directly. Just look on its structure and try to find a way to maintain it after adding new numbers into it. |
|
0
You should set not only sum and coin[i] as available. For example, after adding the first three coins all numbers from 1 to sum (which is equal to 5) will be available. I don't want to reveal the whole solution now, try to figure it out by yourself using the hint I gave.
|
|
0
You can solve this problem for one machine in O(NlogN). Try to sort all coins in ascending order of their values and iteratively build the set of all representable numbers. Then see what happens with this set after adding a new number.
|
|
0
Quote from the editorial:
"If X and(A - X) ≠ X then the answer is also -1." Here X=5 and A-X=9. 5 and 9 = 1, which is not equal to 5. So the answer is -1 here. |
|
0
It was a typo. "Obsiously" should be, of course, "obviously".
Also I occasionally used P instead of M'. It is fixed now, thanks for pointing this out. |
|
0
If some two events have the same time then it is impossible to visit them both, so we are not interested in their relative order in the sorted array (after performing the transformation). After the transformation we can get from the point (pi, qi) to the point (pj, qj) iff pi ≤ pj and qi ≤ qj. After performing the sorting described in the editorial all points reachable from the point (pi, qi) will have greater indexes in the array. This automatically means that the sequence will be non-decreasing by pi, so we only need to care about qi. The longest non-decreasing sequence by qi is the sequence we are looking for. |
|
0
If ai=2 then 12 items will be displayed on 6 pages, but 13 items will be displayed on 7 pages.
|
|
0
"If there is no amount of fuel that can reach synchrophasotron, output -1 -1" means that you should output "-1 -1" only if all conditions on capacities can not be satisfied simultaneously.
There is a sentence in output section of the statement: The amount of fuel which will flow into synchrophasotron is not neccessary positive. It could be equal to zero if the minimum constraint of every pipe is equal to zero. |
|
0
164: #include <iostream> __int64 n,k,x,y,a[' '],b[' '],d,i; main() { std::cin>>n>>k>>x>>y; for(k%=2*n;d<k;d++) std::cin>>a[d]>>b[d],x=2*a[d%n]-x,y=2*b[d%n]-y; std::cout<<x<<" "<<y; } |
|
0
You can find Codeforces Beta 13 tutorial here.
|
|
+20
I didn't use neither Suffix Arrays nor hashing, nor DP. I've just stored all distances between equal numbers and then performed exactly the same thing that is written in the statement, i.e. tried to remove repeats in the increasing order of their lengths. The main observation is that the distance between the numbers from the first half of the repeat and the respective numbers from the second half remains unchanged.
|
|
+3
Suppose there is no optimal sequence where each element is equal to some element from the initial sequence. Then there is an element i which is not equal to any of the elements of {ai}. If the elements with numbers i-1 and i+1 are not equal to element i, then we can move it closer to ai and the answer will decrease. So there is a block of equal elements and all of them are not equal to any of the elements of the initial sequence. Note, that we can increase all block by 1 or decrease it by 1 and one of this actions will not increase the answer, so we can move this block up or down until all its elements will be equal to some element from the initial sequence.
|
|
0
The fact that your solution works correctly on this test case doesn't mean that it is correct :)
My solution passes this test. |
|
0
Maybe you have used int32 instead of int64.
|
|
+3
That's pity that I have missed such test case.
Anyways, you are lucky :) |
|
0
I can just say that it is the first big test case (N=5000). All previous ones are very small (N<=10).
|
|
0
Unfortunatelly, there was not any solution, written on Java for this problem. The complexity of my solution is O(N^2*(N+M)) and the worst execution time was 0.86s, so I decided that 2s will be enough to pass all test cases using any language.
|
|
0
Beaten :)
|
|
0
Try to replace scanf("%lld",&num) with scanf("%I64d",&num) and printf("%lld\n",i) with printf("%I64d\n",i).
|