t0rto1se's blog

By t0rto1se, 15 months ago, In English

As you can see from Contests, the recent CF round (#844) was (Div. 1 + Div. 2). But there are some rounds (such as #829, or the one scheduled on Feb 5, 2023) which are held as two contests, one for Div. 1 and another for Div. 2.

What is the reason to split some contests into two divisions, and combine some other contests? Is it done for more variety in the type of contests, or based on specific features of the problemset, or something else?

Full text and comments »

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

By t0rto1se, history, 21 month(s) ago, In English

I would love it if we could hide the problem tags, but at the same time be able to see difficulty inside the problem statement. Sometimes I get a link to a random question (through some resource) and I have to go to the problemset to check "show tags for unsolved problems", so that I can see the rating of the problem.

It'd be nice to have a separate option to enable difficulty rating. What do you guys think?

Full text and comments »

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

By t0rto1se, history, 21 month(s) ago, In English

Problem Name — "Group Photo"

There are $$$N$$$ people, each with a unique height. The height of the $$$i^{th}$$$ person is $$$i (1 \leq i \leq N)$$$. The $$$i^{th}$$$ person will smile in the photo if at least $$$A[i]$$$ people in the photo are shorter than him and at most $$$B[i]$$$ people in the photo are taller than him.

Find the largest group such that everyone will smile in the photo of this group. A group is a collection of randomly selected people from the given $$$N$$$ people.

Constraints:

  • $$$1 \leq N \leq 10^5$$$

  • $$$0 \leq A[i], B[i] \leq N$$$

Example Test Case
My O(N^2) approach

I cannot come up with a better solution for this. Any help would be greatly appreciated, thanks!

Full text and comments »

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