(Context: https://codeforces.me/blog/entry/136021)

Oh, hello there! It’s me, the stuffed penguin. You might think I’m just sitting around here, looking cute with my pink feet and fluffy wings, but little do you know, I’m actually the perfect embodiment of wisdom. Or, well, that’s what I tell myself to feel better about my life of plushy leisure.

I often get teased about being “lazy, just like a segment tree.” Honestly, I don’t even mind. Have you ever seen a segment tree in action? It looks like it’s doing absolutely nothing most of the time, just like me! But when the moment calls for it, bam, it comes out of nowhere and solves complex range queries with ease. That’s kind of my approach to life: hang out, chill in my little spot, and when the time comes to be cuddled or admired, I deliver. Efficiently.

Now, let’s get one thing straight: just because I spend most of my time sitting next to this igloo house (which I rarely leave), doesn’t mean I’m not doing anything. Much like a segment tree, I’m always “ready.” In programming terms, I’m in a state of restful, pre-processed calm. You never know when you’ll need me to provide comfort or inspiration. I like to think that I’m working smarter, not harder, like a true optimization master.

So, next time you see me lounging around, remember—there’s more going on behind these plushy eyes than you think!

In IOI 2017 toy train, does anyone know what are the intended solutions for the subtasks, particularly subtasks 3-5? The editorial goes straight to the full solution.

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.me/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₁, ... , 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:

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₁, ... , m_k such that , where l is an integer and l ≤ 2 × ceil(log₂(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₁, m₂, ..., 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://codeforces.me/contest/615/submission/19726073