valeriu's blog

By valeriu, 5 weeks ago, In English

Hello Codeforces,

I will present today, and in any day in the future, a means to correctly calculate a corner case of the well known small-to-large trick, and how this can be employed to solve a set of certain problems. This blog is written with encouragement from the Month of Blog Posts initiative.

Forenote; Height definition

The standard example.

Let's try to solve the following problem: Cat In a Tree, BOI 2017. Although this problem can be solved employing some greedy algorithm, assume we have no idea what greedy is or how it could be correct, and revert to the basics:

The standard DP.

How can we formulate a DP on this problem? Well, what we need to keep track of is how can we select multiple nodes such that they are all at distance greater than D. When we are considering a correct solution on a subtree and we want to merge it with that of its brother, only one parameter is of importance: the distance of the closest chosen node to the root (As much as any other pair of nodes that traverse their common ancestor would have their length at least as long). And as this seems to be sufficient, we find that the following DP definition is sufficient: $$$dp_{\texttt{node}, \texttt{closest}} = $$$ the highest cardinal of any solution included in the subtree of the node $$$node$$$ such that the closest node chosen is at distance $$$closest$$$

The transition from the sons into their father would look like the following (for two sons $$$s1$$$ and $$$s2$$$): $$$dp_{\texttt{root}, \texttt{min+1}} =\max(dp_{\texttt{s1}, \texttt{min}} + dp_{\texttt{s2}, \texttt{x}},dp_{\texttt{s1},\texttt{x}} + dp_{\texttt{s2}, \texttt{min}})$$$ for any $$$x + min + 2 \ge D$$$ and $$$min \le x$$$

It is clear that the transition for more than two sons is made progressively by merging the current calculated dp in the root with yet another son. Furthermore, we can tweak the definition to represent instead the highest cardinal of any solution whose closest chosen node to the root is at distance at least $$$closest$$$ (i.e. perform suffix maximums). This will help reduce the unnecesary linear traversal of index $$$x$$$, leaving only $$$min$$$ to be iterated.

To sum up these observations in some comprehensive formula, let's rephrase the transition algorithm as follows:

  1. At first, we take the $$$dp$$$ array of a son $$$^\dagger$$$. We now assign $$$dp_{\texttt{node}, \texttt{closest+1}} = dp_{\texttt{son}, \texttt{closest}}$$$. We also assign $$$dp_{\texttt{node}, \texttt{0}} = dp_{\texttt{son},\texttt{D-1}} + 1$$$ (i.e. adding a new node to the solution).
  2. To further merge this $$$dp$$$ array with that of a different son, we assign: $$$dp_{\texttt{node}, \texttt{T}} = \max( \,(dp_{\texttt{node},\texttt{T}})^{v_1}\,,\,(dp_{\texttt{node}, \texttt{H}} + dp_{\texttt{son}, \texttt{T}})^{v_2}\,,\,(dp_{\texttt{node}, \texttt{T}} + dp_{\texttt{son}, \texttt{H}})^{v_3}\,)$$$ where $$$H$$$ is $$$\max(T, D-T-1)$$$. Then, adjust to preserve the $$$dp$$$ definition by setting $$$dp_{\texttt{node}, \texttt{T}} = \max( dp_{\texttt{node}, \texttt{T}}, dp_{\texttt{node}, \texttt{T+1}})$$$. (Markings $$$v_1, v_2, v_3$$$ are footnotes, not exponents)

Turns out that $$$\dagger$$$ makes this entire algorithm $$$O(N)$$$.

Full text and comments »

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

By valeriu, history, 16 months ago, In English

Hi everyone!

Recently I asked someone out but they rejected me. So, to fill that inner void they left me, I decided to be looking for someone who wants to join me at grinding OI (including but not limited to JOI/IOI, etc). My actual purpose is to improve my CP competency probably my plan is to make virtual contests of past IOIs (or other OIs) and discuss maybe subtasks of problems that one did and the other didn't or just chat? I'm probably gonna communicate on Discord. If you want to join, please PM me from codeforces.

Here is a list of some requirements. You don't totally have to meet the requirements but if a lot of people write (It won't happen :sadge:), I will have to eliminate them according to these.

Requirements

  • Has free time to solve virtual contests and ~30 minutes of discussing time at some frequency (I don't know yet)
  • English speaker
  • Eligible for future (or current) IOI participation
  • Didn't solve past OIs (not necessary)
  • Codeforces M or IM. Other platforms are accepted too, I will evaluate them. (NO I'M NOT SEXIST BUT OBVIOUSLY IT'S BETTER TO BE AT CLOSER LEVELS :D)

(Thanks if you at least tried to read this meaningless pile of words until here.)

Full text and comments »

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

By valeriu, history, 22 months ago, In English

Hello codeforces,

Today, I am regretably in math class with the subject of modular arithmetic. While thinking about a problem, I reminded myself of a question I asked myself some time ago.

Given $$$p$$$ and $$$mod$$$, find a $$$q$$$ such that $$$q^2$$$ = $$$p$$$ (modulo $$$mod$$$). $$$mod$$$ is prime and ≫ $$$10^8$$$

Does this admit an online logarithmic-complexity solution?

Full text and comments »

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

By valeriu, 2 years ago, In English

Since no one asked on how to un-become Master I decided to post one. So, here are the ways I managed to un-become Master after a lot of effort and hard work.

Have a life

Having a life is the easiest and most efficient way to un-become Master on Codeforces. Relax, play ping-pong

Get a class

Getting a class is another perfect way to un-become Master. You have way less time to focus on Competitive Programming and way more teme which is perfect for losing rating. In my personal experience, after I got a 10 at a prestigious Paul I started to not care so much about competitive programming because in the end of the day virtual rating on Codeforces is meaningless, but 10 on catalog is eternal.

Prepare for IIOT

Trying to compose a team for IIOT instantly brings your free time to 0, which might sound tragic but actually is a great thing. You realize there are more important things than virtual points and you start thinking about what people to team up with. A beginner mistake is to take stranger words for granted and start with Gupa, because instantly later you will lose them. Then, to fill your void, hire Ganto because it seems like a safer bet, and then accept Cuni proposal, but they will all give up on you at some point because they were employed by better/worse teams. Still, anyone else would reject you because they wouldn't give up on the promise they formerly made to their first employer

Edit from the future: apparently, as it has been proven by Mr. AaaIelonmusc (and a special case by myself), best way to prepare for IIOT is to not make a team because then you need to coordinate them, draining away time you could've used yourself by solving the problems. So to all the people that rejected me, I didn't want you anyway (L)

Sleep with the window open

This may not seem like a relevant thing, but get this: At first, for the more based countried, it is mid autumn, so during night-time, approaching morning it is cold. However, decide to still sleep with the windows open because of some fixation you have. You might be asking: but why would this decrease your programming capabilities? Well, they are worse than what they can be: For example, when I was at municipal stage two months ago (jesus time flies so fast) I went to first day, slept with window open, got 200 points. Second day, because Alec Sdima was cold and couldn't sleep with window open, I made a sacrifice and closed the window. Then, I got 201 points.

Coincidence? I think not.

Participate when wake up unoptimally

If you wake up, like I did, 2 hours before the contest, it is painfully obvious that you started your morning wrong. Because if you wake up at 9, you have 30 minutes of time to do morning exercise and routine, then you can plan your meal correctly, walk your dog outside, come back and do your arts homework. If you would've woken up 2 minutes before contest, your mind wouldn't be so filled of these trivialities and you would always have a scapegoat of your own misfortune. Otherwise, you are left only to blame yourself for your incompetency, and that never leads to a good path, because obviously you are never wrong and everyone is against you.

Never upsolve.

If a problem appears in a contest, what are the chances of appearing again?

These are the words of the most famous programmer to date, Hienadz Caratchievici. Unfortunately, mister Hienadz Caratchievici had obviously never been to Lot juniori, because there we have all the problems in the world. Not only that, but we have all the problems that will appear in contests. I will not detaliate. Let's just say, there was a problem that had a statement, but that didn't have good tests. As such, I randomly selected a solution, outputted it, and got 93 points. Unfortunately, next time I meet the same statement, I didn't know how to solve it (because I didn't read editorial), random didn't work, and from potential Vila in Dubai I arrived at Caruta cu Cai (I swear to god I had the same solution as theirs). Obviously, this was the fault of the scientific committee that didn't tell me the solution after contest. I should've payed own interest in finding it. Stupid.

Nuvele fantastice

La țigănci

--de Mircea Eliade, tibinyte (he wanted on writers list)

Nuvela este specia literară epică cu acțiune mai complicată decât a schiței, cu un singur fir narativ, cu un conflict puternic prin care se reliefează caracterul personajelor.

Nuvela "La țigănci" se încadrează în fantasticul literar prezentând camuflarea sacrului în profan, limita dintre real și ireal fiind pe alocuri insesizabilă. Adrian Marino consideră că la nivel textual se regăsesc patru tipuri de rupturi:

  1. Ruperea în ordinea realitățîi-- când irealul intempestiv în cotidian, ale cărui mărci sunt: cifra trei (3), monologul incoerent al protagonistului "Ești un om norocos, Gavrilescule" și bordeiul că spațialitate fantastică.

  2. Ruperea în ordinea rațiunii-- când eroul intră în bordei, cere apă și i se oferă cafea fierbinte.

  3. Ruperea în ordinea semnificației-- personajul nu realizează că

    • Baba este în postura de Cerber, paznic al Hadesului, primind taxa pentru accesul la "lumea de dincolo"
    • Cele trei (3) fete simbolizează cele trei ursitoare, sau parcere, patroane ale destinului uman
    • Birjarul este luntrasul Caron, ce poartă sufletele în dimensiunea cealaltă
    • Bordeiul este spațiul pe care se desfășoară moartea inițiatică ce amintește de ritualul basmic din Harap-Alb
  4. Ruperea în ordinea temporalitățîi-- aplicată în momentul în care Gavrilescu pierde controlul timpului obiectiv spatializat, iar cele trei ore de "durata pură" din bordei devin doisprezece ani în concretenta lumii. Moartea inițiatică nu are efect transfigurator la nivel de fizicalitate, ci ii propune un alt contur de personalitate, sensul real al acestei inițieri fiind racordarea ființei La Marele Suflet Universal sau reintegrarea În Ființă Universală în explicație Blagiană

Perspectiva narativă focalizare zero, viziune din spate ("par derriere"), în persoană a treia.

Watch Hunter x Hunter

Hunter x Hunter is one of the best ways to lose good RMI medal (It was proven by some other CPers and I won't explain why here, feel free to consider the proof as an exercise for the reader). If you don't watch it, you may disregard it, but if you do, it's a sign from god. But maybe not the good one, since last time you had the same sign from god you got 0.86 points that day, dumbass.

Full text and comments »

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

By valeriu, history, 2 years ago, In English

Hello, Codeforces! Or, as we like to say in Romania: Noi nu spunem asa ceva, Codeforces!

We are proud to finally invite you to participate in Codeforces Round #804, which will start on Monday, July 4th, 2022, 14:35 UTC You will be given 5 problems and 2 hours to solve them. We greatly recommend to read all the problems, statements are very short and straight to the point.

In this round, the theme is not Independance Day related. I know, maybe we should've made the theme "Freedom", but we are not Americans and the puns within the problems were already written.

Joining me on the problem setting panel are:

Also, we would like to thank:

Here is the scoring distribution: $$$500 - 1000 - 1500 - 1750 - 2500$$$.

Good luck & have fun & the third part!

UPD1: Editorial is up!

UPD2: Winners!

Div 2:

Div 1:

Full text and comments »

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

By valeriu, 3 years ago, In English

Hello Codeforces!

We would like to invite you to the first (and possibly only) round of Infoleague Spring 2022, the contest starting on Wednesday, March 30th from 12:30 GMT+3. The problems in this round have been prepared to train high school students for the upcoming Romanian National Olympiad in Informatics (ONI).

The registration period for this contest starts from 6:30 GMT+3 on Wednesday, March 30th.

This contest has two divisions, Div 1 and Div 2. The Div 2 contest intends to mimic an ONI problemset for 9th and 10th graders, while Div 1 is mainly focused towards challenging 11th and 12th graders.

Contest links: Div1, Div2

Contest duration:

  • Div 1: 4 hours

  • Div 2: 4 hours

Scoring distribution (for both divisions): 100-100-100

The scoring system is IOI-esque, with full feedback and subtasks. All problem statements will be available in both English and Romanian.

Round authors: Gheal, tibinyte, valeriu

Tester: andrei_boaca (orz)

Upd 1: The round is over! Congratulations to the winners!

Div1:

  1. Pyqe and rama_pang tied with 300 points
  2. yz_ with 250 points
  3. Kira_1234 with 210 points

Div2:

  1. Doru and Kira_1234 tied with 300 points
  2. codrincrismariu and Ciornei_Stefan tied with 270 points
  3. robertoeugenio, alexkrunker and sheldonn tied with 220 points

The editorial has also been posted here.

Full text and comments »

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

By valeriu, 3 years ago, In English

Recently, I attempted a problem. It doesn't matter which. A portion of problem could've been easily solved using Maximum Bipartite Matching. I, however, disregarded the portion of the statement implying it could've been solved with this algorithm for some time, and had found myself trying to solve the following problem (using flows, which turned out to be underwhelmingly difficult):

Given a graph $$$G = (V = (L, R), E)$$$, then find a maximal set of edges such that each element from $$$R$$$ has at least an incident edge and each element from $$$L$$$ has exactly one incident edge.

Is this problem solvable in any way? If yes, how, if no, why?

Full text and comments »

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

By valeriu, 3 years ago, In English

Hello Codeforces!

We would like to invite you to the first official round of Infoleague Winter 2022, starting Saturday, January 8th at 14:00 GMT.

This contest will have 2 divisions, each containing 3 problems, which are not necessarily sorted in increasing order of difficulty. Div 2 is recommended for low-Experts and below (i.e. <1700), while Div 1 is recommended mainly for high experts, CMs and Masters.

Contest links Div1, Div2

Contest duration:

  • Div 1: 5 hours

  • Div 2: 3 hours

Scoring distribution (for both divisions): 100-100-100

The scoring system is IOI-esque, with full feedback. All problem statements will be available in English.

Problemsetters: Gheal, tibinyte, valeriu

Testers: andrei_boaca, IacobTudor, RaresFelix

Upd 1: The Div. 2 round is over! Conngratulations to the winners!

  1. codrincrismariu with 224 points
  2. Kripton2005 with 198 points
  3. alexkrunker with 133 points
  4. sheldonn and amcbn with 120 points
  5. Frappuccino, shabh_m3y, YMSeah and bugdone with 100 points

The Div. 2 editorial can also be found here!

Upd 2: The Div. 1 round is over! Congratulations to everyone who participated! The editorial can be found here.

Full text and comments »

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

By valeriu, 3 years ago, In English

103449A — Mountains

Author: Gheal

Solution
Code

103449B — Antigo

Author: valeriu

Solution
Code

103449C — Find Set

Author: Hidden for their safety

Solution
Code

103449D — Updating Inversions

Author: Gheal

Solution
Code 1 (SQRT decomposition)
Code 2 (Fenwick + Bitwise Trie)

103449E — Rubik String

Author: Gheal

Solution
Code 1 (DP)
Code 2 (Greedy)

103449F — àPaPdnarG

Author: tibinyte

Solution
Code

103449G — Xor Plains

Author: Gheal

Solution
Code

103449H — Autumn

Author: valeriu

Solution
Code
damn it!

Full text and comments »

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

By valeriu, history, 3 years ago, In English

Hello,

I would like to put GIFs in statements (in polygon), but attaching the GIF directly (and then inserting it like a picture) doesn't do the job. Does anybody know how to do this? please don't downvote me, I'm a very boomer

Full text and comments »

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

By valeriu, history, 3 years ago, In English

103423A - Bordered Subarrays

Idea and Solution: Gheal

Solution

103423B - Vacuum Cleaner

Idea and Solution: valeriu

Solution
Author's Note

103423C - Birthday Nim

Idea: Gheal

Solution: tibinyte and Gheal

Solution

Full text and comments »

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

By valeriu, history, 3 years ago, In English

103422A - MLCS

Problem author : Gheal

Solution

103422B - Gorbachev Sort

Problem author : valeriu

Hint 1
Hint 2
Solution

103422C - Charity

Problem authors : tibinyte + Gheal

Solution

Thanks for participating in this round ! Also , we would love if you could share your thoughts about this round ( how were the problems , what could be improved in the future etc )

Full text and comments »

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

By valeriu, 3 years ago, In English

Hello,

Not for long, I have been using polygon to manage problem creation (so those could be subsequently be posted in a contest of some kind), and while creating a problem, I thought the following dynamic could be interesting to be implemented: The user can, in the beginning of the program, mention the checker that it would either want to print the queries in the problem in an offline manner or an online manner (i.e. the online method could be implemented via an interactive checker of some kind, while the offline method could work normally). But as I am a beginner with the polygon system, I do not know if there could be some way of ''internally'' (i.e. while the contestant's code is being checked) to change the type of the problem to interactive/normal. Is this possible or is it only science fiction?

I do acknowledge the fact that this could be implemented all in an interactive checker, but I do not know how to modify one to accept both types of implementations (offline/ online)

Thanks in advance (hopefully not for downvotes?)

Full text and comments »

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

By valeriu, history, 4 years ago, In English

What are the steps one have to go through for creating a successful contest? How do you propose problems, and what happens when they get rejected? when can they get rejected, and when is the round considered to be ready?

Thank you a lot in avance.

Full text and comments »

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

By valeriu, history, 4 years ago, In English

How could one be selected to test problems in a codeforces contest? And what would be the requirements to do so?

Full text and comments »

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