wfe2017's blog

By wfe2017, history, 3 months ago, In English

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.

Full text and comments »

  • Vote: I like it
  • +5
  • Vote: I do not like it

By wfe2017, history, 7 years ago, In English

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?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By wfe2017, history, 8 years ago, In English

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?

Full text and comments »

  • Vote: I like it
  • -7
  • Vote: I do not like it

By wfe2017, history, 8 years ago, In English

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:

Spoiler 0
Spoiler 1
Spoiler 2
Spoiler 3
Spoiler 4
Mega Spoiler

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.

Full text and comments »

  • Vote: I like it
  • +71
  • Vote: I do not like it

By wfe2017, history, 8 years ago, In English

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?

Full text and comments »

  • Vote: I like it
  • +7
  • Vote: I do not like it

By wfe2017, history, 8 years ago, In English

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!

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By wfe2017, history, 8 years ago, In English

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.net/contest/615/submission/19726073

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it