Savior-of-Cross's blog

By Savior-of-Cross, history, 11 months ago, In English

Contest Link

How to solve A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, and Q?

(I'm only curious about N and O, but I might as well ask them all in case others are curious about other problems)

Full text and comments »

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

By Savior-of-Cross, history, 14 months ago, In English
  • Vote: I like it
  • +35
  • Vote: I do not like it

By Savior-of-Cross, history, 15 months ago, In English
  • Vote: I like it
  • +158
  • Vote: I do not like it

By Savior-of-Cross, history, 19 months ago, In English

Hello Codeforces! The 14th Stage of the 1st Universal Cup is coming. It will be held from Apr 29th to 30th.

The contest was used in the Osijek Competitive Programming Camp 2023 Winter. If you have solved any problems from the last day of the camp, please skip this round. Teams that participated in the camp can have their camp results included in the final standings.

All problems are authored and prepared by me.

I want to thank

As usual, we have three time windows for participating. You can participate in the contest in the following three time windows:

  • Apr 29th 13:00 — 18:00 (UTC +8)
  • Apr 29th 19:00 — 24:00 (UTC +8)
  • Apr 30th 02:00 — 07:00 (UTC +8)

Please note that you can see two scoreboards in DOMjudge. The 'Local Scoreboard' shows the standings ONLY IN THE CURRENT TIME WINDOW. And the 'Combined Scoreboard' shows all participants, including the onsite participants, and the cup participants in the previous time windows.

Contest link: https://domjudge.qoj.ac/

Universal Cup Scoreboard: https://qoj.ac/ucup/scoreboard

About Universal Cup:

Universal Cup is a non-profit organization dedicated to providing trainings for competitive programming teams. Up to now, there are more than 500 teams from all over the world registering for Universal Cup.

A more detailed introduction: https://mirror.codeforces.com/blog/entry/111672

Register a new team: https://ucup.ac/register (the registration request will be processed before each stage)

Results of the past stages: https://ucup.ac/results

Terms: https://ucup.ac/terms

Ratings: https://ucup.ac/rating

Full text and comments »

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

By Savior-of-Cross, history, 2 years ago, In English

How to add color to a polygon statement? \color seems to not work :(

Full text and comments »

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

By Savior-of-Cross, history, 3 years ago, In English

I was reading mango_lassi's blog and in one of the paper referred in his blog, I found a $$$O(N^2)$$$ algorithm for constructing a longest k-increasing subsequence (a subsequence of maximum length which is a union of k increasing subsequences). While implementing it, ko_osaga told me about the problem E in "AMPPZ-2015 MIPT-2015 ACM-ICPC Workshop Round 1" (id #6275 in opentrain) where the problem asks to construct such subsequence with constraint $$$N \le 2 \cdot 10^5$$$ and $$$K \le 20$$$.

The official solution runs in $$$O(N \cdot K \cdot (K + \log(N)))$$$. The first half seems to be doing the RSK mapping, but I couldn't figure out why the second half works. It seems to be unrolling the mapping from the back, and maintaining $$$K$$$ intervals for each row in the tableau. And the editorial only explains the first half. Can someone please explain why it works?

Official Solution

Erid-near-windmill

Full text and comments »

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

By Savior-of-Cross, history, 3 years ago, In English

All my recent round experiences are like "code -> code -> code -> ... -> code contest ends".

I think it won't hurt to increase the default contest duration to 3h so that we can have some time to think about harder problems.

Any thoughts?

roxy

(Mendatory Waifu Pic)

Full text and comments »

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

By Savior-of-Cross, history, 3 years ago, In English

Not sure if this has been mentioned before, but the following code involving std::inclusive_scan doesn't compile on CF on both "GNU G++17 7.3.0" and "GNU G++17 9.2.0 (64bit, msys 2)". This function is part of the C++17 standard, according to the reference, so it should compile on both versions (and it does compile locally).

inclusive_scan

std::exclusive_scan doesn't compile on CF as well.

exclusive_scan

Full text and comments »

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

By Savior-of-Cross, 4 years ago, In English

I was solving the string section problems from Brazilian summer camp 2018, and there were following problems:

You are given z-function of some (unknown for you) string s, write prefix-function of the string s.

You are given prefix-function of some (unknown for you) string s, write z-function of the string s.

I thought that if these were solvable, just storing all the equality information would suffice on both problems, and they indeed got AC (Code below). But I have no clue how to prove either of these, and I couldn't find the editorial on google.

Can someone tell me how to prove these?

z->pi
pi->z

Full text and comments »

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