induk_v_tsiane's blog

By induk_v_tsiane, history, 5 months ago, translation, In English

Recently (two weeks ago) RuCode Festival 7.0 concluded.

Let's discuss the problems here.

How to solve A from DIVAB? I know how to solve most tasks, except A, C, F and L.

Full text and comments »

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

By induk_v_tsiane, history, 7 months ago, translation, In English

Hi, Codeforces.

Recently I have been thinking about the following task:

You are given $$$N$$$ lines of form $$$f_i(x) = a_i * x + b_i$$$ and $$$Q$$$ queries of form $$$x_j, k_j$$$ — if we sort all of the values of lines in point $$$x_j$$$, which line would be on the $$$k_j$$$-th spot? The queries are offline. I will use $$$K$$$ — the maximum out of all $$$k_j$$$.

I thought about this and developed some methods:

The first one runs in $$$O(sqrt(N)logN + KlogKsqrt(N)$$$ pre query and is online. We use sqrt-decomposition, build CHT on every block, for each query we do the following: run over the blocks, get $$$K$$$ minimums and the blocks where they occurred. Now we know that the needed minimum lies inside one of this blocks, we can now iterate over $$$K * sqrt(N)$$$ blocks, maintaining the $$$K$$$ smallest values with a set.

The second one runs in $$$O(NKlogNlogMAX)$$$ total: for each position from $$$i$$$ to $$$K$$$, we do the following: process the queries left to right, get the current minimum with its index. On the next walkthrough, we will use D&C to delete that line before this query using Li-Chao tree, and then add it back.

The third one runs in $$$O(N^2logN + QlogQ)$$$. We generate all $$$O(N^2)$$$ points of intersection, sort them together with the requests, then simply swap the two lines which intersect.

So, all of these are kinda not good enough(((. If anyone can share any ideas, I will be extremely grateful.

Full text and comments »

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

By induk_v_tsiane, history, 8 months ago, translation, In English

We hope you liked the problems.

Task A was invented and prepared by induk_v_tsiane.

Task B was invented by induk_v_tsiane, and prepared by i_love_penguins.

Task C was invented and prepared by induk_v_tsiane.

Task D was invented by i_love_penguins and efimovpaul, and prepared by i_love_penguins.

Task E was invented by induk_v_tsiane and kristevalex, and prepared by induk_v_tsiane.

Task F was invented by induk_v_tsiane and Artyom123, and prepared by induk_v_tsiane.

1859A - United We Stand

Hints
Tutorial
Author's code

1859B - Olya and Game with Arrays

Hints
Tutorial
Author's code

1859C - Another Permutation Problem

Hints
Tutorial
Author's code

1859D - Andrey and Escape from Capygrad

Hints
Tutorial
Author's code

1859E - Maximum Monogonosity

Hints
Tutorial
Author's code

1859F - Teleportation in Byteland

Hints
Tutorial
Author's code

Some notes/challenges:

  • We know about the $$$O(N^2)$$$ solution in C, but we did not find a good suitable proof for it (and, using the method, we could achieve faster solutions).

  • You can solve $$$D$$$ without the constraint that the segments are contained, but that is harder. It is solvable in $$$(ONlogN)$$$.

  • Thank you all for participating! If you have any complaints/suggestions/advice for future rounds, feel free to share in the comments!

Full text and comments »

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

By induk_v_tsiane, history, 8 months ago, translation, In English

Hello, Codeforces.

We are happy to invite you to Codeforces Round 892 (Div. 2), which will take place on Aug/12/2023 17:35 (Moscow time). All of the problems are original and were prepared by a collective of authors, consisting of kristevalex, i_love_penguins, efimovpaul and me, induk_v_tsiane. This round will be rated for participants with a rating lower than 2100.

We would like to thank:

You will be given 6 problems and 2 hours to solve them. The score distribution is 500 — 1000 — 1250 — 1750 — 2250 — 3000.

I would like to also congratulate my cousin Max, who is turning 30 the day of the round. If you wish, you can write birthday wishes for him and I will pass them on.

UPD: Editorial

UPD 2: Congratulations to the winners!

Div. 2:

  1. modulo998244353

  2. botjiaxun

  3. Tmath_OneLove

  4. FengjianZhu

  5. Alihan_8

Div. 1:

  1. Geothermal

  2. heno239

  3. maspy

  4. jiangly

  5. Ormlis

Full text and comments »

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