# | User | Rating |
---|---|---|
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 |
# | User | Contrib. |
---|---|---|
1 | cry | 167 |
2 | Um_nik | 163 |
3 | maomao90 | 162 |
3 | atcoder_official | 162 |
5 | adamant | 159 |
6 | -is-this-fft- | 158 |
7 | awoo | 157 |
8 | TheScrasse | 154 |
9 | Dominater069 | 153 |
9 | nor | 153 |
I tried accessing my account at my home IP and it does not work. I'm sure that it's not banned by my router, and it works before I came back from the IOI. Two other proxies I used also did not work. Does anyone have an idea why is this?
What are some tricks that we can use to find binomials faster? Usually, I just "exploit" some condition, which is like the binomials are not far from each other.
You could see the code here: http://codeforces.net/contest/785/submission/25528358
(This is for round 404, problem D)
What other tricks are there? I saw that other users' code aren't that long, but I don't really understand the codes. Note that for this problem, a naive implementation for the binomial coefficient would fail.
The only trick I know is getting a binomial from a nearby binomial by incrementing/decrementing the numerator and the denominator. Like for example, to transform 69C7 to 75C4, we do 69C7 -> 70C7 -> 71C7 -> ... -> 75C7 -> 75C6 -> 75C5 -> 75C4; it is easy to get the conversion factors from aCb to (a+1)Cb, or (a-1)Cb.
But the problem is that the code here is long. Are there more elegant ways to get binomials faster?
Here's the problem (IMO 2013 Problem 1): Assume that k and n are two positive integers. Prove that there exist positive integers m1, ... , mk such that .
There is an inductive proof, which is generally the more popular solution among IMO contestants, but I would like to demonstrate a solution that relates this problem to a well-known data structure: the segment tree.
Think:
How is this related to segtrees?
Could you reformulate the "fraction multiplication" into something that is more similar to something related to segtrees?
Maybe we could relate the ranges in a segtree to fractions of the form 1 + 1/m.
Yes, each thing on the RHS may be taken as ranges. But you need the range length (including start, but not end) to be a divisor of the numerator. Note that we could multiply the numerator and denominator by the same number. For example . Hmmm now how could we do this?
In a segment tree that covers the range (1,1024), look at all the nodes that cover ranges of size 8. Which ones have anything in common with fractions of the form 1+1/m? How about if the size is 2, 4, or 16?
Let's try to turn the LHS fraction to a range [n, n + 2k - 1]. "Modify" our segment tree so that each range overlaps with the previous range of the same size, such as [0,8], [8,16], [16,24] for size = 8. You may want to see the visualization here: http://codeforces.net/blog/entry/18051, as an idea on how it works.
What happens when you do a range sum query? What happens to the lengths?
Here's a generalization, which is much easier once you've found the segtree solution to the above problem. Assume that k and n are two positive integers. Prove that there exist positive integers m1, ... , mk such that , where l is an integer and l ≤ 2 × ceil(log2(k / 2 + 1)).
Challenge: Implement the two variants of the problem. In the generalization, you are given k and n, and you are required to output an array that consists of m1, m2, ..., ml. Post the solution in the comments.
From the preliminary results, is anyone able to calculate the Averages and the Full Solves for each of the problems?
Predictions for difficulty / style of Day 2 problems?
Does anyone have a solution to this problem, even just for part b?
The question is basically (for the highest sub-task) that you have to decode a length 1000 binary string, and you have 1024 queries of the form "is substring S present", on which an answer of Yes or No will be given.
Thanks!
I was looking at my previous codes and I noticed a very strange Memory Limit Exceeded Error. The error occurred on test case 24, which has 127 numbers in the array, while in all previous test cases, I used at most 4MB. Does anyone have an explanation? The only large chunk of memory I allotted in my code is a 200,000-longlongint array which shouldn't take more than 2MB. However, in this test case, I used 256MB and got MLE.
Name |
---|