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?

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

1 | tourist | 3870 |

2 | Benq | 3618 |

3 | Miracle03 | 3453 |

4 | peehs_moorhsum | 3430 |

5 | Radewoosh | 3418 |

6 | Petr | 3408 |

7 | maroonrk | 3387 |

8 | sunset | 3338 |

9 | ko_osaga | 3334 |

9 | jiangly | 3334 |

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

1 | YouKn0wWho | 214 |

2 | 1-gon | 203 |

3 | Um_nik | 195 |

4 | Errichto | 181 |

5 | awoo | 180 |

6 | tourist | 176 |

7 | sus | 175 |

8 | antontrygubO_o | 173 |

9 | maroonrk | 170 |

10 | SecondThread | 169 |

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.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://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!

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/09/2021 11:29:30 (k2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|