hocky's blog

TLX Special Open Contest — April Fools 2024!
By hocky, 9 months ago, In English 
/***
 *      _____   ___    ___    ___           ___     __    ___   _ _                          
 *     |_   _| / __|  / _ \  / __|         |_  )   /  \  |_  ) | | |  O O o                  
 *       | |   \__ \ | (_) || (__           / /   | () |  / /  |_  _|      o                 
 *      _|_|_  |___/  \___/  \___|  _____  /___|  _\__/  /___|  _|_|_ [O]__ZT                
 *    _|"""""_|"""""_|"""""_|"""""_|     _|"""""_|"""""_|"""""_|"""""_|======}               
 *    "`-0-0-"`-0-0-"`-0-0-"`-0-0-"`-0-0-"`-0-0-"`-0-0-"`-0-0-"`-0-0-"`000--o\.              
 *               ___     ___   ___    ___    _              ___   ___    ___    _      ___   
 *        o O O /   \   | _ \ | _ \  |_ _|  | |            | __| / _ \  / _ \  | |    / __|  
 *       o      | - |   |  _/ |   /   | |   | |__          | _| | (_) || (_) | | |__  \__ \  
 *      TS__[O] |_|_|  _|_|_  |_|_\  |___|  |____| _____  _|_|_  \___/  \___/  |____| |___/  
 *     {======_|"""""_| """ _|"""""_|"""""_|"""""_|     _| """ _|"""""_|"""""_|"""""_|"""""| 
 *    ./o--000"`-0-0-"`-0-0-"`-0-0-"`-0-0-"`-0-0-"`-0-0-"`-0-0-"`-0-0-"`-0-0-"`-0-0-"`-0-0-' 
 */

🦏👯️🔬🔢🤣🃏🎮🩸🍳🟢🔑💌

Hello everyone!

We're very happy to announce and invite you to TLX Special Open Contest (TSOC) — April Fools 2024!

Having a break from the past 3 years, and here I am, a sudden comeback on the April Fools' contest 🤡

We strongly encourage you to read all the problems!

Go Go Go Go

P.S: We would like to thank fushar a lot lot lot as an organizer who worked hard to prepare the TLX platform <3~!

UPD: Contest is over!

Congratulations to the top 5:

  1. SanguineChameleon

  2. CDuongg

  3. thenymphsofdelphi

  4. Morphymorphymorphy

  5. Berted

Congratulations to our first solvers:

Problems I like:

  • A:

  • B:

  • C:

  • D:

  • E:

  • F:

  • G:

  • H:

  • I:

  • J:

  • K:

  • L:

Problems I hate the most:

Editorial is available in the contest!

Thank you for participating!

You can now upsolve the problems here.

Full text and comments »

Tags tlx
  • Vote: I like it
  • +78
  • Vote: I do not like it

[CF Extension] How Not To Feel Bad About Yourself
By hocky, history, 13 months ago, In English

I've made some tampermonkey extensions, I will make it available in Google Chrome Extension store if I'm not busy and lazy.
The extensions are for those whose souls are as weak as mine. ⸜(｡˃ ᵕ ˂ )⸝♡

Simple UI

The first one is the simple UI if you want to just read or print CF problem statements in compact mode.

Screenshots

What it does:

  • Remove the problem letters (to avoid bias)
  • Make it clean and printable
  • Auto display spoilers (for printing's sake)
CF Simple UI

Anti Ratist

The second one is an anti-ratist extensions which would hide anyone's rating and number of solvers in a contest page. ପ(๑•ᴗ•๑)ଓ ♡

Screenshots
CF Anti Ratist

P.S: Just so you know the anti ratist extension is useless because everytime I open cf from my phone I will end up seeing my rating again.

Full text and comments »

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

Tier List
By hocky, history, 13 months ago, In English

Rank ur uwn tier list here

Please let me know in the comments what other topics should I add/remove (UωU) ૮ ˶ᵔ ᵕ ᵔ˶ ა

˚˖𓍢ִ໋🌷͙֒✧˚.🎀༘⋆

Change logs:

  • Add the first 46 topics

Full text and comments »

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

[Tuωutoωoial] Convex Polygon Counting
By hocky, history, 14 months ago, In English

Hi everyone, today I'm back with another blog that sadly, nor won't have to spend 45 minutes GPT-ing my anime and kaomoji propaganda to read it. ૮₍ ˃ ⤙ ˂ ₎ა 👅

Not sure whether there is another blog explaining this technique in a "so many visualizations" manner.

There are so many paper about these problems in particular. So please put your opinions and any other similar techniques you know in the comment section 📃📃📜. I think this is a "very known technique" for GMs, so you guys might want to skip reading this blog.

I also do expect this is a "very common geometry problem" in China or something but, here is my attempt on explaining it.

Here is a cute quote by me oωo

When it comes to polygon problems, sometimes you have to see 🐦 🎀 𝓈𝑒𝑔𝓂𝑒𝓃𝓉 🎀 🐦 instead of points ✨.

This blog is about polygon counting and Dynamic Programming techniques. Truly, if you think about it there is only 1 method to do this, that is DP. But on how to count it, you got to use some polar sweeping and polar inclusion exclusion. 🔴🔴

Now, I'll talk about 4 problems which more or less uses the same idea.

Triangles

Basically we have to count how many triangles that doesnt have any set of points inside of that triangle. 📐

If you take the consideration of the time limit, you can actually connect some sense that we can brute force and fix for each pair of $$$2$$$ points, and check whether a certain triangle doesn't have any other point inside. ✌️

Okay, now let's do an attempt on that.

Consider the pair of point $$$A$$$ and $$$B$$$: Your basic intuition must tell you that every point below the vector $$$\vec{AB}$$$ can be ignored.

image-20231018174036052

You obtain these kinds of diagram, but you have no idea on how to count the blue points inside the triangle $$$ABO$$$, you can only get the amount of points on the left of $$$AO$$$, and $$$BO$$$ but you cannot separate the blue points 💙 and red ❤️ points above and below $$$O$$$.

image-20231018174036052

Yes, you can sort the points by order of orientation from $$$\vec{AB}$$$ and $$$\vec{BA}$$$, and you can count how many points $$$(x', y')$$$ is strictly less than $$$(x, y)$$$ for an observed point. But let's assume this method doesn't exist 😠

Okay now, this is where we approach the problem in a quite irregular way.

Without loss of generality, let's assume $$$O$$$ we're looking for are always in between $$$A$$$ and $$$B$$$ in terms of cartesian space. It's true that $$$A.x \leq O.x \leq B.x$$$.

Now here's the nasty part, instead of looking for the points that is on the right for $$$OB$$$ entirely, we limit the points to only the ones that have $$$O.x \leq C.x \leq B.x$$$, and the right of $$$\vec{OB}$$$.

image-20231018175019922

BOOM, now no double counting, the amount of points inside the triangle $$$AOB$$$ is now just $$$\text{count}(A, B) - \text{count}(A, O) - \text{count}(O, B)$$$. This count function, we can precompute! 💥💥🤯🤯🤯

Nice, because we're bruteforcing all 3 points, we know which all 3 points that are involved, so finding the largest one shouldn't be a problem for us. ૮ • ﻌ — ა

image-20231018175915649

One thing to pay attention to is when $$$O$$$ is in the right of $$$\vec{AB}$$$, than the point count can be negative, if you use the same formula. so if it's a counting problem you might want to take the absolute value instead.

Solution for D. Triangles — 13D

code

Extending it to Convex K Gon

Lol, you're right, we're basically doing inclusion exclusion!

Consider the two points $$$A$$$ $$$B$$$ again, now let's separate those available points on top of $$$A$$$ and on the bottom of $$$B$$$, we're now looking for a sequence of point on top of $$$AB$$$ and bottom of $$$AB$$$, now let's think of building the convex hull in monotone chain manner.

The dumb idea is we do sum kind of subset sum, we want to match the upper hull first. If we know the $$$\text{count}(A, B)$$$ = finalSum, we can iterate the existing state, the state that we store is: dp[x][y][sum], inside we store how many combinations that leads to this, where $$$x$$$ is the second last point of our hull, and $$$y$$$ is the last point of our hull, and sum is the current total sum of points. (*ᴗ͈ˬᴗ͈)ꕤ*.ﾟ

so when we're checking the new point $$$z$$$, make sure that point $$$x, y, z$$$ is a valid hull, $$$p[x].\text{cross}(p[y], p[z]) > 0$$$. Our answer is in dp[x][B][finalSum] for arbitrary x.

Now, to combine, just combine with the bottom hull as well. The time complexity is $$$O(N^6)$$$ lol. Too hard im not even sure whether this is correct, but let's just talk about a better approach later, first, let's look at some other problems, maybe we can find a better approach! (Spoiler: we do) (๑･㉨･๑)

image-20231018182356806

Gadget Construction

Read it first:

G. Gadget Construction — 104619G

😱😱😱😱 Oh, shoot it's a convex hull problem and we need to count!, more over not all edges can be merged, and more over we have to count how many points inside them convex hull, this is basically the previous problem but harder. We're dead. ૮ ˙Ⱉ˙ ა rawr!    

Yes, we are.

Constructing the Convex Polygon

First and foremost, let's just ignore the points inside the convex hull, and assume we just want to count how many existing convex hulls are there first.

Okay I'll just give you on how to compute it, let's make a two dynamic programming, one to compute an upper hull and one to compute the lower hull. (◍´ಲ`◍) 🐢

We will create a memoization here, lets define $$$memo[0][a][b]$$$ as the upper hull that starts at $$$a$$$ and ends at $$$b$$$.

Let's define another one here $$$memo[1][a][b]$$$ is the lower hull that starts at $$$a$$$ and ends at $$$b$$$. Here the upper hull has the property where $$$a \leq b$$$ and the lower hull has the property where $$$a \geq b$$$, so in the end our answer is stored at $$$memo[0][a][b] \times memo[1][b][a]$$$ for all pair $$$(1 \leq a \leq b\leq n)$$$.

image-20231019144146812

If you see here, a valid upper hull all of them have a valid property in common, that is, for each line, $$$XYZ$$$ in a convex hull, $$$X.\text{cross}(Y, Z) < 0$$$, meaning the line is on the right side of the other. We would like to construct the convex hull from the back, that is $$$B = C[0] \rightarrow C[1] \rightarrow \dots \rightarrow C[K] = A$$$. for $$$K \ge 0$$$. ଘ(੭ˊᵕˋ)੭

Now the transition is the tricky part. Let's say we have two points $$$AB$$$ that is a valid convex hull, how to find all points $$$C$$$ that $$$BC$$$ is a valid convex hull, and $$$ABC$$$ too? 🤔🤔🤔

Let's make the problem simpler, consider $$$memo[0][B][C]$$$ now contains the number of valid convex hull from $$$B$$$ to $$$C$$$, now, if we were to add a single point $$$A$$$. (灬╹ω╹灬)

image-20231019183948089

Okay now consider this, what we want is, we count:

  • $$$memo[0][B][C] = {[B, C]}$$$
  • $$$memo[0][A][B] = {[A, B]}$$$
  • $$$memo[0][A][D] = {[A, D]}$$$
  • $$$memo[0][D][C] = {[D, C], [D, B, C]}$$$
  • $$$memo[0][A][C] = {[A, C], [A, B, C]}$$$
    • We don't want to count the $$$[A, D, C]$$$ because it's not a valid convex hull, yet, we still don't want to miss the convex hull $$$[A, D]$$$. ૮ ˙Ⱉ˙ ა rawr!    

So, let's sum it up, we will now create lines for every pair of points $$$X, Y$$$, where $$$X.x < Y.x$$$ or ($$$X.x = Y.x$$$ and $$$X.y < Y.y$$$), and lets consider the vertical line we consider are the ones that is going up, so we can just sort the points as usual and only pair up the ones with $$$X < Y$$$.

image-20231019183044685

In short, our upper hull (black lines) will only contains the line which have the angle $$$(-\frac{\pi}{2}, \frac{\pi}{2}]$$$. Observe that WLOG, a convex hull containing two vertical lines (assuming no collinear points) will have each part contained in different part of the hull, which we can obtain if we can solve the subproblem of creating the upper hull.

When talking about angle, let's use atan2's terms and quadrants (,,◕ ⋏ ◕,,)

image-20231019183942805

Back to this one, now after we have all the appropriate lines, we would know that when extending a line $$$AB$$$, basically, we would like to know how many valid $$$memo[0][B][C]$$$, and when extending a line $$$AD$$$, we would like to skip $$$memo[0][D][C]$$$. Let's make another case to better sort this out.

image-20231019184913684

Here, when relaxing $$$AB$$$, I want to count $$$ABC$$$, $$$ABF$$$, $$$ABD$$$, $$$ABDE$$$, $$$\dots$$$ but not $$$ABCE$$$. What differentiate this $$$ABCE$$$ from the other? 🐢

Think about $$$BC$$$ which connects $$$BCE$$$. 🤔🤔🤔

The answer

Here's a cat image before you scroll further and think about how to handle the counting case above.

Now, let's sort out the gradients. Based on the above observation, a convex hull relaxation is valid only if the gradient which comes from the upper hull comes later. So when relaxing the line $$$BC$$$, it can only saw the degenerate convex hull $$$C$$$ and not $$$CE$$$ (which comes later when relaxing the line $$$CE$$$). (･◡ु‹ )

So our relaxation become more or less like:

sort(all(slopes), [&](const Slope & a, const Slope & b) {
  return a.fi.cross(b.fi) > 0;
});
// Give the degen convex hull containing only 1 vertex a value
rep(i,0,n) memo[0][i][i] = 1;
trav(slope, slopes) {
  int i = slope.se.fi, j = slope.se.se;
  for (int k = 0; k < n; k++) {
    memo[0][i][k] += (memo[0][i][k] + memo[0][j][k]);
  }
}

Boom, now you finished counting all upper hull starting at a point $$$A$$$ and ends at $$$B$$$, which will be stored in $$$memo[0][A][B]$$$. 💥💥🤯🤯🤯

The code basically relaxes the line $$$i$$$, $$$j$$$, and for each of the endpoints $$$k$$$, we will try to append this $$$i,j$$$ line to the existing convex hull $$$j, k$$$, which we store at convex hull $$$i, k$$$.

Basically that's it, now to count the lower hull, just do the same thing, except we swap the slope.

trav(slope, slopes) {
  int i = slope.se.fi, j = slope.se.se;
  swap(i, j);
  for (int k = 0; k < n; k++) {
    memo[1][i][k] += (memo[1][i][k] + memo[1][j][k]);
  }
}

Now, multiplying all parts $$$memo[0][i][j] \times memo[1][j][i]$$$ will do it. Lastly, don't forget that we have to make sure that we don't double count those convex hull with vertex $$$\le 2$$$. ( つ•̀ω•́)つ

Back to the top one. Now back to gadget construction, we have 2 more subproblems to solve 😭😭

Alternating Cogs

Amazingly, you can simply sort out which lines we can relax!, when pushing the slopes, you can ignore the lines which connects two same color of cogs, if you pay attention, only valid hull are considered in this case.

We can add other requirements depending on what the problem wants.

Even if we see here, the line $$$AE$$$ is not even connected by a line and will be never relaxed, so all convex hull accumulated in our dynamic programming wont take this into account.

But $$$memo[0][A][E]$$$ will still have a value, which consists of $$$[ABE, ADE, ABCDE]$$$ and the lower hull counter part is $$$memo[1][E][A] = [EFA]$$$, if this is empty, no full hull will be counted, just like how $$$BE$$$. Amazing. 😱😱😱😱

image-20231019191414030

Cogs Triangle Counting

Here comes the last part. We were said that we have to count how many cogs are on each hull, and do a $$$2^c$$$ of when a hull contains $$$c$$$ cogs. Fortunately, this function can easily be attached to our $$$dp$$$. Take the above case and let's count.

image-20231019192539694

Thanks to our convex polygon triangulation property, each pair of non adjacent point is a diagonal, which means we can separate the total number of cogs inside a polygon by counting each of the triangle appended to it ૮₍˶ •. • ⑅₎ა ♡. so:

  • when relaxing $$$CD$$$ to $$$DE$$$'s convex hull, we can multiply $$$2^c$$$ where $$$c$$$ is the number of cogs inside the triangle $$$C[\dots]E$$$.
  • when we're relaxing $$$BC$$$, we multiply $$$2^{BCD}$$$ to get the $$$B[\dots]D$$$ one, and $$$2^{BCE}$$$ to get the $$$BC[\dots]E$$$ one.

Why is this true? ୧ ‧₊˚ 🍓 ⋅ ☆

image-20231019194026320

  • Let's say has $$$CEB$$$ has $$$2$$$ cogs inside, $$$CDB$$$ has $$$4$$$ cogs inside, the $$$memo[0][C][B]$$$ should be $$$CEB + CDB + CB = 2^2 + 2^4 + 2^0 = 21$$$.
  • Now, when relaxing $$$AC$$$, which have $$$3$$$ cogs inside, those values will all multiply by $$$2^3$$$. Thus, $$$memo[0][A][B] = ACDB + ACEB + ACB = 2^3(2^2 + 2^4 + 2^0)$$$.
  • Clear.

Now this one subproblem on counting how many points inside the triangle is just the first problem.

create the same exact DP with the first problem, but the blue set is the red set.

image-20231019205054934

again, to get the number of points in $$$i, j, k$$$, is $$$count(i, j) + count(j, k) - count(i, k)$$$. No three points are collinear mean there is no point between $$$i$$$ and $$$k$$$, so safely be ignored.

image-20231019205147878

Now this one another case is $$$count(i, k) - count(i, j) - count(j, k) - 1$$$, cause the point $$$j$$$ is counted by $$$count(i, k)$$$. 🐢

Spoiler

Back to Extending it to Convex K Gon

The $$$memo[i][j]$$$ apparently is not enough, we can add another state $$$memo[i][j][k]$$$ where $$$k$$$ is the number of points being used. Now the counting the number of convex $$$K$$$ gon is reduced to $$$O(kN^3)$$$ hooray. To check the maximum area we can check the triangle count and only relax when the triangle count is 0. Even, this dp can be extended to count the convex polygon having exactly $$$M$$$ points inside.

I think there is a known faster solution to this problem. Explained in this recent paper https://www.sciencedirect.com/science/article/pii/S0020019021001368#fg0020. Just read it. I haven't.

Security at Museums

K. Security at Museums — 104160K

We're not done yet, unfortunately. ₊˚ʚ ᗢ₊˚✧ ﾟ.

We're back at the last one. Security at museums. Please read it.

Okay, let's define $$$isBad(i, j)$$$ is true if those edge cannot see each other. I'll make another blog on how to compute this and its variation, but for now, assume there exist a function that can compute that within $$$O(N^3)$$$. But that's not the main suffering of this problem, which is the polygon counting.

Okay, can we apply the same technique like gadget construction? OK. AC.

EOF.

No.

It has collinear points. We're doomed. It's really hard to handle those cases. Just try for yourself if you don't believe me. 😭😭

Our previous DP can't survive. It has so many weaknesses when it comes to double counting the upper and lower hull. 🦈

We have to add some more observation. 🐢

image-20231020021133972

So if the go (represented in blue line) will count those 4 points, the back DP shall be computed in a reversed order. So now, we have to insert our line in a better order, that is to insert it back first, if those points are labeled $$$A$$$, $$$B$$$, $$$C$$$, and $$$D$$$ consecutively, then we will do: CD, BD, AD, BC, AC, AB

or any order that forms a DAG will do. This also ok. I'll use this one.

image-20231020022136996

AD, BD, CD, BC, AC, AB

The reversed one is the same but reversed.

  for (int i = n - 1; i >= 0; i--) rep(j, i + 1, n) {
    if (!isBad[i][j]) {
      slopes.pb({isi[j] - isi[i], {i, j}});
    }
  }

Double Counting Case

Now the above case will be counted so many times, for example when we fix point $$$AD$$$, there is $$$2^2$$$ ways to go, (using $$$B$$$ or $$$C$$$) and $$$2^2$$$ ways to go home too. In total there is a $$$2^4$$$ hull counted, while there only should be $$$2^2$$$ ways.

We can handle that separately. So when processing i, j, we gotta check if there is a point k in between which encompasses this case. (Assume the point array is sorted by x and y) 🦈

  for (int i = n - 1; i >= 0; i--) rep(j, i + 1, n) {
    if (!isBad[i][j]) {
      // remove the double counting cases
      int sameGradient = 0;
      rep(k, i + 1, j) {
        if (isi[k].cross(isi[i], isi[j]) == 0) {
          sameGradient++;
        }
      }
      ans = ans - pow2[sameGradient * 2] + pow2[sameGradient];
    }
  }

image-20231020002207482

Btw, here's the case where our Gadget Construction's code fail. If we dont handle collinear points. When it tries to compute $$$P5, P3$$$, the $$$P2, P5$$$ ignores the $$$P1$$$. 🐔

There is another implementation variation to solve this problem,

At this point of writing the previous solution, I don't even understand it, but thanks to 244mhq I'm able to understand the logic through his code.

Now instead of sorting all lines, and counting the upper hull and lower hull separately, we will consider one point as a pivot, and count how many convex polygon if we use this point as our left bottom most pivot point.

Instead of separating the process of the hull, just sort the lines, first check if it's a blue go line (its in the first or 4th quadrant), or its a red come line, which is the exact same but reversed.

Then do the dp on DAG casually (pay attention that all blue lines will computed first, then the red come line will come back to the first point)

image-20231020023334349

You can notice that basically all the lines is contained in one container slopes , the blue line will be run first, (sorted based on gradient, computing all the upper hull), then when it entered the red lines, it will return all the lower hull. The dp will be more or less like this, very short. 🐔

But the comparison of the slopes shall include some dot product calculation to make sure the DAG computed correctly. That is to check which slope is further in the same direction, 

    for (int i = 0; i < n; i++) {
        // i is the pivot
        memset(dp, 0, sizeof dp);
        dp[i] = 1;
        for (auto& it : slopes) {
            // This ignore all slopes that is on the left of the pivot
            if (it.first < i || it.second < i) continue;
            // This is the red line that comes back to the pivot
            if (it.second == i) {
                ans = sum(ans, dp[it.first]);
            }
            else {
                dp[it.second] = sum(dp[it.second], dp[it.first]);
            }
        }
    }

Messages

( . .) (. . )
( づ🍫⊂ )

Dear Problem setters, I'm sorry if I spilled a near-contest problem with similar techniques.

And dear contestants, I apologize as this blog will just give problems setters more idea on problem and open up so many more crazy geometry problems in your future ICPCs :p.

I'm planning to blog good geometry techniques I discover in the future also. So brace yourselves.

I also stole the idea by reading some of the judge's sample solution code, turns out it is quite readable (at least for me), and 244mhq which provide a really cool and short implementation for this dp. If you may you can explain the comparator for the slopes for the reader ;), especially the dot product part. 🐟 🐔

Naming

Should we name this kinds of polygon counting technique?

  • DP Go and Come
  • DP Convex Hull
  • Convex Polygon DP
  • Don't name it, it's too classic

Full text and comments »

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

Luvliest Lub Lub Dynamic Diameter and Euler Tour??
By hocky, 14 months ago, In English

ωeecently, I've encountered this pωoblem in a local contest in my coωountωy and I find this pωobωem has a ωeeeaωy cuωul tωick, i aωso found out that this has a s-s-similar idea, and the pωoblem can be fuωuωutheω be ωeduced to ✨ Dynamic Diameter ✨

https://oj.uz/problem/view/CEOI19_diameter

Pωobωem S-S-Statement (,,> ᴗ <,,)

Ur given a🌳 with $$$N$$$ n-n-nodes and $$$N - 1$$$ e-edges connecting each of the nodes. Each edge is a tuωuωuωuple $$$(u[i], v[i], c[i])$$$, connecting node $$$u[i]$$$ and $$$v[i]$$$ with weight $$$c[i]$$$ $$$(0 \leq i \leq n - 2)$$$. 🏠🏋️

You're given $$$Q$$$ quewees:

  • 1, output the RAWWRGESTTT 🦁🦁🦁🦁 diameter of the tωee, foωoωed with Tωo✌️ nodes $$$x$$$ and $$$y$$$ de-de-denoting the endpωoints of the diameterr. 🛖
  • 2 x, output the distance between $$$x$$$ and $$$y$$$, where $$$y$$$ is the node with fuwtheessst 🚩 distance from $$$x$$$, output the $$$y$$$ as well. 🏃‍♂️૮ ˶ᵔ ᵕ ᵔ˶ ა
  • 3 x v change the coωost of $$$c[x] := v$$$ . 🤑 UωU i wike incωease inωwease decωease decωease

Vocabs Voωocabs (๑>◡<๑)

I will use the word highest/higher/high ☝️☝️ to refer the node that is closeωr to the rωoot, and deepest/deeper/deep 👇👇 to refer the node that is further from the ωo.ot. 🙏

Centωoid Decomposition Solution

Buωuilding the Centωoid Tωeeeeeee 🛝🛝🛝🌳 and Getting The Quωueωഴ

Lemma 1

Diameter of a tωee is the distance between two furthest nodes in the tωee. Let's say the diameter pair is (x, y), when adding a new point u, the new diameter pair is either (x, y), (x, u) or (u, y).

Lemma 2

For each node in u, the furthest node from u is either x or y, where the diameter pair of the tωee is (x, y).

Next

UωULOG, let's root the original tωee 🌳 at $$$1$$$. Define $$$depth[x]$$$ as the distance of a node $$$x$$$ in the tωee 🌳 from the root, where $$$depth[1] = 0$$$.

You might approach this problem with centωoid decompoωosition 🕷️🕸️, we can use the p-p-property where the LCA (loωoest common ancestoωor) 🎅 of two ✌️ nodes $$$x$$$ and $$$y$$$ in the centωoid tωee, let's call it $$$lca$$$, have this pωoperty of $$$distance(x, lca) + distance(y, lca) = distance(x, y)$$$ in the real tωee 🌳 as well. 😱

To sωolve this pωoblem, for each noωode $$$u$$$ in the centωoid tωee we will keep a set called $$$bestMatch$$$, containing $$$(furthestDistance, v, x)$$$, where $$$v$$$ is the furthest distance of $$$u$$$ to any of the subtωee 🌴 of node $$$v$$$, and we will store $$$v$$$ where $$$v$$$ is the direct cheeωdωen of node $$$u$$$, and $$$x$$$ is the respectable node where $$$x$$$ to $$$u$$$ is the furthest. 📦

Let's claim this build method is true:

decompose(x):
  x = findCentroid(x);
  for (child : edge[x]):
    edge[child].erase(x);
    edge[x].erase(child);
    nextCentroid = decompose(child);
    centroidEdge[x].push(nextCentroid)
  return x;

root = decompose(1);
set bestDiameter;
set[] bestMatch;
pair[] diameterPair;

buildTree(x):
    diameterPair[x] = {x, x};
  bestDiameter[x] = 0
  for(child : centroidEdge[x])
    buildTree(child)
        // Use lemma 2, to get bestMatch or furthest node for x in the subtree of child,
        // just compare them with the diameter
        bestMatch[x] = compareBestMatch(diameterPair[child][0], diameterPair[child][1])
    // Use lemma 1, Adjust the bestDiameter value as well in this 
    diameterPair[x] = compareBestDiameter(diameterPair[x],
                                              diameterPair[child]);
  if(size(bestMatch[x]) > 1):
    diameterPair[x] = compareBestDiameter(diameterPair[x],
                                              (bestMatch[x][0], bestMatch[x][1]));
    else:
    diameterPair[x] = compareBestDiameter(diameterPair[x],
                                              (bestMatch[x][0], x));

Sadly, as for now, the distance between two nodes in a tωee can only be computed with Heavy Light Decomposition with edge update: 🥲

  • Can update edge weight 🏋️
  • Can count the distance between two nodes 🎁

Which will result this algorithm to have the time complexity $$$O(N \log^2 N)$$$.

For the implementation details and debugging 🐜🐛: Let's look at this random example. Consider this unweighted tωee (each tωee's weight is $$$1$$$). 🤔

image-20231004113212648

image-20231004113226341

Consider the centωoid decomposition of this tωee, if we see here, the node $$$2$$$ in the centωoid tωee will store: 💌

  • $$$bestMatch[2] = {(1, 1, 1), (4, 8, 10), (3, 5, 6)}$$$
    • $$$(\color{red}{1}, \color{blue}{1}, \color{green}{1})$$$ means for this child $$$\color{blue}{1}$$$, we can get the maximum distance of $$$\color{red}{1}$$$, by going to the node $$$\color{green}{1}$$$.
    • $$$(\color{red}{4}, \color{blue}{8}, \color{green}{10})$$$ means for this child $$$\color{blue}{8}$$$, we can get the maximum distance of $$$\color{red}{4}$$$, by going to the node $$$\color{green}{10}$$$.
      • This is correct because if you see in the original tωee, the distance of $$$2$$$ to $$$10$$$ is $$$4$$$.
      • Now, this is just a simple case where the tωee is unweighted, but the logic 🧠🤯 will be similar for weighted tωees, it's just when computing depth, we will increase it by the edge weight instead of just $$$1$$$. 😊

Now we will keep another set containing each node $$$u$$$ in the centωoid tωee 🎄🎄, what is the maximum diameter of the tωee that passes this $$$\boldsymbol{u}$$$, which can be done by matching the deepest and second deepest maximum distance we get from $$$bestMatch[u]$$$. 🌊🌊

Details: don't forget to coωonsider the deepest one only in case when the size or cardinality of $$$bestMatch[u]$$$ is $$$1$$$.

Now, we can store it in the global set $$$bestDiameter = {(diameter(1), 1), (diameter(2), 2), dots (diameter(u), u)}$$$, for every node $$$u$$$ ($$$1 \leq u \leq n$$$). Where diameter is the best diameter that goes through $$$u$$$ in the centωoid tωee. 👨‍💻👨‍💻

the answer is just the best diameter, to store the two best pairs, just create another array that maps the current $$$u$$$ to its best pair. 🧑‍🤝‍🧑

The same idea could be done to $$$bestMatch[u]$$$ too, we can just store the pairs $$$(furthestDistance, v)$$$ without the $$$x$$$ (previously was $$$(furthestDistance, v, x)$$$).

Updating

Centωoid tωee have this property where the depth of the tωee is $$$O(\log (N))$$$. Meaning when updating something, one can casually crawl up to the root within $$$\log N$$$ steps. 🪜

Updating can be tricky, when updating the edge tuple $$$(u, v, c)$$$, 🤔😔

Let's say we want to update the tuple to $$$(8, 11, 3)$$$, or change the weight coωonnecting $$$8$$$ and $$$11$$$ from $$$1$$$ to $$$3$$$. 🫦

In the centωoid tωee, $$$8$$$ and $$$11$$$ by the property of centωoid tωee must have this ancestor-cheeωdωen relationship. 👶👨‍👩‍👧‍👦

Coωonsider both of them is still in the same tωee when decomposing, if both of them is not picked as the centωoid yet, they both will still stay together. If one of them is picked, for example $$$u$$$ is picked (the other we can coωonsider as $$$v$$$) then the tωee will decompose into subtωees, which one of them coωontains $$$v$$$. 🫢

So here, we can just pick whichever is the shallowest in terms of depth in the centωoid tωee. In this case, 8 is higher in the centωoid tωee. We will recompute every node from $$$8$$$ to the root by using the same build method, instead of just storing the max, indeed we have to store all data to recompare at the end. ⚖️

The edge 8 and 11 wouldn't be involved in the subtωee of child of 8 coωontaining 11, so recomputation is not needed.

Euler Tour and Segment Tωee Solution

Building The Segment Ttωee

Let's coωonsider the same t-t-tωee used in the centωoid decomposition, let's make this euler tour decomposition based on that tωee 🚞🚞

12
1 2
2 3
3 4
3 5
5 6 
5 7
2 12
12 11
11 8
8 9
8 10

image-20231004113518738

order[1] = (1, 23)
order[2] = (2, 22)
order[3] = (3, 11)
order[4] = (4, 4)
order[5] = (6, 10)
order[6] = (7, 7)
order[7] = (9, 9)
order[8] = (15, 19)
order[9] = (16, 16)
order[10] = (18, 18)
order[11] = (14, 20)
order[12] = (13, 21)

Let's talk about some property this Euler tour have.

image-20231004114824496

  • First we can use this euler tour to do LCA, to get the lca of two node $$$x$$$ and $$$y$$$, simply get the minimum depth from order[x].first and order[y].first, oωbserve that the order[x].first is the first occurence of that certain node in the, tωee, ໒꒰ྀིっ˕ -｡꒱ྀི১ traversing to both will always pass the LCA, also oωbserve that the euler tour event length will be $$$2N - 1$$$. See for that certain event length. 😎🥸

Okay now, let's oωbserve on how to compute the diameter on unweighted tωee. Let's store 5 values on the segment tωee over the event node. Each event represent a single node in the tωee. 🎋

maxDepth, minDepth, prefixDeep, suffixDeep, diameter

  • maxDepth is the maximum depth for that interval. 😡

    • This essentially means the deepest node for this current event interval.
    • Initialize this with $$$Depth[Events[Index]]$$$.

  • minDepth is the minimum depth for that interval. 😭

    • This essentially mean the highest node in this current height interval.
    • Oωbserve that the node for this minDepth is always the root for this current interval
    • image-20231004122149867
    • For example, when querying the tosca interval, if $$$x$$$ is inside them, then $$$x$$$'s depth will always be denoted as minDepth for that interval
    • Initialize this with $$$Depth[Events[Index]]$$$.
  • prefixDeep is the best ready to sum distance, it coωontains the best $$$x$$$ for the current interval, where $$$depth[x] - 2 \times depth[lca]$$$ is the largest, it also true that $$$x \leq lca$$$. 👈
    • Initialize this with $$$depth[events[index]] - 2 \times depth[events[index]]$$$.

  • suffixDeep is the ready to sum distance, it coωontains the best $$$y$$$ for the current interval where $$$depth[y] - 2 \times depth[lca]$$$ is the largest, it's also true that $$$lca \leq y$$$. 👉

    • Initialize this with $$$depth[events[index]] - 2 \times depth[events[index]]$$$.

What is ready to sum distance? 🤔

  • Denote $$$[Lstart, Lend]$$$ as the first interval and $$$[Rstart, Rend]$$$ as the second interval.
  • If you pay attention to the formula, diameter of an interval is two longest pair in that interval, What happens if two interval merges? There are two possibilities:
    • The diameter are grabbed entirely from either the first interval or second interval
    • There is a certain node in the first interval, There is also a node in the second interval, and when both the interval merged, it will become the new diameter of the interval. This will only happen, if? ૮ ˶´ ᵕˋ ˶ა
      • Let's say the node in the first interval is $$$x$$$ ($$$Lstart \leq x \leq Lend$$$), and the second interval is $$$y$$$ ($$$Rstart \leq x \leq Rend$$$). This node will go to each other passing their LCA, and the LCA will always be the highest node between $$$[x, Lend]$$$ or is in $$$[Rstart, y]$$$.
      • Either way, when we're computing the merged diameter, we will consider the $$$depth[x] + depth[y] - 2 \times depth[lca]$$$. Meaning, if we were to match the deepest $$$depth[y]$$$, we shall prepare $$$depth[x] - 2 \times depth[lca]$$$, the same suffice if we were to match the deepest $$$depth[x]$$$ we shall prepare $$$depth[y] - 2 \times depth[lca]$$$.

  • diameter is just the diameter of this current interval's euler jouωuney tωee.

    • Diameter is basically $$$depth[a] + depth[c] - 2 \times depth[b]$$$, where $$$b$$$ is the lca of $$$a$$$ and $$$c$$$, but don't worry, we can just ignore this $$$b$$$, because for any arbitrary $$$a$$$ and $$$c$$$ in that interval, the minimum

Example 1

This seems counterintuitive and very weird. But let's take a look of several cases

image-case-1 image-case-2

10 12 Computing: 
Maxdepth: (3, 5)
Mindepth: (1, 2)
prefixDeep: (-1, 2)
suffixDeep: (1, 5) (This basically prepares the pair (depth[5] - 2 * depth[2]))
diameter (2, (5, 2))

13 14 Computing: 
Maxdepth: (3, 11) (Will try to match this with the suffixDeep of [10, 12] (depth[11] will be paired with (depth[5] - 2 * depth[2])))
Mindepth: (2, 12)
prefixDeep: (-1, 11) (Prefix is depth[11] - 2 * depth[12])
suffixDeep: (-2, 12) (Suffix also have depth[12] - 2 * depth[12]). Why not depth[12] - 2 * depth[11]? because suffix should be left depth max - 2 * right depth min 
diameter (1, (11, 12))

10 14 Computing: 
Maxdepth: (3, 11)
Mindepth: (1, 2)
prefixDeep: (1, 11)
suffixDeep: (1, 5)
diameter (4, (11, 5)) (this is the result)

Example 2

image-20231004185107951

image-20231004190526046

3 5 Computing: 
Maxdepth: (2, 3)
Mindepth: (0, 1)
prefixDeep: (0, 1)
suffixDeep: (2, 3) (Check this one out, this is depth[3] - 2 * depth[0])
diameter (2, (3, 1))

// Case [3, 6] is the same
3 6 Computing: 
Maxdepth: (2, 3)
Mindepth: (0, 1)
prefixDeep: (1, 4)
suffixDeep: (2, 3)
diameter (3, (3, 4))

// [7, 8] is obvious, if you think, should be using 5 -> 4 as the suffix
7 8 Computing: 
Maxdepth: (2, 5)
Mindepth: (1, 4)
prefixDeep: (-1, 4)
suffixDeep: (0, 5)
diameter (1, (5, 4))

// Now what happens when we merge [3, 6] and [7, 8]
3 8 Computing: 
Maxdepth: (2, 5)
Mindepth: (0, 1)
prefixDeep: (2, 5)
suffixDeep: (2, 3) (Still using 3 -> 2 -> 1, because depth[3] - 2 * depth[1] > depth[5] - 2 * depth[4]).
diameter (4, (3, 5))

image-20231004190703232

Smart, instead of extending the diameter with $$$5 \rightarrow 4, ...,$$$ it's actually better if we use $$$3 \rightarrow 2 \rightarrow 1$$$, and merge it with $$$maxDepth$$$ from the right segment. 😱😱😱😱

If you think about it again, if we add the edge $$$(5, 8)$$$, $$$depth[8]$$$ will not suffice to replace $$$suffixDeep$$$, but if we again add $$$(8, 9)$$$, $$$depth[9] - 2 \times depth[4] = depth[3] - 2 \times depth[1]$$$ has the same ready to sum distance! When the tωee is weighted, This invariant is still correct. ✅

Based on that information, we can maintain the information for each of the interval using this merge method. 🎍🎍

void merge(Node &head, Node &l, Node &r) {
  head.maxDepth = max(l.maxDepth, r.maxDepth);
  head.minDepth = min(l.minDepth, r.minDepth);

  head.suffixDeep = max(l.suffixDeep, r.suffixDeep);
  head.suffixDeep = max(head.suffixDeep, l.maxDepth - 2 * r.minDepth);

  head.prefixDeep = max(l.prefixDeep, r.prefixDeep);
  head.prefixDeep = max(head.prefixDeep, r.maxDepth - 2 * l.minDepth);

  head.diameter = max(l.diameter, r.diameter);
  head.diameter = max(head.diameter, l.maxDepth + r.prefixDeep);
  head.diameter = max(head.diameter, r.maxDepth + l.suffixDeep);
}

Update and Lazy Propagation ‧₊˚🖇️✩ ₊˚🎧⊹♡

OwOkayy~~ Seωious mowode~

Now, let's think on how to update a certain edge's weight 🧠, let's say we want to update $$$(u, v, +c)$$$, WLOG, let's consider the update as a delta between the old weight and the new weight. WLOG, assume $$$depth[u] < depth[v]$$$ ($$$v$$$ is deeper and $$$u$$$ is closer to the root) What we're doing is basically increasing the depth for all the subtωee of $$$v$$$. For example we are increase the weight of $$$(2, 3)$$$ by $$$3$$$, we will update the interval $$$[order[3].first, order[3].second]= [3, 11]$$$ in this case by $$$+3$$$, the propagation is easy, because:

  • It doesn't affect the diameter of that current subtωee, it only affects the diameter pair for the range that:
    • Starts with an index $$$L < order[3].first$$$, and ends with index $$$order[3].first \leq R \leq order[3].second$$$.
    • Starts with an index $$$order[3].first \leq L \leq order[3].second$$$ and ends with index $$$order[3].second < R$$$.
  • The lazy propagation for that certain interval thus only affects maxDepth and minDepth (just an increase of $$$+c$$$), prefixDeep and suffixDeep (decrease of $$$c$$$).
void pushDown(int rangeL = 1, int rangeR = dfsTime, int idx = 1) {
  if (segt[idx].lazy == 0) return;
  auto &val = segt[idx].lazy;
  segt[idx].maxDepth += val;
  segt[idx].minDepth += val;
  segt[idx].suffixDeep -= val;
  segt[idx].prefixDeep -= val;
  if (rangeL != rangeR) {
    segt[idx * 2].lazy += val;
    segt[idx * 2 + 1].lazy += val;
  }
  val = 0;
  return;
}

By this, the invariant of that interval is maintained accordingly after pushing down a node. The parent node then can merge and adjust again.

image-20231004123703880

Obtaining the Diameter Pair ⸜(｡˃ ᵕ ˂ )⸝♡

The main observation doωoesn't actually change, the pushdown is not modified, we just need to k-k-k-keep tωack which node is invoωovt duωing obtt-t-aining the diameteω of the tωeeee. 🔢

void merge(Node &head, Node &l, Node &r) {
  head.maxDepth = max(l.maxDepth, r.maxDepth);
  head.minDepth = min(l.minDepth, r.minDepth);
    
  head.prefixDeep = max(l.prefixDeep, r.prefixDeep);
  head.prefixDeep = max(head.prefixDeep, {r.maxDepth.fi - 2 * l.minDepth.fi, r.maxDepth.se});

  head.suffixDeep = max(l.suffixDeep, r.suffixDeep);
  head.suffixDeep = max(head.suffixDeep, {l.maxDepth.fi - 2 * r.minDepth.fi, l.maxDepth.se});

  head.diameter = max(l.diameter, r.diameter);
  head.diameter = max(head.diameter, {l.maxDepth.fi + r.prefixDeep.fi, {l.maxDepth.se, r.prefixDeep.se}});
  head.diameter = max(head.diameter, {r.maxDepth.fi + l.suffixDeep.fi, {r.maxDepth.se, l.suffixDeep.se}});
}

G-Getting Fuωuthest N-N-Noωde From X ૮₍ ˃ ⤙ ˂ ₎ა

By getting the diameter p-p-ppair 😳👉👈, essentially u can just plugin another HLD to get $$$max(distance(X, pair[0]), distance(Y, pair[1]))$$$. But that's just dumb, we can just get the LCA and compute it by getting it using ur classic $$$depth[x] + depth[y] - 2 \times depth[lca]$$$. By the time u ωeaωize this, yes, you can also use this data stωuctuω to do dynameec uωupdate on ωeight, and get distance of tuωu node in the tωee.. 🌳

Code Code Code yay

Other Poωoblem Variation ૮꒰ ˶• ༝ •˶꒱ა ♡

  • Get Subtωee D-D-Diameter 😱
  • Get Fuωuthest node for a ceωtain $$$x$$$ under a subtωee 🤔

If you know any otheω techniques or oωotheω usage of Euler Touωur that is quite magic like this plss sharee. The one that is quite simiraωr is the Ultimate Link Cuωut Tωee I saω moωonths agωo >< じゃーじゃーまたね～

Full text and comments »

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

COMPFEST 13 — Editorial
By hocky, history, 3 years ago, In English

1575A. Another Sorting Problem

Author: hocky
Developer: richiesenlia
Editorialist: hocky

Idea

1575B. Building an Amusement Park

Author: Panji
Developer: hocky, rama_pang
Editorialist: hocky, rama_pang

Idea

1575C. Cyclic Sum

Author: steven.novaryo
Developer: steven.novaryo
Editorialist: steven.novaryo

Idea

1575D. Divisible by Twenty-Five

Author: hocky
Developer: hocky
Editorialist: hocky

Idea
Short Solution

1575E. Eye-Pleasing City Park Tour

Author: steven.novaryo
Developer: rama_pang, hocky, steven.novaryo
Editorialist: rama_pang, steven.novaryo

Idea

1575F. Finding Expected Value

Author: rama_pang
Developer: rama_pang
Editorialist: rama_pang

Idea

1575G. GCD Festival

Author: yz_
Developer: hocky, yz_
Editorialist: rama_pang

Idea

1575H. Holiday Wall Ornaments

Author: hocky
Developer: Sakamoto, hocky
Editorialist: hocky, rama_pang

Idea

1575I. Illusions of the Desert

Author: JulianFernando
Developer: JulianFernando, hocky
Editorialist: hocky

Idea

1575J. Jeopardy of Dropped Balls

Author: richiesenlia
Developer: richiesenlia
Editorialist: hocky

Idea

1575K. Knitting Batik

Author: hocky
Developer: hocky
Editorialist: hocky

Fun fact
Idea

1575L. Longest Array Deconstruction

Author: yz_
Developer: steven.novaryo
Editorialist: steven.novaryo

Idea

1575M. Managing Telephone Poles

Author: yz_
Developer: steven.novaryo
Editorialist: steven.novaryo

Fun fact
Idea

Full text and comments »

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

COMPFEST 13 Finals Mirror (Unrated, ICPC Rules, Teams Preferred)
By hocky, 3 years ago, In English

logo

Hi Codeforces ଘ(੭*ˊᵕˋ)੭* ੈ♡‧₊˚!

We're delighted to invite you to COMPFEST 13 — Finals Online Mirror (Unrated, ICPC Rules, Teams Preferred) on .

All problems were written and prepared by hocky, steven.novaryo, rama_pang, JulianFernando, yz_, Panji, richiesenlia, Sakamoto, and markus_geger.

I would also like to thank:

  • KAN for helping to host the mirror round;
  • (AVM.Martin, Ace_02), Berted, ardan, wijayareynaldo, and bukanYohandi for testing the round locally and improved the problems in early phases;
  • UWr Kobor 53 (w0nsh, kobor, Fly_37), Almost Retired (KAN, Um_nik, Ekler), and errorgorn for testing the round and their really useful feedbacks;
  • Universitas Indonesia, all the local committees, administrators, and managers of the whole COMPFEST event;
  • prabowo for observing the contest;
  • fushar for the Judgels platform used in the official contest; and finally
  • MikeMirzayanov for the great Codeforces and our lovely Polygon!
  • Extra thanks for rama_pang and steven.novaryo for working hard night 🌚 and day 🌞 making sure the problems are well-prepared (the contest wouldn't exist without their hands).

The duration will be 5 hours, consisting of 13 problems. You can register individually, but teams are preferred. You may expect relatively easier problems than ICPC Regional Contests. You may code parallely with several computers with your teammates and use prewritten codes and templates.

COMPFEST itself is an annual event hosted by Universitas Indonesia. It is the largest student-run IT event in Indonesia and competitive programming contest is one of the competitions hosted.

We've put great effort into preparing this contest and we hope that you will enjoy it. See you! ありがとう~! 🐾

UPD: Editorial is out!!! Editowial UωU

Congratulations to our top 5!

  1. leziren (jqdai0815, TLE, Rewinding)
  2. heno239
  3. bubble (riantkb, nuip, mtsd)
  4. gisp_zjz
  5. We Won it 0 time (aarr, afterall, Amoo_Safar)

Full text and comments »

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

FBHC wuining uw Day? Incwease uw stacc size! (ㅅ´ ˘ `)
By hocky, history, 3 years ago, In English

Hello! Today I'm going to show you how to incwease stacc 📒 size in some various opewating systems ( ^◡^)
I'm sowwy if my engwish is bad (⁄ ⁄>⁄ω⁄<⁄ ⁄)⁄

u awe using Mac ⌘ ૮ ˶ᵔ ᵕ ᵔ˶ ა

I used mac for my internship for several months and I used to compile C++ using mac. 🌿

Mac iws a bit wetawded bcuzz its weawwy hawd to set up #include <bits/stdc++.h>

Mac

will incwease the stacc size to 512MB 💙, (the hexadecimal is in bytes)

Hmppfff... It seems like there are no ways to increase more than that. Deploy uwsewf an AWS or GCP micwo VM instance.. (.﹒︣︿﹒︣.)

u awe using Windows ૮₍ ˃ ⤙ ˂ ₎ა

Windows

will incwease the stacc size to 1GB 💙, (the decimal is in bytes)

u awe using any winux wistwibution ฅ՞•ﻌ•՞ฅ

Winux

🐧 will incwease the stacc size to 1GB 💙, (the decimal is in kiwobytes)

Uwpu uwpudeitooo~! U can eidd this wunction in uw ~/.bashewc wike thiws

bashrc

and can dooooo: runcpp B < input.txt > out.txt

Full text and comments »

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

How To Debug With Colors ⊂(´･◡･⊂ )∘˚˳°
By hocky, 3 years ago, In English

Hello! Today I'm going to show you how to debug with colors in your lovely console ( ^◡^)
I'm sowwy if my engwish is bad (⁄ ⁄>⁄ω⁄<⁄ ⁄)⁄

First Step: wet's see huw it wurksss (*ゝω・)ﾉ 🍎🍌🍀📘

Okay, so first things first, our terminal has it's own way to interpret color. It basically will escape a certain kind of stuffs and it will interpret it as color for the next stream.

Pwease see this code: 💖💖

Code UωU

2nd Step: wet's make a cwass!

If we wunt to use itt.. Let's make it really easy for us to use!

ColorDebugger Class UωU

Pay attention that I defined endl as \n because we 💗 codeforces. Just kidding, that's because std::endl is a weird stuff that can't be defined with simple generics, and it's really weird, endl is more like a function (it's not but just take it for granted). Next, we got this implementation without defining endl as \n.

ColorDebugger Class Finish UωU

Step 三

Let's see this in action:

Input is in the color dark and output is blue

Beside windows, linux terminal has the same syntax, I awso have twied it.

Pwoof

Don't be confused with bashfast and compileCPP it's basically an alias I've made to access my WSL (Windows Subsystem fow Winux) and to compile C++ code.

ありがとう~! 🐾

I use light mode because it's cwuteeee UωU~~!! 🐾 🐾

Full text and comments »

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

Invitation to TOKI Special Open Contest — April Fools 2021!
By hocky, history, 4 years ago, In English

TSOC Logo
Dear Codeforces community,

We're excited to invite you to TOKI Special Open Contest (TSOC) — April Fools 2021!
There will always be time to spend on these kinds of contests, right 🤡?

Key details:

Come and join the contest! We hope you will enjoy TSOC — April Fools 2021!

We would like to thank fushar as an organizer who worked hard to prepare the platform and all the writers as our problem testers.

Congratulations for our Top 5!! Y'all did greatt! 🎉🎉🎉

  1. i_type_stuff
  2. SorahISA
  3. ya_
  4. Pa.Nic
  5. azaky

As usual, the editorial is available here.
And you can upsolve the problems here. See you again next yearr!!!

Full text and comments »

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

Invitation to TOKI Special Open Contest — April Fools 2020
By hocky, history, 5 years ago, In English

Dear Codeforces community,

It's the time of the year again, we believe it will never be too late to celebrate April Fools!
We're excited to invite you to TOKI Special Open Contest (TSOC) — April Fools 2020!

Key details:

Please register to the contest, and we hope you will enjoy TSOC — April Fools 2020!

We would like to thank yogahmad77, prabowo as organizers who worked really hard to prepare the contest, and all the writers as testers.

UPD: The contest is over! Congratulations to the top 5:

  1. zscoder, Solved 11 problems, didn't solve F, First solve E, H, and J!
  2. i_type_stuff, Solved 9 problems, First solve F and G!
  3. faustaadp, Solved 8 problems, First solve K (One shot)!
  4. ayaze, Solved 8 problems, Solves D (One shot)!
  5. Motarack, Solved 8 Problems, Solves E,F,H,I,J,K, and L (One Shot)!

Honorable Mentions:

Editorial is available here.

Thank you for participating! See you in the next TROC(s)!

Full text and comments »

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