You can use several words in query to find by all of them at the same time. In addition, if you are lucky search understands word forms and some synonyms. It supports search by title and author. Examples:

  • 305 — search for 305, most probably it will find blogs about the Round 305
  • andrew stankevich contests — search for words "andrew", "stankevich" and "contests" at the same time
  • user:mikemirzayanov title:testlib — search containing "testlib" in title by MikeMirzayanov
  • "vk cup" — use quotes to find phrase as is
  • title:educational — search in title

Results

1.
By andreyv, 12 years ago, translation, In English
Catching silly mistakes with GCC As you know, the C++ language assumes that the programmer is always correct. Therefore C++ compilers don't add additional checks to the program, such as checks for null pointer dereference or out-of-bounds array access. This is good, because C++ programs run as fast as possible, and this is bad, because sometimes we may spend a long time debugging some silly mistake. We would want that the compiler can find such mistakes automatically. And many compilers can! In this post I will show various GCC options that do this. Previously [user:zakharvoit,2015-01-02] already wrote about this [here](/blog/entry/13875). All options that will follow should be added to the GCC command line. In various IDEs you can do it in IDE or compiler settings. Many of the options can also be used with Clang (for example, in Xcode). For MSVC++, I think, there is nothing better than Debug mode and `/W4`. [cut]   GCC warnings ------------------ Of course, the first step to debugging is to enable compi...
GCC expects bitwise operators. - `-Wshift-overflow=2` — warns about left shift overflows (GCC 6, `-fsanitize=undefined` can also find divisions by zero, undefined integer shifts, signedinteger

Full text and comments »

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

2.
By Monogon, history, 6 years ago, In English
[Tutorial] Voronoi Diagram and Delaunay Triangulation in O(n log n) with Fortune's Algorithm What's a Voronoi Diagram? ------------------ Given a set $S$ of $n$ points in the 2D plane, the Voronoi diagram is a partition of the plane into regions. The region associated with a point $p\in S$ contains precisely the points $q$ such that $q$ is closer to $p$ than any other point in $S$. In other words, a point $q$ belongs to the region of its nearest neighbor. <img src="https://upload.wikimedia.org/wikipedia/commons/thumb/5/54/Euclidean_Voronoi_diagram.svg/1024px-Euclidean_Voronoi_diagram.svg.png" width="300px" height="auto"/> The Voronoi diagram can be represented by the planar graph of boundaries between regions. A vertex in this graph is where three or more segments meet (or a point at infinity), and an edge is a segment connecting two of these vertices. The way the regions were defined, we see that a segment contains the points equidistant to two points in $S$, so it is part of their perpendicular bisector. Similarly, a Voronoi vertex is equidistant to three or more v...
in mind that the algorithms using only integers have a risk of integer overflow even on reasonably, , keep in mind that the algorithms using only integers have a risk of integer overflow even on

Full text and comments »

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

3.
By Monogon, history, 6 years ago, In English
Efficient 3D Convex Hull Tutorial _Warning: The following contains graphic depictions of geometry, precision errors, and degenerate cases. Viewer discretion is advised._ ### Prerequisites I assume the reader is familiar with: - 2D Convex Hulls - 3D Vector Operations (dot and cross products) ### Introduction Recall that in the 2D convex hull problem, you are given a set of 2D points, and you must compute the smallest convex polygon containing all the given points. By convex, we mean that for any two points $A$ and $B$ inside the polygon, the entire line segment $AB$ is also inside the polygon. The problem in 3D is completely analogous. You are given $n$ 3D points, and you must compute the smallest convex polyhedron containing all the given points. Similarly, a polyhedron is convex if for any two points $A$ and $B$ inside the polyhedron, the line segment $AB$ is also inside the polyhedron. In the 2D case, it is more obvious what the output is. We can simply output a circular list of vertices on the ...
overflows on 64-bit integer types, we can convert to floating points for computations, and set $\epsilon, -bit integer types, we can convert to floating points for computations, and set $\epsilon=0.5$. Note

Full text and comments »

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

4.
By ToxicPie9, 4 years ago, In English
[Tutorial/Parody Post] Common Mistakes in Competitive Programming and How to Avoid Them Yesterday [user:YouKn0wWho,2023-01-11] posted a [blog](https://codeforces.me/blog/entry/111217) explaining common mistakes in competitive programming and how to avoid them. I was greatly inspired by that post so I decided to make my own. I have compiled some of the mistakes that I didn't make in my early Competitive Programming phase. I also mentioned how to avoid them. Also, in most cases, I will give you a chance to find out what the bug is before I reveal the culprit as I tried to make this blog interactive. The codes that I have used in this blog have been written in Rust as it is the most beloved language for CP. #### Mistake 1 Check out the following code: <spoiler summary="Code"> ``` fn main() { let x: i32 = 1_000_000_000; let y: i32 = 1_000_000_000; println!("{}", x * y); } ``` </spoiler> The output should be $10^{18}$. But if you run the code, you will get a different output. Why? <spoiler summary="Reason"> Because it won't even compile....
= 1 << 40;` will not overflow as Rust will try to deduce the types of integer literals if they're not, Because of integer overflow., Rust has the functions `pow()`, `ilog()`, `ilog2()`, etc. for integer, ``` thread 'main' panicked at 'attempt to subtract with overflow', foo.rs:3:20 note: run with, overflow as Rust will try to deduce the types of integer literals if they're not specified. In this

Full text and comments »

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

5.
By ninja_28, history, 6 years ago, In English
CodeCraft-21 and Codeforces Round #711 (Div. 2) Editorial [problem:1498A] ================== #### [**Video Editorial**](https://www.youtube.com/watch?v=lV5cb8wh3sE) **Author and Problemsetting:** [user:ninja_28,2021-03-29] **Editorialist:** [user:sigma_g,2021-03-29] <spoiler summary="Hint"> Can you think of the simplest properties that relate a number and its sum of digits? </spoiler> <spoiler summary="Hint 2"> Note that if $X$ is a multiple of 3, then **both** $X$ as well as the sum of digits of $X$ are a multiple of 3! Can you put this property to use here? </spoiler> <spoiler summary="Hint 3"> If $X$ is a multiple of 3, then $\texttt{gcd-sum}(X) \ge 3$. Therefore, we are guaranteed that at least every third number will satisfy the constraints required by our problem $(\texttt{gcd-sum}(X) > 1)$. </spoiler> <spoiler summary="Solution"> Therefore, for the input $n$, we can simply check which one of $n$, $n+1$, and $n+2$ has its gcd-sum $> 1$, and print the lowest of them. </spoiler> <spoi...
1. Integer overflows: $x'$ does not fit in integer range 2, . Integer overflows: $x'$ does not fit in integer range 2. Out of bounds access: simulating the $y_t

Full text and comments »

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

6.
By YouKn0wWho, 4 years ago, In English
[Tutorial] Common Mistakes in Competitive Programming and How to Avoid Them One thing is for sure. You do make mistakes. I also make miskates and that's what makes us human. But what we can surely do is &mdash; to try to minimize the errors that we make throughout our life. I have compiled some of the mistakes that I made in my early Competitive Programming phase. I also mentioned how to avoid them. Also, in most cases, I will give you a chance to find out what the bug is before I reveal the culprit as I tried to make this blog interactive. The codes that I have used in this blog have been written in C++ as it is the most used language for CP. **So, if you are new to CP, stick with me as you might don't wanna repeat the mistakes that I made when I was a beginner.** #### Mistake 1 Check out the following code: <spoiler summary="Code"> ~~~~~ #include<bits/stdc++.h> using namespace std; int main() { int a = 1000'000'000,b = 1000'000'000; long long product = a * b; cout << product << '\n'; return 0; } ~~~~~ </spoiler> The outp...
constraint of the problem to make sure of it. - `long long x = 1 << 40` will stilloverflow as `1` is, summary="Reason"> Overflow! Even if you declared the `product` variable as `long long`, what's

Full text and comments »

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

7.
By rembocoder, history, 4 years ago, In English
Integer Binary Search – proper implementation It seems, there are so many materials on binary search already that everyone must know how to code it, however every material seems to tell its own approach, and I see people being lost and still making bugs on such a simple thing. That's why I want to tell you about an approach which I find the most elegant. Of all the variety of articles, I saw my approach only in this [comment](https://codeforces.me/blog/entry/9901?#comment-153756) (but less generalized). UPD: Also in the [user:nor,2022-05-29]'s [blog](https://codeforces.me/blog/entry/96699). ### The problem Suppose you want to find the last element less than `x` in a sorted array and just store a segment of candidates for the answer `[l, r]`. If you write: ~~~~~ int l = 0, r = n - 1; // the segment of candidates while (l < r) { // there are more than 1 candidate int mid = (l + r) / 2; if (a[mid] < x) { l = mid; } else { r = mid - 1; } } cout << l; ~~~~~ ...you will run int...
Integer Binary Search – proper implementation, have a statement about an integer number `n` that is _true_ for integers smaller than some bound, but, Just be careful to not choose a `r` too large, as it can lead to overflow.

Full text and comments »

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

8.
By Endagorion, history, 11 years ago, In English
Codeforces Round #339 Editorial I'm terribly sorry for the delay. Please report any mistakes. [problem:614A] Author: [user:Tigutor,2016-01-16] Developers: [user:Tigutor,2016-01-16], [user:ch_egor,2016-01-16] You had to print all numbers of form $k^x$ for non-negative integers $x$ that lie with the range $[l; r]$. A simple cycle works: start with $1 = k^0$, go over all powers that do not exceed $r$ and print those which are at least $l$. One should be careful with 64-bit integer overflows: consider the test $l = 1$, $r = 10^{18}$, $k = 10^9$, the powers will be 1, $10^9$, $10^{18}$, and the next power is $10^{27}$, which does not fit in a standard integer type. [problem:614B] Author, developer: [user:ch_egor,2016-01-16] You were asked to print the product of $n$ large numbers, but it was guaranteed that at least $n-1$ are beautiful. It's not hard to see that beautiful numbers are 0 and all powers of 10 (that is, 1 followed by arbitrary number of zeros). If there is at least one zero among the g...
print those which are at least $l$. One should be careful with 64-bit integer overflows: consider the, which are at least $l$. One should be careful with 64-bit integer overflows: consider the test $l

Full text and comments »

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

9.
By Geothermal, history, 7 years ago, In English
AtCoder Beginner Contest 137 English Solutions Although AtCoder seems to be getting back to posting English editorials, I'm continuing to release some myself in case having the extra explanations helps some people. (Sidenote: Some of the provided submissions come from after the contest itself, because I had to leave midway through, before I got the chance to debug my E or write my F.) --- #A &mdash; +-X Just use your language's max function. As $A$ and $B$ are small, we don't need to worry about integer overflow. Runtime: $O(1).$ [Click here for my submission.](https://atcoder.jp/contests/abc137/submissions/6802607) --- #B &mdash; One Clue Let's try to find the minimum and maximum values in the answer. It's fairly easy to see that all integers between them will also be in the set. To find the minimum possible position of a black stone, we place $K$ black stones such that $X$ is at the maximum position. Then, the minimum position will thus be $X-K+1$, as we have $K-1$ black stones to the left of $X$....
max function. As $A$ and $B$ are small, we don't need to worry about integer overflow. Runtime, integer overflow.

Full text and comments »

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

10.
By HosseinYousefi, history, 8 years ago, In English
Competitive C++ Manifesto: A Style Guide # Competitive C++ Manifesto: A Style Guide There are many style guides for C++ out there, but we can't really use them as competitive programmers. We just want to write our code correctly as fast as possible! Trying to hack people here on codeforces, I realized there is a need for a style guide! Our goal is to write correct, fast, clear and consistent code. > #### Disclaimer > This is not a rulebook. You can integrate parts of it into your coding style. > Don't overthink it, especially during a contest! I'm going to use this guide for myself and to [teach my students](https://in.harbour.space/computer-science/modern-c-programming-hossein-yousefi/). I'm planning to make some good stuff in the future following these principles! Stay tuned! ## Compiler Make use of C++17. Use `-Wall -Wextra -Wshadow` flags for compilation, and try to eliminate all of the warning messages, this will prevent you from having some silly bugs. There are more debugging flags like `-fsanitize=un...
-range access and integer overflow during runtime. For more information, check out "Read More" section., =undefined` which helps you eliminate bugs such as array out-of-range access and integer overflow

Full text and comments »

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

11.
By mfv, history, 11 years ago, In English
Experimental Educational Round: VolBIT Formulas Blitz Editorial #### [A. Again Twenty Five!](http://codeforces.me/problemset/problem/630/A) The problem of getting the last two digits is equivalent to the problem of getting the number modulo $100$. So we need to calculate $5^{n} \mod 100$. According to [cut] the rules of modular arithmetic $(a \cdot b) \mod c = ( (a \mod c) \cdot (b \mod c) ) \mod c$ So $5^{n} \mod 100 = ((5^{n-1} \mod 100) \cdot 5) \mod 100$ Let's note that $5^2=25$. Then $5^3 \mod 100 = ((5^2 \mod 100) \cdot 5) \mod 100 = (25 \cdot 5) \mod 100 = 25$ $5^4 \mod 100 = ((5^3 \mod 100) \cdot 5) \mod 100 = (25 \cdot 5) \mod 100 = 25$ And so on. All $5^n \mod 100$ are equal to $25$ for all $n \ge 2$. So to solve the problem one need to just output `25`. There is no need to read $n$. #### [B. Moore's Law](http://codeforces.me/problemset/problem/630/B) Every second the number is multiplied by $1.000000011$. Multiplication several times to the same number is equivalent to exponentiation. So the formula i...
avoid overflow, multiplication in the formula should be performed in 64-bit integer type. For this, To avoid 64-bit integer overflow $\frac{n!}{(n-7)!7!}$ can be calculated in the following way: `n, To avoid 64-bit integer overflow recommended order of computation is exactly as in the formula, To avoid overflow of 64-bit integer type recommended formulas for computation are `(n + 2) / 1 * (n, To avoid overflow, multiplication in the formula should be performed in 64-bit integer type. For, To avoid overflow, multiplication should be computed in 64-bit integer type.

Full text and comments »

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

12.
By Endagorion, 12 years ago, In English
Codeforces Round #295 Editorial (now with bonuses!) We would like to thank the testers of this round's and Winter Computer Camp olympiad's problems: [user:alger95,2015-03-02], [user:thefacetakt,2015-03-02], [user:adamant,2015-03-02], [user:dragonic,2015-03-02], [user:Who179,2015-03-02], [user:ASverdlov,2015-03-02]. Make sure to comment if you find any mistakes. **UPD**: I've just remembered to put up the usual challenges for the problems. So, here they go. [problem:520A] Idea: [user:Endagorion,2015-03-02] Preparation: [user:Endagorion,2015-03-02] To check that every letter is present in the string we can just make a boolean array of size 26 and for every letter set the corresponding variable to TRUE. In the end check that there are 26 TRUEs. That is an $O(n)$ solution. Also don't forget to change all letters to lowercase (or all to uppercase). To make all the letters lowercase, one could use standard functions, like `tolower` in Python. Also, it is known that the letters from `a` to `z` have consecutive ASCII numbe...
for a multiplication is an integer up to $10^6$; the ratio for an addition is a fraction of general, in the fractions. The ratio for a multiplication is an integer up to $10^6$; the ratio for an

Full text and comments »

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

13.
By Leftist_G, 9 months ago, In English
Codeforces Round 1083 (Div. 2) Editorial Thank you for participating and accompanying Simons! We hope you enjoyed the problems. <spoiler summary="Rate the contest!"> - Horrible contest - Bad contest - Average contest - Good contest - Epic contest </spoiler> <spoiler summary="Rate the difficulty!"> - Impossible contest - Hard contest - Average contest - Simple contest - Trivial contest </spoiler> <spoiler summary="Rating Predictions"> | | A | B | C | D | E | F | G | |-----| ----- | -----| -----| -----| -----| -----| -----| | [user:Leftist_G,2026-02-25] | 800 | 800 | 1400 | 2000 | 2400 | 2600 | 2900 | | [user:cool_milo,2026-02-25] | 800 | 800 | 1400 | 1800 | 2400 | 2700 | 3300 | | [user:StayAlone,2026-02-25] | 800 | 900 | 1500 | 1900 | 2300 | 2200 | 2800 | | [user:liuhangxin,2026-02-25] | 800 | 900 | 1000 | 1300 | | 2500 |...
Note that some not-so-good solutions may apply `__int128` to avoid integer overflow. Don't forget

Full text and comments »

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

14.
By cry, 23 months ago, In English
Codeforces Round 993 (Div. 4) Editorial #### Special thanks to our hub of testuwuers for contributing solution explanations! #### [problem:2044A] Problem Credits: [user:cry,2024-12-15] <br> Analysis: [user:macaquedev,2024-12-15] <spoiler summary="Solution "> For any $n$, Cube can set $a$ = any integer between $1$ and $n-1$ inclusive, and set $b = n - a$. $a$ cannot be less than $1$, because then it would be non-positive, and $a$ cannot be greater than $n-1$, because then $b$ would be less than $1$, which would make it non-positive. Therefore the answer is just $n-1$ for all $n$. </spoiler> <spoiler summary="Code (Python)"> ```import sys input = sys.stdin.readline for _ in range(int(input())): print(int(input())-1) ``` </spoiler> #### [problem:2044B] Problem Credits: [user:Lilypad,2024-12-15] <br> Analysis: [user:Lilypad,2024-12-15], [user:macaquedev,2024-12-15] <spoiler summary="Solution "> The letters she reads that comprise string $b$ are just the letters that comprise string $a$, flip...
] For any $n$, Cube can set $a$ = any integer between $1$ and $n-1

Full text and comments »

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

15.
By minstdfx, history, 3 weeks ago, In English
[Shitpost] How to Teach Kids Basic Data Structures Using the Methods of a Mathematics Textbook ## Conventions This article is based on ordinary set theory. Natural numbers, integers, finite sequences, maps, Cartesian products, total orders, trees, induction, and the finite recursion theorem are assumed to be established. Write $\mathbf N=\{0,1,\ldots\}$ and $\mathbf N_{>0}=\mathbf N\setminus\{0\}$. All trees are finite trees; all intervals not otherwise qualified are integer intervals. For $l,r\in\mathbf Z$, put $$ [l,r]=\{i\in\mathbf Z:l\le i\le r\},\qquad [n]=[1,n]. $$ When $l>r$, $[l,r]=\varnothing$. For a nonempty finite set $E$, $|E|$ denotes its cardinality. The symbol $\sqcup$ denotes disjoint union. Composition of maps follows the convention $(f\circ g)(x)=f(g(x))$. For $n\ge1$, put $$ \lambda(n)=1+\lfloor\log_2 n\rfloor. $$ All asymptotic estimates are taken as $n\to\infty$; bounds written in terms of $\lambda(n)$ also apply to $n=1$. **Computational conventions.** Unless otherwise stated, we use the random-access machine model with word leng...
multiplication of a group element by a known integer length, $(p,c)\mapsto pc$, are counted as basic, \setminus\{0\}$. All trees are finite trees; all intervals not otherwise qualified areinteger intervals

Full text and comments »

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

16.
By Ripatti, 15 years ago, translation, In English
Editorial for Codeforces Beta Round #93 <p><b>div2 A.</b> In this problem you should find length of polyline, multiply it by $k/50$ and output that you will recieve. Length of polyline is sum of lengths of its segments. You can calculate length of every segment using Pythagorean theorem: $d(A,B)=\sqrt{ (x_A - x_B)^2 + (y_A - y_B)^2 }$.<br />[cut]<br /><b>div2 B.</b> Idea of this problem was offered by [[user:RAD,2011-11-10]]. It was the last problem in the problemset and I had no any easy idea:) I thank him for it.<br /><br />Here you should calculate an array $cnt[100]$. $i$-th element of it stores number of sticks whose lengths equal $i$. Now you should calculate number of pairs of sticks of equal lengths. This number is $k = \sum_{i=1}^{100} [cnt[a]/2]$, where $[x]$ is floor of $x$. For every frame you need 2 if such pairs and <span class="short_text" lang="en"><span class="hps">you can choose it in any order</span></span>. Therefore the answer will be $z = [k/2]$.<br /><br /><b>div2 С. div1 A.</b> At the first you should...
/>All calculations should be done in 64-bit integers (8th pretest checks overflow of 32-bit integers, All calculations should be done in 64-bit integers (8th pretest checks overflow of 32-bit integers

Full text and comments »

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

17.
By Proof_by_QED, 8 months ago, In English
Nebius Round 2 and Codeforces Round 1088 Editorial <spoiler summary="Rating Predictions"> | Predictor | A | B | C | D | E | F | G | H | |----------------------------------|-----|-----|-----|------|------|------|------|------| | [user:Proof_by_QED,2026-03-27] | 800 | 1300 | (1400-2000) | 1700 | 2100 | 2400 | 2600 | 3500| | [user:nifeshe,2026-03-27] | 800 | 1400 | (1400-1900) | 1800 | 2200 | 2600 | 3000 | 3500| | [user:dinohaur,2026-03-27] | 800 | 1200 | (1400-1700) | 2100 | 2300 | 2600 | 2900 | 3300 | | [user:_istil,2026-03-27] | 800 | 1200 | (1300-1800) | 1900 | 2300 | 2500 | 2800 | 3300 | | [user:Dragos,2026-03-27] | 800 | 1400 | (1400-1900) | 1800 | 2100 | 2400 | 2800 | 3500 | | [user:Argentum47,2026-03-27] | 800 | 1300 | (1400-2000) | 1900 | 2200 | 2500 | ? | ? | | [user:simplelife,2026-03-27] | 800 | 1200 | (1200-1800) | 1600 | 2000 | 2500 | 6700 | 6700 | | [user:AksLolCoding,2026-03-27] | 800 | 1000 | (1100-1800) | 1600 | 1900 | 2400 | ? | ? | | [user:nik_exists,2026-03-27]...
$(a\cdot b)/\text{GCD}(a,b)$. However, note that the calculations will never overflow $64$-bit

Full text and comments »

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

18.
By greateric, history, 4 months ago, In English
Useless CP Information #7: How to Become an Assembly Bro (Assembly Tutorial Part 1) _If you were ever curious but were confused by the youtube tutorials. I'm going to try to make this as concise and useful as possible. Also, x86 is way easier to code in than ARM and if you disagree, you're wrong. And Intel syntax is better than AT&T syntax_ _This assumes you have a basic understanding of how pointers work in C_ First program & compiling ================== Make a file named `hello.s`: ~~~~~ .intel_syntax noprefix .section .rodata mystring: .ascii "Hello, World!\n" mystring_end: .section .text .globl main .type main, @function main: endbr64 push rbp mov rbp, rsp mov eax, 1 # write mov rdi, 1 # stdout lea rsi, mystring[rip] mov rdx, mystring_end - mystring syscall xor eax, eax leave ret ~~~~~ Compile and run with ~~~~~ $ gcc -o hello hello.s $ ./hello ~~~~~ In assembly, you are writing CPU instructions, so you only have access to low-level things: - Registers: the...
load integer into rsi 55a8 call printf 55b0 set exit code to 0 55b8 leave 55c0, to worry about overflow.

Full text and comments »

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

19.
By vovuh, history, 7 years ago, translation, In English
Codeforces Round #624 (Div. 3) &lt;almost-copy-pasted-part&gt; Hello! [contest:1311] will start at [contest_time:1311]. You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially. The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests &mdash; just like you will be upset if many solutions fail after the contest is over. You will be given 6 or 7 (or 8) problems and 2 hours to solve them. Note that **the penalty** for the wrong submission in this round (and the following Div. 3 rounds) is **10 minutes**. [Remember] (/blog/entry/59228) that only the <i>trusted participants of the third division</i> will be included in the ...
turned out that in the problem C, such a test exists that the answer overflows 32-bitinteger type, integer type (int). Since such a test was not in the test set, many participants made such a mistake

Full text and comments »

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

20.
By dmkozyrev, history, 7 years ago, translation, In English
Быстрый поиск глупых ошибок на C++ кратко и с примерами **Чтобы найти ошибку в коде нужно просто...** [cut] $$\text{ }$$ Первым делом нужно проверить переполнения типов данных, ошибки вроде `=` вместо `==`, то, что вы записываете значение `long long` в переменную `int`, и многое другое. Предупредить возникновение некоторых глупых ошибок можно включением всех предупреждений компилятора. Экстренно проверить код можно [по этой ссылке](https://godbolt.org/z/H7iLd9), там есть примеры. Необходимо заменить код из примера на свой код, дождаться компиляции и пофиксить все проблемные места. Предупреждения не являются ошибками, но могут ими все-таки быть из-за невнимательности. [Описание предупреждений есть тут](https://codeforces.me/blog/entry/15547). <spoiler summary="Список использованных предупреждений"> ``` -Wall -Wextra -pedantic -std=c++17 -O3 -Wshadow -Wformat=2 -Wfloat-equal -Wconversion -Wlogical-op -Wshift-overflow=2 -Wduplicated-cond -Wcast-qual -Wcast-align -D_GLIBCXX_DEBUG -D_GLIBCXX_DEBUG_PEDANTIC ``` </spoiler> З...
`10000000 10000000` вы увидите следующее ```runtime error: signed integer overflow: 10000000, ``` #include int main, ``` #include int64_t val, res, Firsly, you can check overflow of integer types, mistakes like `=` instead `==`, writing a `long, On testcase `10000000 10000000` you will see nexr: ```runtime error: signed integer overflow, overflow of integer types, mistakes like `=` instead `==`, writing a `long long` value in `int` and, Для теста `10000000 10000000` вы увидите следующее ```runtime error: signed integer overflow

Full text and comments »

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

21.
By SPyofgame, history, 6 years ago, In English
Counting nonegative integer solutions of two variables Linear Diophantine Equation ### The equation A Linear Diophantine Equation is an equation of the general form: $\underset{i = 1}{\overset{n}{\Sigma}} (a_i \cdot x_i) = N$ Where $a_i$ and $N$ are given integers and $x_i$ are unknown integers. ---------- ---------- ### The problem Given Linear Diophantine Equation of only 2 variables: $ax + by = c$ With given integers $a, b, c$ and unknown integers $x, y$ <spoiler summary="Some interesting property"> - The equation only have solution when $c$ is a mutiple of $g$ where $g$ is [the greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor) of $a$ and $b$ - When there is a solution $(x, y)$ satisfy $ax + by = c$. We also have $(x + kv, y - ku)$ a solution of the equation (for arbitrary integer $k$ and quotients $u = \frac{a}{g}$ , $v = \frac{b}{g}$) </spoiler> We have to count the number of $(x, y)$ non-negative integers solutions for the equation (assume that these value are under $10^9$ so that we dont dea...
Counting nonegative integer solutions of two variables Linear Diophantine Equation, also have $(x + kv, y - ku)$ a solution of the equation (for arbitrary integer $k$ and quotients $u, that these value are under $10^9$ so that we dont deal with overflow cases$

Full text and comments »

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

22.
By I_love_Hoang_Yen, 12 years ago, In English
[GYM] ACM ICPC Vietnam National First Round 2014 — Solutions Following are unofficial solutions for all problems. [problem:100499A] ----------------- **Solution 1** The most obvious solution for this problem is to brute force all numbers, and check if it is a cool number. [My code](http://ideone.com/S5T6en) After running this code for several minutes, you should be able to get results for all $K \leq 9$. The only result for $K = 7$ is $3211000$, for $K = 8$ is $42101000$ and for $K = 9$ is $521001000$. From these results, you should be able to guess the result for $K = 10$ is $6210001000$. **Solution 2** There are many ways to optimize the above solution. The most standard way is to see that the sum of all digits is equal to K, thus if you restrict your brute force to exit when sum of digit is greater than K, you should get a solution which runs in around a few seconds. [problem:100499B] ----------------- Since all numbers are at most $10^7$, you can count number of occurrence of each value. [My code](http://ideone...
three parts: Integer, fraction and repeated fraction. Then add these parts together. When add these, So, to solve this problem, you need to split the number into three parts: Integer, fraction and

Full text and comments »

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

23.
By roycf123, 3 years ago, In English
Dealing with integers, evading precision errors in C++ This is my first time actually trying to contribute something, so please go easy on me.... Hello Codeforces! After a long time of search for a cure for precision errors in C++ while dealing with just integers, I was motivated to write a blog for a curated collection of one. Sure some common ones do already exist in the previous blogs, some really cool ones can be found while browsing other programmers' templates, but why not have a blog which saves the time of search and makes it easier for CP Enthusiasts to improve? I have implemented a few as follows (may include the common ones): 1) ceil(a/b) and floor(a/b): Handling negative division as well... ~~~~~ ll divceil(ll a,ll b){ return a/b+(a%b>0);} ll divfloor(ll a,ll b){ return a/b-(a%b<0);} ~~~~~ 2) power(a,b): ~~~~~ ll binpow(ll a,ll b){ ll res=1; while(b){ if(b&1) res*=a; a*=a,b>>=1; } return res; } ~~~~~ 3) Floor(logb(x)): ~~~~~ ll lg(ll x,ll b=2){ if(b==1...
integer range.

Full text and comments »

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

24.
By Malinovsky239, 14 years ago, translation, In English
Codeforces Round #140 Editorial ### [A div2. Where do I Turn?](http://codeforces.me/contest/227/problem/A) Let's consider cross product of vectors $\overrightarrow{AB}$ and $\overrightarrow{BC}$, which is equal to $\overrightarrow{AB_x} \cdot \overrightarrow{BC_y} - \overrightarrow{AB_y} \cdot \overrightarrow{BC_x}$. Sign of cross product defines sign of a sine of oriented angle between vectors (because cross product is also equal to $|\overrightarrow{AB}| \cdot |\overrightarrow{BC}| \cdot sin(\overrightarrow{AB}, \overrightarrow{BC})$), and that sign leads us to the correct answer. If cross product is equal to zero, then $A, B$ and $C$ lay on the same straight line. So the answer is <<TOWARDS>>. If cross product is more than zero, then answer is <<LEFT>>. And, at last, if it's less than zero, the answer is <<RIGHT>>. Also you should notice that the value of cross product doesn't fit 32-bit type, so you have to use 64-bit type in order to avoid integer overflow. [Implementation](http://pastebin.co...
64-bit type in order to avoid integer overflow.

Full text and comments »

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

25.
By Geothermal, history, 6 years ago, In English
AtCoder Beginner Contest 169 Unofficial Editorial I just did my first ABC in a while, so I decided to write up and share my solutions below. Feel free to leave questions in the comments! There were several questions this round that had the potential to create precision issues; however, the solutions below give approaches that sidestep those errors altogether. Sadly, I think compiling and testing my A prevented me from winning the round :( #A &mdash; Multiplication 1 Just multiply the numbers and print them out. It's not that hard. Time Complexity: $O(1)$. [Click here for my submission.](https://atcoder.jp/contests/abc169/submissions/13800320) --- #B &mdash; Multiplication 2 This turns out not to be quite as easy as the last problem. Multiplying numbers this large is actually a challenge in C++ because the result is likely to be greater than $2^{63}$, and thus will cause long long overflow. Thus, in C++, we can't just multiply the numbers and check if the result is greater than $10^{18}$. One possible appr...
is likely to be greater than $2^{63}$, and thus will cause long long overflow. Thus, in C++, we

Full text and comments »

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

26.
By Spheniscine, history, 7 years ago, In English
Notes on FFT / NTT, and the "ultimate" NTT with modulus > 9 * 10^18 Prerequisites: you need to be familiar with both [modular arithmetic](https://codeforces.me/blog/entry/72527) and Fast Fourier Transform / number theoretic transform. The latter can be a rather advanced topic, but I personally found [this article](https://cp-algorithms.com/algebra/fft.html) helpful. Note that there are some relatively easy optimizations/improvements that can be done, like precalculating the modular inverse of $n$, the "bit-reversed-indices" (can be done in $O(n)$ with DP), as well as the powers of $\omega_n$. Also useful is modifying it so that the input array length can be any power of two $\leq n$; some problems require multiplying polynomials of many different lengths, and you'd rather the runtime be $O(n \log n)$ over the sums of lengths, rather than (number of polynomials * maximum capacity). Also helpful is knowing how to use NTT to solve problems modulo $998244353$, like [problem:1096G] and [problem:1251F]. Note that for some problems it's easier to think of...
integers. Addition is complicated by possible overflow into the sign bit, thus the usual `if(x >= m) x, may overflow even 64-bit integer types. 2. Do FFT with complex numbers and floating point types, * Choose integer $k$ such that $2^k > m $. $k = 63$ works for our modulus. * Precompute, . Restoring the result with CRT requires either brute force or multiplications modulo $pq$, which mayoverflow

Full text and comments »

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

27.
By Ripatti, 15 years ago, translation, In English
Solutions for Codeforces Beta Round #74 <p><b>A div2</b>. In this problem you can <span id="result_box" class="short_text" lang="en"><span title="Нажмите, чтобы увидеть альтернативный перевод" class="hps">simulate the</span> <span title="Нажмите, чтобы увидеть альтернативный перевод" class="hps">process. You can consider all minutes and in </span></span><span id="result_box" class="short_text" lang="en"><span title="Нажмите, чтобы увидеть альтернативный перевод" class="hps">dependence by a color of a current cablecar decrease size of </span></span>corresponding group of students $G$ by<span id="result_box" class="short_text" lang="en"><span title="Нажмите, чтобы увидеть альтернативный перевод" class="hps"></span></span> $min(|G|,2)$, where $|G|$ is size of the group. After that you should determine the first minute $t$ in that all three groups of students will be empty. So $t+30$ is an answer. This solution works in $O(r+g+b)$.<br>[cut]<br>Also there is $O(1)$ solution. It is following formula: $ans = max(3[(R+1)/2] + 27, 3[...
$ diamonds from every odd cell, where $c$ is some integer. $c$ lies in range from $-min\{a[i], i\text, Be careful fith overflow of 32bit integers. Here you should use an 64bit integers. D div2

Full text and comments »

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

28.
By rng_58, history, 11 years ago, In English
Returned to TopCoder as a competitor I was an admin of TopCoder for about 4 years. Recently I came back as a competitor and I participated in four SRMs. Here are my performances: #### SRM 681 Hard: CoinFlips It was an easy DP, but I started to implement something stupid and wasted time. When I finished coding around 5 minutes before the end of the contest, the server was slow and I couldn't compile my solution. Though the match was unrated, I should have solved it earlier. #### SRM 682 Hard: TheKFactor My solution failed because of precision errors (in Linear Programming). I should have used long doubles instead of doubles (and passed in the practice room). #### SRM 683 Hard: RandomWalkOnGrid Failed systest because of two (!) stupid mistakes: incorrect array size and integer overflow. #### SRM 684 Hard: Permutant Missed cases with a.size() == 1. Failed systest again. It's really important to keep participating in TopCoder matches. Now I can't solve anything!
because of two (!) stupid mistakes: incorrect array size and integer overflow. #### SRM 684 Hard, Failed systest because of two (!) stupid mistakes: incorrect array size and integer overflow.

Full text and comments »

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

29.
By ACGN, history, 2 years ago, In English
About 2031C (Penchick and BBQ Buns, problem C of CF Round 987), and extra challenges Author of the problem [problem:2031C] here, hope you enjoyed the contest yesterday (Almost exactly 24 hours ago...)! Looking at the votes on [the editorial](https://codeforces.me/blog/entry/136260), it's obvious that it's a very polarizing problem: an hour or so after the contest, the problem had roughly equal numbers of "likes" and "dislikes", and now (as of writing) there are around 320 likes to 200 dislikes. Of course, this is completely predictable: the opinions on this problem were quite polarized for a few reasons: 1. Troll and WA trap: it's **very** easy to fall into the trap of thinking that there is no solution for all odd $n$; thus, **over 12,900** (!) WA on pretest 2 solutions were received, as compared to only 4,700ish Accepted solutions. This ratio seems a bit extreme for a problem C; in the previous Div.2's problem C ([problem:2028C]), there were 3,500ish Rejected solutions to 2,500ish Accepted ones. 2. The construction: hard-coding the case $n=27$ seems weird an...
$. For general $n$, let $m$ be the greatest integer such that $n-27\ge 2m^2$. Then we can cover the

Full text and comments »

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

30.
By quasisphere, 10 years ago, In English
Fast convolution for 64-bit integers Fast convolution for 64-bit integers ==================================== Warning: Math ahead. You can find my reference C++ implementation at https://github.com/quasisphere/conv64 Introduction ------------ Let $(a_0,\dots,a_{n-1})$ and $(b_0,\dots,b_{n-1})$, $n \ge 1$, be two tuples of elements of some ring $R$. By their convolution we mean the tuple $(c_0,\dots,c_{2n-2})$ whose elements are given by $$c_k = a_{0} b_{k} + a_{1} b_{k-1} + \dots + a_{n-1} b_{k-n+1}.$$ (Here we understand that $a_{i} = b_{i} = 0$ for $i < 0$ or $i \ge n$.) A succinct way of encoding this is via polynomials: If $A(x) = a_{0} + a_{1} x + \dots + a_{n-1} x^{n-1}$ and $B(x) = b_{0} + b_{1} x + \dots + b_{n-1} x^{n-1}$, then $$A(x) \cdot B(x) = C(x) = c_{0} + c_{1} x + \dots + c_{2n-2} x^{2n-2}.$$ Convolution can thus be understood via multiplication of polynomials and vice versa. From this point on we will exclusively work with polynomials instead of tuples since that is much more ...
not overflow, and we can deduce the result of the original multiplication., the Fast Fourier Transform. The same method can also be applied to polynomials withinteger, zero-pad the polynomial (so that no cyclic overflow occurs).

Full text and comments »

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

31.
By willy108, history, 3 years ago, In English
Teamscode Spring 2024 Contest Official Editorial Sorry for the long wait. These problems were brought to you by [user:esomer,2024-04-05], [user:danx,2024-04-05], [user:dutin,2024-04-05], [user:jay_jayjay,2024-04-05], [user:oursaco,2024-04-05], [user:superhelen,2024-04-05], [user:thehunterjames,2024-04-05], [user:willy108,2024-04-05], and [user:yash_9a3b,2024-04-05]. Also, massive thanks to [user:omeganot,2024-04-05] for his [unofficial editorial](https://codeforces.me/blog/omeganot) (which was posted a lot sooner than ours). [Novice A/](https://codeforces.me/gym/105066/problem/A)[Advanced A: It's Time to Submit](https://codeforces.me/gym/105067/problem/A) ================== <spoiler summary="Solution"> Both "YES" and "NO" are consistent answer (as long as exactly one of them is the answer). If you print "YES" and get AC, you are getting AC by printing the sample output. If you print "NO" and get AC, you are getting AC by not printing the sample output. Never assume just because the carrot is big ... the sample out...
case. Be careful of integer overflow.

Full text and comments »

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

32.
By Asakire, history, 10 months ago, In English
Modulo and Integer arithmetic Recently i went through few modulo and integer arithmetic section from a website I am writing this as recap for myself but it might help beginners who are unfamiliar with Modular arithmetic A few basic observations ======================== If a mod b = 0, then a is divisible by b. This single condition appears in an enormous number of problems, from basic number theory to constraints checking. Another common use is determining parity. `If n mod 2 = 0, the number is even`; `if n mod 2 = 1, it is odd`. Whenever a problem involves alternating behavior, parity, or splitting elements into two groups, modulo 2 is usually the first thing worth checking. Modulo and cyclic behavior ========================== One important property of modulo is that it naturally creates cycles. The values of n mod 5, for instance, repeat as `0, 1, 2, 3, 4, 0, 1, 2, 3, 4, ....` This is extremely useful in practice. Circular arrays, rotating turns, and repeating patterns can all be handl...
Modulo and Integer arithmetic, often leads to overflow and incorrect results., return ML (Memory limit error due to overflow while doing the pow), . Multiplying first and taking modulo at the end often causes overflow, while applying modulo during, Recently i went through few modulo and integer arithmetic section from a website I am writing, overflow even 64-bit integers. By reducing both numbers modulo m first, then multiplying, and finally

Full text and comments »

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

33.
By alan-c, 11 months ago, In English
C++ Modular Integer Template Performance Analysis A _modular integer template_ implements basic integer operations that wrap around when they reach some modulus. There are many ways to do this, but some ways are slower. This article compares the performance of different methods. ## Summary For the best performance: - Addition of two modular integers should be done **without** modulo operations. - Any modulus operation (using %) should be done using **unsigned** integer types. Speed comparison, extensions, and other operations are discussed later. ## Basic template For simplicity, I'll use a fixed prime modulus $M$. If you need multiple moduli at the same time then you can extend this using a c++ template parameter. This is the simplest and easiest to implement, but it's slower. ~~~~~ using ll = long long; struct BasicMint { int n; BasicMint(ll m = 0) : n(m % M) {} BasicMint operator+(BasicMint m) { return BasicMint(n + m.n); } BasicMint operator*(BasicMint m) { return BasicMint((ll)n * m.n...
C++ Modular Integer Template Performance Analysis, expression will not overflow. However, a modular integer template would need to perform 2 modular, operation because we see the whole expression will not overflow. However, a modularinteger template

Full text and comments »

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

34.
By marat.snowbear, 12 years ago, In English
Codeforces Round #269 Editorial [problem:471A] ------------------ Given six sticks and their lengths we need to decide whether we can make an elephant or a bear using those sticks. The only common requirement for both animals is that four leg-sticks should have same length. This means that the answer "Alien" should be given **only** if we can't find four sticks for the legs. Otherwise we will be able to make some animal. The type of the animal will depend on the relation of the remaining sticks' lengths. If they are equal then it will an elephant, if they are different we will have a bear. So this algorithm should solve the problem: 1. Find the number which appears at least four times in the input. 2. If no such number exist then the answer is "Alien". 3. Otherwise remove four entries of that number from the input. 4. After removing that number you will have two numbers left, compare them and decide whether it's an elephant or a bear. One shortcut for this problem might be to sort the in...
array. This number might be very large and it might easily overflow even long integer type. And what is, give non-decreasing array. This number might be very large and it might easily overflow even long

Full text and comments »

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

35.
By polosatic, history, 4 years ago, translation, In English
Interpolation of a multivariable polynomial, or how to guess a formula Hello, Codeforces. I wrote a prorgam using [this theorem](https://en.wikipedia.org/wiki/Combinatorial_Nullstellensatz?wprov=srpw1_1) for interpolation a function as a polynomial. At first, I will explain how does it work and then show some examples of using it. Wikipedia does not provide one formula I need, so I will show it <spoiler summary="Formula"> If there are now monomials with all exponents more or equal than our exponents, the coefficient with our monomial can be calculated by formula ![ ](/predownloaded/03/5e/035e5f0089c741b747d1816e0c773d0eaa138529.png) </spoiler> Code is quite long, but simple in use. How to use program ------------------ At first, you need to set values of constants. N is the number of variables, MAX_DEG is the maximal exponent of a variable over all monomials. In `main` you need to fill 2 arrays: names contains the names of all variables, max_exp[i] is the maximal exponent of the i-th variable, or the upper_bound of its value. Define...
code it returns an integer, but its type is ld to avoid ll overflow., returns an integer, but its type is ld to avoid ll overflow.

Full text and comments »

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

36.
By Spheniscine, history, 20 months ago, In English
Unofficial Editorial — Dilhan's Computing Contest 1 [Partial, P1~4 + P5S1] Contest hosted on DMOJ [https://dmoj.ca/contest/dcc1](https://dmoj.ca/contest/dcc1) ### [P1 &mdash; The Cathedral of Learning](https://dmoj.ca/problem/dcc1p1) <spoiler> If $a > b$, the answer is `NO`, as Alice always goes up and Bob always goes down. Otherwise, $a \leq b$, and the answer is `YES` if and only if the parity (oddness or evenness) of $a$ and $b$ is equal (equivalently, that $b - a$ is even). This is because the difference between them reduces by $2$ each step, and if the difference is odd, they'll end up on neighboring floors and then pass and miss each other on the next step. Time complexity: $O(1)$ </spoiler> ### [P2 &mdash; Square Sum](https://dmoj.ca/problem/dcc1p2) <spoiler> Assume that $A \leq B$ (otherwise, swap them). Now let's count the valid pairs $(a, b)$ where $a + b = c^2$ for some non-negative integer $c$. Let's also define a useful function $\displaystyle P(n) = \sum_{i = 1}^{n} i^2 = \frac {n(n+1)(2n+1)} {6}$, representing the sum of th...
://en.wikipedia.org/wiki/Square_pyramidal_number). Note that computing this mightoverflow a standard 64-bit integer, overflow a standard 64-bit integer type, so you either need to use [modular inversion](https

Full text and comments »

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

37.
By Egor, 14 years ago, In English
CHelper 3.9 I would really appreciate any new ideas of what new features to add I would also appreciate [donations](https://money.yandex.ru/embed/shop.xml?account=410011732687384&quickpay=shop&payment-type-choice=on&writer=seller&targets=CHelper&targets-hint=&default-sum=100&button-text=03&successURL=) ----- 3.99 Kattis support for both Chrome and Contest parsers. You'd need to accept new permissions for Chrome extension. Good luck at ACM ICPC World Finals online contest! ----- 3.98 Codechef fix ----- 3.97 Fixed issue with template selection and Chrome plugin interaction ----- 3.96 Smallish update &mdash; you can now select task template per task. You can have several templates for general tasks, one where you need to output with Case #, GCJ where you need to integrate parallelization and similar ----- 3.95 Support for Idea 14.1+ Parsers for RCC and USACO fixed You can now parse other Codeforces contests when live contest is ongoing Sorry fo...
find errors such as unitended integer overflow and others. Support is turned off by default, you can, ://code.google.com/p/cojac/). This is to help find errors such as unitended integer overflow and others

Full text and comments »

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

38.
By Spheniscine, history, 6 years ago, In English
[AtCoder] Unofficial HHKB Programming Contest 2020 Editorial ### [A &ndash; Keyboard](https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_a) <spoiler> Basically, just do what it says in the problem statement. The function to turn a character uppercase is `std::toupper(t)` in C++, `Character.toUpperCase(t)` in Java, `t.toUpperCase()` in Kotlin, or `t.upper()` in Python. </spoiler> ### [B &ndash; Futon](https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_b) <spoiler> Iterate through every row and column. If the current square is `.`, look at the neighbor to the right, if it's also `.`, increment the answer. Likewise the neighbor downward. There is no need to look leftward or upward as those positions would already have been counted. </spoiler> ### [C &ndash; Neq Min](https://atcoder.jp/contests/hhkb2020/tasks/hhkb2020_c) <spoiler> Initiate an array of booleans indexed over $[0, 1 + \max p]$. Maintain a pointer $j$ starting at index $0$. Iterate through $p$. In each iteration, mark the corresponding index as "true", then use ...
may overflow even a 64-bit integer, thus it's important to [calculate them under modulo as well, overflow even a 64-bit integer, thus it's important to [calculate them under modulo as well](https

Full text and comments »

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

39.
By neal, 8 years ago, In English
Blowing up unordered_map, and how to stop getting hacked on it C++ has always had the convenient data structures `std::set` and `std::map`, which are tree data structures whose operations take $O(\log n)$ time. With C++11, we finally received a hash set and hash map in `std::unordered_set` and `std::unordered_map`. Unfortunately, I've seen a lot of people on Codeforces get hacked or fail system tests when using these. In this post I'll explain how it's possible to break these data structures and what you can do in order to continue using your favorite hash maps without worrying about being hacked [cut] . So how are they hackable? We always assume hash maps are $O(1)$ per operation (insert, erase, access, etc.). But this depends on a key assumption, which is that each item _only runs into $O(1)$ collisions on average_. If our input data is completely random, this is a reasonable assumption. But this is no longer a safe bet when the input isn't random, especially so if someone is adversarially designing inputs to our code (a.k.a. hacking ph...

Full text and comments »

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

40.
By skywalkert, history, 7 years ago, In English
2018 CMUT BeihangU Contest, Editorial This editorial corresponds to [contest:102114] (stage 5), which was held on Aug 6th, 2018. Moreover, this problem set was also used as Jingzhe Tang Contest 1 in Petrozavodsk Winter Camp on Jan 30th, 2019. **This post is now finished**, in which I try to elaborate on notes, solutions and maybe some data generating. Alternatively, you can refer to [an old published material](https://drive.google.com/file/d/1CFumWbNLTUEywkVDNF-LKT3SzYd1r15L/view), though I think the old English version did not explain something clearly. --- [problem:102114A] This problem requires to calculate $s$-$t$ min cut between any two vertices on a weighted cactus graph having $n$ vertices, denoted by $\mathrm{flow}(s, t)$. You need to report $\sum_{s < t}{(s \oplus t \oplus \mathrm{flow}(s, t))}$. $n \leq 10^5$, $\sum{n} \leq 10^6$, weights are $\leq 10^9$. Try to find some features of this graph. <spoiler summary="solution"> By contradiction, we can prove that for an undirected graph, each ed...
should be careful with $64$-bit integer overflow. , )$ rather than $\mathcal{O}(m \log w)$. --- [problem:102114B] Given an integer $n$, you

Full text and comments »

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

41.
By oweMeEternity, 11 months ago, In English
A Guide to Debugging Runtime Errors with Compiler Sanitizers We have all been there. You submit your solution, wait anxiously, and then see the dreaded Runtime Error on test 2. Is it an array out-of-bounds index? A signed integer overflow? A null pointer dereference? Usually, you have to stare at your code or add a dozen printf statements to find out. But there is a better way. ![ ](https://i.ibb.co.com/8g1j2NT9/Screenshot-2025-12-25-172753.jpg) ![ ](https://i.ibb.co.com/s9yBm35K/Screenshot-2025-12-25-16503f5.jpg) ![ ](https://i.ibb.co.com/ynHZFnPG/Screenshot-2025-12-25-165035.jpg) By using compiler sanitizers and debug flags, you can make your compiler tell you exactly which line caused the error and why. Here is how to set up a powerful debugging environment on both Linux and Windows. ### For Linux Users Linux makes this incredibly easy with GCC. Instead of your standard compilation command, use the following flags to catch errors at runtime. `g++ -g -O2 -fsanitize=undefined -fsanitize=address -fno-omit-frame-pointer -D_GLIB...
Error on test 2. Is it an array out-of-bounds index? A signed integer overflow ? A null pointer, , such as signed integer overflows, division by zero, and invalid bitwise shifts. - **-fsanitize

Full text and comments »

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

42.
By alex_rider123, 7 months ago, In English
Freshers' CodeNite 2026 Hello everyone! Thanks for participating in the contest! Link to access the contest: [Freshers' CodeNite 2026](https://codeforces.me/contestInvitation/aa6ac1740a448d12475ec188f62b8321d4499580) Below are the hints and solutions for all the problems. --- ### [Illu Hopping](https://codeforces.me/gym/683650/problem/A) **Author:** [user:rakshit_ranka,2026-04-11] <spoiler summary="Hint"> Try to write out the pattern for small values of n and k and observe when you get stuck in invalid cycles. What are the gaps between the numbers in the invalid cycles? </spoiler> <spoiler summary="Tutorial"> There are 2 valid approaches to the problem under the given constraints. **Approach 1:** You may simulate the process of jumping and mark the visited halls using an array or set. When you reach a hall already visited check if the number of halls visited is n. **Approach 2:** This problem is a classic application of modular arithmetic. It is a known mathematical property that...
sums and the final answer to avoid integer overflow.

Full text and comments »

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

43.
By reiracofage, 15 years ago, In English
Some ideas for Round #95 (Div 2) <p>Hi, these are just some ideas of what I did to solve the problems in #95 (div 2). They're just what I did, better solutions may exist and will be very welcome!<br />Also, sorry if I wrote something wrong, English isn't my first language.<br />Also, (a b) is a choose b (a!/(b!(a-b)!)).<br /><b><br />Problem A</b><br /><br />Just do what the statement asks you to. Check if all letters are uppercase, except for the first one, that you don't need to check. If so, change the case of the entire string. If not, do nothing. Please notice that an one-letter string must have its case changed.</p><p>It can be easly done in O(n), where n is the lenght of the string.<br /><br /><b>Problem B</b><br /><br />First, let <i>count(i) </i>be the numbers of occurrences of the number <i>i</i> in the input,<br />&nbsp;&nbsp;&nbsp; for<i> -10 &lt;= i &lt;= 10</i>. Remember that there may be negative numbers in the input, so one can use an offset to store these values (use an 21-sized array <i>C</i> and sto...
compute it with the traditional formula, if its implementation takes care of possibleoverflow (30, overflow (30! doesn't fit in 64-bit integer type). Problem D A graph

Full text and comments »

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

44.
By Spheniscine, history, 7 years ago, In English
Modular Arithmetic for Beginners Introduction ------------------ If you're new to the world of competitive programming, you may have noticed that some tasks, typically combinatorial and probability tasks, have this funny habit of asking you to calculate a huge number, then tell you that "because this number can be huge, please output it modulo $10^9 + 7$". Like, it's not enough that they ask you to calculate a number they know will overflow basic integer data types, but now you need to apply the modulo operation after that? Even worse are those that say you need to calculate a fraction $\frac pq$ and ask you to output $r$ where $r \cdot q \equiv p \pmod m$... not only do you have to calculate a fraction with huge numbers, how in the *world* are you going to find $r$? Actually, the modulo is there to make the calculation *easier*, not *harder*. This may sound counterintuitive, but once you know how modular arithmetic works, you'll see why too. Soon you'll be solving these problems like second nature. Terminol...
know will overflow basic integer data types, but now you need to apply the modulo operation after that, modulo as often as needed to avoid integer overflow. You may even decide to wrap them into their own, , it's not enough that they ask you to calculate a number they know will overflow basic integer data

Full text and comments »

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

45.
By jeqcho, history, 6 years ago, In English
Alternative approaches to ceil() Sometimes we need to compute the division of an integer rounded up (ie by ceiling, not by rounding those with remainder $r \geq 0.5$). For example, $\lceil 3/2 \rceil = \lceil 1.5 \rceil = 2$ and $\lceil 13/3 \rceil = \lceil 4.333 \rceil = 5$. TLDR, use `(a+b-1) / b` or other approaches below. #### Typical approach If we want to do this in C++, we can call the `ceil()` function, but with caution. For the example above, ~~~~~ int a = 3; int b = 2; cout << ceil(a/b) << endl; >>>> 1 ~~~~~ Note that it prints out 1, not 2! This is because a and b are `int` data types, so that their quotient `a/b` is in `int` and the decimal values are discarded (floored). `a/b` = `1` so `ceil(a/b)` = `ceil(1)` = `1`. We can simply overcome this by casting the `double` data type so that the decimal values are kept during intermediate calculations. ~~~~~ cout << ceil( (double) a / (double) b) << endl; >>>> 2 ~~~~~ **But wait!** Some people think that using `double` is a risky ap...
used instead of `(a + b - 1) / b` to prevent integer overflow when `a` and `b` is large. However, it, `(a - 1)/b + 1` is used instead of `(a + b - 1) / b` to prevent integer overflow when `a` and `b

Full text and comments »

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

46.
By alexvim, history, 2 years ago, translation, In English
Montgomery/Barret reduction and NTT [Performance optimization] $\DeclareMathOperator{\ord}{ord}$ $\DeclareMathOperator{\mod}{mod}$ Montgomery/Barret reduction and NTT ================== **In this article** it will be shown how to apply Montgomery/Barret reduction of modular arithmetic to Number Theoretic Transform and combinatorial tasks. We will implement NTT with minimum of modular operations that beats classic FFT both in precision and speed. We will compare the performance of various optimizations of NTT and FFT in complex field. Also it will be shown how to add support of negative coefficients to NTT and replace FFT. 1. Why use NTT ------------------ DFT (Discrete Fourier Transform) is widely used for polynomial multiplication. DFT can be calculated in every field such that there is nth root (element with order n). For instance, we can use complex numbers or numbers modulo some $p$ (finite field). Widely known realization &mdash; Fast Fourier Transform &mdash; calculates DFT in $O(n\log{n})$ both in complex numbers and in...
with reductions because of trick with overflow: it doesn't lead to undefined behavior but returns, , if we are given polynomials with non-negative integer coefficients to multiply, we are able to use

Full text and comments »

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

47.
By -739397, 18 months ago, In English
10x Your CP Workflow: A Smooth Bash Script to Automate Parsing, Testing, Stressing and many more # 10x Your CP Workflow: A Smooth Bash Script to Automate Parsing, Testing, Stressing and many more Hello Codeforces fam, Over the past few months, I've been building and using a personal tool that **completely automates** my competitive programming workflow. From **parsing** problems to **checking solutions**, **stress testing**, **debugging**, and even **validating edge cases** — this tool has made my life 10x easier and smoother. And now, I’m excited to share it with you so that you can boost your productivity! ## What is this tool? It’s a **template-driven Bash script** designed to integrate with [Competitive Companion](https://github.com/jmerle/competitive-companion) and streamline everything — whether you're solving problems on **Codeforces, AtCoder, LeetCode, CodeChef**, or anywhere else. With just one command, you can: - Parse problems - Compile and run code - Switch between fast and debug modes - Stress test using a brute-force checker - Validate solutio...
(e.g., -DLOCAL -fsanitize=address -fsanitize=undefined -fsanitize=signed- integer-overflow, =address -fsanitize=undefined -fsanitize=signed-integer-overflow -D_GLIBCXX_DEBUG). This helps

Full text and comments »

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

48.
By hzzt_2004, 3 weeks ago, In English
Intra-Pilani Educational Contest : Editorial Thanks for participating! This is the first iteration in a series of educational contests held in BITS Pilani, Pilani Campus. The editorial for all seven problems is below. Open the hints one at a time before reading the rest. Contest link -> https://codeforces.me/contestInvitation/3ad0b848ae9e772cb849a80f90943647a6ee9b6c The problems were authored by [me](https://codeforces.me/profile/hzzt_2004), and tested by [user:keeshu,2026-10-26] and [user:Ultimateyagyik22,2026-10-26] Congratulations to the top 3: [user:sidat,2026-10-26], [user:ameasa,2026-10-26], [user:jagannathpisharody,2026-10-26]! <hr/> <b>A. AAAAAAAAAAAAAA</b> <spoiler summary="Hint 1"> Write the first few screaming numbers in decimal and see how each one relates to the previous one. </spoiler> <spoiler summary="Hint 2"> Adding one more digit $A$ on the right changes the number in a simple way. Can you simulate that directly, keeping everything modulo $10^9+7$? </spoiler> <spoiler summary="Obser...
-bit integer, so use long long.

Full text and comments »

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

49.
By Jakube, history, 8 years ago, In English
Avoid overflow in linear diophantine equation: I solved [problem:986F] today and faced the following problem. You had to solve a linear diophantine equation: $$a \cdot x + b \cdot y = c$$ This is of course quite easy, with the extended Euclidean algorithm you can find a solution: $$a \cdot x_0 + b \cdot y_0 = g$$ and by multiplying with $c / g$ gives a final solution: $$a \cdot (x_0 \cdot c / g) + b \cdot (y_0 \cdot c / g) = c$$ And all solutions can be written as $$a \cdot (x_0 \cdot c / g + k \cdot b/g) + b \cdot (y_0 \cdot c / g - k \cdot a/g) = c$$ The problem is, that this can easily give an integer overflow. E.g. when $a$, $b$ and $c$ are as large as $10^{18}$. To solve the problem I just took my BigInteger implementation. But this is of course quite ugly (400 additional lines of code just for one simple calculation). How can we avoid the overflow? I want a solution for $a \cdot x + b \cdot y = c$ with $|x|, |y| \le 10^18$. I found the following code in the solution of [user:tourist,2018-06-04]....
Avoid overflow in linear diophantine equation:, \cdot c / g - k \cdot a/g) = c$$ The problem is, that this can easily give an integer overflow, The problem is, that this can easily give an integer overflow. E.g. when $a$, $b$ and $c$ are as

Full text and comments »

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

50.
By madhur4127, history, 8 years ago, In English
Avoid silly overflow mistakes taking modulo in C++ TL;DR This article features `Modular` class which can be conviniently used for modular arithmetic more "naturally". #### Motivation Recent round featured an interesting problem [problem:1081C] (if you plan to solve it, read this later). Combinatoric solution requires you to calculate: $$ \displaystyle \binom{n-1}{k}m \left( m-1 \right) ^{k} \mod 998244353 $$ Many contestants failed pretest because of missing modulo operation somewhere in code. #### Solution Many contestants use functions like `add(ll a, ll b)` or `mul(ll a , ll b)` which makes implementation somewhat clumsy. I present you an alternate approach using `Modular` class. --- ~~~~~cpp template <int MOD=998'244'353> struct Modular { int value; static const int MOD_value = MOD; Modular(long long v = 0) { value = v % MOD; if (value < 0) value += MOD;} Modular(long long a, long long b) : value(0){ *this += a; *this /= b;} Modular& operator+=(Modular const& b) {value += b.value; if ...
Avoid silly overflow mistakes taking modulo in C++

Full text and comments »

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

51.
By halyavin, 11 years ago, In English
Educational Codeforces Round 10 Challenge Overview. 652A &mdash; Gabriel and Caterpillar ------------------------------ I have lost count of number of different challenges in this problem. Only 14 author tests for such a tricky problem were clearly not enough. There were 2 types of challenges. The first type use integer overflow. When I saw that both <i>h</i><sub>1</sub>, <i>h</i><sub>2</sub> and <i>a</i>, <i>b</i> are bounded by 10<sup>5</sup> I suspected that overflow could be a problem. But my solution divided heights by speeds to get the number of days. Surely there are no need to multiply these quantities I thought. Boy I was wrong. A lot of solutions used a simulation of the process. As long as <i>a</i> &gt; <i>b</i> and the caterpillar is going up, there is no problem. But if the caterpillar is going down, you need to give up eventually and return -1. The largest positive answer is about 10<sup>5</sup>/12 but the largest lose of height per day is about 12&middot;10<sup>5</sup>. The product is about 10<sup>10</sup> &gt; 2<...
clearly not enough. There were 2 types of challenges. The first type use integer overflow. When I saw, The first type use integer overflow. When I saw that both h1, h2

Full text and comments »

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

52.
By AVdovin, history, 3 years ago, In English
What is wrong with system tests and hacks? Hello, Codeforces! First of all, I would like to emphasize, that I am writing this post not out of fury or disappointment, but I just want to verify, if there are anyone who share my POV. Yesterday [contest:1923] was held. And I liked it! Problems were very nice and interesting. But one thing happened, that is still on my mind. My [B](https://codeforces.me/contest/1923/problem/B) got [FST](https://codeforces.me/contest/1923/submission/247902606) (Failed System Tests). For those unfamiliar with this system, I'll explain it to you. When you send your code, during round it works on some relatively small tests set, after the contest is finished your last successful submission for each problem is retested on expended tests set (it also includes all successful hacks). This system exists to lessen delays in testing queue. In my mind the problem behind this system is that during the round you see if your code failed some test, and you can find an issue and fix it, but after the end of the...
the contest you can't. In my case, i got FST caused by integer overflow, which is not quiet fair to, In my case, i got FST caused by integer overflow, which is not quiet fair to my mind. No, it's

Full text and comments »

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

53.
By Harly24, history, 5 weeks ago, In English
A C++ debug header that prints anything, and a build that names the line you crashed on Hi Codeforces! A mod bug in my combination code recently cost me two wrong submissions on a Div. 3 problem C. Stripped down, it was this: ```cpp const int MOD = 1e18 + 7; // "big enough that I never need a real mod" ... fact[i] = fact[i - 1] * i % MOD; ``` `fact[i - 1] * i` overflows `long long` long before the `% MOD` runs, and the program happily printed garbage. Here is the same code in my current setup, first run, sample input: ``` ✗ Runtime error: UB trap, one of • signed overflow: a * b or a + b too big for long long • 1 << j with j >= 31: write 1LL << j • x / 0 or x % 0 • C-array index out of range → line 12: fact[i] = fact[i - 1] * i % MOD; ``` This post is about the pieces behind that: a debug header that prints anything you give it, and a build that catches the mistakes the judge only reports as "Wrong answer on test 2". Everything is on GitHub: [harly24-cp](https://github.com/Abhayanthk/harly24-cp). It works with any editor; I...
-integer-overflow,shift,integer-divide-by-zero,bounds -fsanitize-trap=all \ -Wall -Wextra -Wshadow, ``` g++ -std=c++20 -O1 -g1 -DLOCAL -D_GLIBCXX_DEBUG \ -fsanitize=signed-integer- overflow

Full text and comments »

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

54.
By drazil, history, 10 years ago, In English
Editorial of Weekly Training Farm 21 **Update** Editorial of PF is published. PA This is a relatively simple problem. We only need to check if the sum of the lengths is larger than $m$ times $60$. 簡單題。判斷所有的歌曲長度加起來有沒有大於 $m$ 的 $60$ 倍。 PB This problem is asking the index of the very next Fibonacci number. The takeaway point is that there is only a small amount of Fibonacci numbers in the range of 32-bits integer. Also, overflow needs to be considered if you choose to use 32-bits integer instead of 64-bits data types. 這題是在問下一個費波那契數列中數字是第幾個。一個小重點是 32 位元整數範圍內的費波那契數列很稀少。另外如果使用 32 位元非 64 位元資料型態的話,那必須考慮溢位的問題。 PC https://en.wikipedia.org/wiki/Great-circle_distance https://zh.wikipedia.org/wiki/大圓距離 PD We binary search the answer. To check if time $T$ is sufficient, we check the maximum flow of the following new constructed graph: Firstly, we split every vertex $v$ in the original graph into $2 \times t$ vertices in the new graph $(v, dir, t)$ where $dir \in {in, out}$ and $t$ is the time index st...
there is only a small amount of Fibonacci numbers in the range of 32-bits integer. Also, overflow needs, , overflow needs to be considered if you choose to use 32-bits integer instead of 64-bits data types

Full text and comments »

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

55.
By dendi239, history, 6 years ago, In English
Micro- and macro-management for your next cpp source: For Hello, codeforces! In this article, I would like to show you how to reduce time spent on working with `for` cycle. There're a few ways to do it, I'll show macro-based and expressible in pure c++. # Introduction I love `for` cycle. It looks quite simple: ~~~~ for (init statement; condition; increment) ~~~~ But you can adapt it to do many great things. To illustrate the power of `for`, let's look at the simple binary search problem: we have some values `l`, `r` and a predicate `p` which is true on segment `[l, x]` and false on `(x, r)`, and we are asked to find x. Using `for` we can implement the solution in basically just one line: ~~~~~ for (int m = (l + r) / 2; abs(r - l) > 1; (p(m) ? l : r) = m, m = (l + r) / 2); ~~~~~ Pretty neat, huh? After the cycle finishes, you'll get `l = x`. Another important note, the `(p(m) ? l : r) = m` part works because ternary operator returns reference type. It means that `(is_left ? left : right) = new_value;` assigns `ne...
huge `a` and `b` (not fitting into `int` for example), then you will get integer overflow for `i`. To, you will get integer overflow for `i`. To resolve it, you could use `decltype` expression to get the

Full text and comments »

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

56.
By avnithv, 18 months ago, In English
TJIOI 2025 Editorial Congratulations to all the teams that participated in TJIOI 2025 in both the in-person contest and online mirror! To view the problems, first join the Codeforces group: [https://codeforces.me/group/nHKRGA8qo6](https://codeforces.me/group/nHKRGA8qo6). The results of the in-person contest can be found at [https://activities.tjhsst.edu/tjioi](https://activities.tjhsst.edu/tjioi). ##### Cookie Tower (In-person only) Idea: [user:Atvaster,2025-05-23] Preparation: [user:Atvaster,2025-05-23] <spoiler summary="Problem"> Cookie Monster is playing with his three cookies, which have distinct sizes $a$, $b$, and $c$, respectively. He wants to create a cookie tower by stacking them up. Cookie Monster wants the largest cookie to be on the bottom (for a strong foundation). However, he wants the top of the tower to be big as well, so he wants to place the second largest cookie on top and the smallest cookie in the middle. Given the sizes of Cookie Monster's cookies $a$, $b$, and $c$...
binary exponentiation algorithm, as well as utilizes 128-bit integers to avoid overflow with the scale, "> Define a fixed point as an integer $i \in [1, n]$ such that $a_i = i$. Let $f(a)$ be the number of

Full text and comments »

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

57.
By ToxicPie9, 23 months ago, In English
It's almost 2025, why are you still choosing GCC 7 (32-bit)? This is my answer to https://codeforces.me/blog/entry/137484, in which [user:-is-this-fft-,2024-12-20] asked a bizarre question. This answer is too big for a comment so I made a blog post instead. ## The question The submission [submission:297353626] behaves normally with 180 MiB memory usage while [submission:297352244] got a runtime error due to stack overflow (with 256 MiB stack). Both submissions have identical code, don't seem to contain bugs, and an assertion exists to make sure the recursion is at most $2\times10^5$ layers deep. What's happening? ## TL;DR Notice that the solution with stack overflow uses GCC 7 (32-bit) while the accepted ones use GCC 13 (64-bit). This is not a coincidence. The main reason of unreasonable stack usage boils down to two points: GCC 7, and 32-bit. ## 32-bit First of all, the code is compiled and run in 32-bit mode. Compiling the submission with GCC 7.5 in 32-bit on [godbolt](https://godbolt.org/z/WT9WsdeW4) shows that the `lo...
usage while [submission:297352244] got a runtime error due to stack overflow (with 256 MiB stack). Both

Full text and comments »

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

58.
By jeqcho, history, 6 years ago, In English
Problem Solving Guide to Modular Combinatorics and Exponentiation Sometimes, you are asked to calculate the combination or permutation modulo a number, for example $^nC_k \mod p$. Here I want to write about a complete method to solve such problems with a good time complexity because it took me a lot of googling and asking to finally have the complete approach. I hope this blog can help other users and save their time when they solve combinatorics problem in Codeforces. #### Example Problem Find the value of $^nC_k$, ($1 \leq n,k \leq 10^6$). As this number can be rather large, print the answer modulo $p$. ($p = 1000000007 = 10^9 + 7$) #### Combination (binomial coefficients) $^nC_k$ means how many ways you can choose $k$ items from an array of $n$ items, also denoted as $\binom{n}{k}$. This is also known as binomial coefficients. The formula for combination is $$ ^nC_k = \frac{n!}{k!(n-k)!} $$ Sometimes, the denominator $k!(n-k)!$ is very large, but we can't modulo it since modulo operations can't be done independently on the denomina...
Exponentiation To prevent integer overflow, we can carry out modulo operations **during** the evaluation, To prevent integer overflow, we can carry out modulo operations **during** the evaluation of our

Full text and comments »

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

59.
By michel, history, 3 years ago, In English
Avoid WA by integer overflow In the last contest ([contest:1941]), while solving the problem [problem:1941F], I got WA on my [first attempt](https://codeforces.me/contest/1941/submission/250788723). On debugging, I found this bit of code was problematic ``` const int INF = 1 << 30; // this is equal to 1073741824 ``` I've always used this as my infinite value for integers, but it was not large enough in this case. **Note 1**: _Be sure your infinity is actually an upper bound for your problem_ Well, I made `INF` large enough and submitted it again [submission:250809384]. WA. Can you spot the issue in my code? I was pretty sure that I didn't need to make every integer 64 bits so that the problem passed. But I did it and it passed. **Note 2**: _If doubtful, go ahead and make every `int` a `long long int`. It's ok for CP; avoid the unsuccessful submission penalty_ The bug in my code was pointed out to me by Codeforces when I played a bit more after the contest [submission:250815419]. And it's so si...
Avoid WA by integer overflow, issue in my code? I was pretty sure that I didn't need to make every integer 64 bits so that the, ? I was pretty sure that I didn't need to make every integer 64 bits so that the problem passed. But

Full text and comments »

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

60.
By Dhaval_kumar, history, 5 years ago, In English
DesCode 4.0 ## Details **Date:** 29th January 2022 **Time:** 03:00 pm to 06:00 pm **Platform:** codeforces **By:** The Society of Coders, IIIT Naya Raipur **For:** BTech Students **Contest Link:** [DesCode 4.0](https://codeforces.me/contestInvitation/8bab3f0bf9445dcdd6c5eaa5618bc7380e5ed685) We would like to express our great gratitude to: - [user:monkedluffy,2022-01-29], [user:sonicBoom,2022-01-29], [user:shinigami_09,2022-01-29] and [user:momotaroUWU,2022-01-29] for the coordination of the round and preparing problems. - [user:Yoks1729-,2022-01-29] and [user:sandesh_04_06,2022-01-29] for testing the round and providing useful feedback. - [user:MikeMirzayanov,2022-01-29] for cool platforms Codeforces and Polygon. This contest had 3 hours to solve 8 problems. ## Editorial Thanks for participating, hope you enjoyed the problems! Please do not hesitate to provide feedback, so we can improve in setting problems next time. #### Problem &mdash; A : [Majnu Ki M...
Consider the edge case ($a_{i}$ $=$ $0$) and integer overflows, result, then the answer is $NO$ cause $n$ must be an integer, otherwise the answer is $YES$ and the

Full text and comments »

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

61.
By witua, 15 years ago, translation, In English
Codeforces Beta Round #91 - Analysis <div><b>1. [[problem:122A,Lucky Div (Div2 A)]]</b></div><div><br /></div><div>In this problem you just need to loop through the integers $i$ from $1$ to $n$ determine, is $i$ lucky, if yes, then try, if $n$ mod $i$ = $0$, then answer is &quot;YES&quot;. If there are no such $i$, answer is &quot;NO&quot;.</div><div><br /></div><div><b>2.&nbsp;[[problem:122B,Lucky Substring (Div2 B)]]</b></div><div><br /></div><div>Notice, that answer is either one digit or -1. So, if there are no $4$ and $7$ digits, then answer is -1. Else, if there is more or equel number of digits $4$, then answer is $4$, else answer is $7$.</div><div><br /></div><div><b>3.&nbsp;[[problem:121A,Lucky Sum (Div1 A + Div2 C)]]</b></div><div><br /></div><div>Let generate all lucky number between $1$ and $10^10$. Consider all segment&nbsp;$[1; L0]$, $[L0+1; L1]$, $[L1+1; L2]$ ... Then the result equals to product of intersection of segments&nbsp;$[1; L0]$ and $[1; n]$ by $L0$ plus size of intersection of $[L0+1; L1]$ and &n...
permutation (suffix) we need to find $k$-th permutation of number from $1$ to $t$ ($t$ is maximuninteger

Full text and comments »

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

62.
By djay24, history, 4 years ago, In English
Memory Limit Exceeded Error when defining pragma #define int long long int else Accepted While up solving [F &mdash; Dasha and Nightmares](https://codeforces.me/contest/1800/problem/F) I came across an unusual error. It's been more than six months now I'm practicing writing #define int long long int pragma at the start of my code, I never faced any issues except today. I submitted 2 codes, when I write #define int long long int it's giving MLE error but if I removed that line it's getting accepted. I'm using GNU C++20 (64). Although both code are running fine in my sublime text editor. ### MLE : ~~~~~ #include <bits/stdc++.h> #define int long long int const int MAXN = 26; int cnt[1 << MAXN]; void solve(){ std::ios::sync_with_stdio(false); std::cin.tie(0); int n; std::cin >> n; std::vector<std::pair <int, int>> vals; for (int i = 0; i < n; i++) { std::string s; std::cin >> s; int cor = 0, cxor = 0; for (char c : s) { int v = (c - 'a'); cor = cor | (...
followed in general so there is not an integer overflow ? Thank you :) , What practice should be followed in general so there is not an integer overflow ?

Full text and comments »

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

63.
By Maxim, 8 years ago, translation, In English
Binary search on real values What does a typical binary search in real values look like? Like this: ~~~~~ float l = 0.0f, r = 1e14f; for (int i = 0; i < iteration_count && l + eps < r; ++i) {     float mid = 0.5f * (l + r);     if (check(mid))         r = mid;     else         l = mid; } ~~~~~ Here `l` and `r` are the boundaries that depends on the condition, `check (x)` is a function that returns true starting from some x and false before x and we need to find this x. As a rule, `l` or `0.5 * (l + r)` is the answer. But there are several disadvantages: 1. The number of iterations must be choosed balancing between the precision and the execution time. 2. Answer with an error. ### What can be done with this? First, let's take a look at how real values are represented. You can read in detail, for example, [here] (https://en.wikipedia.org/wiki/Single-precision_floating-point_format) and [here] (http://www.volkerschatz.com/science/float.html). We use the fact that if we perform the operati...
both interpretations. - `l + r` may overflow, therefore `l + (r - l) / 2` instead of `(l + r) / 2, integer whose bitwise representation is the same as X (returns the same X interpreted as aninteger

Full text and comments »

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

64.
By amartya110, 8 months ago, In English
Editorial for CodeHurdle Athlos 03 We want to thank you all for participating in the contest, and hope you enjoyed it. Any feedback would be appreciated! [Contest Link](https://codeforces.me/contestInvitation/757663ba04187f27abf08bbf2fa40710f1777b4f) ### [A — Modular Station Assembly](https://codeforces.me/gym/677155/problem/A) Writer: [user:amartya110,2026-01-19] <spoiler summary="Editorial"> Even Dimensions: If $n$ or $m$ is even, the grid can be perfectly tiled using only $1 \times 2$ I-Beams, making the answer YES.Thin Grids: If $n=1$ or $m=1$ (and the other is odd), the C-Core module cannot fit physically as it requires a $2 \times 3$ footprint, leaving an odd area that $1 \times 2$ beams cannot fill (NO).Small Odd Grids ($3 \times 3$): Although the area is 9, placing a $2 \times 3$ footprint C-Core in a $3 \times 3$ space creates geometric obstructions that prevent the remaining 4 cells from forming two valid $1 \times 2$ blocks (NO).Large Odd Grids: For all other odd $n, m \ge 3$, there is sufficient...
> \frac{2y}{2x + 1}$. To find the smallest valid integer $a$, we calculate $a = \lfloor \frac{2y}{2x, }$. To find the smallest valid integer $a$, we calculate $a = \lfloor \frac{2y}{2x + 1} \rfloor + 1

Full text and comments »

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

65.
By amartya110, history, 9 months ago, In English
Editorial for CodeHurdle Athlos 02 We want to thank you all for participating in the contest, and hope you enjoyed it. Any feedback would be appreciated! [Contest Link](https://codeforces.me/contestInvitation/c9482c2d71d0b5cdc04841221671e06b827c1e07) ### [A — Costly Divisibility](https://codeforces.me/gym/670769/problem/A) Writer: [user:amartya110,2026-01-19] <spoiler summary="Editorial"> In this case any $a[i]>=b[i]$ for all $(1<=i<=n)$, you can easily make a[i]%b[i]==0 by decreasing the value of a[i] or increase the value of b[i] with cost 0, and otherwise the cost is the absolute difference between a[i] and b[i]. </spoiler> <spoiler summary="Solution"> ```c++ #include <bits/stdc++.h> using namespace std; #define faster ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define testcase int t; cin>>t; for(int i=0;i<t;i++) #define ll long long int ll lcm(ll a, ll b) { return (a / __gcd(a, b)) * b; } void solved(){ /*start*/ ll n; cin>>n; vecto...
$[2, \sqrt[i]{x}]$.To prevent integer overflow during the calculation of $a^i$, we use a safe, binary search in the range $[2, \sqrt[i]{x}]$.To prevent integer overflow during the calculation of $a^i

Full text and comments »

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

66.
By greateric, history, 5 months ago, In English
Should UBSan be allowed as an optional compiler option during contest? In practice our C++ solutions get to be run with Undefined Behavior Sanitizer, also known as the diagnostics, which catch things like bad memory accesses from out of bounds array indices and integer overflows. I think we should be allowed to enable this during a submission during an actual contest. You'd have a checkbox at the bottom that says something like "enable diagnostic checks (warning: code may run much slower)" where you can choose to enable it or not. Is this unfair? I don't think so, UBSan is basically just a souped up template and you can achieve the same effect with one. You would be able to get the same effect by jamming `assert(result of addition did not overflow)` before every addition or having a template safe int / safe long class that does that for you or `__builtin_add_overflow`. Of course, you shouldn't be told the line number or what the problem was, just runtime error should be sufficient. (Since if you do it yourself the only information you get is that a ...
diagnostics, which catch things like bad memory accesses from out of bounds array indices andinteger

Full text and comments »

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

67.
By e-maxx, 16 years ago, translation, In English
Codeforces Beta Round #30. Tutorial for problem A <h1>Tutorial for problem "A. Accounting"</h1><h3>First solution: naive brute</h3><p>Let's brute all possible values of $X$, and check each of them. It's easy to understand, that $X$ will be constrained in the same limits as values $A$ and $B$, that is, from -1000 to 1000 inclusive (obviously, there exists a test for each such $X$, so we can't decrease these limits).</p><p>When we have some fixed value of $X$, we check it simply by multiplying $A$ by $X$ $n$ times. But, you should be careful with possible integer (and even 64-bit integer :) ) overflow. For example, you should stop multiplying by $X$ if the currect result exceeds 1000 by absolute value already.</p><h3>Second solution: formula</h3><p>It's easy to note, that if solution exists, then it is $n$-th root from $|B|/|A|$ fraction, with changed sign if $A$ and $B$ have different signs and if $n$ is odd (if $n$ is even, then no solution exists). That's why we could just use pow() function (or some analog in your language) to calcu...
with possible integer (and even 64-bit integer :) ) overflow. For example, you should stop multiplying, . But, you should be careful with possible integer (and even 64-bit integer :) ) overflow. For example

Full text and comments »

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

68.
By dlu, history, 3 years ago, In English
Hello World (1926G Solution) Hi everyone! I'm not sure that I'll be posting here very often, but I'll be mainly outlining interesting solutions to hard problems or just noting something worthwhile to think about for competitive programming. Although I recently promoted to the Silver division in USACO, I managed to fail horribly in solving graph problems. Before I was promoted, I also saw this issue from past Codeforces contests, especially in problem C (see [problem:1830A]). A recent example is [problem:1926G], which I couldn't manage to solve in-contest. After trying to upsolve it and looking at the main solution, I still didn't get how dynamic programming portion over the three types of water functioned. After a very long time searching up other solutions, I suddenly got inspired to do dp over whether music was played or not at a particular node. I wrote down all of the details of the dp because being a newbie, I do not see the solution very clearly. **Solution** Denote a p-node as a node tha...
=0, n=1?), integer overflow, etc. -WHEN IN DOUBT, USE LONG LONG -check the for loops -watch out, ? -CHECK YOUR CODE -pay attention to BOUNDS -errors - out of bounds, edge case(n=0, n=1?),integer

Full text and comments »

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

69.
By Mr.Quantum_1915, 10 months ago, In English
Editorial for CCxEnigma: Tesseract '26 (IIIT Vadodara) Tesseract '26 Editorial ================== Hello Everyone! Hope you enjoyed **[CCxEnigma: Tesseract '26](https://codeforces.me/blog/entry/150726)** conducted by [IIITV Coding Club](https://iiitvcc.vercel.app/home) and Mathematics Club at IIIT Vadodara. Thank you for participating in the contest. Hope you had fun solving the problems with the new Sandbox twist :) This was the first time a reverse coding event was hosted in this **style**! _Feel Free to give some feedback in comments whether you **liked** it, suggestions for **improvement**, or ideas for the **Next** Edition :)_ Here are the official tutorials for the problems. Access the Sandbox here &mdash; [_SANDBOX_](https://tesseract-2k26.vercel.app/sandbox) ### [Problem A: DDR4 Shortage](https://codeforces.me/gym/668703/problem/A) Author: [user:Mr.Quantum_1915,2026-02-01] <spoiler summary="Hint"> Try entering aa and aaa in the sandbox. aa (Length 2) $\to$ 2a (Length 2). No space is saved, so i...
1.999999999999999999 will overflow standard integer type., Compare chunks from left to right as Integers (or numerical strings to avoid overflow).

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

70.
By CristianoPenaldo, history, 4 years ago, In English
Atcoder 279G-At most 2 colors: Generating functions [Second-hand, Newbie Oriented]. **Part1: Introduction** [Atcoder Beginner Contest 279](https://atcoder.jp/contests/abc279) is good for learning [generating functions (GFs)](https://en.wikipedia.org/wiki/Generating_function). GFs could solve two of them (G and Ex). The English version tutorial of [279Ex](https://atcoder.jp/contests/abc279/tasks/abc279_h) has already been posted on the [MathStackExchange](https://math.stackexchange.com/questions/4586327/sum-of-product-of-min-which-is-related-to-the-pentagonal-number-theorem) by a kind person. Unfortunately, the English tutorial on [279G](https://atcoder.jp/contests/abc279/tasks/abc279_g) is not available. Now I would like to make a second-hand tutorial on [279G](https://atcoder.jp/contests/abc279/tasks/abc279_g) based on [PCTprobability's idea](https://atcoder.jp/contests/abc279/editorial/5293). I spend a huge amount of time understanding this idea. For contestants at about my level, it is quite difficult to understand [the idea](https://atcoder.jp/contests/abc27...
<< (c + ((1ll*c*(c-1))%998244353)*xinv[n-2]())%998244353 << "\n"; //Care about integer overflow, ))%998244353)*xinv[n-2]())%998244353 << "\n"; //Care about integer overflow! Remember to add c for the

Full text and comments »

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

71.
By YouKn0wWho, 7 years ago, In English
[Editorial]Contest Based on SUST Intra University Programming Contest 2019 [A. Perfect Points](https://toph.co/p/perfect-points) Author: [user:YouKn0wWho,2019-12-20] <spoiler summary="Tutorial"> Here $$y=m(c+1)+c: \; c \geq 1 $$ $$ \rightarrow y \mod (c+1) = c: \; c \geq 1 $$ $$ \rightarrow y \mod c = c-1: \; c \geq 2 $$ $$ \rightarrow (y+1) \mod c = 0: \; c \geq 2 $$ Note that $m \geq 1$, so $(y+1) > c$. So we can say that $ (y+1) \; is \; composite: \; y \geq 1$ So $K^{th}$ value of $y$ is ($K^{th}$ composite number $-1$ ). How can we find it given that $K \leq 10^9$? <spoiler summary="Hint"> - [Prime Counting Function](https://codeforces.me/blog/entry/57826?fbclid=IwAR084Ea_mN7LFqr-LLooQrtJQ8jiN5g7W3PvA1_JnHuVOsHrj0DH4UIKqTo#comment-414818) - Binary Search </spoiler> </spoiler> <spoiler summary="Solution"> ~~~~~ #include<bits/stdc++.h> using namespace std; #define pii pair<int,int> #define pll pair<ll,ll> #define eb emplace_back #define ll long long #define nl '\n' #define deb(x) cerr<<#x" = "<<x<<nl #define i...
<=n;i++) cout<<<" \n"[i==n]; return 0; } ///Before submit=> /// *check for integer, integer overflow,array bounds /// *check for n=1 ~~~~~

Full text and comments »

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

72.
By Lgdony, history, 9 days ago, In English
What It Felt Like to Be Purple for Less Than 24 Hours Hello, Codeforces! I remember a day last year when there was a contest scheduled at an unusual time, right in the middle of my school day. That day, I left school early and went home to participate in the contest. During that contest, I solved A-C at a good pace. At minute 38, I submitted a solution for D that was logically correct, with integer overflow being its only issue. (I usually had `#define int int64_t` in my code, but I had removed it in that particular submission.) However, after eventually finding the bug and getting D accepted (which took quite a while), I lost my motivation and couldn't properly focus on the remaining problems. I believe that if this hadn't happened, I would have been fully capable of solving the entirety of E during the contest. (Later that same day, after the contest, when I was in a calmer state of mind, I solved it very quickly.) That would have given me the rank I needed to reach CM in that round. <a href="https://imgflip.com/i/b5e37z"><i...
solution for D that was logically correct, with integer overflow being its only issue. (I usually had, was logically correct, with integer overflow being its only issue. (I usually had `#define int

Full text and comments »

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

73.
By drazil, 12 years ago, In English
Codeforces Round #272 Editorial First I want to thank all the problem solvers!<br> Hope you had or are going to have a good time with Dreamoon!<br> If you think there's something that can be improved in this editorial please let me know!<br> Definitions used in this editorial:<br> $\lceil\rceil$ stands for ceiling function.<br> $\lfloor\rfloor$ stands for floor function.<br> $\frac{a}{b}$ stands for real division.<br> For non-negative integer $a$ and positive integer $b$, $div(a,b)$ stands for integral division, $div(a,b)=\lfloor\frac{a}{b}\rfloor$.<br> For non-negative integer $a$ and positive integer $b$, $mod(a,b)$ stands for module operation, $a=div(a,b)*b + mod(a,b)$.<br> $length(string)$ is the length of $string$.<br> For non-negative integer $a \leq b$, $A[a..b]$ stands for the set of $A[a], A[a+1], A[a+2] \dots A[b-1]$ when $A$ is an array and the substring of $A$ consists of $a^{th}$ to $(b-1)^{th}$ character(inclusive) of $A$ when $A$ is a string. For such substring we have $length(A[a..b])=b-...
notice that if an integer $x$ is $nice$ it can only be $nice$ for a single particular $k$ because a, > For non-negative integer $a$ and positive integer $b$, $div(a,b)$ stands for integral division

Full text and comments »

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

74.
By TheOpChicken123, history, 4 years ago, In English
This question is taking over my mind! Please help. I have been recently doing this problem: https://codebreaker.xyz/problem/truck . Please read it before reading my question. I have written code for it which has a time complexity of O(nlogn + q * logn) which should be sufficient to solve the question. Also, my code passes the two example testcases given in the problem statement. However, when I submit my code, it fails EVERY SINGLE other testcase. I have been debugging my code for almost a week now, trying to see if I am getting integer overflow anywhere, or if my logic is wrong. But i simply haven't found anything. I am asking you guys, PLEASE, for the sake of my sanity, help me solve my problem. My code: https://pastebin.com/fnWh1Xbc Definitions: Even though tolls are assigned to edges, I'm going to assign nodes tolls instead. Namely, the toll of a node is the toll of the edge from its parent, to itself. Also, total distance of some node a is the distance from the root to a. Total toll of some node a is the sum of tolls fr...
my code for almost a week now, trying to see if I am getting integer overflow anywhere, or if my, to stop integer overflow.

Full text and comments »

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

75.
By Redpo, 3 years ago, In English
[C++] Some programming language tips and tricks Hello, Codeforces! Here are some language tips and tricks I have discovered that could (hopefully) help you write more concise or efficient code. Note that all of the below tips are specific to the C++ programming language and the STL library. ## Creating a `std::set` or `std::map` from sorted data in $O(n)$ time The sorted containers `set` and `map` are usually implemented as red–black trees, meaning that their `insert` operation runs in $O(\log n)$ time by default. Naturally, repeating the `insert` operation $n$ times would result in a time complexity of $O(n\log n)$. ~~~~~ vector<int> a = /* ... */; set<int> s1; for (int e : a) { s1.insert(e); } // O(n log n) ~~~~~ However, `set` and `map` also provide a constructor method, that directly constructs the data structure from a given pair of iterators. In most implementations of C++, if the data contained within the range is already sorted, the constructor instead runs in $O(n)$ time. ~~~~~ vector<int> a = /* some...
considerable degree. - `div` and `lldiv` (``): takes two integer arguments (int for div, long, - `div` and `lldiv` (``): takes two integer arguments (int for div, long long for lldiv

Full text and comments »

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

76.
By VeniVidiVici, 12 years ago, In English
Why do users make multiple accounts? I will attempt to explain why I think people do this, and hopefully start a serious examination of how to deal with the problem... ~~~~~ struct Warning{ long long story; }; ~~~~~ Label: Meet Bob. Bob has always been a pretty bright individual. Deciding that he should use his intelligence for good, Bob decided to put his skills to the test. As Bob knows, people use computers for programming. Because Bob owns a computer, he figures he must be a programmer as well. So Bob decided he was going to create the best game ever &mdash; one that would inspire a generation of children to waste their lives chasing pixels &mdash; solely with the power of his mind. Absolutely sure of how to continue, Bob promptly opened up the command prompt. This made sense to Bob because he once saw a monospaced screen in a movie where some dude hacked the government in 90 seconds. He proceeded to type in his masterpiece: ~~~~~ open a new window make the background look like trees put a guy w...
for integer overflow. Bob was on the top of the standings. Nobody would solve problem E that contest, mortals in their place by exploiting their mistakes, such as integer overflow, incorrect bounds on, their mistakes, such as integer overflow, incorrect bounds on their binary searches, tricky n=1 cases

Full text and comments »

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

77.
By gkcs, history, 11 years ago, In English
The other end of the telescope To try and understand the psychology of a problem solver, let us ask a few abstract questions: 1) Why do you like solving problems? 2) What is the biggest challenge you face when implementing your solution? 3) Which key area in your skill set can you improve simultaneously along with problem solving? The answers to the first question are very interesting: Contestants swear about how much they love math/algorithms and designing data structures. I have **never** heard someone say : "Oh, I _love_ checking for integer overflows!" or "Finding the maximum in an array is so _awesome_!". And yet, we find ourselves stuck doing these exact same things, again and again, till our minds are trying hard to stick to the original problem while our fingers frantically type out the code. So we have an answer to our first question. We solve problems to challenge our mind, to sooth our egos by looking at green ticks and savour the adrenaline coursing through our veins when we are put in cr...
: "Oh, I _love_ checking for integer overflows!" or "Finding the maximum in an array is so _awesome_, checking for integer overflows!" or "Finding the maximum in an array is so _awesome_!". And yet, we

Full text and comments »

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

78.
By kirankumarmitra, history, 8 years ago, In English
Storing integers Can someone suggest any good resources to learn about how various integer data types are manipulated in C++ from a competitive programming perspective ? I'm having problems with understanding them, for example - When you do something like `long int x = y*z`, where `y` and `z` are `long long int`, but the value of `y` and `z` are small (say 100), would it cause overflow ? - When you do something like `int x = (a*b) % prime` when `a, b, prime` are of the order $10^9$ (but still stored in int), would it cause overflow ? - What is the difference between double/point/long double etc ? How they're manipulated (like the above) ? - Does using longer (for example, using `long long int` instead of `int`) causes the programme to run slower ? If yes, then how much (like a factor of 2 ? a factor of 4 ?) - Why almost nobody uses long double in competitive programming ? - When manipulating digits of HUGE orders (like $10^500$), how that's done in CP ? - Why the strange result...
value of `y` and `z` are small (say 100), would it cause overflow ?, $ (but still stored in int), would it cause overflow ?, Can someone suggest any good resources to learn about how various integer data types are

Full text and comments »

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

79.
By Valiors, history, 8 years ago, In English
[Tutorial] Chinese Remainder Theorem **#IjustWantContribution** Hello Codeforces. In this post, I would like to introduce some of you to a very popular, yet maybe not fully understood technique called Chinese Remainder Theorem (CRT). I have seen many articles that present CRT in a way that lacks practical competitive programming approach (no info about how to handle overflows, how to implement it effectively, what to do when modulos are not coprime etc.) and derivation of the formulas seem like some sort of guesswork. The purpose of this article is to address this issue. **Problem and solution** You are given two pairs (main goal is to solve it for $t$ pairs) of integers $(a_1, n_1)$, $(a_2, n_2)$. **There is no assumption that $n_1$ and $n_2$ are coprime**. Find an integer $x$ that satisfies $$ \left\{ \begin{array}{c} x \equiv a_1 \pmod {n_1} \\ x \equiv a_2 \pmod {n_2} \end{array} \right. $$ This system of congruences implies that $$ \left\{ \begin{array}{c} x = a_1 + n_1k_1 \\ x = a_2 + n_2k_...
assumption that $n_1$ and $n_2$ are coprime**. Find an integer $x$ that satisfies $$ \left\{ \begin

Full text and comments »

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

80.
By _QuantumBifrost_, 20 months ago, In English
Faster Square Root Computation Using an Optimized Binary Search Hello there, welcome to my first Codeforces blog post! Today I’d like to share an educational — and frankly a fun observation — on optimizing the process of finding the square root of large integers using binary search. This may not be something you’d use in your everyday code (after all the built-in `sqrtll()` is hard to beat in speed), but it’s a neat mathematical trick that can literally save you seconds when processing many numbers. Before we dive in, a huge thanks to [user:chromate00,2025-03-13]. An answer of mine getting hacked in one of his contests sparked this discovery. --- ## Aim In a typical binary search algorithm for computing the integer square root of a number `S`, we initialize the search range with: - `low = 0` - `high = S` This approach finds the square root in **O(log(S))** iterations. But if we have to compute square roots for too many numbers (like $10^8$), it can become laggy. However, if we can choose `low` and `high` more intelligently based ...
. --- ## Aim In a typical binary search algorithm for computing the integer square root of a number `S, if (__builtin_popcountll(val) == 1) { // when theta is integer // when S is, if (__builtin_popcountll(val) == 1) { // when theta is integer i.e. // when

Full text and comments »

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

81.
By vaibhav1997, history, 9 years ago, In English
All the good tutorials found for Competitive Programming Here is the list of some of the good tutorials written by codeforces users :- **C++** - [C++ Tricks](http://codeforces.me/blog/entry/15643) by [user:Swift,2018-01-22] - [C++ STL: map and set](http://codeforces.me/blog/entry/9702) by [user:adamant,2018-01-24] - [C++ STL: Policy based data structures](http://codeforces.me/blog/entry/11080) by [user:adamant,2018-03-05] - [Competitive C++ Manifesto: A Style Guide](https://codeforces.me/blog/entry/64218) by [user:Swift,2019-03-04] - [Catching silly mistakes with GCC](https://codeforces.me/blog/entry/15547) by [user:andreyv,2019-03-04] - [About a general reader / writer for STL-Structures,](https://codeforces.me/blog/entry/71075) by [user:Arturgo,2020-12-20] - [Blowing up unordered_map, and how to stop getting hacked on it](https://codeforces.me/blog/entry/62393) by [user:neal,2020-12-20] - [C++ tips and tricks](https://codeforces.me/...
[user:dmkozyrev,2018-07-21] - [Avoid overflow in linear diophantine equation](http://codeforces.me/blog, [user:w33z8kqrqk8zzzx33,2020-12-20] - [[Tutorial] A powerful representation of integer sets](https

Full text and comments »

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

82.
By orz, history, 5 years ago, translation, In English
Fast modular multiplication Consider the following problem: given three integers $x$, $y$ и $m$, $0 \leqslant x,y < m < 2^{32}$, calculate $xy\bmod m$. The easy way is just to multiply these numbers and apply the modulo operation: ~~~~~ uint32_t prod(const uint32_t x, const uint32_t y, const uint32_t m) { return x * y % m; } ~~~~~ As you might have guessed, this solution is wrong. The thing is that an overflow is possible in such a procedure: the operation `x * y` is performed in the type` uint32_t`, and in fact the intermediate result of this operation will not be $xy$, but $xy\bmod2^{32}$. If after that we take the result modulo $m$, it may differ from the correct one: $$ \left(xy\bmod2^{32}\right)\bmod m\ne xy\bmod m. $$ The way out is simple — you need to multiply in a larger type: ~~~~~ uint64_t prod_uint64(const uint64_t x, const uint64_t y, const uint64_t m) { return x * y % m; } ~~~~~ If you do this, then, since $xy<2^{64}$, this product will definitely not overflow, and after tak...
% m; } ~~~~~ As you might have guessed, this solution is wrong. The thing is that anoverflow is

Full text and comments »

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

83.
By Chortos-2, 16 years ago, In English
A Solution of the Industrial Nim Problem <p><a href="http://codeforces.me/contest/15/problem/C">Industrial Nim</a> is the problem C of beta contest #15. Here I present and explain in detail an efficient solution of the problem that runs in time linear in $n$, which is at most $10^5$.</p> <p>[cut]</p> <p>First of all, notice that the problem statement mentions ‘a well-known game Nim’. It also describes the rules but not the winning strategy; yet you are asked to determine which player wins. All of this means that if you do not know anything related to the winning strategy, you can simply look up the <a href="http://en.wikipedia.org/wiki/Nim">Nim game on Wikipedia</a> and see if it has any useful information. It indeed does; specifically, you need to know that the winner in the Nim game, assuming both players play perfectly, is uniquely defined by the <a href="http://en.wikipedia.org/wiki/Exclusive_or">exclusive-or (XOR) sum</a> of the stone heap sizes: if the sum is zero, then the first player loses, otherwise the first pla...
avoid integer overflows but no dumper has more than $10^{16}+10^{16}-1 \approx 2^{54.15}$ stones, care to avoid integer overflows but no dumper has more than $10^{16}+10^{16}-1 \approx 2^{54.15

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

84.
By srsonia98, 3 years ago, In English
What you need to know about Least Common Multiple (LCM)? Least common multiple (LCM), typically denoted by lcm(a, b), is the smallest positive integer that is divisible by both a and b. Number theory dictates that the product of gcd(a, b) and lcm(a, b) is ab for positive integers, a and b ie lcm is simply absolute value of ab divided by gcd(a, b). When dealing with the greatest common divisor (GCD), the typical approach involves utilizing Bézout's identity, which builds upon the Euclidean theorem. Bézout's identity states that for integers a and b with a greatest common divisor d, there exist integers x and y such that ax + by = d. The extended Euclidean algorithm can be employed to compute a pair of Bézout coefficients efficiently. ~~~~~ static int gcd(int a, int b) { if (b == 0)return a; else return gcd(b, a % b); } static int lcm(int a, int b){ return Math.abs(a * b) / gcd(a, b); } ~~~~~ However, it's worth noting that this method may lead to integer overflow issues, particularly when dealing with larg...
worth noting that this method may lead to integer overflow issues, particularly when dealing with, However, it's worth noting that this method may lead to integer overflow issues, particularly when

Full text and comments »

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

85.
By gerasikoff, 5 months ago, In English
Wrong author solution in G The official solution for G is wrong: it overflows signed 64-bit integer. This is shown by these submissions: https://codeforces.me/contest/2241/submission/380753097 https://codeforces.me/contest/2241/submission/380758313 i mean Solution verdict: OK Checker: ok 1 number(s): "-8491303560709551616" is not okay, check my hacks. "Recently, your account was used to crawl. Please change your password to prevent your account from being used for unauthorized activities." is very stupid. I can't even hack.
The official solution for G is wrong: it overflows signed 64-bit integer.

Full text and comments »

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

86.
By 7etuPr0mK_X-VPA.8-ER1SYJ, history, 3 years ago, In English
Why unrated? I know many people think the problems are bad and want the contest unrated. I lost GM from this round too. But I think the problems are somehow ok. FSTs on A is avoidable, and using `long long` is actually very obvious. More low rated users FSTed than high rated users, so this is ok and I consider it as part of the problem. BCDEF are good(though I didn't solve E, and also I ignored m<=5000 in F). I know the std for G was wrong at first, but it's fixed quickly, which isn't a big problem. H would also be a good problem, if there isn't [oeis](https://oeis.org/). I noticed that many people had passed H when I was doing E, so I tried H in the last 1h. I nearly got the formula in the contest. Though I still think that authors should at least try to check on oeis before having problems like this, and they should also check for integer overflows for every problem. Hope to reach GM soon and good luck for everyone :)
this, and they should also check for integer overflows for every problem.

Full text and comments »

87.
By CodingKnight, 9 years ago, In English
Computing huge Binomial coefficients without overflow and without using the arithmetic modulus operator The following are C++11 classes `huge_unsigned` and `binomial_coefficient` for computing huge Binomial coefficients C( n, k ), where n and k are positive integers. The class implements the iterative multiplicative formula: ~~~~~ def binomialCoefficient(n, k): if k < 0 or k > n: return 0 if k == 0 or k == n: return 1 k = min(k, n - k) # take advantage of symmetry c = 1 for i in range(k): c = c * (n - i) / (i + 1) return c ~~~~~ reported in [Binomial coefficient](https://en.wikipedia.org/wiki/Binomial_coefficient) without **overflow**, and without using the **modulus** arithmetic operator. Items of the STL base class `vector< uint32_t >` are used to store the successive digits of a base-4,294,967,296 representation of C( n, k ). C( 32000, 16000 ) has been computed using 1000 huge_unsigned digits in 1.873 sec. on Intel Core i3 processor with 3 GB RAM running at 2.4 GHz. Comments and votes (like or do not like) are thankf...
Computing huge Binomial coefficients without overflow and without using the arithmetic modulus, **overflow**, and without using the **modulus** arithmetic operator. Items of the STL base class `vector

Full text and comments »

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

88.
By errorgorn, 5 years ago, In English
Pragma Insanity: Weird Behaviour with Pragma O3 Here is a simple problem. Count the number of array $A$ of non-negative integers size $N$ such that $\sum\limits_{i=1}^{N} A_i \cdot i=K$. Where $N,K \leq 5000$. Find the answer modulo $1000000007$. I unfortunately cannot share the link to a submissions page as it is on a private local judge. Update: I have asked judge devs of the local judge, the compile command is `g++ -O2 -o {compiledName} {sourceName} -m64 -static -std=gnu++14 -lm -s -w -Wall -Wshadow -fmax-errors=512` But anyways, here is the problem. <spoiler summary="AC code"> ~~~~~ #pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt") #include <bits/stdc++.h> using namespace std; #define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--)) const int MOD=1000000007; int n,k; int memo[5005]; int main(){ cin>>n>>k; memo[k]=1; rep(x,n+1,1) if (k>=x) rep(y,k+1,x){ assert(y-x>=0); memo[y-x]=(memo[y-x]+...
that perhaps it is overflow. And indeed, after changing `int memo[5005]` to `long long memo[5005

Full text and comments »

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

89.
By Eren-Jaeger, history, 4 years ago, In English
STL #1 Round Editorial Thanks for participating! <br> The top 5 contestants from this week's contest are: <br> 1. [user:Yashbanna,2022-06-12] 2. [user:Sandeep_Nitharwal,2022-06-12] 3. [user:Aditya_subramanian,2022-06-12] 4. [user:tushaar9876,2022-06-12] 5. [user:BrightHammer_07,2022-06-12] Great job guys! Here's the Editorial for the contest. Feedback of any kind is appreciated in the comments. <br> [A. Tea Queue](https://codeforces.me/group/ctEtdi2TSJ/contest/384561/problem/A) <spoiler summary="Tutorial"> Let's store the last moment when somebody gets a tea in the variable $lst$. Then if for the $i-th$ student $lst ≥ ri$ then he will not get a tea. Otherwise he will get it during max($lst$ + 1, $l_i$) second. And if he gets a tea then $lst$ will be replaced with the answer for this student. </spoiler> <spoiler summary="Solution"> [submission:159713776] </spoiler> [B. Eren and Armored Titan](https://codeforces.me/group/ctEtdi2TSJ/contest/384561/problem/B) <br> Prep...
equal to $2^{32}$ to the answer, it immediately becomes "OVERFLOW!!!". Thus let's push not the real, . Catch Overflow !](https://codeforces.me/group/ctEtdi2TSJ/contest/384561/problem/E)

Full text and comments »

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

90.
By pajenegod, history, 3 years ago, In English
Tutorial: A simple O(n log n) polynomial multiplication algorithm Hi Codeforces! I have something exciting to tell you guys about today! I have recently come up with a really neat and simple recursive algorithm for multiplying polynomials in $O(n \log n)$ time. It is so neat and simple that I think it might possibly revolutionize the way that fast polynomial multiplication is taught and coded. You don't need to know anything about FFT to understand and implement this algorithm. Big thanks to [user:nor,2023-07-10], [user:c1729,2023-07-10] and [user:spheniscine,2023-07-10] for discussing the contents of the blog with me and comming up with ideas for how to improve the blog =). I've split this blog up into two parts. The first part is intended for anyone to be able to read and understand. The second part is advanced and goes into a ton of interesting ideas and concepts related to this algorithm. Prerequisite: Polynomial quotient and remainder, see [Wiki article] (https://en.wikipedia.org/wiki/Polynomial_greatest_common_divisor#Euclidean_divi...
-quotient-and-remainder). ### Task: Given two polynomials $P$ and $Q$, an integer $n$ and a non

Full text and comments »

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

91.
By Betlista, 12 years ago, In English
No more int overflows in Java (Eclipse) I failed in contest [#280](http://codeforces.me/contest/492) because of int overflow. I knew I have to handle that, but I missed it :-( So I was looking for some automatic check. [cut] My Java IDE is Eclipse, so this tutorial is for Eclipse... Current Eclipse version I'm using is Luna (4.4.1), may be different, but similar in other newer/older versions... 1. From Eclipse Marketplace (Help > Eclipse Marketplace...) install FindBugs (search for "findbugs", current version of FindBugs plugin is 3.0.0) 2. when installed and Eclipse is restarted, from Window > Preferences in FindBugs preferences set minimum rank to max &mdash; 20 and confidence to min &mdash; low ![Eclipse FingBugs preferences](http://i.imgur.com/7b4qAhK.png) 3. As a last thing you have to set up from project properties (again FindBugs properties), that scanning is running automatically ![Eclipse FindBugs project properties](http://i.imgur.com/wRMoDu5.png) The result is then similar to: ![Fin...
![FindBugs — integer multiplication cast to long](http://i.imgur.com/3kHY0BC.png), I failed in contest [#280](http://codeforces.me/contest/492) because of int overflow. I knew I

Full text and comments »

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

92.
By Taha1506, history, 6 years ago, In English
overflow issue? I was solving [This](https://codeforces.me/problemset/problem/1477/B) problem and submitted [submission:106080441].I am getting runtime errors on test 4.The codeforces diagnoser says it is because it is of integer overflow I changed everything to long long but it gives me again the same error.Can anyone say Whats wrong with my code please?Thanks. Edit:Ok I got it I should have checked lx<a.size();
overflow issue?, it is of integer overflow I changed everything to long long but it gives me again the same error.Can

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

93.
By box, 5 years ago, In English
On the Min25 sieve and extensions / SPOJ ASSIEVE Consider the following problem (general form of original Min25 sieve): We are given some *multiplicative* function $f(n)$, described at prime powers by $f(p^k)=g(p,k)$, where $g(p,1)$ is a polynomial of low degree, and we can calculate $g(p,k)$ for any singular $p$ and $k$ in $O(1)$. How do we calculate the prefix sum of $f(n)$ at the distinct positive integer values of $\lfloor\frac Nk\rfloor$, where $N\le 10^{10}$? Clearly, brute force or regular sieves are not going to cut it here. --- Prerequisite: For any integer $N$, for all integers $1\le k\le N$ there are at most $2\sqrt N$ distinct values of $\lfloor\frac Nk\rfloor$. Call these $2\sqrt N$ such values the *blocks* of $N$. (A note on notation: In the following text, $\frac Nk$ will be used to describe regular division, and $N/k$ will be used to denote floored division.) <spoiler summary="Proof"> For $k\le\sqrt N$, each $k$ contributes at most one distinct value, for a total of $\sqrt N$ elements. For $k>\sqrt ...
we calculate the prefix sum of $f(n)$ at the distinct positive integer values of $\lfloor\frac Nk

Full text and comments »

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

94.
By JoshuaYang, history, 4 years ago, In English
Funny Example of Unsigned Integer Overflow Let's look at a simple block of code, specifically the conditional statement in the for loop ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { string s = "123"; string s2 = "12332"; for (int i=0; i<(s.size()-s2.size()); ++i) { cout << "WTF"; } } ~~~~~ You expect the for loop to not even run because `s.size()-s2.size()` is `-2`, right? Well turns out since size() or .length() is returned as an unsigned integer (makes sense in retrospect), when c++ executes `s.size() - s2.size()`, you end with a large positive integer ( specifically `18446744073709551614`) due to overflow because unsigned integers **cannot** be negative. Something FYI I learned today after debugging for ~30 min and thought was interesting to share. Peace out, JY out.
Funny Example of Unsigned Integer Overflow, since size() or .length() is returned as an unsigned integer (makes sense in retrospect), when c, turns out since size() or .length() is returned as an unsigned integer (makes sense in retrospect

Full text and comments »

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

95.
By stgatilov, 16 years ago, translation, In English
Codeforces #47 problem solutions <p><em><strong>Problem A</strong></em>: Answer is floor(N*M*0.5). Since there is N*M cells on the board and each domino covers exactly two of them we cannot place more for sure. Now let's show how to place exactly this number of dominoes. If N is even, then place M rows of N/2 dominoes and cover the whole board. Else N is odd, so cover N-1 row of the board as shown above and put floor(M/2) dominoes to the last row. In the worst case (N and M are odd) one cell remains uncovered.<br>[cut]<br><em><strong>Problem B</strong></em>: Of course you were expected to code solution which is not quadratic in time complexity. Iterate over the string and count how many times each char is used. Let K<sub>i</sub> be the number of occurrences of char with ASCII-code i in the string S. Then answer is sum(K<sub>i</sub><sup>2</sup>). While coding the solution the following common mistakes were made:<br><br>1. Code quadratic solution (double loop over the string)<br>2. Forget to use int64. Whether in answer...
when copy/pasting it into the test editor. Of course the overflow in solution disappears after it

Full text and comments »

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

96.
By niklasb, 13 years ago, In English
Dynamic Programming on Integers I wrote a post about [how to tackle certain problems on numbers using dynamic programming techniques](http://stackoverflow.com/questions/22394257/how-to-count-find-integers-between-large-a-and-b-with-a-certain-property/22394258) over at Stack Overflow. This includes tasks like * "Find the sum of integers X with digit sum S, where X <= Y" (Y given) * "Find the number of palindromic integers between L and R" * "Enumerate all integers between L and R that only have digits 4 and 7" * "Find the probability that an integer X uniformly chosen from the range [L,R] has at least 10 common digits with a given number S" that can all be solved with a very similar idea. Just in case somebody's interested.
-a-certain-property/22394258) over at Stack Overflow. This includes tasks like

Full text and comments »

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

97.
By Not_Abdul_Munim, 4 days ago, In English
Can somebody explain please ? In the last round [Codeforces Round 1134 (Div. 4)](https://codeforces.me/contest/2290) this [submission](https://codeforces.me/contest/2290/submission/398300564) got accepted for the problem E &mdash; Avalanche although after looking at the constraints we can clearly see that the code will face an integer overflow so, is it due to weak testcases or something else ? because mostly when I get an integer overflow I get a diagnostic warning if it is normal can any one tell for which integer overflows our code will run normal and for which it will not and also there is also a submission I was seeing code of this person [code](https://codeforces.me/contest/2290/submission/398441403) he has similar logic but he is having a wrong answer due to the integer overflow so my question is that did the code above passed by luck or is there something else behind the scenes! Any insights would be appreciated! ![ ](/predownloaded/37/1d/371d87815392a9684282bedb040b74a331682c3e.png)
code will face an integer overflow so, is it due to weak testcases or something else ? because mostly, face an integer overflow so, is it due to weak testcases or something else ? because mostly when I get, he has similar logic but he is having a wrong answer due to the integer overflow so my question is

Full text and comments »

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

98.
By lvisbl_, history, 2 years ago, In English
Weird overflow behavior of min(a,b) function Recently I have done [problem:711C], and I have found an overflow when I use min(a,b) function. More specifically, if I use: min(a, b + c) when a, b and c are long long and sum of b + c large than 32-bit integer then the sum b + c will be treated as 32-bits integer and hence the overflow. but let say, if I use a temporary variable: long long tmp = b + c then min(a, tmp) will not overflow What kind of behavior is this? This is two submissions, one is overflow and the another one use a temporary variable will not overflow: Overflow: [submission:285989412] Not overflow: [submission:286024512]
Weird overflow behavior of min(a,b) function, 32-bit integer then the sum b + c will be treated as 32-bits integer and hence theoverflow, b + c will be treated as 32-bits integer and hence the overflow.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

99.
By Dambola, history, 8 years ago, In English
SESCOMP Marathon 2018 — Federal University of Ceará — TUTORIAL Problem A – Academia ------------------ #### ENGLISH This is a Dynamic programming (and/or simulation) question. It's a derivative from the classic Knapsack Problem. First we do vector, with size from $0$ to $T_{max}$ $(T_{max}+1)$, where we can simulate "how heavy is our bag", that is, how much time we spend. Initially the vector is filled with zeros, because we have no Power of Muscle. For every exercise we will do the following: 1) We are going to see the vector between $[0, T_{max} - T_{exercise}]$, this is our storage vector for every exercise. 2) For $t_i$ in $[0,T_{max} - T_{exercise}]$ we will propagate the sum of Power of Muscle from $vector[t_i]$ and $P_{exercise}$ to the next time. 3) Doing: $vector[t_{i} + T_{exercise}] = max(vector[t_i] + P_{exercise}, vector[t_{i} + T_{exercise}])$ OBS: Do $ti$ in $[0,T_{max} - T_{exercise}]$ goes from right to left to not have a overlapping of Power of Muscle. At the end, search for the higher value of $...
Another observation, $10^{12}$ overflows the size of integer in C/C++/JAVA, for that we use

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

100.
By Mohammad_Ali, history, 11 years ago, In English
Factorization Sieve There's a popular blog on CodeForces that lays out a lot of important Sieves (The Divisor Sieve, the Euler Phi Function Sieve, the Sieve of Eratosthenes, etc...). There's one important augmentation to the Sieve of Eratosthenes that was missing however. It's possible to speed-up factorization of integers with a sieve. Let `smf[i]` denote the smallest prime factor of `i`. ~~~~~ # Initialize sequences. smf[1 .. N] := {N, ..., N} composite[1 .. N] := {false, ..., false} # The empty product smf[1] := 1 # Optimized Sieve of Eratosthenes # First Handle the even integers smf[2] := 2 for i in [4, 6, ..., N]: composite[i] := true smf[i] := 2 # Handle the odd numbers now. for i in [3, 5, ..., N]: if not composite[i]: smf[i] := i for j in [i*i, i*i + 2*i, i*i + 4*i, ..., N]: composite[j] := true smf[j] := min(smf[j], i) ~~~~~ Note that since we're doing `i*i` in the inner loop, we have to be cautious about overfl...
Note that since we're doing `i*i` in the inner loop, we have to be cautious aboutoverflow. After, overflow. After this sieve is done, factoring an integer in `[1 .. N]` is straightforward

Full text and comments »

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

101.
By ChallaAjay, history, 3 weeks ago, In English
Can You Break My Code? #6 — The Prefix Sum That Overflows Round 6. Today's code is supposed to be pretty straightforward. We have an array of positive integers, and we need to find the sum of all its elements. Nothing fancy. No segment trees, no DP, no 200-line template. Just a loop. ## The code ```cpp #include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int> a(n); for (int &x : a) cin >> x; int sum = 0; for (int x : a) sum += x; cout << sum << '\n'; } ``` Looks completely fine, doesn't it? It compiles. It runs. It gives the correct answer on small examples. But the constraints are: - `1 <= n <= 200000` - `1 <= a[i] <= 1000000000` ## Your mission Find a valid input for which this code fails. 1. Give a counterexample that makes the output incorrect. 2. Explain exactly what goes wrong. 3. What's the smallest change needed to fix it? 4. Bonus: can you explain why the same bug might go unnoticed during local testing? T...

Full text and comments »

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

102.
By tobias_tris, history, 3 years ago, In English
Handling Overflows which performing pow(a, b) in C++ While solving [round 883Div3 &mdash; 1846E2](https://codeforces.me/contest/1846/problem/E2) I encountered a strange problem. I want to handle the overflow of long long while doing addition and multiplication. I used Geeks for Geeks logic to handle them and wrote the code [submission:212721992]. While it is working locally, Codeforces is giving a wrong answer with a warning of signed integer overflow. Can anyone help me how to handle Overflows in general?
encountered a strange problem. I want to handle the overflow of long long while doing addition and

Full text and comments »

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

103.
By AB22, history, 17 months ago, In English
Clean Rust Library for Competitive Programming Hey Codeforces! \(^_^) I've been working on a Rust library that makes competitive programming in Rust much cleaner and less verbose. If you've ever tried Rust for CP, you know the pain of writing the same input parsing boilerplate over and over again. ### The Problem Standard Rust CP code looks like this: ~~~~~ use std::{ io::{stdin, stdout, BufRead, BufReader, BufWriter, Read, Write}, iter::repeat, }; fn solve<R: Read, W: Write>(input: R, output: W) { let mut reader = BufReader::new(input); let mut writer = BufWriter::new(output); let mut buf = String::new(); reader.read_line(&mut buf).unwrap(); let n: usize = buf.trim().parse().unwrap(); buf.clear(); reader.read_line(&mut buf).unwrap(); let a: Vec<i64> = buf.split_whitespace().map(|s| s.parse().unwrap()).collect(); // rest of the logic here writeln!(writer, "{}", ans).unwrap(); } fn main() { let stdin = stdin(); let stdout = stdout(); ...
integer arr: [i32], // Space-separated integers matrix: [[i32

Full text and comments »

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

104.
By SPyofgame, history, 5 years ago, In English
Count a, b, c satisfy a + b + c <= S and a * b * c <= T for large S, T ### Statement This question is based on bonus of [this problem](https://atcoder.jp/contests/abc214/tasks/abc214_b). We need to count such non-negative integer triple $(a, b, c)$ that satisfy $(0 \leq a + b + c \leq S)$ and $(0 \leq a \times b \times c \leq T)$. Since the result may be very big, you can either use **bignum** or **modulo** $10^9 + 7$ for convention ---------- **Notice that:** - $(0, 0, 1) \neq (0, 1, 0) \neq (1, 0, 0)$ ---------- **Constraint:** - $0 \leq S, T \leq 10^{18}$ - $0 \leq a, b, c$ ---------- **No Time Limit. But expect to be 10 seconds** ---------- **Memory Limit: 1Gb** ---------- **Input:** - A single line contain only two positive **60-bit integers** $S$ and $T$ ($0 \leq S, T \leq 10^{18}$) ---------- **Output:** - Print a single integer, the number of positive tuple satisfy mathematical condition ----------------------------------- **Example:** <spoiler summary="Example 0"> ```css ...
/abc214/tasks/abc214_b). We need to count such non-negative integer triple $(a, b, c)$ that satisfy

Full text and comments »

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

105.
By kpw29, 5 years ago, In English
[ICPC blog series #0] My last ACM experience Disclaimer ================== This isn't really a first tutorial in the series. If you are interested in reading what participating in ICPC World Finals feels like, you can enjoy my <s>pathetic</s> behind-the-scenes story of the Cambridge silver-medal performance in WF2020. I tried to write a spoiler--free blog so that it contains minimum information about the problems. Motivation ================== In 2016 I have written a blogpost [My first ACM experience](https://codeforces.me/blog/entry/48082). It made sense to me to also close some chapter of the book by writing up about how my last serious contest went. I advise not to take the blog too seriously, it is just an honest stream of consciousness (some facts may not even be 100% accurate, though I will fix things people point me). Feel free to comment, praise, <s>or hate</s>. For a different perspective, check out [user:IBaloff,2021-10-07]'s [blog](https://codeforces.cc/blog/entry/95526). The hero and heroine of the story o...
functions was templated on arbitrary type , but actually worked correctly only forinteger T

Full text and comments »

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

106.
By grhkm, history, 6 years ago, In English
[Tutorial] Calculate modulo inverses efficiently! <spoiler summary="Thank you"> If you haven't read my previous post on lagrange interpolation, please do! It'll be great Also, thank you for the support on that post. It was my first time writing a blog and there were many mistakes, but I hope it's good now! Let's get started on today's useless math topic. </spoiler> Hello! We're going to learn how to find inverses mod p today (efficiently). **Pre-req: Know how to find inverses** Main results: ------------- As we know, finding the inverse of n numbers is $O(n\log{p})$. That is too slow, especially when time limit is tight. Therefore, we want a faster way. I present: - Find inverse of all numbers between 1 and n in $O(n)$ - Find inverse of n numbers in $O(n + \log{p})$ Idea 1: ------- Notice that $p = i \cdot \lfloor \frac{p}{i} \rfloor + (p \% i)$. (If you don't know why, compare it to $13=3\cdot 4+1$) $$p = i \cdot \lfloor \frac{p}{i} \rfloor + (p \% i)$$ $$\implies i \cdot \lfloor \frac{p}{i}...
}) \mod p$$ Or to make it easier to read: (Integer division) $$inv[i] \equiv (-(p/i) \cdot inv[p

Full text and comments »

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

107.
By chromate00, 3 years ago, In English
Breakthrough in 1955G — Bitset where you least expect Two days ago, the Div.3 ([contest:1955]) suffered from severe issues of hacks, because the problem G ([problem:1955G]) did not have proper validation for the sum of $nm$ in hacks, which was specified as at most $2 \cdot 10^5$ in the statements. Sure, I won't ask about why that happened, that is not constructive discussion. Instead, I will discuss about something very interesting about the task. During that incident, I was wondering. There has to be a way to solve this without the constraint on $n \cdot m$, right? Of course, $7\times 10^8$ bytes of input is impossible anyways, but if we ignore that, $10^8$ is not a very "dreaded" number under these ages of optimizations. There has to be a way to do this. Then the idea came to me. ------ Before we cover the solution, we cover a few basic facts on number theory &mdash; it might not be necessary to know this to understand the solution, but it will be helpful. Basically, every integer is a point on the grid of infinite dimension...
solution, but it will be helpful. Basically, every integer is a point on the grid of infinite

Full text and comments »

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

108.
By SummerSky, 9 years ago, In English
Notes on Codeforces Beta Round #112, Div2- A, B, C, D, E [problem:165A] Straightforward implementation with exhaustive enumeration. [problem:165B] The main idea is binary search, since if $v$ is a reasonable result, then any $v'>v$ also serves as a reasonable answer. Moreover, we can calculate $k^p$ in previous, and it is sufficient to consider $p$ up to $40$, since the problem guarantees that the maximum value of $n$ is $10^9$. Do not worry that $k^p$ will lead to overflow, as we will never use the value which exceeds $v$. The left work is to adopt binary search to find the minimum value of $v$. [problem:165C] We can solve this problem based on two cases. 1) $k=0$: we find out all the consecutive intervals $[l, r]$ that only 0s are included. This interval contributes $\frac{t(t+1)}{2}$ to the final answer, where $t=r-l+1$. 2) $k>0$: we find out each interval $[l, r]$ that exactly $k$ 1s are included and integers with indices $l$ and $r$ are also 1s. Then, we move from position $l$ to the left and find out the first inde...
that $k^p$ will lead to overflow, as we will never use the value which exceeds $v$. The left work is

Full text and comments »

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

109.
By cse, 4 months ago, In English
Copeforces — a Problem Solving Toolkit for Competitive Programmers <center> <img src="/predownloaded/6e/09/6e09f42ec30b2e9c7b450c15b66b4d7c245f10c9.png" alt="Copeforces" style="max-width: 720px; width: 50%;" /> </center> Hello Codeforces! Today I want to share my project <b>Copeforces</b>, a problem solving toolkit I made for competitive programmers. I built it to make common competitive programming workflows faster, cleaner, and easier to visualize while practicing, upsolving, or debugging ideas. You can try it here: <ul> <li><a href="https://copeforces.netlify.app" target="_blank">copeforces.netlify.app</a></li> </ul> <h3>What is Copeforces?</h3> Copeforces is a web-based toolkit for competitive programming. It brings many small but useful utilities into one place, so I do not need to keep switching between notes, scratch files, calculators, visualizers, and reference pages. It is designed especially for: <ul> <li>Practicing algorithms</li> <li>Upsolving problems</li> <li>Debugging ideas</li> <li>Testing ...
tables, overflow checker, float precision tester, big integer calculator, expression evaluator, and, , overflow checker, float precision tester, big integer calculator, expression evaluator, and more

Full text and comments »

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

110.
By suraj021, 11 years ago, In English
BITMASKS — FOR BEGINNERS I was having trouble understanding Bitmask, then I found an unknown pdf about Bitmask on google. I would like to help the beginners like me in understanding Bitmasks and their uses. Here we go : **#### MOTIVATION** Suppose you have a set of objects and you want some way to represent which objects to pick and which ones not to pick. How do you represent that in in a program? More generally, how do you represent a subest of a set?One way is to use a Map to associate with each object a boolean value indicating whether the object is picked. Alternatively,if the object can be indexed ``by integers, you can use a boolean array. However, this takes up a lot of memory and can be slow due to the overhead of Map and array. If the size of the set is not too large, a bitmask is much more efficient (and convenient)! **#### WHAT IS BITMASKS ?** Bitmasks a.k.a. lightweight, small sets of Booleans (native support in C/C++/Java). An integer is stored in a computer’s memory as a sequen...
of Booleans (native support in C/C++/Java). An integer is stored in a computer’s memory as a

Full text and comments »

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

111.
By komendart, history, 11 years ago, translation, In English
Codeforces Round #353 (Div. 2) Editorial Someday I will arrange C and D correctly :) [problem:675A] Firstly, in case $c = 0$ we should output YES if $a = b$ else answer is NO. If $b$ belongs to sequence $b = a + k * c$ where k is non-negative integer. So answer is YES if $(b - a) / c$ is non-negative integer else answer is NO. <spoiler summary="Code"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int a, b, c; cin >> a >> b >> c; if (c == 0) { if (a == b) cout << "YESn"; else cout << "NOn"; } else { if ((b - a) % c == 0 && (b - a) / c >= 0) cout << "YESn"; else cout << "NOn"; } } ~~~~~ </spoiler> [problem:675B] x a y b m c z d w Number in the center may be any from 1 to $n$ because number in the center belongs to all subsquares $2\times 2$. So, let's find answer with fixed number in the center and then multiply answer by $n$. Let's iterate over all possible $x$. Sums of ea...
non-negative integer. So answer is YES if $(b - a) / c$ is non-negative integer else answer is NO

Full text and comments »

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

112.
By Naaz, history, 3 years ago, In English
Unusual behaviour of G++ 20 compiler on the code. i recently submitted a code to the task [problem:1436C] but one submission where i used the modular inverse to calculate nPr went straight passed without any hassle.so then i decided to create a struct which would create all the factorial and inverse and would contain the correlated function for calculating the nPr and nCr under a certain modulo. Here is the code for it. ~~~~~ struct BINO { ll N; vector<ll> fact, inv; BINO(ll n) { N = n; fact = vector<ll>(N + 10); inv = vector<ll>(N + 10); fact[0] = fact[1] = 1; FOR(i, 2, N) fact[i] = (fact[i - 1] * i) % MOD; FOR(i, 0, N) inv[i] = bin_pow(fact[i], MOD - 2); } ll bin_pow(ll b , ll e) { ll res = 1; while ( e) { if ( e & 1) res = (res * b) % MOD; b = (b * b) % MOD; e /= 2; } return res % MOD; } ll fac(ll k ) { return fact[k] % MOD;} ll nPR(ll n , ll r) { return ( fact[n] * inv[n - r]) % MOD; } ll nCR(ll n , ll r) { return (((fact[n] * inv[n - r]) % MOD) * inv[r]) % MOD;...
, but when used custom test on codeforces with CLANG 20 diagnostics. it showed someoverflow., with CLANG 20 diagnostics. it showed some overflow. Please help me to find the integer overflow, Please help me to find the integer overflow. Or is it some default behaviour of gcc which I don't

Full text and comments »

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

113.
By mohittkkumar, 7 years ago, In English
Maximum value LCM Pair in an array — Problem 1285F So, I was solving this problem ------ https://codeforces.me/contest/1285/problem/F It wants us to find out maximum LCM value pair in an array. I saw this problem elsewhere ( then came to know it was copied from here) and was thinking how to solve it.I couldn't come up with a ideal approach, so i tried many greedy methods and none of them seemed to work. Until I came up with this approach What i did was &mdash; For every i in 1 to MAX_NUMBER : Find all multiples of i store it in a vector (say vec). Find the maximum element in the original input array that is not present in vec (say M) Find the LCM of M with all elements in vec and keep track of max LCM so far. Finally Output the max LCM so far. Solution link -- https://codeforces.me/contest/1285/submission/78453487 Now when initially i wrote it and submitted it on the platform i got 7 Wrong verdict : 6 were due to signed integer overflow and 1 was because all the elements...
platform i got 7 Wrong verdict : 6 were due to signed integer overflow and 1 was because all the, to signed integer overflow and 1 was because all the elements in the array were same so i was not

Full text and comments »

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

114.
By iib2022029, history, 21 month(s) ago, In English
Python Runtime Error, but C++ Accepted – Why? (Mortal Kombat Tower – 1418C) Hey everyone, I was solving the problem Mortal Kombat Tower (1418C)(https://codeforces.me/contest/1418/problem/C) and wrote my solution in Python first. However, when I submitted it, I got a Runtime Error on Test Case 3. Feeling stuck, I randomly decided to convert the same logic into C++ and submitted it... And guess what? It got accepted! Now, I'm really confused! How did the same logic work in C++ but fail in Python? Here are my submissions: Python Code (Runtime Error ): [305031310](https://codeforces.me/contest/1418/submission/305031310) C++ Code (Accepted ): [305032334](https://codeforces.me/contest/1418/submission/305032334) What could be the reason? I have a few possible guesses: 1. Integer Overflow or Recursion Limit in Python 2. Differences in Default Recursion Depth (C++ vs Python) 3. Memory Usage Differences 4. Unintentional Indexing Issues in Python But I'm still not sure! If anyone can analyze my submissions and explain what went wrong, I...
a few possible guesses: 1. Integer Overflow or Recursion Limit in Python 2. Differences in, What could be the reason? I have a few possible guesses: 1. Integer Overflow or Recursion Limit

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

115.
By abdulmusavir.juraev, history, 5 weeks ago, translation, In English
Can Python carry you high on Codeforces? Hi Codeforces! Many people say that Python is too slow for competitive programming and that everyone should switch to C++. While C++ is undeniably faster, I believe Python is still an amazing language for problem-solving if used correctly. Here are a few things I learned while solving problems in Python on Codeforces: ### 1. PyPy 3 is a lifesaver Never submit in pure Python 3 if execution time matters. PyPy 3 JIT compiler makes loops significantly faster. ### 2. Avoid input() in big loops Using sys.stdin.read().split() instead of standard input() reduced my I/O time significantly on large datasets. ### 3. Python's hidden superpowers - Built-in support for Big Integers (no need to worry about 64-bit overflow). - Extremely fast string manipulations and list comprehensions. - Easy-to-read syntax which lets you focus purely on the logic during contests. --- Question for the community: What is your peak rating using Python/PyPy? Do you think it's worth switchi...
(no need to worry about 64-bit overflow). - Extremely fast string manipulations and list, -bit overflow). - Extremely fast string manipulations and list comprehensions. - Easy-to-read

Full text and comments »

116.
By jaglike_makkar, history, 5 years ago, In English
Strange Runtime Error Please have a look at the following two submissions of [problem:1582E]: 1. [submission:138848779] 2. [submission:138849288] The first submission gave RTE on test 8. But just by replacing `ll` with `int`, it passed test 8. (Though it failed on test 9 due to integer overflow). Can anyone tell why is the first submission giving RTE? Any help is appreciated. C++ is not my primary language, so I may be making some silly errors.
. (Though it failed on test 9 due to integer overflow). Can anyone tell why is the first submission, ` with `int`, it passed test 8. (Though it failed on test 9 due to integer overflow). Can anyone tell

Full text and comments »

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

117.
By clyring, history, 5 years ago, In English
Haskell is now 64-bit on Codeforces I haven't seen any announcement about this and only found out when I saw that my stupid non-`Int64` submission [submission:137642072] to problem C in today's round didn't fail pretests. But maybe some of you would like to know. Performance-wise, I think it's probably a nice win for some problems but not that significant overall. The convenience of not having to import `Int64` and fiddle with explicit conversions or so frequently ask myself if one of the 'unimportant' constraints I don't have at top-of-mind will cause `Int` overflow will definitely be appreciated, though. On the plus side: Arithmetic with large integers is presumably 2-3x faster now. Also, in my experience, `Int64`-related class methods often lack the performant specializations and rewrite rules available for their `Int` counterparts, and `Int64` values tend to be unboxed less aggressively on 32-bit systems, all of which made awkward using efficiently the type. GHC's pointer-tagging magic will also probably work b...
at top-of-mind will cause `Int` overflow will definitely be appreciated, though. On the plus

Full text and comments »

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

118.
By Black_Fate, history, 4 years ago, In English
[Educational] Combinatorics Study Notes (2) Hello Codeforces! Today I'll be writing about what I have learnt about combinatorics, which played, and, in my opinion, will still be playing a important role in both Codeforces and CP (short for competitive programming). However, combinatorics is such a great subject that made that impossible for me to write it all in one blog. So, this is just the second blog, which is friendly to beginners. If you are interested, please, pay attention to this account and I'll give posts as series for a long term. If you have found some mistakes in the text, or if you have some questions about the topic, please, leave a comment, and I'll check it weekly and reply. Also, if you find some grammar mistakes, a kind comment will be also welcomed. ### Previous Blogs - [Combinatorics (1)](https://codeforces.me/blog/entry/110376) ### Blogs in the future If finished, I'll link them. - Combinatorics (3) - Bitmask - Probabilities ### Content 1. Quick power 2. Fermat's little th...
theorem 3. extend-gcd 4. The multiplicative inverse of an integer 5. Prework optimize 6. homework

Full text and comments »

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

119.
By cry, 2 years ago, In English
Codeforces Round 952 (Div. 4) Editorial This was our first time setting a Div.4 contest. We sincerely hope you enjoyed the problems! #####[problem:1985A] Problem Credits: [user:cry,2024-05-26] <br/> Analysis: [user:cry,2024-05-26] <spoiler summary="Solution"> To swap the first character of the strings, you can use the built-in method std::swap in C++, or for each string, separate the first character from the rest of the string and concatenate it with the other string. </spoiler> <spoiler summary="Code (C++)"> ```cpp #include <bits/stdc++.h> using namespace std; int main(){ int t; cin >> t; while(t--){ string a, b; cin >> a >> b; swap(a[0], b[0]); cout << a << " " << b << endl; } } ``` </spoiler> #####[problem:1985B] Problem Credits: [user:cry,2024-05-26] <br/> Analysis: [user:cry,2024-05-26] <spoiler summary="Solution"> To maximize the number of multiples of $x$ less than $n$, it optimal to choose a small $x$, in this case, $2$. The only exception is $n = 3$, where it is op...
$, and deduce that $c=\frac{k}{a \cdot b}$ (make sure $c \leq z$ and $c$ is an integer). To get the

Full text and comments »

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

120.
By dacin21, history, 8 years ago, In English
On the mathematics behind rolling hashes and anti-hash tests This blog assumes the reader is familiar with the basic concept of rolling hashes. There are some math-heavy parts, but one can get most of the ideas without understanding every detail. The main focus of this blog is on how to choose the rolling-hash parameters to avoid getting hacked and on how to hack codes with poorly chosen parameters. # Designing hard-to-hack rolling hashes ## Recap on rolling hashes and collisions Recall that a rolling hash has two parameters $(p, a)$ where $p$ is the modulo and $0 \leq a < p$ the base. (We'll see that $p$ should be a big prime and $a$ larger than the size $\left|\Sigma\right|$ of the alphabet.) The hash value of a string $S = s_0 \dots s_{n-1}$ is given by $$ h(S) := \left(\sum\limits_{i=0}^{n-1} a^{n-1-i} s_i\right) \mod p $$ For now, lets consider the simple problem of: given two strings $S, T$ of equal length, decide whether they're equal by comparing their hash values $h(S), h(T)$. Our algorithm declares $S$ and $T$ t...
~~~~~ __builtin_ia32_rdtsc(); ~~~~~ - some heap address converted to an integer

Full text and comments »

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

121.
By raihan-hosen, 9 days ago, In English
Hello Codeforces! How I Cheesed a Hard-Looking Problem (My First Post) Hi everyone! This is my very first blog post here on Codeforces. I am still quite new to competitive programming and trying my best to learn new algorithms every day. Today, I was looking at a problem called **H. Simple Mod** and found something so funny that I just had to share it. --- When I first opened the problem, the constraints looked absolutely terrifying: * We are given a huge number $N$ that can have up to **100 digits** ($1 \le N \le 10^{100}$). * We need to find two integers $X$ and $Y$ such that $(X^2 + Y^2) \pmod N = 0$. Looking at the examples, they showed outputs like `4 3` and `5 5`. I immediately started worrying. How am I supposed to handle a 100-digit number in C++? Do I need to learn complex math or big-integer coding just to solve this? --- I sat there staring at the screen, and then I carefully re-read this specific line in the problem description: > *"...such that $X$ and $Y$ are **non-negative** integers."* Non-negative means the numbe...
number in C++? Do I need to learn complex math or big-integer coding just to solve this? --- I

Full text and comments »

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

122.
By ChaituBoi, 6 years ago, In English
CF round 672 Div 2 Rock and lever , some basic doubt about ranges Now what i did was similar to editorial. The problem isnt with the approach but with the fact that if use operation `ans+=(n*(n-1))/2` i get wrong answer due to integer overflow, now I AM using `long long` but still it gives -ve answer in 2nd test case which is ofcourse due to overflow. To solve this what i did was first divide n or (n-1) by 2 (depending upon parity) and then multiplying and got answer accepted. Can someone tell why this is happening?? I know i would probably be a very dumb mistake but plz dont judge harshly. :D MY CODE: `#include<bits/stdc++.h>` `using namespace std;` `//void swap(int &a,int &b){` `// int tmp=a;a=b;b=tmp;` `//}` `int size(long long a){` ` int n=0;` ` while(a!=0){` ` n++;` ` a/=2;` ` }` ` return n;` `}` `int main(){` ` ios_base::sync_with_stdio(false);` ` cin.tie(NULL);` ` int t,n;` ` cin>>t;` ` while(t--){` ` cin>>n;` ` long long A[n],ans=0;` ` for(int i=0;i<n;i++)cin>>A[i]...
if use operation `ans+=(n*(n-1))/2` i get wrong answer due to integer overflow , now I AM using

Full text and comments »

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

123.
By fatalerror, history, 15 months ago, In English
Python Optimization Tricks in Competitive Programming > For better reading experience in Chinese, please refer to: [LeetCode](https://leetcode.cn/discuss/post/3746464). # Preface This article introduces techniques to reduce runtime in competitive programming using Python, under the premise that the complexity remains **correct** and **unchanged**. Each technique is accompanied by a Speedup on CPython 3.11.5 / PyPy 3.10.13. # I/O ### Use fast input Replace the built-in `input` with `sys.stdin.readline`. Each `input()` call incurs prompt handling and a `sys.stdin` lookup, while `readline()` reads a line directly. The more input lines, the larger the gap. Speedup: CPython ~×4.2; PyPy ~×16.4. ~~~~~ import sys input = lambda: sys.stdin.readline().rstrip() # strip the trailing newline II = lambda: int(input()) LII = lambda: list(map(int, input().split())) ~~~~~ ### Read all input at once Use `sys.stdin.read().split()` to read everything into memory once, then consume as needed. This avoids calling the read fun...
modulo Integer modulo is essentially division, far more expensive than addition/subtraction

Full text and comments »

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

124.
By acash, history, 6 years ago, In English
how to compute (a!+b!)/a!*b! efficiently? I was solving the probablity problem ? In which i faced this calculation. Please forgive me if my ques is not good ? I am still a beginner.I know that pasting code here is not considered good . But I am not able to understand some part in solution after trying it whole day Please help me . I am going to copy whole post here and i will refer in that. where the above calculation is being calculated.So that your time is not wasted. In the perm function you can see that ans is taking as double but we can see that (a!+b!)/a!*b! involves integer calculation (although i have tried unsigned long long but it overflowed)it means we have already lost some data by taking double . moreover we are calculating perm(a)*perm(b) in dfs function which also gives number of ways which also involves integers but again we are multiplying two double values which already gone through precision loss. [Problem Link on leetcode](https://leetcode.com/problems/probability-of-a-two-boxes-having-the-sam...
double but we can see that (a!+b!)/a!*b! involves integer calculation (although i have tried unsigned, that ans is taking as double but we can see that (a!+b!)/a!*b! involves integer calculation (although

Full text and comments »

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

125.
By brucewayne123, history, 10 years ago, In English
amritapuri practice round on amritaicpc.cloudcontest.org hi everyone! i was trying this problem HENRY:- Henry and Lost Ranges Henry is a curious little boy. He likes to play around with numbers. One day, he defined a fun ction f for natural numbers such that: f(X) = largest prime factor of X , where X > 1 For example: f(2) = 2 f(3) = 3 f(75) = 5 Now, Henry selected two integers A and B ( A ≤ B ) and counted all numbers X between A and B (both inclusive) such that f(X) = K . He found out that there are N such numbers. After that Henry went for playing. When he returned home, he found out that he had forgotten the upper limit of range i.e. the integer B . However, he remembers all other numbers i.e. A , K and N . Henry wants to find out B as soon as possible. Can you help him finding it ? Note: ● If there are multiple possible values of B , output the least value out of those. ● It is assured that the input will be in such a way that final value of B will be within the range of long long int . Input First...
range i.e. the integer B . However, he remembers all other numbers i.e. A , K and N . Henry wants

Full text and comments »

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

126.
By Siriuslight, history, 9 years ago, In English
Need help on 903D I have implemented [903D](http://codeforces.me/problemset/problem/903/D) using Mergesort Tree and maintaining a prefix sum vector for every vector of merge sort tree. For every a[i], I am calculating the sum of all a[j], where a[j] > a[i]+1 or a[j] < a[i]-1, j < i. Using this sum I am subtracting this sum from answer and adding a[i], same number of times. My [submission](http://codeforces.me/contest/903/submission/33196495). This error is because of integer overflow, but when I change all integers to long long. It gives me wrong answer. Any help would be appreciated. :)
://codeforces.com/contest/903/submission/33196495). This error is because of integer overflow, but when I change, integer overflow, but when I change all integers to long long. It gives me wrong answer.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

127.
By NemanjaSo2005, 3 years ago, In English
Codeforces Round 911 (Div. 2) Editorial [problem:1900A] Author: [user:NemanjaSo2005,2023-11-26] <spoiler summary="Hint 1"> Assume that cells $i-1$, $i$, and $i+1$ are covered in water. What happens if you remove water from cell $i$? </spoiler> <spoiler summary="Hint 2"> The water at position $i$ is replaced as both cells $i-1$ and $i+1$ have water in them. </spoiler> <spoiler summary="Solution"> Read the hints. If there are 3 consecutive empty cells $i-1$, $i$, $i+1$, we can place water in cells $i-1$ and $i+1$ and then move water from cell $i$ to all other cells. If there are no such cells, we have to place water on every empty cell. So if we find substring ''...'' in the array, the answer is $2$, otherwise the answer is the number of empty cells. Time and memory complexities are $O(N)$. </spoiler> <spoiler summary="Bonus"> Solve the problem if it is required that each cell is filled with water, or next to at least $1$ cell that is filled with water. </spoiler> [problem:1900B] ...
calculate the number of triples that have a value of function $f$ that is an integer multiple of $i

Full text and comments »

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

128.
By _h_, history, 11 years ago, In English
Short modular inverse Hi! [Modular inverses](https://en.wikipedia.org/wiki/Modular_multiplicative_inverse) are used in the solutions to a lot of number theory problems, such as [problem:622F] from the latest educational round. I want to share a one-liner (essentially) that computes modular inverse with the same complexity as the exteneded Euclidean algorithm (a and b are supposed to be positive co-prime integers, and inv(a,b) is the inverse of a modulo b, lying between 1 and b): ~~~~~ long long inv(long long a, long long b){ return 1<a ? b - inv(b%a,a)*b/a : 1; } ~~~~~ The idea behind the code is that to compute inv(a,b), we find x such that $x = 1 \textup{ mod } b$ and $x = 0 \textup{ mod } a$, and then return `x/a`. To find x, we can write $x = yb+1$ and solve for y by recursively computing inv(b,a). (Actually `inv(b%a,a)`) This isn't the fastest method if you're worried about performance, and you will probably get overflow if a*b doesn't fit inside a long long. But I think it's neat.
, and you will probably get overflow if a*b doesn't fit inside a long long. But I think it's neat.

Full text and comments »

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

129.
By Destopia, history, 4 years ago, In English
Evil Integer Overflow Consider following code: ~~~~~ #include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; vector<int> a(n); int sum = 0; for (auto &it : a) { cin >> it; sum += it; } cout << sum << "\n"; for (int i = 0; i < n; i++) { cout << a[i] << " "; } cout << endl; } ~~~~~ Input like (or anything greater than INT_MAX into k) ~~~~~ 5 1234567891564 1 2 3 4 5 ~~~~~ makes the program print ~~~~~ 0 0 0 0 0 0 ~~~~~ What actually happens? We don't use the value of $k$ at all.
Evil Integer Overflow

Full text and comments »

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

130.
By idonthatephy, history, 4 years ago, In English
how to overcome integer overflow in this particular problem [problem:1574C]--this is the problem given below is my code- [submission:158115252] it is failing test case 3 because of integer overflow, is there any way to overcome the integer overflow?
how to overcome integer overflow in this particular problem, failing test case 3 because of integer overflow, is there any way to overcome theinteger overflow?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

131.
By WaterColor2037, history, 7 years ago, In English
AtCoder Beginner Contest 129 — Unofficial English Editorial Hello Codeforces! Did you enjoy the [AtCoder Beginner Contest 129](https://atcoder.jp/contests/abc129)? As usual, there was only [Japanese editorial](https://img.atcoder.jp/abc129/editorial.pdf) published, so I translated it into English again. **Disclaimer.** Note that this is an unofficial editorial and AtCoder has no responsibility for this. Also, I didn't do proofreading at all, so it might contain many typos. Moreover, this is the second experience I write such kind of editorial, so the English may not be clear, may be confusing, or even contain mistakes. Any minor corrections (including grammatical one) or improvement suggestions are welcome. Please do not hesitate posting a comment about it. ## A: Airplane There are 6 orders to visit the airports, so you can try all of them and look for the minimum value. However, if you realized that each cost of a route is equal to the sum of two integers out of the given three, you could also obtain an answer by subtracting ...
$X$ and an integer $s$. First, $X = "0", s=A$. * In one operation, concat $s$ to the bottom of $X

Full text and comments »

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

132.
By ChallaAjay, history, 4 weeks ago, In English
GCD and LCM: the small things I wish I knew earlier Hi everyone! I'm not a high-rated guy (just ~1300), so this isn't some deep post. I just noticed that gcd and lcm show up in a LOT of problems, and every time I would forget some tiny detail and lose time on it. So I wrote everything in one place. Maybe it helps someone who is at the same stage as me, and if I got something wrong please tell me in the comments, I'll fix it :) ### 1. Euclid's algorithm The whole idea is one line: `gcd(a, b) = gcd(b, a % b)`, and when `b = 0` the answer is `a`. ~~~~~ long long gcd(long long a, long long b) { while (b) { a %= b; swap(a, b); } return a; } ~~~~~ If you use C++17 you can just write `std::gcd(a, b)` (it's in `<numeric>`). On older compilers `__gcd(a, b)` works too. It runs in `O(log(min(a, b)))`. Reason: every two steps the bigger number becomes at least half of what it was. So even for numbers around 10^18 it's like 90 steps, nothing to worry about. One small thing: `gcd(0, x) = x`. Th...
. ### 2. LCM (and the overflow trap) `lcm(a, b) = a / gcd(a, b) * b` Please **divide first

Full text and comments »

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

133.
By Not-Afraid, history, 7 years ago, In English
Help in Self Powers(Project Euler Hackerrank problem 48) I am getting TLE on last test case of this problem [Link to the problem](https://www.hackerrank.com/contests/projecteuler/challenges/euler048/problem), i used Big mod [Link to Big mod implmentation](https://www.geeksforgeeks.org/multiply-large-integers-under-large-modulo/) for multiplication while calculating power as we need last ten digits so we have to modulo it by 1e10 which will overflow in C++. Any type of help is appreciated. Thanks in advance.
calculating power as we need last ten digits so we have to modulo it by 1e10 which willoverflow in

Full text and comments »

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

134.
By helpme, 11 years ago, In English
Need help in Hashing with overflow technique Hello everyone, Recently I've read some tutorial on hashing, I learned that after some preprocessing we can find the hash of a substring in O(1) using modular inverse. But, I was surprised to see that people do not use modular arithmetic! For example, see this submission: [submission:845264], How is it counting hash? Is it utilizing the integer overflow? Moreover, it does not use any modular inverse to find the hash of a substring, e.g. ~~~~~ inline int hh(int x,int y) { return a[y]-a[x-1]*p[y-x+1]; } ~~~~~ I can't understand how it actually works. It would be great if any of you could explain this or suggest some online resources about this. Thanks in advance!
Need help in Hashing with overflow technique, hash? Is it utilizing the integer overflow? Moreover, it does not use any modular inverse to find the, ], How is it counting hash? Is it utilizing the integer overflow? Moreover, it does not use any modular

Full text and comments »

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

135.
By Geothermal, history, 7 years ago, In English
Codeforces Round #570 Solutions Since it will be a little while longer before the editorials for the recent Division 3 Round come out, I thought I'd post some solutions I wrote up. Please feel free to post below if you have any questions or notice any errors. If any of my solutions end up getting hacked, I'll replace the submission and solution text as soon as possible. Links to my submissions are at the bottom of this post. --- **A:** We can easily prove that the answer will not be much bigger than A, so simply iterating through all the possible values until we find one that works will do fine. (As a trivial proof, note that 1003 is interesting, so we will have to test at most 1003 numbers.) Then, the only challenging part from here is finding the sum of the digits of a number, which can be implemented easily with modular arithmetic. --- **B:** Start by sorting the prices. It turns out that only the greatest and least prices matter. We have two key facts to prove: 1. The answer is -1 if the ...
K. Then, the answer is -1 if and only if K / B (using integer division) is less than N. Otherwise

Full text and comments »

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

136.
By PrinceOfPersia, 12 years ago, In English
Codeforces Round #299 Editorial ### [problem:535A] First of all check if $n$ is one of the values $0, 10, 11, …, 19$. Then, let’s have array $x[]$ = {"", "", "twenty", "thirty", …, "ninety"} and $y[]$ = {"", "one", …, "nine"}. ![ ](http://espresso.codeforces.com/d5f38500e79e3e89be0519dc22736124c000bada.png) Let $a = \frac{n}{10}$ and $b = n\ modulo\ 10$. If $n$ is not one of the values above, then if $a=0$, print $y[b]$, else if $b=0$ print $x[a]$ otherwise print $x[a]$-$y[b]$. Time complexity: $O(1)$ [Code](http://ideone.com/mytb2L) by [user:SoroushE,2015-04-02] [Another Code](http://ideone.com/CqgNe5) by [user:PrinceOfPersia,2015-04-05] [Another Code](http://ideone.com/dqiMNL) by [user:Haghani,2015-04-08] [Python Code](http://ideone.com/6tZmNF) by [user:Zlobober,2015-04-04] ### [problem:535B] Sol1: Consider $n$ has $x$ digits, $f(i) = $ decimal representation of binary string $i$, $m$ is a binary string of size $x$ and its $i-th$ digit is 0 if and only if the $i-th$ digit of $...

Full text and comments »

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

137.
By Sujay_27, history, 3 years ago, In English
Signed integer overflow error- Round 905-Div-3 C-Raspberries This is my code-[My code](https://codeforces.me/contest/1883/submission/244204675) . I'm getting signed integer overflow error. I'm getting this error inspite of using long long. Any help would be appreciated. Thanks in advance. [Ques link](https://codeforces.me/contest/1883/problem/C)
Signed integer overflow error- Round 905-Div-3 C-Raspberries, signed integer overflow error. I'm getting this error inspite of using long long. Any help would be

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

138.
By acash, history, 7 years ago, In English
max path sum in binary tree Given a non-empty binary tree, find the maximum path sum. For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root. ~~~~~ -10 / \ 9 20 / \ 15 7 ~~~~~ ans = 42 I am beginner please help me. Below maxpathsum function must return int value i am using long long just to avoid to integer overflow input : [1,2] (1 is parent of two) expected output : 3 actual output : every time garbage value on leetcode but sometimes gives correct output as 3 also I know its data type error i want your help because when i try to run it on visual studio or codeblocks ,i am getting correct output as 3. whats wrong in below code. ~~~~~ long long int solve(TreeNode* root,long long int &res) { if (root == NULL)return INT_MIN; long long int left = solve(root->left, res); long long in...
function must return int value // i am using long long just to avoid to integer overflow int, using long long just to avoid to integer overflow int maxPathSum(TreeNode* root) { long long int res, Below maxpathsum function must return int value i am using long long just to avoid tointeger

Full text and comments »

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

139.
By galen_colin, history, 6 years ago, In English
(Another) editorial of contest (by egor.anisevich) in honor of ending of academic year and exams [Link to contest](https://codeforces.me/contestInvitation/4036ec99932a47484351d57a812de34c7a4fbb2c) [Author's editorial](https://codeforces.me/blog/entry/78650) This is a duplicate of my comment [here](https://codeforces.me/blog/entry/78415?#comment-639262). I've gotten a couple of requests to make it a blog (for some reason), so here it is. Note: this is unofficial, I was just a competitor <spoiler summary="A"> This is mostly about knowing how your language works. Division, however, gets picky. It's a good idea to **not use doubles** because they have precision issues ([read](https://codeforces.me/blog/entry/76595?locale=en)). Instead, you can use integer division, which automatically truncates (in C++, at least), possibly having to be careful with negatives in other languages. For the actual implementation, it seems like the test cases are designed so overflow won't happen and you won't have to mod with negative numbers, so the rest is simple. My submission: [subm...
](https://codeforces.me/blog/entry/76595?locale=en)). Instead, you can use integer division, which

Full text and comments »

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

140.
By luckytoilet, history, 10 years ago, In English
Are programming competitions a good use of time? 10 minutes remaining in the contest, but you’re still a few points short of advancing. Armed with your mighty coding powers, the first three problems fall quickly, but problem 4 is proving a tough nut to crack. After four incorrect attempts, your time is running short, and you’re searching desperately for an off-by-one error, an edge case you haven’t considered. You read the problem statement one more time, and at last, you find it. An integer overflow bug. With a wide grin, you fix the bug with a few quick keystrokes. You upload the source code file... [Continued on my blog](https://luckytoilet.wordpress.com/2016/12/23/are-programming-competitions-a-good-use-of-time/)
one more time, and at last, you find it. An integer overflow bug. With a wide grin, you fix the bug, You read the problem statement one more time, and at last, you find it. An integer overflow bug

Full text and comments »

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

141.
By rachitiitr, history, 10 years ago, In English
[Help] Gym Problem 100570F (Centroid Decomposition) Hey everyone! I have just understood the idea of Centroid Decomposition in previous zscoder's contest. I was doing another [problem](http://codeforces.me/gym/100570/problem/F) based on this concept. Here is my detailed source [code](http://ideone.com/gggPgL) Can someone help me figure out what am I doing wrong. I have checked the integer overflow cases and the code almost seems right. I can't view the test cases of the gym problem. Thanks.
out what am I doing wrong. I have checked the integer overflow cases and the code almost seems right

Full text and comments »

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

142.
By Mohamed.Bassem, 14 years ago, In English
I'm getting a WA in round 174 problem C Div2 (Solved) Hi All, I'm getting a strange precision error in this problem : [problem:284C] and this is my code : [submission:3346105] I know that this problem could be solved by many other ways , but what's wrong with this implementation ? I'm using a segment tree with lazy propagation , every node contains three integers , the value of the node ( which is the summation over this range ) the update flag ( and value ) and the number of leafs under this node. Thanks :) **UPDATE :** The problem was that integers overflow and the size of the vector was causing some problems too , Thanks to [user:HadronWave,2013-03-18] and here is my accepted solution [submission:3348952] :)
that integers overflow and the size of the vector was causing some problems too , Thanks to, **UPDATE :** The problem was that integers overflow and the size of the vector was causing some

Full text and comments »

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

143.
By ekzhang, history, 6 years ago, In English
[Tutorial] Kinetic Tournament (Used in FBHC Round 2) Background ------------------ During Facebook Hacker Cup Round 2 today, Problem D caught my attention. It reminded me of a particular data structure called a **kinetic tournament**, which is not very well known in this community. However, it offers an extremely clean and slick solution to the problem, in my opinion. I first learned about this data structure from [user:dragonslayerintraining,2020-08-30], who described a variant of it in this [Codeforces blog comment](https://codeforces.me/blog/entry/68534#comment-530381). Since the data structure is so interesting, I feel like it deserves a longer explanation, some template code, and more examples. That's why I am writing this blog post. Kinetic Tournaments ------------------ Briefly, the functionality of the data structure is a mix between a line container, i.e., "convex hull trick", and a segment tree. Suppose that you have an array containing pairs of nonnegative integers, $A[i]$ and $B[i]$. You also have a global...
= temp + (delta - 1) / delta_slope + 1; return mint > temp ? mint : INF; // preventoverflow

Full text and comments »

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

144.
By KEPuzOfficial, 22 months ago, translation, In English
KEP Contest #12 ![ ](/predownloaded/4d/f9/4df9fdecea71f4e44c5a030ab07f8cb7310c4581.png) I invite everyone to the [contest](https://kep.uz/competitions/contests/contest/419), which will take place on **January 11, 2025 at 14:35UTC**. Interesting problems await you in the contest. Thanks to [user:MathModel,2025-01-09] for ideas for several problems and [user:Timosh,2025-01-09] for inspiring ideas. **Contest info:** - Number of problems: **13** - Difficulty of problems: **< 2400** - Duration: **3 hours** - Contest type: **ACM20M** - Languages: **C++, Python, C, Kotlin, Haskell, R, Nodejs, PHP, C#, Java, Rust, Go** **Prizes:** - First place – **25$ (USDT)** - Second place – **20$** - Third place – **15$** - Fouth place – **12$** - Fifth place – **10$** Link to the platform: https://kep.uz/competitions/contests/ P.S. Registration on the platform only via Gmail/Github. **UPD** Thank you for participating. I hope you enjoyed the contest. **Results** ...
- We have $P_m = 2^{\frac{2^m - 1}{k}}$. - $P_m$ is integer $\iff \frac{2^m - 1}{k} \in \mathbb{Z

Full text and comments »

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

145.
By acash, history, 7 years ago, In English
Urgent help for interview Please help : I have two job interview first one is tomorrow next one is a week later In last 18 hours i solved 25 interview problems from diferent In seven days My target is 300 ,please save my life :) I am trying to find diameter using recursion ,I am confused with recursion some of the test cases I tried I got correct answer at some point Integer overflow occured But Below author's solution was accepted with same data types My approach: For every node, length of longest path which pass it = MaxDepth of its left subtree + MaxDepth of its right subtree. My question is whats wrong with my implementation ~~~~~ class Solution { public: int mx = 0; int solve(TreeNode* root) { if (root == NULL)return 0; int leftheight = solve(root->left) + 1; int rightheight = solve(root->right) + 1; mx = max(mx, leftheight + rightheight); return max(leftheight, rightheight); } int diameterOfBina...
test cases I tried I got correct answer at some point Integer overflow occured But Below author's, some of the test cases I tried I got correct answer at some point Integer overflow occured But

Full text and comments »

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

146.
By Spheniscine, history, 5 years ago, In English
Unofficial AtCoder Beginner Contest 237 Editorial ### [A &ndash; Not Overflow](https://atcoder.jp/contests/abc237/tasks/abc237_a) <spoiler> Note that $N$ has to be read as a signed 64-bit integer type. You could check it by either doing to comparison manually, or casting back and forth between the signed 32-bit integer type. Time complexity: $O(1)$ </spoiler> ### [B &ndash; Matrix Transposition](https://atcoder.jp/contests/abc237/tasks/abc237_b) <spoiler> Simply construct a $W$-by-$H$ matrix, assign $B_{i, j} = A_{j, i}$ for all relevant $i, j$, then output it. Alternatively, if you use Python, the `numpy` library installed in AtCoder gives a really short implementation, as noted in this user editorial: https://atcoder.jp/contests/abc237/editorial/3344 Time complexity: $O(HW)$ </spoiler> ### [C &ndash; kasaka](https://atcoder.jp/contests/abc237/tasks/abc237_c) <spoiler> Note that for a string to be a palindrome, it must start with the same number of contiguous `a`s as it ends with. If there are less con...
### [A – Not Overflow](https://atcoder.jp/contests/abc237/tasks/abc237_a) Note

Full text and comments »

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

147.
By Sujay_27, history, 3 years ago, In English
Doubt in the Codeforces(918) Div4-C problem Hello folks, Need some help in debugging.. The question is on the right : [Ques](https://codeforces.me/contest/1915/problem/C) This is the code I submitted : [Code](https://codeforces.me/contest/1915/submission/239459218) I don't know why I'm getting signed integer overflow, inspite of having all the variables as long long. Can someone enlighten me on what I'm missing. [contest:918][problem:1915C]
/1915/submission/239459218) I don't know why I'm getting signed integer overflow , inspite of having

Full text and comments »

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

148.
By PokemonMaster, history, 14 months ago, translation, In English
2140B Editorial (1049 round) # Editorial: Concatenation & Divisibility (extended version of CF 2140B) *Below is a guide for solving the **extended version of problem 2140B**, where instead of outputting just any valid solution, we describe how to enumerate **all** valid integers $y$. This problem is much deeper than just printing the trivial $y=2x$.* --- ## Problem statement (recap) We are given an integer $x$ ($1 \le x < 10^8$). We want to find an integer $y$ ($1 \le y < 10^9$) such that $$ x\#y \equiv 0 \pmod{x+y}, \quad\text{where}\quad x\#y = x \cdot 10^k + y, $$ and $k$ is the number of digits of $y$. The original problem (CF 2140B) only required outputting **any** valid $y$. Here we discuss the structural description of **all solutions** and two efficient constructive algorithms. --- ## Key equivalence The condition is: $$ x \cdot 10^k + y \equiv 0 \pmod{x+y} \ \iff\ x(10^k-1) \equiv 0 \pmod{x+y}. $$ Let $d=\gcd(x,y)$, $x=ad,\ y=bd$. Then $x+y = d(a...
printing the trivial $y=2x$.* --- ## Problem statement (recap) We are given an integer

Full text and comments »

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

149.
By IcpcTanta, history, 20 months ago, In English
Contest #2 — Editorial ## Introduction Contest #2 was an exciting competition with strong participation from multiple contestants. The contest featured four problems (A, B, C, D), and the results were as follows: [user:lilpluton,2025-03-06] was the first to solve A. [user:__baozii__,2025-03-06] was the first to solve B. [user:AkbarKING,2025-03-06] was the first to solve C. [user:MR_NoSolution,2025-03-06] was the first to solve D. The fastest full completion was achieved by [user:__baozii__,2025-03-06] (88 minutes). --- ## Standings | Rank | User | Solved | Penalty | |------|------|--------|---------| | 1 | [user:__baozii__,2025-03-06] | 4 | 88| | 2 | [user:AkbarKING,2025-03-06] | 4 | 89| | 3 | [user:MoamenZ,2025-03-06] | 4 | 120| | 4 | [user:MR_NoSolution,2025-03-06] | 4 | 150| | 5 | [user:gholyo,2025-03-06] | 4 | 204 | | 6 | [user:ammahmed004,2025-03-06] | 4 | 342| | 7 | [user:Mostafa_Alaa99,2025-03-06] | 3 | 37| | 8 | [user:Sparky_,2025-03-06] | 3 | 54| | 9 | [user:ibluefox...
that avoids overflow. Because the resulting number can be extremely large, the solution uses a

Full text and comments »

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

150.
By GM_Dan4Life, 2 years ago, In English
[Tutorial] Solving Range (Chmin, Chmax, Add, Assign) + Point queries Hi Codeforces! This is my first attempt at a tutorial blog XD. Disclaimer: No headaches occured during the making of this blog Problem statement ----------------- Given an integer array $A$ of length $n$ and $q$ of the following 5 types of queries: 1. For all $i \in [l,r]$, change $A_i$ to $\max(A_i, v)$ 2. For all $i \in [l,r]$, change $A_i$ to $\min(A_i, v)$ 3. For all $i \in [l,r]$, change $A_i$ to $A_i + v$ 4. For all $i \in [l,r]$, change $A_i$ to $v$ 5. Output $A_i$ - $ 1 \leq n,q \leq 10^6 $ - $ 1 \leq l \leq r \leq n $ - $ -10^9 \leq A_i, v \leq 10^9 $ The above is solvable with techniques like [Segment Tree Beats](https://codeforces.me/blog/entry/57319) in $\mathcal{O}(n+q\log^2{n})$, but as a binary search enthusiast, you didn't learn segment tree beats? Don't worry, here's an easier, faster, and shorter solution that solves this particular problem in $\mathcal{O}(n+q\log{n})$ Prerequisites ------------- You should know the following t...
occured during the making of this blog Problem statement ----------------- Given aninteger array

Full text and comments »

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

151.
By SPyofcode, history, 5 years ago, In English
[Variants] An interesting counting problem related to square product ## The statement: Given three integers $n, k, p$, $(1 \leq k \leq n < p)$. Count the number of array $a[]$ of size $k$ that satisfied - $1 \leq a_1 < a_2 < \dots < a_k \leq n$ - $a_i \times a_j$ is perfect square $\forall 1 \leq i < j \leq k$ Since the result can be big, output it under modulo $p$. For convenient, you can assume $p$ is a large constant prime $10^9 + 7$ **Notice that in this blog, we will solve for generalized harder variants** **For original problem you can see in this blog [[Tutorial] An interesting counting problem related to square product](https://codeforces.cc/blog/entry/96379)** --- ## Extra Tasks **These are harder variants, and generalization from the original problem. You can see more detail [here](https://codeforces.cc/blog/entry/96379)** *Marked as solved only if tested with atleast $10^6$ queries **[Solved A](https://codeforces.cc/blog/entry/964...
are given an positive integer $n\ (1 \leq n \leq 10^{14})$. Count the number of pairs $(a, b

Full text and comments »

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

152.
By dnshgyl21, history, 5 years ago, In English
[Editorial] Newton School December 2021 Contest Credits: [user:Lubba_Lubba,2021-10-30], [user:dnshgyl21,2021-10-30], [user:Sawarnik,2021-10-30], [user:Xzirium,2021-10-30] #### [A. AC or not?](https://my.newtonschool.co/playground/code/stlxznqa697h/) ------------------ <spoiler summary = "Solution"> Take the input in variable $n$. So if $n == 1$, print $AC$, else print $WA$. </spoiler> #### [B. ABBA](https://my.newtonschool.co/playground/code/kr38ahzcg1br/) --------------------- We solve this problem in cases: Firstly, we take the case where all the characters of the string are either ‘a’ or ‘b’. For this do not require to perform any operations as every character of the string is equal. Secondly, we take the case where ‘a’ and ‘b’ both exist at least once. Here we can either make all the characters ‘a’ or ‘b’. We try to calculate the minimum operations required to make all characters ‘a’. We also observe that there exists a character ‘b’ with adjacent character ‘a’ since ‘a’ and ‘b’ both exist at least once. We...
value of $a$ is an integer and smaller than $r$, we can add $1$ to the value in map. Thus, all queries

Full text and comments »

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

153.
By death_bringer, 5 years ago, In English
Some questions about CP Hi Codeforces, At this point, I'm doing competitive programming for about a year on and off Codefores. When I started out I had a lot of questions about a lot of things but thought to myself that experience would teach me. But at this 1-year mark, I still don't know a lot of things that even new programmers do. Here's a list of questions: 1. Why use such a big template with so many macros and functions? I have solved problems till 1800 rating but never felt a need but nowadays every solution I see for hacking is using these templates. Is there any reason behind them? <br> 2. How to be friends with authors (to be a tester)? I spend a lot of time on codeforces doing stuff like stalking good programmers, checking out top comments and blogs, and rarely messaging some people to get help but how do people just become friends on codeforces? <br> 3. A lot of time I get a `WA` because of integer overflow. So, I want to use the biggest possible data type for all variables. Is that ok or it...
codeforces? 3. A lot of time I get a `WA` because of integer overflow. So, I want to use the, integer overflow. So, I want to use the biggest possible data type for all variables. Is that ok or

Full text and comments »

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

154.
By Singinginginging, history, 5 years ago, In English
random-oi-facts Dear fellow Codefeorcers, In hope of educating the vast public, I have written the following notes which hopefully can help readers to have skyrocketed ratings soon. Enjoy! the following is a poggers string function: string s, t; getline(cin, s); stringstream ss(s); while (ss >> t) cout << t << '\n'; As a side note, some coders like to use "goto die;" when they are frustrated enough with a task Global variables are initialized as 0, so you don't need to initialize them (unless you want to initialize to something else) remember to write an init function for multisets Today's fact: MATH one of the laws of log Log (a’)=,loga -> this can help prevent use of binary exponentiation to prevent an extra log factor in time complexity If you want to determine whether the i-th bit (from right, 0-based) is set (equal to 1 in binary representation) in integer x, write: if(x & (1LL << i)) (1LL << i) means "2 to the power of i" For example if(x & (1LL << 3)) { cout << "orz\n"; }...
if you try to do pq.size() — 1 with pq.size() = 0 integer overflow might happen (probably

Full text and comments »

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

155.
By balakrishnan, history, 14 months ago, In English
Solving a 4000 rated Number Theory Problem Without Terence Tao–Level Math This is about [the problem](https://codeforces.me/contest/2147/problem/G) that drew controversy in a recent Div. 1 round because it had more accepted solutions than Problem F. That was surprising since G was rated 4000+, while F was intended to be much easier. This solution path is not a polished textbook derivation. Instead, it is a poor man’s, non-mathematician programmer’s way: brute force small cases, notice patterns in the resulting fractions, and then reverse-engineer a clean formula. ### Problem in simple terms You are given an integer m. For each number x, define a sequence like this: - Start with b(0) = 1 - Then repeatedly compute b(i+1) = x ^ b(i) % m We call x "good" if this sequence eventually becomes 1 and then stays 1 forever. The question: what fraction of all positive integers x are good? (That fraction is called the density of good x.) #### Step 1: Start by brute forcing small primes Begin with a small prime modulus p. For each x = 1, 2, … up ...
. ### Problem in simple terms You are given an integer m. For each number x, define a sequence

Full text and comments »

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

156.
By LmuEmuLiberty, history, 3 years ago, In English
Encountering troubles with large numbers that can't be contained in long long In the problem description of Codeforces Round 862 (Div. 2) [F1. Survival of the Weakest (easy version)](https://codeforces.me/problemset/problem/1805/F1), it describes the fact that the answer can be quite large and needs to be outputted modulo 10^9 + 7. While trying to get this answer, I ran into the problem that the answer itself was far too big to even fit in a long long, as codeforces threw an integer overflow error on test case 5. How can I keep the numbers small? Can this problem be done with long long, and is there just a problem with my code? My solution is a faster version of brute force. Normally, one would think of brute forcing all pairs, but would cause the problem to run in N^3. My idea comes from the fact that in a vector sorted in non decreasing order, for any given index,f, as you move the index you pair with it ,s, forward, the sum of the two will naturally get larger. So I added to a priority queue every index and the one index after each one(excluding the very...
threw an integer overflow error on test case 5. How can I keep the numbers small? Can this problem be

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

157.
By Erisu._.3812, history, 4 years ago, In English
Sum of all 2^n-1 subsequences Hi, I have a small problem that has been bothering me for a while. Heres the problem: You're given an array which contains N integers (N <=2*1e5). Your task is to print out the sum of GCD of all 2^n-1 (pow(2,n)-1 for clear statement) subsequence. The definition of an subsquence is a set of index i1, i2, i3, ..., ik that i1<i2<i3<...<ik. You have to moduluo the answer by 1e9+7 otherwise is gonna be overflowed, also a[i] <=1e6 and N <=2*1e5. A sample test case is: input: 3 1 2 3 output: 10 input: 5 3 6 9 5 10 output: 72

Full text and comments »

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

158.
By MathLimitExceeded, history, 10 years ago, In English
Checking For Perfect Squares Without Overflows Hi I am solving a problem that is conceptually simple. Given an integer $x$, such that $1 \le x \le 10^{17}$, check if $v = 5x^2 + 2x + 1$ is a perfect square. I have solved this using Big Integers and long doubles in C++ (with a binary search to find the root) and used PyPy to get it accepted in Python but I did not receive satisfaction in solving it this way. Also, `__int128` do not work on SPOJ for some reason :/ I think Big Integer may be an overkill for such a problem and the uncertainty with floating point precision is never re-assuring. Hence, my question is, is there any way to solve this problem without Big Integers or long doubles in C++? Thanks
Given an integer $x$, such that $1 \le x \le 10^{17}$, check if $v = 5x^2 + 2x + 1$ is a perfect, Hi I am solving a problem that is conceptually simple. Given an integer $x$, such that $1 \le, I think Big Integer may be an overkill for such a problem and the uncertainty with floating point

Full text and comments »

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

159.
By Burglar_anu, history, 3 years ago, In English
integer overflow! I understand that if value exceeds the range of int it gives overflow error like `int a=100000 and int b=100000, int c=a*b then cout<<c; will output overflow error` but instead of storing the value if i just print it then why does it gives overflow error `int a=100000 and int b=100000, cout<<a*b; ` [submission:244431214] Please help!
integer overflow!, I understand that if value exceeds the range of int it gives overflow error like `int a=100000, I understand that if value exceeds the range of int it gives overflow error like, `int a=100000 and int b=100000, int c=a*b then cout<overflow error`, but instead of storing the value if i just print it then why does it gives overflow error

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

160.
By testUser44, history, 13 months ago, In English
Binary Exponentiation Explained (Recursive Method) ## **Why do we need Binary Exponentiation?** In competitive programming, we often need to calculate expressions like `a^b`. A simple approach might be to use `pow(a, b)` or a loop, but both are inefficient or unsafe. Let’s understand why and how we can improve it. --- ## **1. The Basic Approach** We can multiply `a` by itself `b` times: ```cpp int a = 2, b = 13, ans = 1; const int M = 1e9 + 5; for(int i = 0; i < b; ++i) { ans *= a; ans %= M; // To avoid overflow } ``` This works, but its time complexity is **O(b)** — very slow when `b` is large (for example, `b = 10^9`). --- ## **2. The Problem with `pow()` Function** You might think of using the built-in `pow()` function: ```cpp pow(a, b); ``` But this is **not reliable** for competitive programming. `pow()` works with **floating point numbers**, which cannot store large integers with 100% accuracy. It may give **wrong results** for big powers. --- ## **3. The Idea Behin...
overflow } ``` This works, but its time complexity is **O(b)** — very slow when `b` is large (for

Full text and comments »

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

161.
By Lance_HAOH, history, 9 years ago, In English
Longest subarray that contains a majority element Hi. I am trying to solve [this](https://dunjudge.me/analysis/problems/469/) problem. For convenience, I have summarized the problem statement below. <hr /> **Problem Statement** Given an array of length $ \le 2e6 $ containing integers in the range $[0, 1e6]$, find the longest **subarray** that contains a majority element (i.e. an element that occurs $> \lfloor N/2 \rfloor$ times in a list of length $N$). Time limit: 1.5s <hr /> **Example** If the given array is $[1, 2, 1, 2, 3, 2]$, The answer is $5$ because the subarray $[2, 1, 2, 3, 2]$ from position $1$ to $5$ ($0$-indexed) has the number $2$ which appears $ 3 > \lfloor 5/2 \rfloor $ times. Note that we cannot take the entire array because $ 3 = \lfloor 6/2 \rfloor $. <hr /> **My attempt** The first thing that comes to mind is an obvious brute force (but correct) solution which fixes the start and end indexes of a subarray and loop through it to check if it contains a majority element. Then we take the ...
same question on [stack overflow ](https://stackoverflow.com/questions/48273861/find-the-longest

Full text and comments »

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

162.
By steveonalex, 19 months ago, In English
Debug interactive problem more effectively on Codeforces *I cannot find any guide on this on Codeforces, which made me tweak out.* HackMD blog if you prefer it: [HackMD: Debug interactive problem more effectively on Codeforces](https://hackmd.io/@steveonalex/S1RJUMWlgl) Interactive problems are probably the bane of your existence on Codeforces, because they don't appear very often, they can fail on sample testcase and you wouldn't even know, debugging is also hard, among other things. Thus, I will present an easy way (to the best of my knowledge, it is the easiest), to test, debug and probably minimize the number of bugs generated while implementing interactive problems too. ## 1. How to write better code in general. #### Problem statement: *Given $N$ ($N \leq 10^{18}$). Jury has hidden an integer point $(x, y)$ on the 2D plane. It is guaranteed that $0 \leq x, y \leq N$. You have to somehow guess where the point is. You can ask the following question:* *- **`? i j`**: You will ask the point $(i, j)$, and jury will giv...
statement: *Given $N$ ($N \leq 10^{18}$). Jury has hidden an integer point $(x, y)$ on the 2D

Full text and comments »

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

163.
By wakanda-forever, history, 13 months ago, In English
Codeforces Round 1059 (Div. 3) Editorial [problem:2162A] Idea: [user:wakanda-forever,2025-10-10] Preparation: [user:wakanda-forever,2025-10-10] <spoiler summary = "Solution"> Let's say we have a sequence of numbers with an average equal to $k$. Adding a number greater than $k$ increases the average, while adding a smaller one decreases it. Therefore, the maximum average subarray is formed by taking the maximum element, since including anything smaller would only lower the average. Hence, the final answer is the maximum element of the given array. Time Complexity: $O(n)$ per testcase. </spoiler> <spoiler summary = "Implementation"> ~~~~~ #include<bits/stdc++.h> using namespace std; #define ll long long int main(){ int t; cin >> t; while(t--){ int n; cin >> n; vector<int> a(n); for(int i = 0; i < n; i++) cin >> a[i]; cout << *max_element(a.begin(), a.end()) << endl; } return 0; } ~~~~~ </spoiler> [...
the array $a$ is not a permutation, we can choose $x$ to be any integer that does not appear in $a

Full text and comments »

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

164.
By 07-priyanshu, history, 8 months ago, In English
Editorial for Code Enigma Welcome to the official editorial for **Code Enigma**! A massive thank you to everyone who joined us for the contest. The energy was incredible, and the HackSlash team at NIT Patna hopes you had as much fun solving the problem set as we had creating it. Below you will find the tutorials and standard C++ solutions for all the problems. Let's dive in! #### [A) Phase Two](https://codeforces.me/gym/679467/problem/A) <spoiler summary="Tutorial"> The problem asks us to find two integers, $a$ and $b$, such that their product equals a given area $n$. Mathematically, we are looking for any two factors of $n$. The constraints are small ($1 \le n \le 200$). Every integer $n \ge 1$ has at least one pair of factors: $1$ and $n$. Since the problem allows us to print *any* valid pair of dimensions, the absolute simplest approach is to always output $1$ and $n$. </spoiler> <spoiler summary="Code(C++)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { ...
for any two factors of $n$. The constraints are small ($1 \le n \le 200$). Everyinteger $n \ge 1

Full text and comments »

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

165.
By lnishan, 11 years ago, In English
An awesome list for competitive programming! This is a project I started from late January 2016. My motive is that: Although there's fantastic information out there, I think they're still spread all over the place. Therefore, in my opinion it would probably be cool if there's an [awesome list](https://github.com/sindresorhus/awesome) for competitive programming! ( *It's now featured on the main list!* ) I'm actively updating the list here: [https://github.com/lnishan/awesome-competitive-programming](https://github.com/lnishan/awesome-competitive-programming) # Awesome Competitive Programming [![Awesome](https://cdn.rawgit.com/sindresorhus/awesome/d7305f38d29fed78fa85652e3a63e154dd8e8829/media/badge.svg)](https://github.com/sindresorhus/awesome) A curated list of awesome `Competitive Programming`, `Algorithm` and `Data Structure` resources. Created with a view to connecting people to information, this list below contains a complete collection of all the fantastic resources I've collected over the course of my 11...
sample tests. | | ★★★ | [The On-Line Encyclopedia of Integer Sequences (OEIS)](https://oeis.org

Full text and comments »

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

166.
By avik26091998, history, 9 years ago, In English
Unsigned integer Why do unsigned integers wrap without extensively using the modulo operator in c++?? Suppose , Unsigned int a , b; a and b both are 2^32-1. Then what will be the value of a+b? so if they don't overflow how can we make them overflow??
Unsigned integer, don't overflow how can we make them overflow??

Full text and comments »

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

167.
By dolaisubhrabijoy, history, 6 months ago, In English
BIT MANIPULATION # Bit Manipulation for Competitive Programming Bit manipulation is one of the most powerful tools in competitive programming. Many problems that seem difficult at first can be solved elegantly by thinking in terms of bits. In this blog, we'll cover the most useful bit tricks every competitive programmer should know. --- ## 1. Binary Representation Every integer can be represented as a sequence of bits. Example: ``` 13 = 1101₂ ``` Position of bits (from right to left): ``` Bit: 3 2 1 0 1 1 0 1 ``` Value: ``` 13 = 1×2³ + 1×2² + 0×2¹ + 1×2⁰ ``` --- ## 2. Basic Bitwise Operators ### AND (&) A bit is 1 only if both bits are 1. ``` 5 = 101 3 = 011 --------- & = 001 = 1 ``` ### OR (|) A bit is 1 if at least one bit is 1. ``` 5 = 101 3 = 011 --------- | = 111 = 7 ``` ### XOR (^) A bit is 1 if bits are different. ``` 5 = 101 3 = 011 --------- ^ = 110 = 6 ``` Useful property: ``` a ^ a = 0 a ^ ...
programmer should know. --- ## 1. Binary Representation Every integer can be represented

Full text and comments »

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

168.
By rachitiitr, history, 10 years ago, In English
[Help] Getting WA on 466C [Problem Link &mdash; 466C. Number of Ways](http://codeforces.me/problemset/problem/466/C) [Solution Link with comments](http://codeforces.me/contest/466/submission/19187805) I am getting WA on test case 14. I have ensured that integer overflow doesn't exist. Can someone help?
on test case 14. I have ensured that integer overflow doesn't exist. Can someone help?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

169.
By farhan.khwaja, 16 years ago, In English
Simple usage and understanding of HashMap <p>Map is an object that stores key/volume pairs. Given a key, you can find its value. Keys must be unique, but values may be duplicated.</p><p><br></p><p>The HashMap class uses a hash table to implementation of the map interface. This allows the execution time of basic operations, such as <b>get() </b>and <b>put()</b> to be constant.</p><p><u><b><br> </b></u></p><p><u><b>An example is below:</b></u></p><p><br></p><div style="color: cyan;"><p>Q. Find the numbers Divisible by an array of numbers ie div[] between a range ie from 1 to N?</p></div><p>Ans.&nbsp; This can be solved using many ways, but we will be solving using HashMap which will help u understand the concept of HashMap in a better way..</p><p>HashMap&lt;K,V&gt; : K=key, V=value. K &amp; V can be any thing.<br></p><p><u><b><br> </b></u></p><p><u><b>CODE :</b></u></p><p><br></p><pre style="background: url(&quot;http://2.bp.blogspot.com/_z5ltvMQPaa8/SjJXr_U2YBI/AAAAAAAAAAM/46OqEP32CJ8/s320/codebg.gif&quot;) rep...
-family: arial; font-size: 12px; height: auto; line-height: 20px; overflow: auto; padding: 0px; text

Full text and comments »

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

170.
By dmkozyrev, history, 8 years ago, translation, In English
[Tutorial] Rolling hash and 8 interesting problems [Editorial] **UPD**: while I was translating this post from Russian to English, [user:dacin21,2018-07-06] wrote his post, more advanced, [link](http://codeforces.me/blog/entry/60442). I hope that my post will help beginners, but in my post more rough estimates. And in Russia we call **rolling hashes** as a **polynomial hashes**. Hello, codeforces! This blogpost is written for all those who want to understand and use polynomial hashes and learn how to apply them in solving various problems. I will briefly write the theoretical material, consider the features of the implementation and consider some problems, among them: 1. Searching all occurrences of one string of length $n$ in another string length $m$ in $O(n + m)$ time 2. Searching for the largest common substring of two strings of lengths $ n $ and $ m $ $(n \ge m) $ in $O((n+m \cdot log(n)) \cdot log(m))$ and $O(n \cdot log(m))$ time 3. Finding the lexicographically minimal cyclic shift of a string of length $ n $ in $ O(n \cdo...
with open mixing or overflow chains, then you — lucky, boldly replace the hash search for a

Full text and comments »

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

171.
By RHandarov, history, 9 years ago, In English
Change integer type in C++ Hi Codeforces, I ask for help. Can I make a variable which is int type, but when it overflow, it convert to long long type. For example I make an integer variable x. I give max integer value on x. When I add 1 to x, I do not want to overflow. I want to make ( auto convert to) long long and continue with next number. Is it possible? I am sorry if I ask a stupid question.
Change integer type in C++, Hi Codeforces, I ask for help. Can I make a variable which is int type, but when itoverflow, it

Full text and comments »

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

172.
By __Aniket__, history, 2 years ago, In English
Why is same logic in java not working? I was trying to solve Problem B from previous contest &mdash; round 976 div2. My solution is failing a testcase, its **NOT TLE**. Initially I thought maybe its due to Integer or Long overflow. To make sure I am not making any implementation errors, I even tried used the exact same code as given in editorial, still my code is failing testcase 8. Am I missing something, I tried reading other java solutions, but I think they encountered same problems, that's why most people used different approach while solving in java. I am implementing the Code 1 of problem B in editorial.<br> **Problem Link** &mdash; https://codeforces.me/contest/2020/problem/B <br> **Link to editorial** &mdash; https://codeforces.me/blog/entry/134516 <br> **Link to my submission** &mdash; https://codeforces.me/contest/2020/submission/284059093
failing a testcase, its **NOT TLE**. Initially I thought maybe its due to Integer or Long overflow. To

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

173.
By Young.YQ, history, 5 years ago, In English
How do Codeforces find these errors? I want to find them on my own computer. errors like: 1. signed integer overflow 2. array out of bounds ...
I want to find them on my own computer. errors like: 1. signed integer overflow 2. array out of

Full text and comments »

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

174.
By Adam_Jardali, history, 2 years ago, In English
Contest Editorial **Hadi & Math** What is the Sum of the numbers from 1 ... n <spoiler summary="hint"> excepted_sum = n*(n+1)/2 </spoiler> Knowing the actual sum and the excepted sum, how to find the missing sum? <spoiler summary="solution"> answer = n*(n+1)/2 &mdash; sum(Array) </spoiler> <spoiler summary="tip"> For c++ users use long long, and for java users use long to avoid overflow </spoiler> **Michael And The Easy A** <spoiler summary="hint 1"> What is the maximum sum we can obtain if we have even number of negative integers? </spoiler> <spoiler summary="hint 2"> What about odd number of negative integers? </spoiler> <spoiler summary="hint 3"> What is the maximum number of negative integers we may have in an optimal sequence? </spoiler>
> For c++ users use long long, and for java users use long to avoid overflow

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

175.
By TecTrixer, history, 3 years ago, In English
My approach to competitive programming in Rust # My approach to competitive programming in Rust Even though C++ is by far the most dominant competitive programming language today, Rust has become a viable alternative. I started using it for competitive programming a few months ago and I really like it. This is my take on using it for competitive programming, please feel free to ask questions in the comments or to add your own experiences. There are many aspects which make a language well suitable for competitive programming: ## 1. Support Without being supported by the biggest programming platforms such as [Codeforces](https://codeforces.me/), [AtCoder](https://atcoder.jp/) and [LeetCode](https://leetcode.com/) a language is mostly useless for competitive programming (this list is debatable ^^). It can still be used for platforms where you only submit the answer such as [Project Euler](https://projecteuler.net/) or [Advent of Code](https://adventofcode.com/). But I can speak from experience that it really sucks to wan...

Full text and comments »

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

176.
By Michael, 13 years ago, In English
Yandex.Algorithm Online Round 1 Analysis In the first online round of Yandex.Algorithm competition 609 participants submitted at least one solution and 396 submitted at least one correct solution. Problems _Non-Squares_ and _Kingdom Division_ were fairly easy, both resulted in approximately 300 correct submissions. Problem _Stacks of Coins_ was moderately easy and was solved by 145 participants. The three other problems proved to be more difficult. _Stickers_ could be a very challenging string problem, but small input size allowed for dynamic programming solution, which 22 contestants got right. _Assistants_ was solved by 13 participants; it required binary search, greedy, and some basic data structures to get it under time limit.During the contest, nobody was able to solve _State Roads_, which was a neat graph-theoretical problem with a simple to code, but a quite tricky solution. Congratulations to [user:Kenny_HORROR,2013-07-15] who was the only one to solve five problems, and to [user:Petr,2013-07-15], [user:tourist,20...
) In this problem we need to check if a given positive integer $n$ can be represented as a product

Full text and comments »

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

177.
By Adarsh_Singh_01, history, 20 months ago, In English
Some Tricks for Bit Manipulation 1. Checking Odd/Even if (x & 1) { // x is odd } else { // x is even } 2. Clearing the Lowest Set Bit x = x & (x &mdash; 1); 3. Extracting the Lowest Set Bit int lowest = x & -x; 4. Counting Set Bits (Brian Kernighan’s Algorithm) int count = 0; while (x) { x &= (x &mdash; 1);// clear the lowest set bit count++; } 5. XOR Swap Trick a ^= b; b ^= a; a ^= b; 6. Converting Case for Letters ->Uppercase to Lowercase: char lower = ch | ' ' ; ->Lowercase to Uppercase: char upper = ch & '_' ; 7. Next Highest Power of 2 unsigned int v = original; v--;// in case v is already a power of 2 v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16;// For 32-bit integers; extend for 64-bit as needed. v++; 8. Multiply or Divide b...
x by 4 (2^2) 9. Averaging Two Numbers Without Overflow int average = (x & y) + ((x ^ y

Full text and comments »

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

178.
By asdfghjl, history, 9 years ago, In English
841B For [my first solution](http://codeforces.me/contest/841/submission/29561145) I was expecting WA because of integer overflow (int sum) but I got TLE instead which is odd because my time complexity is O(n) and it should work for the maximum value of n(10^6)!! Then I just tried the same code with scanf/printf and got AC :| I also changed the type of sum to long long and used cin/cout like the first time and got AC! Can someone tell me WHYYYY? [link to my second solution](http://codeforces.me/contest/841/submission/29589520) [link to my third solution](http://codeforces.me/contest/841/submission/29591069)
because of integer overflow (int sum) but I got TLE instead which is odd because my time complexity

Full text and comments »

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

179.
By satylogin, history, 9 years ago, In English
Contest on Hackerearth by GEEKHAVEN competitive coding wing Hello guys :) <br> <br> Competitive coding wing of GEEKHAVEN IIIT Allahabad is organising a contest on hackerearth on saturday 12th august. The contest is mainly centred for second year students, although I hope that everyone will be able to enjoy the problem set. The contest is prepared by the members of the wing. <br> <br> It has Balanced problemset with some interesting problems to simulate the grey cells and great to start the weekend. <br><br> <strong>The link of the contest is &mdash; https://www.hackerearth.com/challenge/college/codemania-20/ </strong><br><br> The contest duration is 24 HRS. <br><br> I hope for an huge participation. :) <br><br> <strong> UPD: (EDITORIAL) </strong> <br><br> ###### 1. https://www.hackerearth.com/challenge/college/codemania-20/algorithm/cross-the-stairs/ <spoiler summary="hint"> You can simply brute force for the solution. one by call friend for each level and then compute the answer for that call. Out of all possible sol...
of carry being equal to 1 implies overflow) and 1(in case of value of flag being 0 implies (a&b&c)=0

Full text and comments »

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

180.
By rama_pang, 4 years ago, In English
NUS CS3233 Final Team Contest 2023 Editorial The contest announcement and invitation link is [here](https://codeforces.me/blog/entry/114880). The contest link is [here](https://codeforces.me/gym/104296). ## [A. Artistic Masterpiece](https://codeforces.me/gym/104296/problem/A) <spoiler summary="Tutorial"> Since $(x,y)$ is covered by the brush iff $(x - x_c)^2 + (y - y_c)^4 \leq r$, that means we can decompose the area of the brush into $O(\sqrt[4]{r})$ independent 1-dimensional intervals (a contiguous block with the same $y$-coordinate). For each center $(x_c,y_c)$ traversed by the brush, add the 1-dimensional intervals for $y \in [y_c - \sqrt[4]{r}, y_c + \sqrt[4]{r}]$. After adding these intervals, the problem is now reduced to computing the area union of 1-dimensional intervals for each separate $y$-coordinate. </spoiler> ## [B. Broken Calculator](https://codeforces.me/gym/104296/problem/B) <spoiler summary="Tutorial"> First, we consider the minimum cost to get from an integer $X$ to another integer $Y$ us...
="Tutorial"> First, we consider the minimum cost to get from an integer $X$ to anotherinteger $Y

Full text and comments »

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

181.
By RedNextCentury, 11 years ago, In English
[Gym Contest Editorial] Egyptian Collegiate Programming Contest (ECPC 2015) **Note:** All complexities mentioned in this editorial are per test case. ### A: Arcade Game Let $perm$ be the number of permutations for the digits of $n$. First, sort all these permutations in decreasing order and give each permutation a rank (0 is the largest permutation, 1 is the second largest and so on). $ans[0]=0$ $ans[1]=\displaystyle \frac{1}{perm}$ $ans[rank]=\displaystyle \frac{1}{perm} * (1+ans[rank-1]+ans[rank-2]+...)$ find the rank of $n$ and print it's value from the array. Note: the relation mentioned above can be reduced to: $ans[rank] = \displaystyle \frac{(perm+1)^{rank-1}}{perm^{rank}} $ Which could be written as (to avoid overflow): $ans[rank] = \displaystyle \frac{(\frac{perm+1}{perm})^{rank-1}}{perm} $ Complexity: $O(rank)$ ### B: Unlucky Teacher There are two ways for an answer to a question to be unique: 1) this question was answered correctly in one of the papers. 2) this question was answe...
overflow): $ans[rank] = \displaystyle \frac{(\frac{perm+1}{perm})^{rank-1}}{perm

Full text and comments »

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

182.
By Quercitron, 15 years ago, In Russian
Баг с int64 и Q+ в Delphi 7 <p>Долго пытался найти, почему мое решение получает Runtime Error. Было установлено, что программа падает во время подсчета &quot;векторного произведения&quot; по трем точкам, текст ошибки: <br />&quot;Project E.exe raised exception class EIntOverflow with message 'Integer overflow'.&quot;<br />Координаты точек не превосходили по модулю 10^9, значит координаты векторов не больше 2*10^9, и получаемый результат больше 8*10^18 никак не мог быть. А int64 это примерно до 9*10^18, и вроде все должно замечательно работать.<br />Тогда я поймал значения, на которых программа падала в этом месте. И получилась весьма странная вещь, суть которой сводится к следующему: если запустить такую программу:<br />{&quot;dollar&quot;Q+}<br />uses SysUtils;<br />var<br />  a, b, c: int64;<br />procedure bug;<br />begin<br />    a := -1834569418;<br />    b := -330651027;<br />    c := a * b;<br />end;<br />Begin<br />  bug;<br />End.<br />(&quot;dollar&quot; -- это знак доллара, но я так и не понял, можно ли...
/>"Project E.exe raised exception class EIntOverflow with message 'Integer overflow'."

Full text and comments »

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

183.
By RedNextCentury, history, 8 years ago, In English
[GYM] Damascus-CPC 2018 — Editorial A. Martadella Strikes Again ================== if $ R*R > 2*r*r $ print $1$, otherwise print $2$ $R$ and $r$ should be **long long** or **double** to avoid overflow [C++ Code](https://pastebin.com/1CKZu6yN) B. Amer and Graphs ================== Since the edges are undirected ,we can store the edges ${u,v}$ as $(u \le v)$ for every edge $(1 \le i \le n)$. Let's assign a unique number for every unique edge in the array, then our problem will be reduced to : Find the number of different segments of the array which have the exact same elements ( same frequencies as well for each element ). This problem is a classic hashing problem that can be solved this way : let's choose some random large prime numbers $P$ and $MOD$ ,for example $P=304933 , MOD=10^9+7$. replace every element ${x_i}$ from the array with $ P^{x_i} \% MOD $. now the final problem is about finding different segments of the array which have the same sum value $\% MOD$ . This sol...
$ $R$ and $r$ should be **long long** or **double** to avoid overflow [C++ Code](https

Full text and comments »

Tags gym
  • Vote: I like it
  • +20
  • Vote: I do not like it

184.
By 0t0infinity, history, 6 months ago, In English
Bits That Changed My CP Thinking — (Beginner Part) Bitwise Operations was one of the most confusing topics for me at first. But once I started understanding how bits actually work, many CP problems suddenly became much easier to think about and optimize. This blog is the result of a full day of grinding, where I tried to organize everything I know about bitwise tricks into a clear and structured form — from the basics to useful CP patterns. I tried to keep everything as simple and beginner-friendly as possible so that anyone can understand the core idea behind each trick instead of memorizing formulas. If even one trick from this blog helps someone solve a problem faster or understand bits more clearly, then this effort feels truly meaningful for me. And finally, I want to express my deepest gratitude to `Raha Ahmed` for being The Strongest support in my CP journey. Her constant encouragement, belief and presence have played a huge role in shaping my progress and I’m truly grateful for everything she has done. --- #...
right shift usually divides the number by `2` (integer / floor division). Bits on the right side

Full text and comments »

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

185.
By suraj021, 11 years ago, In English
UVA- Simple Equations — Extreme [Your text to link here...](http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2618) Problem with such large integer constraints always scare me during contests. How do i solve it. My solution gets integer overflow. P.S Positive responses are always appreciated. :)
i solve it. My solution gets integer overflow. P.S Positive responses are always appreciated. :)

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

186.
By Hamsar, history, 7 months ago, In English
Some useful Bit Manipulation Tricks Checking Odd/Even if (x & 1) { // x is odd } else { // x is even } Clearing the Lowest Set Bit x = x & (x — 1); Extracting the Lowest Set Bit int lowest = x & -x; Counting Set Bits (Brian Kernighan’s Algorithm) int count = 0; while (x) { x &= (x — 1);// clear the lowest set bit count++; } XOR Swap Trick a ^= b; b ^= a; a ^= b; Converting Case for Letters ->Uppercase to Lowercase: char lower = ch | ' ' ; ->Lowercase to Uppercase: char upper = ch & '_' ; Next Highest Power of 2 unsigned int v = original; v--;// in case v is already a power of 2 v |= v >> 1; v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16;// For 32-bit integers; extend for 64-bit as needed. v++; Multiply or Divide by Powers of Two int mul = x << 3; // Multiply x by 8 (2^3) int div = x >> 2; // Divide x by 4 (2^2) Averaging Two Numbers Without Overflow int average = (x & y) + ((x ^ y) >> 1);
div = x >> 2; // Divide x by 4 (2^2) Averaging Two Numbers Without Overflow int average = (x

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

187.
By DuyMinh3005, 3 weeks ago, In English
Rewriting blogs that aren't well written part 1: Inversion count using mergesort/fenwick tree <i>This blog's target audience is for newbies who don't know this (like me!). So, if you knew this before, it would be great if you read this blog and give me some valuable feedbacks. Thanks ^^!</i> Now for the intro: A while ago, I met a problem where it requires me to count the number of inversion of an array. Having 2 braincells, I knew nothing about this. So, I decided to ask my friends [user:ballss,2026-10-24] and [user:quanhoangbla,2026-10-24]. <strike>Of course, they are good friends so they taught me everything about that.</strike> NO. [user:ballss,2026-10-24] just called me dumb, so I decided to learn it myself. That's when I stumbled across [this](https://codeforces.me/blog/entry/86294) blog. This blog, in my opinion, is a great blog, but it was not really well written. As a result, it got heavily downvoted (I recommend you upvote that blog, although it's most likely that the author have stopped doing CP, since the last time he/she visited was 9 months ago). Although I...
long long cnt; //The number of inversions. Use long long to avoid overflow int main() { int n; cin

Full text and comments »

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

188.
By abyboi, history, 5 years ago, In English
727-D (Div 2) personal solution correction This is the problem I have been trying to solve: https://codeforces.me/contest/1539/problem/D This was my attempted solution: https://codeforces.me/contest/1539/submission/120232784 The attempt was inspired from the tutorial &mdash; Sorting b_i and using a custom two pointer technique for buying multiple products at once. However, it is failing test #8 and I don't know what is the reason (I think that maybe some integer overflow/a small bug is present otherwise my approach is correct). If someone could guide me on how to go about this that'd be great!
reason (I think that maybe some integer overflow/a small bug is present otherwise my approach is

Full text and comments »

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

189.
By DashratRajpurohit, history, 8 months ago, In English
Day 2: My Design Skills Can't Save Me from Edge Cases Yesterday, I felt like a king because I solved a few A-problems. Today? Today, the Codeforces judge reminded me that I am, indeed, a Newbie.In Frontend, if a button is 2px off, the site still works. In Competitive Programming, if your integer overflows by 1, or you forget that $n$ can be $1$, the whole thing collapses.The Lesson Learned: Thinking, Not GuessingI spent two hours today on a problem that looked simple. I kept hitting "Wrong Answer on Test 2."The Newbie mistake: Changing a + to a &mdash; and hitting submit again, hoping for magic.The Engineering fix: Actually sitting down with a pen and paper to trace the logic.I’m realizing that CP isn't about how fast you type; it's about how clearly you think before you touch the keyboard.A Little CP HumorMe: "My code is perfect. It works on the sample test cases."The Judge: "Allow me to introduce you to... Extreme Constraints."Help me out!I'm currently using C++. I've heard people talk about long long vs int being the reason for many "W...
. In Competitive Programming, if your integer overflows by 1, or you forget that $n$ can be $1$, the

Full text and comments »

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

190.
By awang11, 22 months ago, In English
Codeforces Round 996 (Div. 2) Editorial Hope you enjoyed the problems! **UPD 1:** Added implementations! **UPD 2:** It seems my wording for the solution to C is not the best, and it is causing some confusion. I've updated it to be better! **UPD 3:** Implementation links didn't work for some reason, so I've just added the code directly. [problem:2055A] <spoiler summary="Hint 1"> Look at the distance between the frogs. </spoiler> <spoiler summary="Solution"> Notice that regardless of how the players move, the difference between the numbers of the lilypads the two players are standing on always alternates even and odd, depending on the starting configuration. Then, the key observation is that exactly one player has the following winning strategy: * Walk towards the other player, and do not stop until they are forced onto lilypad $1$ or $n$. For instance, if Alice and Bob start on lilypads with the same parity, Bob cannot stop Alice from advancing towards him. This is because at the start of Alice's ...
make two times the maximum answer $4 \cdot \ell$ fit within $32$-bit integer types. It is not

Full text and comments »

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

191.
By nuredinbederu10k, history, 18 months ago, In English
Editorial For A2SV Contest #16 [Here](https://codeforces.me/contestInvitation/c220bc3ed4f1bf63dcc865426ad8de589111559f) is the link to the contest. All problems are from Codeforces' problem set. [A. Mirror Magic](https://codeforces.me/gym/613405/problem/A) <spoiler summary="Solution"> To solve the problem, we reverse the input string (since it's seen from the other side of a glass) and then replace each character with its mirrored version: 'p' becomes 'q', 'q' becomes 'p', and 'w' stays the same. We repeat this for each test case. </spoiler> <spoiler summary="Code"> ```python t = int(input()) mirror_map = {'p': 'q', 'q': 'p', 'w': 'w'} for _ in range(t): a = input() b = ''.join(mirror_map[ch] for ch in reversed(a)) print(b) ``` </spoiler> [B. Square-Free Maximum](https://codeforces.me/gym/613405/problem/B) <spoiler summary="Solution"> We're given a list of integers and need to determine the largest number that is not a perfect square. A perfect square is any number t...
that can be expressed as the square of an integer (e.g., 1, 4, 9, 16, etc.). Negative numbers can

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

192.
By jsgoller1, history, 4 years ago, In English
Unnecessary Details: 1B — Spreadsheet [problem:1B] was extremely challenging for me; it took me over 2 hours to get AC. I didn't find the editorial helpful, and then when I went to see practice solutions from red/orange people, it made even less sense (they were basically copy/paste with minor variation of the following): <spoiler summary="Solution"> ~~~~~ #include<cstdio> void g(int t){if(t){g((t-1)/26);putchar(65+(t-1)%26);}} int main(){ int n,x,y; char s[64],*p; for(scanf("%d ",&n);n--;){ gets(s); if(sscanf(s,"%*c%d%*c%d",&x,&y)==2){ g(y); printf("%d\n",x); }else{ for(x=0,p=s;*p>64;++p) x=x*26+*p-64; printf("R%sC%d\n",p,x); } } return 0; } ~~~~~ </spoiler> I'll talk about each part of the problem itself and approaches/alternatives, and then explain how the above solution (henceforth "the solution") handles it. I'll go into unnecessary detail since I'm very new to CP/CF and would've wanted this...
: C++ has no built-in for integer exponentiation. There are a couple workarounds. We could try writing

Full text and comments »

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

193.
By mouryasatyam, 5 years ago, In English
Interesting Problem on Application of Stack Interesting Problem on Application of Stack ================== Hello everyone, This is my first blog entry on Codeforces. I want to share with you all an interesting problem based on application of stack. I came across the question in hiring process and have my detailed accepted solution approach and code. Question: ------------------ Given an integer array A of length n.Find the sum of maximum of contiguous subarray times the length of the subarray for each subarray modulo 10^9+7. ![ ](/predownloaded/28/33/283374f857578b7f3d8d2982e1f96eb7161d3700.png) ####Constraints: ~~~ 1<= n <= 10^5 1<= A[i] <= 10^9 , 1<= i <=n ~~~ Note: Array may have duplicate elements. ####sample input 1 <spoiler summary="Input"> ``` 3 2 3 1 ``` </spoiler> <spoiler summary="Output"> ~~~ 27 ~~~ <spoiler summary="Explanation"> ~~~ subarrays are [2] ans=2 [3] ans=3 [1] ans=1 [2,3] ans=6 [3,1] ans=6 [2,3,1] ans=9 total=2+3+1+6+6+9=27 ~~~ </spoiler> </spoiler> ###...
approach and code. Question: ------------------ Given an integer array A of length n.Find the sum of

Full text and comments »

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

194.
By WorldWarV, history, 2 months ago, In English
Codeforces Round 1122 (Div. 3) Editorial Thanks for participating in [contest:2266]! <spoiler summary="Rate the contest!"> <spoiler summary="Quality"> - Excellent contest - Good contest - Average contest - Bad contest - Horrible contest </spoiler> <spoiler summary="Difficulty"> - Trivial contest - Easy contest - Average contest - Hard contest - Impossible contest </spoiler> </spoiler> [problem:2266A] <spoiler summary="Hint"> How many participants can possibly have solved all three problems? </spoiler> <spoiler summary="Solution"> At most $\min(a_1,a_2,a_3)$ participants could have solved all three problems. This is achievable by making the same $\min(a_1,a_2,a_3)$ participants solve every problem, then distributing the remaining solves arbitrarily. Thus, the answer is $n-\min(a_1,a_2,a_3)$. ...
number of elements to avoid overflow. If $M$ is possible, then every smaller value is also possible

Full text and comments »

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

195.
By NahC0el, 18 months ago, In English
Codeforces Round 1023 (Div 2) Editorial Hope you enjoyed the round! [problem:2107A] <spoiler summary = "Solution"> When all the elements of the array are equal, the solution is trivially impossible since the $\gcd$ of any subset will always be equal to $a_1$. That is infact the only $\texttt{No}$ case. We show a construction otherwise. Let $\operatorname{mx} = \max(a)$. Put all the elements equal to $\operatorname{mx}$ in one set, and all the other elements in the other set. Then, the $\gcd$ of the first set is $\operatorname{mx}$ while the other set will have a strictly smaller $\gcd$ (because $\gcd(a, b) \le \min(a, b)$) Time complexity is $O(n)$. </spoiler> <spoiler summary = "Code"> ```cpp #include <bits/stdc++.h> using namespace std; int main(){ int t; cin >> t; while (t--){ int n; cin >> n; vector <int> a(n); for (int i = 0; i < n; i++){ cin >> a[i]; } int mn = *min_element(a.begin(), a.end()); int mx = *max_el...
property. In both solutions, be careful to avoid overflow. One simple way is to have

Full text and comments »

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

196.
By tipTipBarsaPaani, history, 7 years ago, In English
Please resolve Memory Limit Exceeded Have a look at my [submission](https://codeforces.me/contest/20/submission/54826345) for [this](https://codeforces.me/contest/20/problem/C) problem. Also why is this error generally encountered? Is it mostly messed up space complexity or integer overflow or something else? Thanks
Also why is this error generally encountered? Is it mostly messed up space complexity orinteger

Full text and comments »

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