# | User | Rating |
---|---|---|

1 | tourist | 4009 |

2 | jiangly | 3831 |

3 | Radewoosh | 3646 |

4 | jqdai0815 | 3620 |

4 | Benq | 3620 |

6 | orzdevinwang | 3529 |

7 | ecnerwala | 3446 |

8 | Um_nik | 3396 |

9 | gamegame | 3386 |

10 | ksun48 | 3373 |

# | User | Contrib. |
---|---|---|

1 | cry | 164 |

1 | maomao90 | 164 |

3 | Um_nik | 163 |

4 | atcoder_official | 160 |

5 | -is-this-fft- | 158 |

6 | awoo | 157 |

7 | adamant | 156 |

8 | TheScrasse | 154 |

8 | nor | 154 |

10 | Dominater069 | 153 |

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://mirror.codeforces.com/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 *m*_{1}, ... , *m*_{k} 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* + 2^{k} - 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://mirror.codeforces.com/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 *m*_{1}, ... , *m*_{k} such that , where *l* is an integer and *l* ≤ 2 × *ceil*(*log*_{2}(*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 *m*_{1}, *m*_{2}, ..., *m*_{l}. 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.

http://mirror.codeforces.com/contest/615/submission/19726073

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/07/2024 09:53:17 (j2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|