Top Comments
On orzC++20 is back, 43 hours ago
+55

Considering how "standard" C++ 64bit is, I believe these things change the contest experience drastically and so it is worth having an official annoucement post fixed at the top of Codeforces.

On orzC++20 is back, 5 hours ago
+52

TLDR: Very soon, I will migrate the testing servers to Windows Server 2022. I have spent a great deal of effort in recent days to accomplish this.

Good news: most of these issues are not reproducible there (more precisely, we do not know how to reproduce them), and it will be possible to update some compilers/interpreters that could no longer be updated for Windows 7.

Bad news: modern operating systems have deep protections against speculative vulnerabilities (like Spectre, Meltdown, and others), and therefore, on the whole, any solution will work a bit longer (by my estimates, plus 5-15%).

P.S. We will likely switch to LLVM's clang++ instead of g++. It performs better in some tests.

Are there general methods of constructing testcases that can exploit this GCC/Windows bug and therefore slow down solutions (like there are anti-hash tests for solutions using unordered_set)? Are there methods that slow down both contest mode and custom invocation mode (since 249807302 is only slow in the contest mode whereas 253289473 is only slow in the custom invocation)?

I'm not entirely sure about the current situation. I hope that after migrating to Windows Server 2022, there won't be such methods.

If so, should we expect such tests in future contests, will such methods be used during the test preparation in contests?

I hope that after my work, it will not be possible to exploit the operating system/compiler bugs so explicitly. Therefore, when preparing problems, one should not expect that such tests will be specifically constructed.

However, I urge you to clearly distinguish between two different scenarios in your mind: a bug and a feature of implementation. For example, exploiting collisions in hash tables, quadratic tests for sorting in Java — these are examples of using features of the standard library. The presence of such tests is a feature of problem preparation, and they may either be present or absent in the test set.

If this is deemed an unwanted bug, will participants be protected from unscrupulous hacks and tests? (For example, if the solution was hacked or FSTed because of a compiler bug rather than because of anything else, will the author be able to appeal against it and get their solution accepted?)

In any fairly large and complex software, there are bugs. This is especially true for compilers with their aim to optimize the resulting code. Sometimes the line between a bug and a feature is thin and undefined. I am not ready to take responsibility on our part for individual attention to cases of probable bugs in compilers. In other words, if a participant writes code that encounters unexpected behavior from the compiler/OS, we will not be able to individually understand and help in this situation. On the other hand, I am closely monitoring the situation and paying attention to widespread instances of any such problems.

Is there no bug in 32-bit version? If it's 64-bit only, maybe CF team could add a C++20 32-bit compiler? UPD: 32-bit version can also be slowed down, see 253400416.

I think that 32-bit versions are stable. But currently, I am working on resolving the situation more systematically, rather than fighting it using half measures.

Is there this bug in Microsoft Visual C++ compilers (32 or 64 bits)? If so, is it the reason why we cannot see it among the options?

Read the previous response.

Are there generic methods of protecting against the bug (except switching to 32 bits)? I read (and enjoyed) a blogpost by ToxicPie9 regarding this issue, he suggested to add several lines of code to the solution. However, it does not always help: 253290209 still gets TL (and the author said about that).

I really hope that switching to a modern OS (and likely to clang++ as well) will resolve the issue. However, I'm fairly certain that this won't be the last bug in the compiler/OS, and over time, we will discover new ones.

Has anyone a clue what is going on, why do the aforementioned programs run slowly? Is this bug reported to the GNU or Microsoft developers who are responsible for this strange behavior?

I haven't delved deeply into this issue. It seems that in the current setup, even if somehow resolved, the problem will emerge in some other unexpected place. I prefer to try moving forward.

Why does behavior in custom invocation and in contest/gym mode differ?

Many bugs in the world are quite unstable to reproduce. This is an example of one of them. The method of launching for solutions during testing and during custom invocation is the same.

Is this bug reproducible on other platforms? For instance, on godbolt there are some windows compilers. Is there a way to slow down this code: https://godbolt.org/z/5G73dfezK (by cleverly choosing the value of evil or anything else)? UPD: probably no way since Godbolt uses UCRT rather than MSVCRT. UPDUPD: this code is slow on Godbolt: https://godbolt.org/z/WE4Mxv9cK, so UCRT is also flawed.

It seems to me that this problem is clearly reproduced only on specific versions of Windows 7. This does not mean that there are no other problems in Linux or newer versions of Windows. Tests by maxplus (thank you!) show that there are some irregularities in other setups as well, but we expect that they have little impact on the testing of problem solutions. In any case, I plan to make the main setup one in which such problems do not reproduce at all.

Is there surely no such bug on Linux? (Anyway, with regard to Codeforces it is probably a pointless question. I am quite certain that transition of all invokers to Linux is the last thing MikeMirzayanov would prefer to do since it is for sure really costly in time, effort, architecture changes, and/or money.)

Apparently, this particular bug does not reproduce on Linux. However, even on Codeforces, we lived for a long time without noticing it. I don't know and cannot confidently assert what happens on other systems, especially considering the wide variety of versions, hardware, security patches, etc.

Regarding the switch to Linux: yes, it is a labor-intensive and complex task. We have a huge number of problems (checkers, author solutions, generators, etc.) that may not work or work unpredictably on other systems. In some cases, they are written in languages/dialects whose support in Linux significantly differs.

I should note that the number of participants using Windows is twice as many as those using Linux and iOS combined.

+51

Is it rated?

On flamestormCodeforces Round 937 (Div. 4), 92 minutes ago
+51

Sorry, but I'm moving the round 10 minutes forward. The training session was very cool and long. I'm running to you from the gym!

On orzC++20 is back, 45 hours ago
+40

1: In a way, yes, but these testcases aren't very stable. Adding or removing an allocation of a suitable size will change the set of evil testcases, so abusing this bug to hack a solution would be much more complicated than hacking unordered_set.

4: Yes, 32-bit versions are affected. See TL 1000ms, WA 46ms.

9: Yes, UCRT is affected too. For this particular code, compiler and environment 12581 is an example of an evil constant.

As a monkey tester, the cows are friendly :)

On CPNurdAbout Offensive Comments/Blogs, 44 hours ago
+34

Someone proposed the idea that you can only comment/create blogs if you have participated in at least 10 contests.

On gkO_oA Problem About DAG, 43 hours ago
+34

Order the nodes by some topological order, suppose WLOG that the order is $$$1 \rightarrow 2 \rightarrow \ldots \rightarrow n$$$ (any edge $$$i \rightarrow j$$$ satisfies $$$i < j$$$).

Compute $$$r_i$$$ as the smallest vertex reachable from vertex $$$i$$$, which is simply its edge going to the smallest vertex (if none exists, $$$r_i = \infty$$$). Symmetrically compute $$$l_i$$$ as the largest vertex that can reach $$$i$$$, which is also a neighboring edge (if none exists, $$$l_i = -\infty$$$).

Lemma: A vertex $$$v$$$ is a "super delivery point" iff $$$r_u \leq v$$$ for all $$$u < v$$$, and $$$v \leq l_u$$$ for all $$$v < u$$$.

Proof: If the condition isn't met, WLOG there exists $$$u < v$$$ such that $$$r_u > v$$$, then by definition $$$u$$$ cannot reach $$$v$$$, and because of the topological ordering, $$$v$$$ also cannot reach $$$u$$$. If the condition is met, then for every $$$u < v$$$ you will reach $$$v$$$ if you keep walking on the path $$$u \rightarrow r_u \rightarrow r_{r_u} \rightarrow \ldots \rightarrow v$$$, and symmetrically if $$$v < u$$$ then the reverse of $$$u \rightarrow l_u \rightarrow l_{l_u} \rightarrow \ldots \rightarrow v$$$ is a path. $$$\blacksquare$$$

Therefore, compute $$$l_i,r_i$$$ in $$$O(n)$$$, then compute prefix maximum of $$$r_i$$$ and suffix minimum of $$$l_i$$$, and then a vertex can be checked in $$$O(1)$$$ if it is special, so overall $$$O(n)$$$.

On harshith_04Need Tips to reach CM :), 30 hours ago
+29

The only thing you should do is solve more 1900+ problems. Like you have solved 19 of them or something like that. If after solving 50 or 70 1900+ problems and still not being CM, then you need to change something. But before, just go and solve more hard problems.

Funnily enough, H was exactly the same problem.

+28

The organisation of the event was amazing! Thank you so much!

On orzC++20 is back, 24 hours ago
+28

As a coordinator, I don't know how to deal with point 2. (for example, in the upcoming CodeTON Round 8 (Div. 1 + Div. 2, Rated, Prizes!)), since there is no official answer to point 3.. So I would like a reply on this blog by MikeMirzayanov.

Wansur orz

I just added assertions and turns out that the condition $$$e_i < s_{i+1}$$$ is giving runtime error on test 2. RIP :(

CaptainUknown please check the testcases.

+26

Happy Altiversary! Just 24 minutes before re-registering on Codeforces. By the way, are you a fresh face here on Codeforces, bro. aren't you?

+25

Why no green/cyan testers in Div4 round?

+22

I was interested in similar stuff around a decade back, and here are my favorites that I came up with on my own (the first one is kind of funny, but the second one is genuinely nice in my opinion):

Finding the two-variable AM-GM inequality using thermodynamics

Consider the following problem:

There is an insulated chamber which is partitioned into two chambers, initially at identical conditions, by a massless movable piston. There is an ideal gas inside the chamber. The piston moves uniformly at the same speed, and the gas undergoes a quasi-static adiabatic process. Find the temperature of the chamber when the volumes are in the ratio α : β in terms of the original temperature $$$T_0$$$ and the specific heat ratio of the gas γ.

Now the answer to this problem (integrate the thermodynamic equation after using the ideal gas equation) is $$$T/T_0 = \left(\frac{(\alpha + \beta)^2}{4\alpha\beta}\right)^{\frac{\gamma - 1}{2}}$$$.

Note that the work done is negative (consider the sign of the pressure difference at every point), so the internal energy (and hence the temperature) of the gas must increase. This means $$$\frac{T}{T_0} \ge 1$$$. Also, since $$$c_P = c_V + R$$$, we have $$$\gamma > 1$$$. So by taking the $$$(\gamma - 1)$$$-th root of the inequality, we recover the AM-GM inequality for 2 variables.

Solving the tautochrone problem using Kepler's laws

This was inspired from the solution to an international Olympiad problem that I solved in-contest.

Consider the following problem:

Let two spherical bodies released of mass $$$m_i$$$, i = 1, 2 be released in isolated space, and move under gravity. Find the separation between them as a function of time. (Assume that no collisions happen, i.e. the impact parameter is very small compared to the initial separation $$$r_0$$$ but large compared to the radii of the two spheres.)

If $$$r$$$ is the separation between the masses, then by using conservation of energy in the frame of reference of the center of mass, we have $$$\dot{r}^2 \cdot \frac{1}{2G(m_1 + m_2)} = \frac{1}{r} - \frac{1}{r_0}$$$.

Also consider the following problem:

The tautochrone problem asks for the curve such that the frequency of oscillations of a point mass moving on it frictionlessly under a uniform gravitational field is independent of the amplitude, i.e., if a particle is kept on it at any point, it returns to that position after a time which doesn’t depend on the position where it was kept.

Here's how we get to an equation for it:

For a harmonic oscillator, we know that the time period is independent of the amplitude of motion. So if we have a harmonic potential with respect to arc length, we will have a motion that gives us a tautochronic potential. It is easy to see that the dependence of the potential with respect to the arclength will be unique, which can be seen from the process of building up the tautochrone starting the origin for a given time period.

Thus we have $$$U = ks^2 / 2$$$ for some constant $$$k$$$ where $$$s$$$ is the arclength from the equilibrium. Also we know that to an additive constant, the potential energy of the particle is $$$mgy$$$ where $$$y$$$ is the y-coordinate of a coordinate system lying in the plane of motion and $$$y$$$-axis along the opposite direction of the gravitational acceleration vector. So defining $$$\omega_0^2 = \frac{k}{m}$$$, we get $$$y = \frac{\omega_0^2 s^2}{2g}$$$. Taking the differential and squaring, and expressing $$$s^2$$$ in terms of $$$y$$$ and using the fact that $$$\mathrm{d}s = \sqrt{\mathrm{d}x^2 + \mathrm{d}y^2}$$$, we get $$$\left(\frac{\mathrm{d}x}{\mathrm{d}y}\right)^2 \cdot \frac{2\omega_0^2}{g} = \frac{1}{y} - \frac{2\omega_0^2}{g}$$$.

These equations seem similar (except for the $$$x, y$$$ being swapped on one side of the equation), so we will just solve the first problem using Kepler's laws and use that solution to get a solution to this problem too (with possibly different boundary conditions, but the general form is the same). To that end, we use some geometry.

Kepler's law of areal velocity (or just angular momentum conservation for central fields) concerns itself with area swept out per unit time by the path of the mass (let's say $$$m_1$$$, which is a conic. The conic here is a degenerate ellipse, with the foci at the initial location of the mass $$$m_1$$$ and the center of mass of the system. By performing a "stretch" perpendicular to the line connecting the masses (assuming that the ellipse actually had some negligible but non-zero thickness), since ratios of areas are still preserved under stretch (due to stretching being an affine transform, or just considering what happens to an infinitesimal Cartesian area element under a stretch), we can transform this ellipse into a circle. Let's consider what happens when we consider a point on the resulting circle, let's say with an elevation angle of $$$\theta$$$ from the horizontal. Then $$$r$$$ becomes $$$r_0 \frac{1 + \cos \theta}{2}$$$ and the time taken is proportional to $$$\theta + \sin \theta$$$ (the exact time is easy to find using a different Kepler's law).

It would have been pretty cool if just using the correspondence $$$r = x$$$ and $$$t = y$$$ finished the solution. However, we need a bit more work to finish it.

Define $$$f$$$ such that $$$f(\theta) = \dot{r} / a$$$ where $$$a$$$ is such that $$$f(\pi/2) = -1$$$. Then we have $$$f(\theta) f(\theta - \pi) = -1$$$. The good part about this is, we can now replace $$$f(\theta)$$$ by $$$-1/f(\theta - \pi)$$$ in the equation, to get identical forms of the equation. After translating $$$x$$$ appropriately, we get the solution $$$x = \frac{g}{4\omega_0^2}(\theta - \sin \theta)$$$ and $$$y = \frac{g}{4\omega_0^2}(1 - \cos \theta)$$$, and we're done.

Question G1 on AtCoder would be like:

Count number of connected labelled graphs with $$$n$$$ nodes.

+21

This epic fun doesn't deserve to be hidden from recent blogs/comments.

fun

Virtual Mirror of math round CodeMod on Codeforces would be highly recommended. Please consider this.

On orzC++20 is back, 30 hours ago
+20

I totally agree with you. And if there is no official announcement post, I at least expect MikeMirzayanov to comment on items (2), (3), partly (5), and (8) somewhere else as nobody else knows what CF headquarters is planning to do regarding the situation. It is true that many people, including me, extremely rarely need anything but 64-bit GNU C++20.

Unfortunately, two easiest ways might be to completely ignore the problem, or to switch invokers to Linux. I understand why both of them might seem undesirable for various reasons.

As a tester, smax orz

As a contest co-ordinator of icpc-de-tryst, can surely say the problemset is fun and worth spending your 4 hours on :)

On NamikaI can't prove my solutions, 23 hours ago
+19

It happens in beginning, we solve most of the questions based on intuitions but over time through experience we learn how to prove our solutions as it becomes crucial once you're rating increases. You can read the tutorial to see how they come up with formal proof and learn through it and try to prove the problems that you have solved in the contest after the contest ends.

+18

Wow even as a Candidate Master, you hesitate to engage in blog comments!

Merely replying to a blog necessitates creating a new account.

What a pity!

On bgopccf community in 5 days:, 42 hours ago
+18

how to add a Qoute like that?

Add ">" to the beginning of the sentence.

On NorpPupil in 80 days - Day 14, 24 hours ago
+17

You should reflect in your mind when you do problem why you did/didn't solve it and how you could figure out similar insights in problem in future more. I also think it's good to come up with list of questions to ask yourself in future problems, and always revise/shorten it when you learn new things or realize different ideas come from same fundamental thinking.

However, i'd avoid thinking too much about categorizing problems into groups by solution topic at all, as standard topics can be used in various scenarios and they're more of tools than frameworks to solve. Instead, if you want to categorize put problems you remember/go over in future into groups that compare/contrast differences in questions you ask yourself to get to solution.

Your goal is to make framework where you find new small insights one by one to solve a problem with overarching setup you've never seen before, rather then sorting problems by what geeksforgeeks article they belong to and constraining yourself to only solve problems that follow such templates.

Look at "Extra advice how to think to solve problems" in my post.

G1 and G2 here

but like icpc ends on 30th afternoon, and contest is on 31st night, so 1.5 days gap. I guess since their fest ends on 31st, keeping it on 31st is the optimal choice

Fun fact: the authors of the "most Russian" problem (i.e., 1889D - Game of Stacks) are Chinese.

+15

Ok. I was just curious because it was very strange (insulting his own religion for NO reason).

On NorpPupil in 80 days - Day 13, 44 hours ago
+15

hmm, you should change it to "specialist" in 80 days, i think 80 days will be so much for u to reach pupil :)

+14

Hope it isn't a div2.5 as last time

On bgopccf community in 5 days:, 45 hours ago
+13

I could, of course, be overanalyzing the joke problems.

Perhaps. The problems are basically designed so that the participants can enjoy an entertaining contest after one year of serious ones.

+13

Despite your CM status, you evade blog engagement! Creating a new account just to respond seems like a waste of resources.

It seems your IQ is inversely proportional to your contribution.

On CPNurdAbout Offensive Comments/Blogs, 31 hour(s) ago
+13

no since people from some countries where the government blocks some websites (e.g china, Iran, north Korea) will have a hard time accessing it, I don't know if cf is blocked in any of them but it'll be damaging to some, currently I'm using a VPN just to come on cf

On CPNurdAbout Offensive Comments/Blogs, 29 hours ago
+13

Well, IP bans are rarely a silver bullet solution. Many individuals resort to VPNs to circumvent them. However, the drawback is that IP bans can inadvertently affect multiple users sharing the same IP, like those in a university or library. Consequently, innocent users could find themselves locked out of Codeforces.

On orzC++20 is back, 25 hours ago
+13

I tried using a simple script (link) to find the "evil" constants for Rust, and it actually worked TL, WA

On orzC++20 is back, 24 hours ago
+13

Even python seems to be affected by this bug WA ~500ms, WA ~60ms (n = 10^5) and TL 1000ms, WA ~250ms (n = 10^6)

Evil constant was found by similar script (but the same script found nothing for PyPy)

i wonder why teamscode had to delay their contest

Great contest. Loved the problems, especially DAMYAAN!

On orzC++20 is back, 5 hours ago
+13

P.S. We will likely switch to LLVM's clang++ instead of g++. It performs better in some tests.

Regarding this, will clang++ have any major differences compared to g++? I am sorry if this question sounds naive or something, but I'm quite in the dark regarding the technical details / implementations behind compilers.

+13

It is mentioned in the post that's why he is asking.

1st April Rules

1.Do not trust anything anyone says

2.Do not trust the first rule

As a tester, I can confirm the epicness of this contest.

On polosaticProving math using physics, 47 hours ago
+11

Also, it's not physics per se, but I also came up with a proof of Pythagoras' theorem using only functional equations (posting here since your proof of Pythagoras theorem does not use physics strictly but just assumes some functional form — in this solution, we don't need any such assumptions):

We consider the following functional equation:

Find all functions $$$f: [\mathbb{R}^+ \cup \{0\}]^2 \longrightarrow \mathbb{R}^+ \cup \{0\}$$$ in $$$2$$$ variables satisfying the following properties:

  1. $$$f(\sqrt{ab},f(\frac{a-b}{2}, x))=f(x,\frac{a+b}{2}) \ \ \forall a,b \in \mathbb{R}^+ \cup \{0\} $$$ with $$$a>b$$$.
  2. $$$f(\alpha,0)=\alpha \ \forall \alpha \in \mathbb{R}^+ \cup \{0\}$$$
  3. $$$f(x,y)=f(y,x)$$$ $$$\forall x, y \in \mathbb{R}^+ \cup \{0\}$$$.

The following solution of the functional equation is attributed to the AoPS user pco:

Setting $$$x=0$$$ in (1), we get $$$f(\sqrt{ab},\frac{a-b}2)=\frac{a+b}2$$$ (using (2) and (3)) $$$\forall a>b\ge 0$$$ Note that this equality is still true when $$$a=b$$$

Let $$$x,y\ge 0$$$. Setting in the above $$$a=\sqrt{x^2+y^2}+y$$$ and $$$b=\sqrt{x^2+y^2}-y$$$, we get $$$\boxed{f(x,y)=\sqrt{x^2+y^2}}$$$ which indeed is a solution.

Now note the following figure: let $$$\omega$$$ be a circle with center $$$A$$$. $$$B, D, E$$$ are points on the circle, and the tangent at $$$B$$$ to $$$\omega$$$ meets $$$DE$$$ at $$$C$$$. Let the midpoint of $$$DE$$$ be $$$F$$$ (Note that we can do this for any right-angled triangle $$$ABC$$$, right-angled at $$$B$$$).

Using this figure and computing $$$AC$$$ in two ways, we conclude easily that the function $$$g(x,y)$$$ which is the hypotenuse of a right triangle with legs $$$x, y$$$ satisfies our functional equation, using power of a point. Thus the function $$$g(x,y)$$$ is actually $$$\sqrt{x^2+y^2}$$$, and our proof is complete.

PS: Another way is to just consider the case where the line $$$DE$$$ coincides with the line $$$AC$$$, but this method seems somewhat distinct.

I just had a question regarding C problem for the test case

1

8 4

1 2 3 3 3 3 3 3

1 2 3 3 3 4 4 4

here the answer that got accepted for problem is 1, however if we look at the case where the value is 1 it is when ball with a[i]=3 and colour[i]=3, however it is not possible to colour all the balls '3' since even if i remove the balls with index=0,1,5,6 i will have a ball left with a[7]=3 and colour[7]=4, which is not colourable since a[i]<a[j] is not met. I was wondering if there is something that I am missing?

On CPNurdAbout Offensive Comments/Blogs, 43 hours ago
+11
+11

So, you off your meds again ?

As a tester, I have to say, excellent round, I hope everyone enjoys it thoroughly.

Having such intelligent individuals commenting on the problems is very encouraging, yet depressing at the same time.

Have a nice contest!

On orzC++20 is back, 3 hours ago
+11

From what we have seen above, MSVCRT, UCRT and the direct low-level Windows API (HeapAlloc, also used by MSVCRT and UCRT) all three are hackable. Any compiler will use one of these three implementations, so the only possible fix will be if HeapAlloc is fixed in the new OS (and the corresponding runtime that is used is also fixed). The compiler has nothing to do with this issue.

Migrating from g++ to clang++ will also prevent usage of optimization pragmas, and might introduce some peculiarities to the behaviour of submissions, as well as break compatibility with mirrors/other contests (for example, most onsite contests use g++ and not clang++). GCC also generally produces better code (at least on Linux), and has better warnings (again, at least on Linux). There might be fewer compiler bugs in Clang, but what really matters is whether those compiler bugs are relevant for competitive programming or not — and GCC is much more thoroughly tested (both generally and for competitive programming) compared to Clang. It makes sense to add both compilers and let users decide — this is what AtCoder does, for example.

OTOH, I am hopeful that with the OS update, there will also be newer programming languages added to Codeforces that a lot of people have been requesting for more than a decade now.

EDIT: If the include path is changed when migrating from g++ to clang++ (and/or if g++ is not installed side-by-side), it will also become impossible to use bits/stdc++.h and pbds, which a lot of people use.

+10
"Ladies and gentlemen, finally I can say what I've always wanted to say at Div. 4 rounds announcements: My first unrated contest :)"
On orzC++20 is back, 47 hours ago
+9

6: I believe it is possible to protect against this bug by using the following kind of allocator

code

Although it doesn't recycle memory, it is still an effective way to deal with the problem, since almost all solutions don't heavily depend on memory recycling.

On orzC++20 is back, 47 hours ago
+9

The code as written is UB — names starting with double underscore are reserved for the compiler/standard library implementers.

Just to note, such an allocator is called a bump allocator, and can be found in KACTL for example.

As a tester, I enjoyed helping Farmer John with his never-ending problems.

+9

Div 4 : The format of the event will be identical to Div. 3 rounds Div 3 : The format of the event will be identical to Edu rounds Edu rounds: The format of the event will be identical to Icpc rules

Is that a recursion?

On NorpPupil in 80 days - Day 14, 19 hours ago
+9

They didn't mention bitmask dp, they were talking about bitmask problems, they are very common and range from 800-3500 difficulty.

as a tester with photo of Stewie Griffin i say .........................................................................Brian Griffin

Can anyone please tell why my code for B gives WA on test 2 or find a countercase, i ran several stresses on my solution and it couldn't find any countercase.

Code
On orzC++20 is back, 36 hours ago
+8

10: It's very hard to ensure non-existence of such bugs on Linux, but (1) I've never heard of them (I've been using Linux for a long time and have basic knowledge of memory allocators), (2) I searched the web for a while and could not find similar issues on Linux (OTOH I could find another nasty slowdown bug on Windows), and (3) if a similar bug was found on glibc allocator, it would be more likely to get fixed.

A little more context on (3): on Linux, memory allocators are mostly implemented in a user-land library called glibc (a library is basically the same thing as a DLL on Windows). If a similar bug existed on Linux, I'm very certain that it would be in glibc and not in the kernel (the core of the Linux OS). Bugs in user-land libraries are easier to handle -- basically libraries are compiled in the same way as you compile normal programs -- and I believe a performance bug like this would be considered very serious by glibc people and will get fixed fairly quickly.

On Meron3rSomeone explain binary search, 34 hours ago
+8

There are many articles on binary search in the catalog.

On Meron3rSomeone explain binary search, 33 hours ago
+8

Imagine you wanna check a word in dictionary It's first letter is N What you gonna do page by page go to find N? No Any normal human would open from the middle and see where is then Then goes to left or right, and checks again until it's on N, that's binary search. You have a range of possible answers From a special point always the answer is gonna be correct and you're searching for the minimum correct answer You implement a function to check if ur current answer is correct If it was you change your right pointer to it other wise the left pointer The answer is the right pointer You probably should not learn it now, for now learn partial sums, using set/upper bound/lower bound After pupil learn it

orz myvaluska the pupil tester

On CPNurdAbout Offensive Comments/Blogs, 29 hours ago
+8

Bro, judging by your comment replies, it's clear why you're still a pupil amidst the experts.

On orzC++20 is back, 27 hours ago
+8

I dug into the Rust source for how HeapAlloc is being used, and found this: https://github.com/rust-lang/rust/blob/master/library/std/src/sys/pal/windows/alloc.rs#L139 — this means that the usage is quite similar.

However, it seems that translating the code that breaks HeapAlloc on C++20 (GCC13) into Rust (with exactly the same allocations) does not work — relevant submission. Since the behaviour is also different between GCC versions as well as across C++ standards (and even between custom invocation and submission), a part of it seems to be some issue with libraries installed on Codeforces. It is quite easy to experiment with constants (look for evil and total in the code), so interested people can tweak the constants and try to figure out which ones work. It's possible that they don't work at all, but I've only tried around 10 such constants.

On orzC++20 is back, 21 hour(s) ago
+8

However, in PyPy there are other sorts of strange slowdown bugs, see https://codeforces.com/blog/entry/126654?#comment-1124635, for instance.

+8

smax orz

+7

Ladies and gentlemen, finally I can say what I've always wanted to say at Div. 4 rounds announcements: My first unrated contest :")

You can do it in n*log(n). Sort the endpoints and process them from left to right. When a segment is ending, if it doesn't have a partner yet, this is your last chance to match it, so you might as well try. Among all unmatched open segments, pair this one with the one who ends first.

You can use an exchange argument to show this will always give you the best answer. I'm not sure if it's possible in linear time, but my gut says no.

tofael1104 physical23 annoying ahh bots

Ironically you need to write codes like this in some situations

Example : Solution

On flamestormCodeforces Round 937 (Div. 4), 87 minutes ago
+7

hoping this is not april fools now.

F was a bit standard i guess :)

The answer is possible for this testcase also it will be 3

Please upload editorial

+6

This has been happening for the past few weeks and it has not been fixed. I've tried using a VPN, registering new accounts, and logging in with my gmail, but nothing works.

+6

Hi, we should get it fixed by the end of day. Thanks!

+6

My problem has been solved now. Thank you for your reply.

What about G1? :)

Is there a mirror for Codemod, or maybe even just a way to view problems when they are released?

orz

smax orz

On orzC++20 is back, 29 hours ago
+5

Compiler bootstrapping should not lead to any issues — the main issue is how malloc is implemented in the relevant DLLs on the Windows judge.

I was trying to reproduce this issue with Rust, but directly using the examples in the original blogpost seems to not reproduce the bug. I am guessing that it is still possible, but haven't succeeded yet.

For anyone who wants to reproduce the issue in Rust, here's some relevant stuff:

  1. Default allocator documentation — apparently on Windows, they use HeapAlloc, so the hack for HeapAlloc should work here as well.
  2. Some code:
Spoiler
On Yen_NhiHelp me guy!!, 25 hours ago
+5

not trying to be disrespectful but that is 1700 question when you're 500, maybe spend time on 800-1000 problems? more helpful for u

+5

Congrats! If one is to start Euler project what book resources would you recommend to have a chance to solve most of them? I bet I mean book positions from combinatorics, geometry, number theory, game theory, ... ? What set of skills is crucial to solve the most difficult ones?

Thanks a lot in advance for your tips and recommendations. Cheers, Pawel

On CPNurdAbout Offensive Comments/Blogs, 22 hours ago
+5

Believe it or not, you can climb the ranks to Expert or beyond simply by putting anime pf

On bgopccf community in 5 days:, 17 hours ago
+5

Everytime those test cases humiliates me

Glad you liked the problem :)

smax orz

fr, smax orz

On NorpPupil in 80 days - Day 13, 34 hours ago
+4

There are problems that require some observation, specific technique, or idea (like estimate of number of divisors) that you don't know, and while it's of course possible to come up with it by yourself you need to be a genius to do that, so for mere mortals reading and learning it is faster way to improve than inventing. But there are problems where you just need to imagine the data model and understand what goes where and how calculate it fast (using prefix sum in 295A), in that cases reading editorial will teach you very little because it just skips the understanding part and says what to do.

So rule of thumb is if you understand the problem, but after hard think have no idea how to get to the answer (missing couple pieces of puzzle) read editorial. If you struggle with grasping the problem itself then take a pen and paper and grind it.

And also, reading editorial after you solved any problem is also very good, to find what you could (or did) differently/better/simpler.

On NorpPupil in 80 days - Day 14, 19 hours ago
+4

Bitmask is not really a topic, just a theme that operates around problems with bits. Same with data structures.

I would say 2 pointers is not really necessary to reach pupil, binary search is good enough and most times you can use std::set or std::lower_bound.

On flamestormCodeforces Round 937 (Div. 4), 23 minutes ago
+4

GUYS I WAS JOKING HOW YALL HAVE THIS HORRIBLE SENSE OF HUMOR

We can post the problems online, we'll update the blog in time. Though we won't be accepting any online submissions.