Codeforces Round #810 Editorial Sorry for the late editorial. May this editorial help you. If you have questions, feel free to ask. [problem:1711A] <spoiler summary="hint1."> The minimal weight is at least $1$ since $1$ divides any integer (so $1$ divides $p_1$). </spoiler> <spoiler summary="solution"> Since $k+1$ does not divide $k$, a permutation with weight equal to $1$ is: $[n,1,2,\cdots,n-1]$. </spoiler> <spoiler summary="code"> ~~~~~ #include <bits/stdc++.h> using namespace std; void work() { int n; cin>>n; cout<<n<<' '; for (int i=1;i<n;i++) cout<<i<<' '; cout<<endl; } int main() { int casenum=1; cin>>casenum; for (int testcase=1;testcase<=casenum;testcase++) work(); return 0; } ~~~~~ </spoiler> [problem:1711B] <spoiler summary="hint1."> See the party as a graph. </spoiler> <spoiler summary="hint2."> Divide the vertices into two categories according to their degrees' parity. </spoiler> <spoiler summary="solution"> Let's consider ...

Full text and comments »

[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...

Full text and comments »

About Problemsetting (for AtCoder and Codeforces) Since the amount of information available about the preparation of a competitive programming contest for AtCoder/Codeforces is very little, I decided to collect here what was my experience. I will try to both describe my experiences and give some general advice to wannabe problemsetters. I hope that this will be useful to future problemsetters who are "out of the loop". Moreover, participants might be curious to know what happens behind the scenes (and maybe the platforms may consider this as a form of constructive feedback). *Acronyms*: - AGC = Atcoder Grand Contest - GR = Codeforces Global Round ### Why I know something about problemsetting? I am in the competitive programming world since ~8 years: I have participated in IOI/ICPC/GCJ and a number of contests on AtCoder/Codeforces (and lately Codechef). I am not a top participant but, being in this world for so long, I know, more or less, all the standard tricks. Recently, I was the author of the *flagship conte...

Full text and comments »

New online judge: Library-Checker! Hello, codeforces! Today, I introduce yet another online judge, [Library-Checker](https://judge.yosupo.jp/)! As the name suggests, the object of this site is checking your libraries. The problems are "[Implement RMQ](https://judge.yosupo.jp/problem/staticrmq)", "[Enumerate Primes](https://judge.yosupo.jp/problem/enumerate_primes)", "[Exp of Formal Power Series](https://judge.yosupo.jp/problem/exp_of_formal_power_series)", "[Decompose a graph into three-connected components](https://judge.yosupo.jp/problem/three_edge_connected_components)"... and so on. All problems are managed by me. In other words, I'm the admin of this site. Anything of problems (testcases, solutions, generator, ...) are managed in [github](https://github.com/yosupo06/library-checker-problems). It means, - Anyone can add problems add testcases. Already most of the problems are prepared by other competitive programmers. - Testcases are stronger and stronger with time (ideally). Let's enjoy your l...

Full text and comments »

[Tutorial] Generating Functions in Competitive Programming (Part 2) Welcome to Part 2 of my tutorial on generating functions. The [first part](https://codeforces.com/blog/entry/77468) focused on introducing generating functions to those without any background in generating functions. In this post, I will demonstrate a few applications of generating functions in CP problems. Let us start with some relatively straightforward examples. Note: Unless stated otherwise, all computations are done modulo a convenient prime (usually $998244353$). Also, $[n]$ denotes the set $\\{1,2,...,n\\}$. ### Blatant Applications in Counting Problems **Problem.** [AGC 005 Problem F](https://atcoder.jp/contests/agc005/tasks/agc005_f) You have a tree $T$ with $n$ vertices. For a subset $S$ of vertices, let $f(S)$ denote the minimum number of vertices in a subtree of $T$ which contains all vertices in $S$. For all $1 \le k \le n$, find the sum of $f(S)$ over all subsets $S$ with $|S| = k$. Constraints: $n \le 2 \cdot 10^{5}$. <spoiler summary="Solution"> First, ...

Full text and comments »

Jngen: generic library for generating testcases Two years ago I came up with an [idea](http://codeforces.com/blog/entry/20108) (Russian only) of making a generic library for creating testcases. Months have passed, thoughts circulated in my mind over and over, and finally I sculpted something in code. Far many things are yet not implemented, but I already frequently use ones which are. Here it is: https://github.com/ifsmirnov/jngen. You can download the library itself (its single header jngen.h) [here](https://raw.githubusercontent.com/ifsmirnov/jngen/master/jngen.h). Jngen works with arrays, graphs and trees. It also can generate some strings and geometry and provides command-line options parser and cool SVG drawer. Here are some working examples. ~~~~~ cout << Array::id(10).shuffled().add1() << endl; // permutation of elements from 1 to 10 cout << Tree::random(100000, 20) << endl; // "long" tree with elongation 20 pair<string, string> test = rnds.antiHash({{mod1, base1}, {mod2, base2}}, "a-z", 10000); // should be s...

Full text and comments »

An IDE for competitive programming: fetch testcases from websites, test on testcases in one click, and more When solving CP problems, are you tired of copy-pasting the testcases, and compare the outputs with the answers by eyes? Today I'll recommend a free-software IDE for those who want to automate everything in competitive programming. [](https://github.com/coder3101/cp-editor/releases/latest) [](https://github.com/coder3101/cp-editor/releases) CP Editor began from running testcases in one click, and has been grown into an IDE with many features, like parsing sample testcases from websites and submitting to Codeforces inside the IDE. It's cross-platform and lightweight, and most important, specially designed for competitive programming. You can learn about more features on the [official website](https://cpeditor.github.io/). It's also recommended...

Full text and comments »

Codeforces Round #691, based on ByteDance — Moscow Workshops Online Contest  Hello, Codeforces community! I'm glad to invite you to Codeforces Round #691 (Div. 1) and Codeforces Round #691 (Div. 2), which will be held on [contest_time:1459]. **The round will be rated for both divisions.** The problems were taken (mostly) from the ByteDance — Moscow Workshops Online Contest, which is happening at the same time. They were prepared by me, [user:AndreySergunin,2020-12-17], and [user:amethyst0,2020-12-17]. We are very thankful to the testers: [user:low_,2020-12-18], [user:__rkm__,2020-12-18], [user:ecnerwala,2020-12-18], [user:Tima,2020-12-18], [user:IITianUG,2020-12-18], [user:thenymphsofdelphi,2020-12-18], [user:mohammedehab2002,2020-12-18], [user:namanbansal013,2020-12-19], [user:Redux,2020-12-19] for their time and great feedback. Also big thanks to Bytedance instructors [user:chenjb,2020-12-18] and [user:MiFaFaOvO,2020-12-18] for testing and r...

Full text and comments »

Codeforces Round #723 (Rated for Div 2) Hello again Codeforces! [user:Errorgorn,2021-05-25], [user:Oolimry,2021-05-25] and [user:ILoveIOI,2021-05-25] are glad to invite you to participate in [contest:1526] which will be held at [contest_time:1526]. The round will be **rated for the participants with a rating lower than 2100**. Participants from the first division are also welcomed to take part in the competition but it will be unrated for them. You will be given **2 hours and 30 minutes** to solve **6 questions**. One of the puzzles is interactive, please read [the guide of interactive](https://codeforces.com/blog/entry/45307) [problems](https://en.wikipedia.org/wiki/Binary_search_algorithm) before the contest. We would like to thank: - Our lord and saviour [user:AntontrygubO_o,2021-05-25] for amazing coordination and rejecting our poopoo tasks - [user:dantoh000,2021-05-25] and [user:tqbfjotld,2021-05-25] for roasting our enigmas and testing them before they were prepared - our many testers [user:balbit,2021-05...

Full text and comments »

Linear Basis (Xor Basis Extended) As part of the graduation requirements for my school, I have to complete a simple research project, so I decided to do something related to data structure and algorithms. I believe I have come out with a data structure that maintains the basis of vectors in $(\mathbb{Z}/m\mathbb{Z})^d$, where $m$ **may not be prime**. Since this was related to competitive programming, I think it is a good idea to share it here. Hopefully, this algorithm is actually novel :P I would like to thank: - [user:icypiggy,2021-12-26] for being my research mentor and tolerating my dumb questions - [user:rama_pang,2021-12-26] and [user:adamant,2021-12-28] for their helpful suggestions and comments Please comment under the blog or message me on codeforces if any parts are unclear or wrong. Also, I hope that some LGMs can help solve the open problems in this blog. # Introduction Maintaining the basis of vectors in $(\mathbb{Z}/2 \mathbb{Z})^d$, also known as the xor basis algorithm is a well-studie...

Full text and comments »

Polygon: Warnings for Packages — Incomplete Tests + Statement/Validator Mismatches Hello, Codeforces! If you're developing problems in Polygon, you might like this image to attract attention. <center> <img src="/predownloaded/b4/b6/b4b6e46dd5811c89440ee98bce405e54e3b905c6.png"/> </center> <i>For the new members of the community, I would like to remind you that Polygon (https://polygon.codeforces.com/) is a system developed and maintained by Codeforces for preparing programming problems. It is there that authors and coordinators develop all the problems for the rounds. Moreover, I believe a significant (large?) portion of the problems for other competitions is also developed there: various stages of ICPC, national competitions of different levels, educational problems for various courses, etc. <b>In 2023, more than 50000 problems were prepared in Polygon (only those for which a package was compiled are counted)!</b></i> We often implement such improvements in Polygon that make the process of preparing a problem more reliable. These often include var...

Full text and comments »

[Tutorial] Knapsack, Subset Sum and the (max,+) Convolution I would like to thank: - [user:tfg,2022-01-04] for his helpful discussions, digging through papers and implementing SMAWK. - [user:maomao90,2022-01-04] for proofreading. ## Prerequisites Let us first define the classical knapsack, unbounded knapsack and subset sum problems. #### Knapsack There are $N$ items. The $i$-th item has weight $w_i$ and value $v_i$. Find a set $S$ such that $\sum\limits_{i \in S} w_i \leq C$ and $\sum\limits_{i \in S} v_i$ is maximized. #### Unbounded Knapsack There are $N$ items. The $i$-th item has weight $w_i$ and value $v_i$. Find a **multiset** $S$ such that $\sum\limits_{i \in S} w_i \leq C$ and $\sum\limits_{i \in S} v_i$ is maximized. #### Subset Sum There are $N$ items. The $i$-th item has weight $w_i$. Find a set $S$ such that $\sum\limits_{i \in S} w_i = C$. You should know how to do both versions of knapsack in $O(NC)$ and subset sum in $O(\frac{NC}{32})$ before reading this blog. In this blog post, I will just show...

Full text and comments »

Ultimate guide to TopCoder plugins Hi, I wanted to present to you guide on how you should set up TopCoder Arena in order to make competing in TC much more pleasant experience. Or at least guide how to do the same thing as I did which seem very comfortable to me compared to this big pain of competing in bare default Arena. In case you want to grab easy upvotes please leave here some joke about how I am jealous about ~Radewoosh,2018-08-16 getting insane boost in his contribution by writing his blogs, but the real reason is that I screwed my setup recently and needed to go through this painful and magical setup once again and it seems this information is very nontrivial and not available publicly in a known place (which I believe is one of reasons TopCoder is losing its popularity, but I hope thanks to this post I can give slight boost to it by settling up Arena problems once and for all for many people), so I wanted to share it with others. I want to express my sincere thanks to [user:tomasz.kociumaka,2018-08-16] for guid...

Full text and comments »

Background of Good Bye 2019 Hi there! The recent Good Bye 2019 was very important event for us, and thanks for all the positive feedback we got, especially from [user:Radewoosh,2020-01-01]! As a follow-up, we would like to share some background on its preparation. ### **Problems:** **A**: This one was the hardest to come up with. We wanted it to be super easy but still to include some idea, and this is like the $10$th version of the problem. **B**: Initially there was another problem at this position. However, it turned out to be too hard for B (one orange couldn’t do it during the testing), and people didn’t like it in general, so we came up with another task. **C**: Funny, but we didn’t know that it’s always possible to make array good with adding at most $1$ element before the contest. **D**: This problem was created just 3 days before the contest to make it more balanced :O. We are glad that the contest did turn out to be well-balanced. **E**: Initially we wanted this problem to be at positi...

Full text and comments »

Codeforces Round #652 (Div. 2) Editorial ####[A. FashionabLee :](https://codeforces.com/contest/1369/problem/A) Invented by [user:DeadlyCritic,2020-06-16]. <spoiler summary="Brief Solution"> $\mathcal Brief\;\mathcal Solution :$ A $n$-regular convex polygon is beautiful if and only if $n \% 4 = 0$. ($\%$ is the modular arithmetic symbol) </spoiler> <spoiler summary="Complete Proof"> [tutorial:1369A] </spoiler> <spoiler summary="Python solution"> ~~~~~ t = int(input()) for testcase in range(t): n = int(input()) if(n%4 == 0) : print("Yes") else : print("No") ~~~~~ </spoiler> <spoiler summary="C++ solution"> ~~~~~ #include <iostream> using namespace std; int main(){ int t; cin >> t; while(t--){ int n; cin >> n; if(n % 4 == 0){ cout << "YES\n"; } else cout << "NO\n"; } } ~~~~~ </spoiler> ####[B. AccurateLee :](https://codeforces.com/contest/1369/problem/B) Invente...

Full text and comments »

[Tutorial] Supporting Queue-like Undoing on DS In many data structures, the operation of "undo" on the last update can be implemented easily: we can (usually) maintain a stack of the updates, where each update on the stack holds the memory cells it changed, and their original values. To undo an operation, just revert all changes from the top update on the stack. To maintain good complexity, we require the updates to operate in non-amortized time. I've seen this being used multiple times on DSU (without path compression). If we imagine the updates as a sequence, then we can push an update to the end, and pop an update from the end by undo. Then, this sequence is a stack of updates. Here we discuss the idea of having a queue of updates: we can add a new update, or undo the oldest update still active. Specifically, this blogpost attempts to solve the following problem: Given a data structure that can support some updates, some queries and an "undo" operation (each with their own time complexity), how can we create a data structu...

Full text and comments »

On Div2ABs 2 years ago, [user:antontrygubO_o,2022-04-27] wrote [a blog](https://codeforces.com/blog/entry/75163) about div2ABs where he expressed his opinions that d2ABs should not be about "here is a statement, please implement what is written there". Thanks to him, the quality of d2ABs (and problem quality in general) have certainly improved. However, I still believe that there still quite large differences between how coordinators/problemsetters view d2ABs and how the intended participants view them. From the survey made by [user:kpw29,2022-04-27], we can see that most people agree that most people agree that we should **primarily** consider the target audience when proposing a task. I too think if a task is boring to div 1 contestants, we should not think of that as a reason to immediately disqualify a problem from being a d2A.  I think when people judge the interesting-ness of d2As, they try...

Full text and comments »

I compiled a list of almost all useful blogs ever published on Codeforces [update: till 09.06.2021] <h3 style="color:red">If there are any blogs that I have missed, please tell in the comment section. Thank you.</h3> # Mathematics Stuff - [Number Theory in Competitive Programming [Tutorial]](https://codeforces.com/blog/entry/46620) - [Number of points on Convex hull with lattice points](https://codeforces.com/blog/entry/62183) - [FFT, big modulos, precision errors.](https://codeforces.com/blog/entry/48465) - [Number of ways between two vertices](https://codeforces.com/blog/entry/19078) - [Mathematics For Competitive Programming](https://codeforces.com/blog/entry/76938) - [FFT and NTT](https://codeforces.com/blog/entry/19862) - [Burnside Lemma](https://codeforces.com/blog/entry/51272) - [Number of positive integral solutions of equation 1/x+1/y=1/n!](https://codeforces.com/blog/entry/76836) - [On burnside (again)](https://codeforces.com/blog/entry/64860) - [Simple but often unknown theorems/lemmas/formula? Do you know?](https://codeforces.com/blog/entry/55912) - [Probabili...

Full text and comments »

Educational Codeforces Round 88 Editorial [problem:1359A] Idea: [user:BledDest,2020-05-29] <spoiler summary="Tutorial"> [tutorial:1359A] </spoiler> <spoiler summary="Solution 1 (BledDest)"> ~~~~~ t = int(input()) for i in range(t): n, m, k = map(int, input().split()) d = n // k a1 = min(m, d) a2 = (m - a1 + k - 2) // (k - 1) print(a1 - a2) ~~~~~ </spoiler> <spoiler summary="Solution 2 (BledDest)"> ~~~~~ t = int(input()) for i in range(t): n, m, k = map(int, input().split()) ans = 0 d = n // k for a1 in range(m + 1): for a2 in range(a1 + 1): if(a1 > d): continue if(a1 + a2 > m): continue if(a1 + (k - 1) * a2 < m): continue ans = max(ans, a1 - a2) print(ans) ~~~~~ </spoiler> [problem:1359B] Idea: [user:BledDest,2020-05-29] <spoiler summary="Tutorial"> [tutorial:1359B] </spoiler> <spoiler summary="Solution (pikmike)"> ...

Full text and comments »

My winning theory in IOI 2018 & 2019 — Why I won 2 golds in IOI Dear Codeforces community.<br /> According to [IOI 2019 Results](http://stats.ioinformatics.org/results/2019), I got the 25th place and got successful gold medals twice in a row.<br /> Although it was pretty close to the gold-medal border (only 6.14pts / 600 difference) and it was lower performance than IOI 2018, which I participated when I was orange in Codeforces, I had many chances to get more points in this IOI, even for top 10. Since there are not so many people who have got two gold medals in IOI (and there were many requests like "I want [user:E869120,2019-08-14] to talk about how to get gold in IOI" like [this comment](https://codeforces.com/blog/entry/66909?#comment-510127) and [this comment](https://codeforces.com/blog/entry/66909?#comment-513129)). I want to write something about IOI, which may be useful for people who will participate in IOI next year and also some years later.<br /> <br /> <br /> ### A. First of all At...

Full text and comments »

Tips for writers: What requires a proof? If you are a contestant, you can be relaxed and you can do anything (except for cheating). It's perfectly fine if you just guess the solution and submit it without knowing why (though personally I don't find it very beautiful). However, if you are a writer, you need to prove your solution. Here is the list of things you have to prove: #### 1. Correctness. Does your solution always return correct answers for all possible valid inputs? - GOOD: Strict proof. - BAD: _My intuition tells that this is correct!_ - BAD: _I tried really hard to come up with counterexamples, but I couldn't. It must be correct!_ #### 2. Time Complexity. Does your solution always run in time for all possible valid inputs? - GOOD: It's $O(n^2)$ and the constraints say $n \leq 1000$. It should work. - GOOD: For this problem we can prove that the slowest case is xxx. Experimentally, my solution works for the input xxx under the given TL. - BAD: _I tried really hard to generate various testcases, and ...

Full text and comments »

Codeforces Round #842 (Div. 2) Editorial Hope you liked the problems! <spoiler summary="(from thanhchauns2) Before the round starts"> This is my second contest on Codeforces, inspiring coordination has been done for the last several months, cannot wait until the third round is released! <spoiler summary="Testers' predictions"> <table> <tr style ="background-color:#D3D3D3"> <th>Tester</th> <th>A</th> <th>B</th> <th>C</th> <th>D</th> <th>E</th> <th>F</th> </tr> <tr> <td>[user:xiaoziya,2022-12-13]</td> <td>900</td> <td>1000</td> <td>1400</td> <td>1800</td> <td>2100</td> <td>3000</td> </tr> <tr> <td>[user:feecle6418,2022-12-13]</td> <td>900</td> <td>1200</td> <td>1400</td> <td>1700</td> <td>2200</td> <td>2900</td> </tr> <tr> <td>[user:cadmiumky,2022-12-13]</td> <td>800</td> <td>1100</td> <td>1550</td> <td>1900</td> <td>2200</td> <td>-</td> </tr> <tr> <t...

Full text and comments »

Codeforces Raif Round 1 Editorial [problem:1428A] ------------------ Setter: [user:bensonlzl,2020-10-17] Prepared by: [user:errorgorn,2020-10-17] <spoiler summary="Hint 1"> Consider when $x_1=x_2$ </spoiler> <spoiler summary="Hint 2"> Consider when $x_1 \ne x_2$ </spoiler> <spoiler summary="Solution"> We consider 2 cases. The first is that the starting and ending point lie on an axis-aligned line. In this case, we simply pull the box in 1 direction, and the time needed is the distance between the 2 points as we need 1 second to decrease the distance by 1. The second is that they do not lie on any axis-aligned line. Wabbit can pull the box horizontally (left or right depends on the relative values of $x_1$ and $x_2$) for $|x_1-x_2|$ seconds, take 2 seconds to move either above or below the box, then take another $|y_1-y_2|$ seconds to move the box to $(x_2,y_2)$. </spoiler> <spoiler summary="Code (C++)"> ```c++ #include <bits/stdc++.h> using namespace std; int main(){ ios_base::...

Full text and comments »

Educational Codeforces Round 83 Editorial [problem:1312A] Idea: [user:BledDest,2020-03-10] <spoiler summary="Tutorial"> [tutorial:1312A] </spoiler> <spoiler summary="Solution (vovuh)"> ~~~~~ for i in range(int(input())): n, m = map(int, input().split()) print('YES' if n % m == 0 else 'NO') ~~~~~ </spoiler> [problem:1312B] Idea: [user:Roms,2020-03-10] <spoiler summary="Tutorial"> [tutorial:1312B] </spoiler> <spoiler summary="Solution (Roms)"> ~~~~~ for t in range(int(input())): n = input() print(*sorted(map(int, input().split()))[::-1]) ~~~~~ </spoiler> [problem:1312C] Idea: [user:adedalic,2020-03-10] <spoiler summary="Tutorial"> [tutorial:1312C] </spoiler> <spoiler summary="Solution 1 (adedalic)"> ~~~~~ fun main() { val T = readLine()!!.toInt() testCases@for (tc in 1..T) { val (_, k) = readLine()!!.split(' ').map { it.toLong() } val a = readLine()!!.split(' ').map { it.toLong() }.toLongArray() var maxPower ...

Full text and comments »

Editorial of Pinely Round 3 (Div. 1 + Div. 2) The official implementations of all the problems are [here](https://drive.google.com/file/d/1q2PHS9nJt84FRwfMoiMslQULFE4dTMU4/view?usp=sharing). <spoiler summary="Timeline of the round proposal (may contain spoilers)"> (problems D', H', etc. were not used) - Feb 19, 2022: I proposed problem D' to [contest:1654], but it was not used. - Mar 13, 2023: I invented problem A. - May 16: I invented problem H'. - May 19: I realized problem G can be solved in $O(n)$ time and we used it in the Italian team selection test for IOI. - Jul 04: I opened a Div. 1 proposal containing A, D', G, H' and other problems which are not going to be used. - Aug 09: I invented problem I, with intended solution in $O(n^3)$. - Sep 27: I invented problem C. - Oct 14: [user:errorgorn,2023-12-23] replied to my contest proposal. - Nov 02: I invented problem D''. [user:errorgorn,2023-12-23] solved problem I in $O(n^2 \log n)$. - Nov 08: I invented problems E and F. I didn't propose problem F because I th...

Full text and comments »

Codeforces Round #873 (Div. 1 & 2) Editorial ## [problem:1828A] Idea: [user:thenymphsofdelphi,2023-05-14] <br> Preparation: [user:Mike4235,2023-05-14] <spoiler summary="Hint 1"> Remember the sum of the first $n$ positive integers? </spoiler> <spoiler summary="Hint 2"> Every positive integer is divisible by $1$. </spoiler> <spoiler summary="Solution"> Consider the array $a = \left[1, 2, \ldots, n\right]$ that satisfies the second condition. It has the sum of $1 + 2 + \dots + n = \frac{n(n+1)}{2}$. One solution is to notice that if we double every element $(a=\left[2, 4, 6, \ldots, 2n\right])$, the sum becomes $\frac{n(n+1)}{2} \times 2 = n(n + 1)$, which is divisible by $n$. Another solution is to increase the value of $a_1$ until the sum becomes divisible by $n$. This works because every integer is divisible by $1$, and we only need to increase $a_1$ by at most $n$. Time complexity: $\mathcal{O}(n)$ </spoiler> <spoiler summary="Implementation 1"> ```c++ #include <bits/stdc++.h> using namespace s...

Full text and comments »

C++20 is back In contests and in the custom invocation, after a pause, one can again find GNU G++20 64-bit. However, the [slowdown issue](https://codeforces.com/blog/entry/126654) because of which the language disappeared persists, there are still snippets of code that can slow down the execution on Codeforces servers by a factor of 100 or so. So what is the official position of Codeforces headquarters and of our community on that? 1. Are there general methods of constructing testcases that can exploit this GCC/Windows bug and therefore slow down solutions (like there are [anti-hash tests](https://codeforces.com/blog/entry/62393) for solutions using `unordered_set`)? Are there methods that slow down both contest mode and custom invocation mode (since [submission:249807302] is only slow in the contest mode whereas [submission:253289473] is only slow in the custom invocation)? 2. If so, should we expect such tests in future contests, will such methods be used during the test preparation in co...

Full text and comments »

CodeTON Round 3 (Div. 1 + Div. 2) Editorial [A — Indirect Sort](https://codeforces.com/contest/1750/problem/A) ===== Authors: [user:mejiamejia,2022-10-31], [user:Ecrade_,2022-11-06] <spoiler summary="Solution"> We claim that we can sort the array if and only if $a_1 = 1$. **Necessity** We can notice that index $1$ cannot be affected by any swap operation. Let's see what happens to the value $1$. According to the definition of the operation, it can either increase or be swapped. In order to be increased, there must exist some $k$ such that $1 > a_k$, but since $1$ is the minimum possible value, it will never be true as other values in array $a$ can only increse as well. Since index $1$ can not be affected by a swap operation and $a_1>1$, we conclude that if $a_1 \neq 1$, the answer is **No**. **Sufficiency** Let's focus on the second operation. Since we have $a_1 = 1$, we can always choose $i=1$ and the operation then turns into picking some pair $2 \le j < k \le n$ and swapping $a_j$ with $a_k$. It's t...

Full text and comments »

Codeforces Round #833 (Div. 2) Editorial [A &mdash; The Ultimate Square](https://codeforces.com/contest/1748/problem/A) ------------------ Author: [user:Gheal,2022-10-22] <spoiler summary="Hints"> <spoiler summary="Hint 1"> If $n$ is odd, it is possible to create a square using all $n$ blocks. </spoiler> <spoiler summary="Hint 2"> If $n$ is even, it is possible to create a square using only the first $n-1$ blocks, since $n-1$ is odd. Can we use the last block to create a larger square? </spoiler> </spoiler> <spoiler summary="Solution"> If $n$ is odd, let $k=\frac{n+1}{2}$ be the width of the last block. It is possible to create a square of side length $k$ using every block as follows: - Line $1$ contains a $1 \times k$ block; - Line $2$ contains a $1 \times 1$ block and a $1 \times (k-1)$ block; - Line $3$ contains a $1 \times 2$ block and a $1 \times (k-2)$ block; - $\ldots$ - Line $i$ contains a $1 \times (i-1)$ block and a $1 \times (k-i+1)$ block; - $\ldots$ - Line $k$ contains a $1 \times (...

Full text and comments »

Codeforces command-line interface tool Codeforces Tool is a command-line interface tool for Codeforces. It's written in golang (without any browser driver). And it's fast, small(only about 7 MB), cross-platform(Windows, macOS, Linux) and powerful. You can find the source and binary files in my git repo <https://github.com/xalanq/cf-tool> You can download the tool from release page <https://github.com/xalanq/cf-tool/releases> Features: * Support Contests, Gym, Groups and acmsguru. * Support all programming languages in Codeforces. * Submit codes. * Watch submissions' status dynamically. * Fetch problems' samples. * Compile and test locally. * Clone all codes of someone. * Generate codes from the specified template (including timestamp, author, etc.) * List problems' stats of one contest. * Use default web browser to open problems' pages, standings' page, etc. * Setup a network proxy. Setup a mirror host. * Colorful CLI.  ![...

Full text and comments »

Codeforces Round #875 (Div.1 + Div. 2) Editorial [1831A &mdash; Twin Permutations](https://codeforces.com/contest/1831/problem/A) ------------------ Author: [user:Gheal,2023-05-25] <spoiler summary="Hints"> <spoiler summary="Hint 1"> If $a_i+b_i \le a_{i+1}+b_{i+1}$, then $a_i+b_i$ can be equal to $a_{i+1}+b_{i+1}$. </spoiler> <spoiler summary="Hint 2"> Building on the idea from the first hint, can we build a permutation $b$ such that $a_1+b_1=a_2+b_2=\ldots=a_n+b_n$? </spoiler> </spoiler> <spoiler summary="Solution"> Since $a_i+b_i \le a_{i+1}+b_{i+1}$, then $a_i+b_i$ can be equal to $a_{i+1}+b_{i+1}$. Therefore, any permutation $b$ which satisfies $a_1+b_1=a_2+b_2=\ldots=a_n+b_n$ is a valid answer. If $b_i=n+1-a_i$, then: 1. $b$ is a permutation; 2. $a_1+b_1=a_2+b_2=\ldots=a_n+b_n=n+1$ Consequently, $b=[n+1-a_1,n+1-a_2,\ldots,n+1-a_i,\ldots,n+1-a_n]$ is a valid answer. Time complexity per test case : $O(N)$ </spoiler> <spoiler summary="Code (Gheal, C++)"> ~~~~~ #include<bits/stdc++.h>...

Full text and comments »

Codeforces Round 887 (Div 1, Div 2) Tutorial We hope you enjoyed these problems :) This contest has been in the works for almost a year. <spoiler summary = "About the Authors"> This round was mostly made possible by problemsetters from the [CerealCodes](https://www.cerealcodes.org/) initiative! CerealCodes is an organization based in the United States dedicated to running high quality competitive programming contests. You can check out our previous contest [here](https://codeforces.com/gym/103886). </spoiler> **UPD: D1D Editorial have been updated** **UPD 2: D1D Editorial now has images by [user:EmeraldBlock,2023-08-01]. As an apology gift for being so slow, the image generator is programmatic and available [here](https://artofproblemsolving.com/texer/codeforces).** #### [problem:1853A] Problem Credits: [user:buffering,2023-06-02] Analysis: [user:buffering,2023-06-02] <spoiler summary="Hint 1"> To make $a$ not sorted, we just need to pick one index $i$ so $a_i > a_{i + 1}$. How do we do this? </spoiler...

Full text and comments »

Kotlin Heroes: Episode 6 — Editorial First of all, I would like to thank all testers of the round: [user:Um_nik,2021-03-09], [user:IlyaLos,2021-03-09], [user:Roms,2021-03-09], [user:nuipojaluista,2021-03-09], [user:Supermagzzz,2021-03-09], [user:Stepavly,2021-03-09], [user:hg333,2021-03-09]. Also huge thanks to co-authors of the contest: [user:Ne0n25,2020-11-12], [user:adedalic,2020-11-12], [user:vovuh,2020-11-12] and [user:pikmike,2020-11-12]. I hope you enjoyed participating in the round! Okay, now for the editorial itself: [problem:1488A] Idea: [user:BledDest,2021-03-09], preparation: [user:Neon,2021-03-09] <spoiler summary="Tutorial"> [tutorial:1488A] </spoiler> [problem:1488B] Idea: [user:BledDest,2021-03-09], preparation: [user:BledDest,2021-03-09] <spoiler summary="Tutorial"> [tutorial:1488B] </spoiler> [problem:1488C] Idea: [user:vovuh,2021-03-09], preparation: [user:vovuh,2021-03-09] <spoiler summary="Tutorial"> [tutorial:1488C] </spoiler> [problem:1488D] Idea: [us...

Full text and comments »

What do you do if you get WA? _One day you came up with a brilliant solution during a contest, implemented it very carefully, and submitted it confidently. The verdict was ...... WA._ Probably most of you have experienced this sad situation. You can start debugging if you know the reason of WA, but what do you do otherwise? I frequently have trouble with this situation, so I'd like to ask your opinion. What should we do when we get WA? Here are several possibilities: **1. Reread your code.** This is the simplest way of debugging. You may find some stupid typos. **2. Try various manual testcases.** Examples may not be very strong. Try some small tricky cases against your code. **3. Recheck the correctness of your algorithm.** Have you proved your solution? Is the proof correct? **4. Reread the statement.** You may have misunderstood the statement. Read it again to make sure that you understood the task correctly. **5. Stress-testing.** Write a straightforward solution, create lot...

Full text and comments »

[Tutorial] Amogus Trick omg hi Codeforces! I've been meaning to write a blog about this interesting, but not (as far as I know) documented trick for a while. I've decided to call it the Amogus trick after the first problem where I encountered and used it. Prerequisites ------------------ - [DSU](https://cp-algorithms.com/data_structures/disjoint_set_union.html) - Basic knowledge of [2-SAT](https://cp-algorithms.com/graph/2SAT.html) (definitely not required, but it may make the blog easier to understand) Focus Problem: [problem:1594D] ------------------ First, let's solve an easier version of this problem, where we just need to find whether there exists a configuration of player roles (i.e. Crewmate or Imposter) such that all the statements made by players so far are true. Let's look at the two different types of statements made by players separately. - **Case 1: Player $i$ claims Player $j$ is a crewmate.** Now, if Player $i$ is a crewmate, Player $j$ will also be a crewmate. Similarly, ...

Full text and comments »

General ideas **// Finally translated!** Hi everyone! Do you like ad hoc problems? I do hate them! That's why I decided to make a list of ideas and tricks which can be useful in mane cases. Enjoy and add more if I missed something. :) [cut]<br> **1. Merging many sets in $O(n\log{n})$ amortized.** If you have some sets and you often need to merge some of theme, you can do it in naive way but in such manner that you always move elements from the smaller one to the larger. Thus every element will be moved only $O(\log{n})$ times since its new set always will be at least twice as large as the old one. Some versions of DSU are based on this trick. Also you can use this trick when you merge sets of vertices in subtrees while having dfs. **2. Tricks in statements, part 1.** As you may know, authors can try to hide some special properties of input to make problem less obvious. Once I saw constraints like $\relax 1 \leq a \leq b \leq 10^5, \dots, ab \leq 10^5$. Ha-ha, nice joke. It is actually...

Full text and comments »

Inconsistent times and TLE with C++17 (64bit) vs. C++17 Hi, while submitting [problem:1535F] for the previous educational round I did observe a strange behaviour. I submitted the **absolutely same** code several times:  As you can see, submitting with **C++17** was AC every single time. Submitting with **C++17 (64bit)** lead to timeouts on different testcases, like 18, 27 or 32 but also to several AC with all testcases 18,27,32 only needing <300ms in 64bit. I read my code about 20 times now checking for out of bounds errors or stupid mistakes. I have no random numbers generated. I also did several tests by generating a big number of random testcases with both 64bit and 32bit locally, but I couldn't reproduce this behaviour. I got consistent times all around. Now I'm clueless and want to ask whether someone has an idea why this happens. - AC 32bit: [submission:118502792] - AC 64bit: [submission:118503021] - TLE Testcase 18 64bit: [submission:118502885]...

Full text and comments »

Does Codeforces Need All These Testcases? Codeforces now has 342281 testcases. But how many of these are actually relevant? Let's call a test redundant if nobody has ever submitted a solution that failed on that test. Here's a graph showing what percentage of testcases are redundant over all rounds.  Turns out to be that 173195 tests out of the 342281 tests are actually redundant &mdash; no verdict would change if these tests were never there. That's around 50%. I actually expected more, but still, a lot of testcases are redundant. Here is another representation of data, where the y-axis shows how many problems of each percentage of redundancy.  Codeforces can take advantage of this and save resources by not running these tests at all. But how long should we wait before deciding that the current non-redundant testcases are enough?  As you can see a lot of problems get saturated in the first mon...

Full text and comments »

Codeforces Round 931 (Div. 2) Editorial [1934A &mdash; Too Min Too Max](https://codeforces.com/contest/1934/problem/A) <spoiler summary="Solution"> <spoiler summary="Hint 1"> What will be answer if there were only $4$ elements in the array? </spoiler> <spoiler summary="Solution"> Suppose if there were only $4$ elements in the array. Let them be $a \leq b \leq c \leq d$. Then the answer will be maximum of the three cases which are listed as follows:- $$|a-b|+|b-c|+|c-d|+|d-a| = 2*d - 2*a$$ $$|a-b|+|b-d|+|d-c|+|c-a| = 2*d-2*a$$ $$|a-c|+|c-b|+|b-d|+|d-a| = 2*(d+c)-2*(a+b)$$ so clearly $2*(d+c)-2*(a+b)$ is the maximum. So, to maximize this we can set $d$, $c$ as large as possible and $a$, $b$ as small as possible i.e. $d=a_n$, $c=a_{n-1}$, $b=a_{2}$ and $a=a_{1}$ where $a_i$ means $i^{th}$ element in sorted order of given array. </spoiler> </spoiler> <spoiler summary="Code (C++)"> ``` #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false);...

Full text and comments »

My sad story When I was submitting the problem D in round #371, I clicked the "Choose File" button and selected my code. Before the submission, I read my code another time, found a bug in my code and fixed it. And then I clicked the "submit" button. But it turned out that my solution got wrong answer on pretest 4. I stress-tested my solution, and found it passed the big random data. I was really shocked. umm... Maybe my solution failed on some small testcases. So I tried many ways to generate testcases. But my solution was right on all the testcases I generated. After struggling for about 40mins, I gave up and submitted it again. It passed all the pretests. I compared two codes, and just found I submitted the old version (before fixing the bug) at first time. After asking my roommate, he said when you clicked the "Choose File" button, it would upload the file instead of recording the path. In the rest time of the contest, I tried to solve problem B and E but failed. <S>I think ...

Full text and comments »

Testcase Generator Website **Hello Dear Codeforces Community,** I ([user:farukkastamonuda,2023-07-22]) developed the testcase generator website [Testcase Generator](https://testcase-generator67.netlify.app/) for competitive programmers with my brother [user:ExpertHunter,2023-07-22]. Generating test cases is a significant part of creating problems in competitive programming. However, there is not any prepared website that is designed for this task and problem setters should use some programming languages to prepare test cases. Moreover, these written scripts are used to create test cases for a specific single problem. After analyzing Codeforces input formats, we thought that many of these formats can be generalizable and producible. **Some of doable things on this website are:** - Generating basic types: integer, floating number, string, char, and pair. - Generating 1-D, and 2-D arrays of basic types. - Creating a tree/graph with many features such as acyclic, connected, multiple edg...

Full text and comments »

$O(N^2)$ solution to Facebook Hacker Cup 2021 Round 1 problem A2 (part one) Right after the end of Facebook Hacker Cup 2021 Round 1, [user:wjomlex,2021-09-25] posted the following [comment](https://codeforces.com/blog/entry/94726?#comment-839269) in the discussion section under the announcement blog: > A common issue was people writing O(N^2) solutions to problem A when O(N) solutions are necessary. You won't be able to run an O(N^2) solution in 6 minutes when N = 800,000. But is this really true? Challenge accepted! ##### Problem A1 <div> <spoiler summary="Spoiler"> First of all, here is an $O(N)$ solution for [problem A1](https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-1/problems/A1): <spoiler summary="Spoiler"> ~~~~~ #include <iostream> #include <vector> #include <stdint.h> using namespace std; /* * This is a solution for problem A1. Time complexity: O(N) * Characters in the input buffer are remapped: 'F' => 0, 'X' => 1, 'O' => 2 */ static int32_t solve_a1(const int8_t *arr, int n) { int32_t ans = 0, h...

Full text and comments »

[Tutorial] Inclusion-Exclusion Principle Hello, Codeforces! The reason why I am writing this blog is that my ACM/ICPC teammate [user:calabash_boy_love_15,2019-01-18] is learning this technique recently(he is a master in string algorithms,btw), and he wanted me to provide some useful resources on this topic. I found that although many claim that they do know this topic well, problems concerning inclusion-exclusion principle are sometimes quite tricky and not that easy to deal with. Also, after some few investigations, the so-called "Inclusion-Exclusion principle" some people claim that they know wasn't the generalized one, and has little use when solving problems. So, what I am going to pose here, is somewhat the "Generalized Inclusion-Exclusion Principle". Most of the describing text are from the graduate text book _Graduate Text in Mathematics 238, A Course in Enumeration_, and the problems are those that I encountered in real problem set, so if possible, I'll add a link to the real problem so that you can solve it by yours...

Full text and comments »

[Tutorial] Quick start in solving problems on GPU + CPU Hello, codeforces! Do you have modern GPU and CPU and want to calculate something with them, but you don't know how to do it? Dont be upset, because you can read this blog and run your first GPU program on your AMD/Intel/NVIDIA GPU. I will describe an installation process and then we will dive into the C++ code. As an example, we will calculate a lot of mazes for [Bug Game](https://codeforces.com/blog/entry/115144) in parallel. For doing this in simple way, we will use library [Boost.Compute](https://www.boost.org/doc/libs/1_80_0/libs/compute/doc/html/index.html), which is a C++ STL-style wrapper over OpenCL library. [cut] ... Installation for MacOS (Apple M1 Pro) ================== As [user:Gosunov,2023-06-10] said, `OpenCL` and `g++` are pre-installed on `MacOS`. Everything that you have to do is install `Boost` with command `brew install boost`. After this you will be able to compile your program with command `g++ -std=c++17 -O3 -I/opt/homebrew/Cellar/boost/1.81.0_1/...

Full text and comments »

Codeforces Round #881 (Div. 3) Editorial [problem:1843A] Idea: [user:Sokol080808,2023-06-21], prepared: [user:molney,2023-06-21] <spoiler summary="Tutorial"> [tutorial:1843A] </spoiler> <spoiler summary="Solution"> ~~~~~ def solve(): n = int(input()) a = [int(x) for x in input().split()] a.sort() ans = 0 for i in range(n // 2): ans += a[-i-1] - a[i] print(ans) t = int(input()) for _ in range(t): solve() ~~~~~ </spoiler> <spoiler summary="Rate the problem"> - Didn't solve - Good task - Average task - Bad task </spoiler> [problem:1843B] Idea: [user:EJIC_B_KEDAX,2023-06-21], prepared: [user:molney,2023-06-21] <spoiler summary="Tutorial"> [tutorial:1843B] </spoiler> <spoiler summary="Solution"> ~~~~~ T = int(input()) for _ in range(T): n = int(input()) a = list(map(int, input().split())) sum = 0 cnt = 0 open = False for x in a:...

Full text and comments »

A command-line tool to automate your CP workflow without cluttering your workspace with testcases. Command line tools can efficiently **automate** monotonous and **repetitive tasks** (such as creating source code files, copying boilerplate code, running code on sample testcases, etc.) and make competitive programming more fun. There already **exist various choices** for command line tools in the competitive programming ecosystem like [cpb](https://searleser97.github.io/cpbooster/) and [cf tool](https://github.com/xalanq/cf-tool). The problem with these tools is they follow the **"Flat File Structure" philosophy** in which your source code and testcase files are kept in the same folder to improve the speed of manipulating (creating, updating, deleting) them. This approach causes a mess making it **hard to navigate** between source code files. As changes in testcase are rare, saving a few seconds is manipulating them might not be worth it.  CPPT is a cross-platform command-line tool made specifically to address this issue. It **hi...

Full text and comments »

Problems of CSP(China) Sharing & Discussion Hello codeforces! CSP-J/S(Certified Software Professional-Junior/Senior) of China ended. CSP-J/S (or you can say NOIp ,but it has been dead) was held by OI rules. In OI rules, every problem has the same score distribution $100$ points. In one problem, there is several testdatas (like $10$ ,$20$ or $25$). Every testdata has the same score distributions. Once you pass a testdata, you can get the score. You can submit your code during the contest, but can't see the result. The organizer will judge all the programs together after contest. I'd like to share the problems of CSP-S here! Hope you guys enjoy. Don't mind my poor English, I spent a whole afternoon translating. <spoiler summary="D1T1 code"> $\bf{D1T1\ Gray\ Code\ 1s\ 256MB}$ $\bf{Statement}$ _Gray Code_ is a special permutation of $n$-bit binary strings ,which requires adjacent strings have **exactly one different** bit. Specially, the first string is adjacent to the last string. One example of $2$-bit _Gray Cod...

Full text and comments »

Codeforces Round #878 (Div.3) Editorial [problem:1840A] Idea: [user:isosto,2023-06-06], preparation: [user:isosto,2023-06-06] <spoiler summary="Tutorial"> [tutorial:1840A] </spoiler> <spoiler summary="Solution"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { int n; cin >> n; string s; cin >> s; int i = 0; while (i < n) { int start = i; cout << s[i++]; while (s[i++] != s[start]); } cout << endl; } } ~~~~~ </spoiler> <spoiler summary="Rate the problem"> - Didn't solve - Good task - Average task - Bad task </spoiler> [problem:1840B] Idea: [user:diskoteka,2023-06-06], preparation: [user:diskoteka,2023-06-06] <spoiler summary="Tutorial"> [tutorial:1840B] </spoiler> <spoiler summary="Solution"> ~~~~~ #include <bits/stdc++.h> using namespace std; int32...

Full text and comments »

Your Future Ratings Predictor is here!! (upd:1.0 UI Added) **Update 1.0** : The app is now live [here](https://cffrpredict.netlify.app/). Hello Codeforces, So, I got some requests to predict the future ratings from my fellow coders and I simply didn't ignore it. I have worked a way through which a user can get their future ratings predicted by a piece of code. It was inspired by [user:stefdasca,2021-06-21]'s blog but since I am a bit weak in geometry and graphs so I decided to write a code for it (ignoring the fact that I am weak in coding too). I have tested it rigourously for like 2-3 times and it did work as the results were satisfactory. For Eg: The case of 1-gon's profile: <spoiler summary="Screenshot proof"> <img src="https://i.ibb.co/fQDt7gT/Pics-Art-06-21-06-26-14.jpg" alt="Pics-Art-06-21-06-26-14" border="0"> </spoiler> #### How to get your future ratings:<br> <spoiler summary="Using Web hosted page"> I have made a UI for my app in DHTML. You can give it a try and your review. It is currently deployed [h...

Full text and comments »

Codeforces Round #804 (Div. 2) Editorial Reupload The [original blog](https://web.archive.org/web/20220705073720/https://codeforces.com/blog/entry/104088) was deleted yesterday by one of the other authors. We are very sorry about this. [A — The Third Three Number Problem](https://codeforces.com/contest/1699/problem/A) ===== Authors: [user:antontrygubO_o,2022-10-31], [user:Gheal,2022-10-31] <spoiler summary="Hints"> <spoiler summary="Hint 1"> An answer exists only when $n$ is even. </spoiler> <spoiler summary="Hint 2"> $a \oplus a = 0$ $a \oplus 0 = a$ </spoiler> </spoiler> <spoiler summary="Solution"> First and foremost, it can be proven that $(a \oplus b) + (b \oplus c) + (a \oplus c)$ is always even, for all possible non-negative values of $a$, $b$ and $c$. <spoiler summary="Proof"> Firstly, $a \oplus b$ and $a+b$ have the same parity, since $a + b = a \oplus b + 2 \cdot (a \text{&amp;} b) $. Therefore, $(a \oplus b) + (b \oplus c) + (a \oplus c)$ has the same parity as $(a+b)+(b+c)+(a+c...

Full text and comments »

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]+...

Full text and comments »

Hack me! (Codeforces Round #277.5 (Div. 2)) Welcome after the long break in Hack me! ([contest:489]). Previous posts can be found [here](http://codeforces.com/search?query=hackme). [cut] <h3>Stats</h3> Problem | <small>Successful hacks</small> | <small>Unsuccessful hacks</small> | Other* | Sum | <small>Solutions which can be hacked</small> | <small>Accepted solutions</small> | <small> All solutions on final tests</small>| :---:|:---:|:---:|:---:|:---:|:---:| <small> [problem:489A] </small> | 11 (28.21%) | 24 (61.54%)| 4 (10.26%) | 39 | 400 (17.22%) | 1923 (82.78%) | 2323 | <small> [problem:489B] </small> | 185 (61.26%) | 102 (33.77%)| 15 (4.97%) | 302 | 427 (18.09%) | 1934 (81.91%) | 2361 | <small> [problem:489C] </small> | 8 (11.59%) | 59 (85.51%)| 2 (2.90%) | 69 | 158 (8.90%) | 1618 (91.10%) | 1776 | <small> [problem:489D] </small> | 2 (14.29%) | 6 (42.86%)| 6 (42.86%) | 14 | 38 (4.99%) | 724 (95.01%) | 762 | <small> [problem:489E] </small> | 0 | 0 | 0 | 0 | 23 (41.07%) | 33 (58.93%)| 56 | <small> [problem:4...

Full text and comments »

TheForces Round #20 (7-Problem-Forces) Editorial [A](https://codeforces.com/gym/104471/problem/A) <spoiler summary="code"> ``` #include <bits/stdc++.h> #define int long long #define fi first #define se second using namespace std; int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while (t --> 0) { int n; cin >> n; vector<int> a(n); vector<int> b(n); for (int i = 0; i < n; i++) cin >> a[i]; for (int i = 0; i < n; i++) cin >> b[i]; vector<int> ord(n); iota(ord.begin(), ord.end(), 0); sort(ord.begin(), ord.end(), [&](int x, int y) { if (b[x] == b[y]) return a[x] > a[y]; return b[x] == 1; }); int ans = a[0] * b[0]; int suma = 0, sumb = 0; for (int i = 0; i <...

Full text and comments »

FFT is less precise than you think TL;DR: the popular empirical bounds for FFT stability overestimate the precision by a few bits -- multiplication might thus produce wrong answer even after thorough testing on random inputs. ## Introduction So here's how people typically advise you to use FFT after proving various theorems and providing a $\mathcal{O}(n \log n)$ algorithm. Suppose you want to multiply two big integers, stored in binary. Split them into groups of $B$ bits, called $a_0, a_1, \dots$ and $b_0, b_1, \dots$ respectively, so that the integers are equal to $a_0 + a_1 x + \dots$, $b_0 + b_1 x + \dots$ for $x = 2^B$. Multiply the polynomials $(a_0 + a_1 x + \dots) (b_0 + b_1 x + \dots)$ via FFT and substitute $x = 2^B$ to obtain the $n$-bit product. $B$ is a variable here -- the algorithm works for every $B$, but larger $B$s are faster. We're limited by precision of `double` though, because `double` can only precisely store integers from $0$ to $2^{53} \approx 9 \cdot 10^{15}$ (e.g. $2^{53}+1$ cann...

Full text and comments »

Editorial for CodeCraft-22 and Codeforces Round #795 (Div. 2) [problem:1691A] ================== **[Video Editorial](https://youtu.be/CwsYQXjIwDg)** **Idea:** [user:amul_agrawal,2022-05-26] **Problem Setting:** [user:menavlikar.rutvij,2022-05-26] [user:JadeReaper,2022-05-26] [user:rahulgoel,2022-05-26] [user:amul_agrawal,2022-05-26] **Editorial**: [user:menavlikar.rutvij,2022-05-26] [user:rahulgoel,2022-05-26] **Video Editorial**: [user:rahulgoel,2022-05-26] <spoiler summary="Hint 1"> Sum of two odd numbers is even and sum of two even numbers is also even. </spoiler> <spoiler summary="Hint 2"> If all consecutive pairs have even sum, can we generalize something about the sequence using the above hint? </spoiler> <spoiler summary="Solution"> [tutorial:1691A] </spoiler> <spoiler summary="C++ Code"> ~~~~~ #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 num...

Full text and comments »

Stress testing / bug finding in you code without using Bash Many times we are stuck in a problem and don't know the edge case in which the programme fails, specially during long challenges or monthly challenges we think our solution is correct but it gives WA on submition. So, I'm sharing my idea to stress test your code with a bruteforce or an unoptimized solution without using bash. So, basically what you have to do is first write a brute force solution and put it in the "Solve" function and put the optimized ones in the second one. change the function and return value according to the question also if you want then make the test generating while loop infinite also adjust the array size according to the constraints of your bruteforce solution. I would recommend you to use **Code-blocks** or **VS Code** for this purpose. **Code begins:** ~~~~~ #include <bits/stdc++.h> using namespace std; const int N = 100005; const int MOD = 1e9 + 7; #define show(arr) { for (auto x: arr) cout << x << " "; cout << '\n'; } mt19937 ...

Full text and comments »

Infoleague Winter 2021 Training Round Editorial [103449A &mdash; Mountains](https://codeforces.com/gym/103449/problem/A) ------------------ Author: [user:Gheal,2021-12-01] <spoiler summary="Solution"> At the beginning of year $y$, the height of peak $i$ can be any integer $H \in [h_i + y \cdot l_i, h_i + y \cdot r_i]$. Therefore, the problem boils down to finding the maximum number of overlapping segments, where segment $i$ is $[h_i + y \cdot l_i, h_i + y \cdot r_i]$. This can be done in many ways, either via greedy, or by using difference arrays. Time complexity: $O(N log N)$ </spoiler> <spoiler summary="Code"> ``` #include <bits/stdc++.h> using namespace std; using ll = long long; const ll NMAX = 2e5+9; int main() { ios_base::sync_with_stdio(false); cin.tie(0); ll n, y, v, l, r, peaks=0, maxpeaks=0, cnt=0; map<ll,ll> dif_array; cin>>n>>y; for(ll i=0;i<n;i++){ cin>>v>>l>>r; dif_array[v+l*y]++; dif_array[v+r*y+1]--; } for(auto it = dif_arr...

Full text and comments »

Fast searching silly mistakes in C++: shortly and with examples **To find an error in the code you just need...** [cut] $$\text{ }$$ Firsly, you can check overflow of integer types, mistakes like `=` instead `==`, writing a `long long` value in `int` and something else. It can be done in compile time with enabling of all available warnings. You can check your code fast [there](https://godbolt.org/z/SCiLFB). Link have examples and you can read them. Warnings is not an errors, but sometimes can be. [Description of warnings can be found there](https://codeforces.com/blog/entry/15547). <spoiler summary="List of used warnings"> ``` -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> Secondly, you can test your solution in **custom invocation**. You should go to [Custom invocation](https://codeforces.com/contest/1307/customtest), place your code and test on samples and...

Full text and comments »

Codeforces Round #840 (Div. 2) and Enigma 2022 — Cybros LNMIIT Editorial We hope you liked the problems! Unfortunately, problem C turned out to be harder than usual. Please read its editorial, we hope you'll find that the intended solution is not that hard. # [problem:1763A] Idea: [user:DreadArceus,2022-12-19]<br> Prepared by: [user:DreadArceus,2022-12-19] <spoiler summary="Hint 1"> Which $1$s in the binary representation cannot be changed to $0$. </spoiler> <spoiler summary="Hint 2"> Similarly, Which $0$s in the binary representation cannot be changed to $1$. </spoiler> <spoiler summary="Need more hints?"> Considering the last two hints, try to maximize the maximum element and minimize the minimum element. </spoiler> <spoiler summary="Solution"> In the minimum element, we want to make every bit $0$ when possible, it won't be possible to set a particular bit to $0$ when that bit is set in all the elements of $a$. Therefore, the minimum value we can achieve after performing the operations is the bitwise AND of all the elements of $a$...

Full text and comments »

Clean Explanation of CF Round 901 Div 2 E/1 B I feel that the problem is not explained in tutorial in sufficient detail. Let $a_i$ denote $i^{th}$ bit in $a$, and so on for various variables. First, lets handle the bits independently, for $i^{th}$ bit, we have a tuple $(m_i, a_i, b_i)$ and we want to get $(c_i, d_i)$. Let's map this $i^{th}$ bit tuple $(m_i, a_i, b_i)$ into integer (binary) as $S[i] = 4m_i + 2a_i + b_i$ and tuple $(c_i, d_i)$ into $D[i] = 2*c_i + d_i$ The first observation is that (as highlighted in editorial, that if for some $i$ and $j$, if $S[i] = S[j]$ then, $D[i]$ must be equal to $D[j]$, otherwise no solution exists. The second crucial observation is we can reduce the problem involving "lesser numbers" (instead of dealing with numbers of size $2^{30}$), since there are only $8$ possibilities of $S[i]$ and $4$ for $D[i]$. How do we do that exactly? Consider a $8$ bit number is base $4$, the $i^{th}$ bit $(i < 8)$ in binary represents $S[i]$ (since there are $8$ possibilities we have bits from $0$ ...

Full text and comments »

Infoleague Winter 2022 Round 1 Div. 2 Editorial I would like to apologize for the checker issue with problem C. I selected `std::ncmp` out of habit and forgot to change it afterwards. I would also like to apologize for taking so long to fix the issue. The model solution for div1A was also wrong, and I decided to fix that first. Nonetheless, we still hope that you enjoyed our problems in both Div. 1 and Div. 2. [103503A &mdash; Make Sum Great Again](https://codeforces.com/gym/103503/problem/A) ------------------ Author: [user:Gheal,2022-01-08] <spoiler summary="Hint 1">It is always optimal to add the smallest integer which is not already in the array.</spoiler> <spoiler summary="Hint 2">The number of operations will never exceed $\sqrt{2 \cdot s}.$</spoiler> <spoiler summary="Hint 3">Based on the first hint, the final array will be equal to $\{v_1,v_1,\ldots, v_n\} \cup [1,x]$, for some $x$.</spoiler> <spoiler summary="Hint 4">Hint 4: How can we find the value of $x$ faster than $O(\sqrt{s})$?</spoiler> <spo...

Full text and comments »

How to get 100% points for hackerrank challenges with inadequate solutions In this post I will describe inadequate solutions for 4 hackerrank problems from last 2 codesprint contest, that I participated(with difficulty hard-advanced), that get 100% score and provide counter-test to each solution. [**NCR Codesprint, Coconut Plantation**](https://www.hackerrank.com/contests/ncr-codesprint/challenges/coconut-plantation) At first we will water plants, as described in official editorial:  For example, we need to water squares (2,2,3,3) and (3,3,4,4). We add one to the highest cells of this square and decrement one from cells under this square. After we do this with all rectangles, we can get array of watered coconuts by simple cycle: ~~~~~ for (int i = 0; i < r; i++) for (int j = 0; j < c; j++) b[i][j] = (i>0?b[i-1][j]:0) + a[i][j]; // a[i][j] is array from the picture ~~~~~ We got array b and now we change values of b[i][j] to 1 if b[i][j] >= m else to 0. In official editoria...

Full text and comments »

Teamscode Spring 2023 Editorial This is the editorial for a recent contest [Teamscode](https://www.teamscode.org/). The problems are open for upsolving on [this gym](https://codeforces.com/gym/104287). Problems were prepared by [user:oursaco,2023-04-06], [user:dutin,2023-04-06], [user:thehunterjames,2023-04-06], [user:Bossologist,2023-04-06], [user:Esomer,2023-04-06], and me. ### [A. What do you do when the contest starts? Are you busy? Will you solve Bingo?](https://codeforces.com/gym/104287/problem/A) <spoiler summary = "Editorial"> <spoiler summary = "Are you busy?"> 1. WorldEnd/SukaSuka 2. Bocchi the Rock </spoiler> <spoiler summary = "No Sweep"> 1. Thomas </spoiler> <spoiler summary = "Multiplication Table"> 1. Lycoris Recoil </spoiler> <spoiler summary = "Greatest Common Multiple"> 1. Bokuben </spoiler> <spoiler summary = "A Certain Scientific Tree Problem"> 1. A Certain Scientific Railgun </spoiler> <spoiler summary = "Two and Three"> 1. Quintessential Quintluplets...

Full text and comments »

Editorial of Educational Codeforces Round 16 ### [problem:710A] Easy to see that there are only three cases in this problem. If the king is in the corner of the board the answer is $3$. If the king is on the border of the board but not in a corner then the answer is $5$. Otherwise the answer is $8$. <spoiler summary="С++ solution"> ~~~~~ char c, d; bool read() { return !!(cin >> c >> d); } void solve() { int cnt = 0; if (c == 'a' || c == 'h') cnt++; if (d == '1' || d == '8') cnt++; if (cnt == 0) puts("8"); else if (cnt == 1) puts("5"); else if (cnt == 2) puts("3"); else throw; } ~~~~~ </spoiler> Complexity: $O(1)$. ### [problem:710B] The function of the total distance is monotonic between any pair of adjacent points from the input, so the answer is always in some of the given points. We can use that observation to solve the problem by calculating the total distance for each point from the input and finding the optimal point. The other solution uses the observation that the answer ...

Full text and comments »

Hack me! (CF Round #270) Welcome after the long break in hacks' describtion in [contest:472]. This round had really good pretests, so we didn't have many hacks (81 successful ones), but let's have a look at them. [cut] <h3>Stats</h3> Problem | Successful hacks | Unsuccessful hacks | Other | Sum | :---:|:---:|:---:|:---:|:---:| [problem:472A] | 41 (23.03%) | 105 (58.99%)| 32 (17.98%) | 178 | [problem:472B] | 3 (4.35%) | 52 (75.36%)| 14 (20.29%) | 69 | [problem:472C] | 28 (20.29%) | 38 (27.54%)| 72 (52.17%) | 138 | [problem:472D] | 9 (23.68%) | 19 (50.00%)| 10 (26.32%) | 38 | [problem:472E] | 0 | 0 | 0 | 0 | [problem:472F] | 0 | 0 | 0 | 0 | [problem:472G] | 0 | 0 | 0 | 0 | <center> <img alt="Here should be graph." src="http://www.weaselcrow.com/cfhacks/472a.png" width="100%"> </center> <h3>Description of hacks</h3> [problem:472A] There were no particular errors, most of the hacks were just using some easy to check errors: like using 1 as composite number, bad checking if numbe...

Full text and comments »

Codeforces Round #460 (Div. 2) Hello, Codeforces! It's my honor to invite you to Codeforces Round #460 (Div. 2), which takes place at [13:05 UTC, January 31st](https://www.timeanddate.com/worldclock/fixedtime.html?msg=Codeforces+Round+%23460+%28Div.+2%29&iso=20180131T2105&p1=33&ah=2). The round will be **rated** for all division 2 participants. Also we warmly welcome those division 1 participants to join us out of competition. Note that round starts in the unusual time! :)  This round is prepared by me and my friend [user:wuminyan0607,2018-02-04]. Many thanks to my friend for helping me testing the round and generating testcases. Besides, many thanks to the Codeforces coordinator [user:KAN,2018-01-29] for giving me a chance to hold this round, testers [user:cdkrot,2018-01-29], [user:cyand1317,2018-01-29], [user:demon1999,2018-01-31], [user:glebodin,2018-01-29], [user:gritukan,2018-01-31], [user:neckbosov,2018-01-29] for testing this round and [user:MikeMirzay...

Full text and comments »

Let's Solve Some More Hard Problems! Inspired by ivan100sic's [problem list blog](https://codeforces.com/blog/entry/98630), I'll pick 10 nontrivial-seeming recent POI (Polish Olympiad in Informatics) problems that I haven't solved and track my progress here. It seems to me that POI is better suited for this format as their editorials are quite difficult to find (if possible [at all](https://szkopul.edu.pl/problemset/problem/v2Y2_UW56ENMcbwP22tkTb7a/site/?key=statement)). While Ivan's original challenge was supposed to last an entire year, I'm not nearly as patient, so I won't look for editorials only until February 1st (in just over 2 weeks). Hopefully I'll have completed at least 80% by that time. Until then, GLHF!!! The List: 1. [Multidrink 2013](https://szkopul.edu.pl/problemset/problem/GyDCbdIgFY5FsMa9iIsBl3hf/site/?key=statement) [Solved Jan 15] <spoiler summary="Fun-ness:"> 5/10 <spoiler summary="Comments"> My thought process on this problem went like "ew this is disgusting implementation" => ...

Full text and comments »

Interactors with testlib.h Interactive problems are problems in which solution talks to the judge. For example, [problem:100553G]. We don't see interactive problems much in ACM-ICPC style problems. Most of them are Olympiad style(IOI and CEOI). Unfortunately using interactive in Codeforces contests is not allowed, but you can see some of them in Gym. Also [Polygon](https://polygon.codeforces.com) handles such problems(there's a checkbox `Interactive` in general info of the problem). When we don't wanna handle the judge manually, we should use a code named interactor to talk to code instead of a person. With testlib.h, we can write interactors as simple as checkers and validators. In an interactive problem, you may use also a checker. To connect this programs together(generator, validator, solution, checker and interactor), you can use teslib input streams. An input stream, is a structure that reads data from a specific file using some pre-implemented methods. Input streams you can use with testlib.h: 1. `i...

Full text and comments »

Codeforces Round #601 Editorial [problem:1255A] Author: [user:UncleGrandpa925,2019-11-20]. Prepared by [user:UncleGrandpa925,2019-11-20] <spoiler summary="Tutorial"> [tutorial:1255A] </spoiler> [problem:1255B] Author: [user:prof.PVH,2019-11-20] ft. [user:MikeMirzayanov,2019-11-20]. Prepared by [user:UncleGrandpa925,2019-11-20] <spoiler summary="Tutorial"> #### Modelize the problem We modelize the problem as graph, where each fridge is a vertex and each chain is an edge between two vertexes. The problem is now equivalent to: Given a graph with $n$ vertexes, each vertex has a value $a_i \ge 0$. We have to add $m$ edges to the graph such that each vertex is connected to at least two different vertexes and the total cost of edges added is minimum. The cost of an edge is the sum of value of its two end-points. #### Observe some basic properties of graph Now, each edge added will increase the sum of degree of all vertexes by 2. So adding m edges will make the sum of degree equal to $2 \times m$. ...

Full text and comments »

Invitation to Insomnia Qualifier 2022 Hello Codeforces! Computer Club, MNNIT Allahabad, India is glad to invite you to the annual programming competition of MNNIT, INSOMNIA, which is an ACM-ICPC style team programming contest of 2.5 hours duration held on Codeforces during its annual technical fest Avishkar. The team can consist up to 3 members. <b>Contest Details: </b> <ol> <li> Qualifiers: </li> <ul> <li> Start Time: Wednesday, November 9, 21:00 IST</li> <li> Duration: 2.5 hours</li> </ul> <li> Finals: </li> <ul> <li> Start Time: Sunday, November 13, 12:00 IST</li> <li> Duration: 2.5 hours</li> </ul> </ol> **Top 25** global teams, and **Top 25** teams from MNNIT (based on the result of Qualifiers) will qualify to the Finals. The prize distribution for global teams is mentioned below: <br>  Teams consisting of MNNIT students only will be eligible for a seperate prize pool. Register your team for the qualifiers here: https://forms.gle/BKsbKfoGzSxC394R8 <br>...

Full text and comments »

Infoleague Spring 2022 Round Editorial <spoiler summary="Vote your favourite problem"> <spoiler summary="Div 2"> Div 2A &mdash; The Hatchet Div 2B &mdash; Floor Or Xor Div 2C &mdash; Yet Another Constructive Problem Didn't participate, idc </spoiler> <spoiler summary="Div 1"> Div 1A &mdash; Bamboo Coloring Div 1B &mdash; Xor Or Floor Div 1C &mdash; Jump Didn't participate, idc </spoiler> </spoiler> [103633A &mdash; The Hatchet](https://codeforces.com/gym/103633/problem/A) ------------------ Author: [user:tibinyte,2022-03-30] <spoiler summary="Rate Problem"> 1700 or less 1800 1900 2000 2100 or more Didn't solve it, idk </spoiler> <spoiler summary="Solution"> ### Subtask 1 : $N \le 10^2$ This subta...

Full text and comments »

[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.com/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...

Full text and comments »

AtCoder ZONe Energy Programming Contest Problem F ### Abridged statement There are $N$ vertices in the graph where $N=2^n$ where $n$ is an integer. An array $A$ of size $M$ is given. An edge can be drawn from $i$ to $i\oplus x$ ($\oplus$ represents xor operation) if $x\notin A$. Print $N - 1$ edges such that the edges form a tree. [Statement](https://atcoder.jp/contests/zone2021/tasks/zone2021_f) #### Issue The intended solution uses xor basis / gaussian elimination. However, I found some submissions that uses completely different algorithms that ACs all the testcases. In summary, the code iterates through all the $x\notin A$, and for each $x$, iterate through all the vertices $v$ from $0$ to $n - 1$. While $v$ and $v \oplus x$ are not connected, connect them and move on to vertex $v + 1$, otherwise, break. This algorithm runs in $O(n)$ as it will only connect edges $n - 1$ times and when it cannot connect edges, it breaks immediately. However, does anyone have a proof that it is correct? Will there be any case where breakin...

Full text and comments »

Codeforces Round #867 (Div. 3) Editorial [problem:1822A] Idea: [user:diskoteka,2023-04-25], prepared: [user:Vladosiya,2023-04-25] <spoiler summary="Tutorial"> [tutorial:1822A] </spoiler> <spoiler summary="Solution"> ~~~~~ def solve(): n, t = map(int, input().split()) a = [int(x) for x in input().split()] b = [int(x) for x in input().split()] bst = -2 for i in range(n): if i + a[i] <= t and (bst == -2 or b[bst] < b[i]): bst = i print(bst + 1) t = int(input()) for _ in range(t): solve() ~~~~~ </spoiler> <spoiler summary="Rate the problem"> - Didn't solve - Good task - Average task - Bad task </spoiler> [problem:1822B] Idea: [user:playerr17,2023-04-25], prepared: [user:playerr17,2023-04-25] <spoiler summary="Tutorial"> [tutorial:1822B] </spoiler> <spoiler summary="Solution"> ~~~~~ t = int(input()) for testCase in range(t): n = int(input()) a ...

Full text and comments »

Hack me! (Codeforces Round #278 (Div. 2)) Welcome in hacks' statistics in [contest:488]. That was really nice round for hackers! Many possibilities, many hacks, let's have a look! Post for Div. 1. contest <s>will be added later (there are pretty many hacks to parse :))</s> is [here](http://codeforces.com/blog/entry/14801). Previous posts can be found [here](http://codeforces.com/search?query=hackme). Your comments are always welcome. [cut] <h3>Stats</h3> Problem | <small>Successful hacks</small> | <small>Unsuccessful hacks</small> | Other* | Sum | <small>Solutions which can be hacked</small> | <small>Accepted solutions</small> | <small> All solutions on final tests</small>| :---:|:---:|:---:|:---:|:---:|:---:| <small> [problem:488A] </small> | 99 (46.05%) | 86 (40.00%)| 30 (13.95%) | 215 | 228 (12.20%) | 1641 (87.80%) | 1869 | <small> [problem:488B] </small> | 23 (50.00%) | 17 (36.96%)| 6 (13.04%) | 46 | 265 (63.55%) | 152 (36.45%) | 417 | <small> [problem:488C] </small> | 21 (65.62%) | 10 (31.25%)| 1 (3...

Full text and comments »

Editorial for Codeforces Round #150 **Adiv2.** Consider an array $A$ of integers in range from 1 to $nk$. Let's remove from $A$ all numbers $a_i$ and all other numbers store into an array $B$. The array $B$ will have $(n-1)k$ elements. Now for $i$-th kid you should output numbers $a_i$, $B[(n-1)*(i-1) + 1]$, $B[(n-1)*(i-1) + 2]$, ... $B[(n-1)*(i-1) + n - 1]$ ($B$ is 1-based). Author is [user:Gerald] [cut] . **Bvid2.** Solution 1. You should write some bruteforce solution over all numbers with no more than 9 digits (number $10^9$ should be considered separately). Bruteforce algo seems like this: ~~~~~ dfs( int num ) // run it as dfs(0) if (num > 0 && num <= n) ans++ if (num >= 10^8) return for a = 0..9 do if num*10+a>0 then if number num*10+a has no more than 2 different digits then dfs( num*10+a ) ~~~~~ ans will store the answer. After that you wrote bruteforce, you can run it and see that it works fast (that is same time for any testcase). Solution 2. Let's build al...

Full text and comments »

Codeforces Round 915 (Div. 2) Editorial [A — Constructive Problems](https://codeforces.com/contest/1905/problem/A) ===== Author: [user:valeriu,2023-12-16] <spoiler summary="Solution"> We can observe an invariant given by the problem is that every time we apply adjacent aid on any state of the matrix, the sets of rows that have at least one rebuilt city, respectively the sets of columns that appear that have at least one rebuilt city remain constant. Therefore, if we want to have a full matrix as consequence of applying adjacent aid multiple times, both of these sets must contain all rows/columns. As such, the answer is bounded by $max(n, m)$. We can tighten this bound by finding an example which always satisfies the statement. If we take, without loss of generality, $n \le m$, the following initial setting will satisfy the statement: $(1, 1), (2, 2), (3, 3), ..., (n, n), (n, n + 1), (n, n + 2), .. (n, m)$ <spoiler summary="Author's Note"> I have proposed this div2A at 3 contests and after 1 year of waiti...

Full text and comments »

Python Optimisation for Round 867 G1. Magic Triples (Easy Version) I was doing G1 ([https://codeforces.com/contest/1822/problem/G1](https://codeforces.com/contest/1822/problem/G1)) and came up with this solution which is O(n * sqrt(m)) as stated in the editorial. [This TLEs in testcase 13 due to constant factors](https://codeforces.com/contest/1822/submission/204488997). <spoiler summary="TLE Code 1"> ~~~~~ import sys input = sys.stdin.readline def solve(n, arr): counts = [0] * (max(arr) + 1) for i in arr: counts[i] += 1 ans = 0 for i in set(arr): b = 1 while i * b * b < len(counts): x, y, z = counts[i], counts[i * b], counts[i * b * b] if b == 1: ans += x * (x - 1) * (x - 2) else: ans += x * y * z b += 1 print(ans) def main(): t = int(input()) for _ in range(t): n = int(input()) arr = list(map(int, input().split())) solve(n, arr) main() ~~~~~...

Full text and comments »

Help needed! Python code optimisation for USACO Silver: Wormhole Sort I am requesting for help from python experts (e.g: [user:pajenegod,2022-11-29]) regarding this issue. Article: [https://usaco.guide/general/choosing-lang](https://usaco.guide/general/choosing-lang) Problem: [http://www.usaco.org/index.php?page=viewproblem2&cpid=992](http://www.usaco.org/index.php?page=viewproblem2&cpid=992) Over here in this article, they mentioned that: "A comparable Python solution only passes the first five test cases:", "After some optimizations, this solution still passes only the first seven test cases:", "We are not sure whether it is possible to modify the above approach to receive full credit (please let us know if you manage to succeed)! Of course, it is possible to pass this problem in Python using DSU (a Gold topic):" So I went ahead to try to optimise the approach (Binary Search with DFS) but I could only get 9/10 testcases to pass reliably. Very rarely, I will have 10/10 testcases passed, with the 10th testcase having ~3990 ms. I wonder if it ...

Full text and comments »

Command-line virtual-assistant for competitive programming. It is a terminal-based virtual assistant especially made for competitive programming. It has a lot of features, including running python or c++ file, parsing problem set with test cases and test against all the cases in one click, test with brute force solution, and many more. It will help you to boost your programming skill and help you to do a good performance in the programming contest. It can give voice reply and take your voice command. You can turn off or on these features. Basic settings can be easily changed from config option. For installing write the given commands, > pip3 install wheel and > pip3 install ai-virtual-assistant I recommand after installing checkout the config file. The config can be open by the given command, > jarvis -config  ## Programming Features - [x] [Run c++ or python program] - [x] [Competitive Companion Support] - [x] [parse proble...

Full text and comments »

A Hacking atempt to 1107G Today I am doing [1107G](https://codeforces.com/contest/1107/problem/G), I find there is something wrong with my `st-table`, so I change the `st-table` into brute force and submit it only to check if my main algorithm is correct. But to my surprise, the brute force got an "Accepted" verdict in "233ms".(the time limit is 3.5s) https://codeforces.com/contest/1107/submission/180935577 I am very confused and check the time complexity of my code. Then I find that: The st-table code is $O(n\log n)$. If I change the `<=` on the 61-th line into `<`,it's also right though it seems to be $O(n^2)$. Because under the constraint of $d_{i}<d_{i+1}$, it's impossible to construct a testcase with more than 40000 positions with a increasing $(d_{i}-d_{i+1})^2$.(if the limit of $d_i$ is $10^{18}$,it will be TLE as well. But the original code is totally wrong. It will be TLE on a test constructed in this way: int cur=100; cout<<300000<<" "<<300000<<endl; cout<<1<<" "<...

Full text and comments »

Today was the day Practice makes perfect, and cyan feels better than green. (Skip to the end if you don't wanna hear an interesting story) A while ago, I made a post about almost being specialist. After a month of getting stuck on pupil, I was starting to think I was not fit to advance in my competitive programming journey. Doubts fell like droplets on a rainy day... But I still practiced... Day after day I would do my daily dose of problems, learning cool new algorithms along the way. Maybe DSU? BFS? DP? Probabilities? Every day I was equipping my toolbelt for the journey. Every day I would challenge myself to a slightly harder task. Although I had to admit, in the back of my head, I was wondering when I will ever use these Data Structures and Algorithms. Then the day came. In today's contest (Round #736 Div1+Div2), I briskly solved A (as I usually do) and took my time on B. (it was implementation, so it was a little annoying). Then I met C. C was an interesting graph problem. I was thi...

Full text and comments »

Suggestions about pretests and systests The purpose of pretests is so that the judge queue is not be overloaded during the contest. At first I thought this means that the judge never runs the systests until the end of the contest. However, after setting a few contests, I realize that the judge actually grades the systests during contest time, and as problemsetters we can even see in real time who will FST by the end of the contest. I assume this means that the grader prioritizes grading pretests and when it has "free time" it grades the systests. Of course, this is a good system to prevent the judge queue from clogging if it ever becomes too long. However, for the four contests I've got the chance to observe the grading process, the systests does not seem to have any backlog, and almost all have been graded except those which just came in. This is probably because almost everyone uses multitests now and because of that we can usually fit the systest into the pretest. Which brings me to my suggestion: if the grader is ...

Full text and comments »

CP Editor 4.0: New year update Check : https://cpeditor.github.io ================== Hi guys! **Happy new year**, may this year brings a lot of AC and high ratings to you. This winter break I decided to improve the CP editor and after days and hours of works and thousands of lines of code changes I am glad to present the new CP Editor. **Everything has changed**, except the functionality. It is now much faster, more professional looking and offers many new features which were highly requested in old versions. Let's quickly dive into the changes of **CP Editor 4.0**: #### What's New - You can now **drag and resize the editor** or input boxes, you can also make editor take complete space of window by dragging all the way to right. You can also make Input and other boxes take complete window by dragging all the way to left. You can drag from sides to undo these changes. - Editor has now **5 themes to choose from** (Light (default), Drakula ,Monkai (sublime), Solarised and Solarised Dark). These themes...

Full text and comments »

Editorial Codeforces Round #302 ###[problem:544A] In that task you need to implement what was written in the statements. Let's iterate over all characters of string and keep array $used$. Also let's keep current string. If current character was not used previously, then let's put current string to the answer and after that we need to clear current string. Otherwise, let's append current character to the current string. If array, that contain answer will have more then $k$ elements, we will concatenate few last strings. The jury solution: [submission: 11035685] ###[problem:544B] It's clear to understand, that optimal answer will consists of simple cells, for which following condition fullfills: the sum of indices of row and column is even. We will try to put $k$ islands in such way, and if it's impossible, we will report that answer is NO. Try to prove that this solution is optimal. The jury solution: [submission: 11035691] ###[problem:543A] Let's create the solution, which will work too slow, but...

Full text and comments »

How bugged Floyd-Warshall is not bugged Yesterday at SRM 670 I got a funny story which I want to describe. During challenge phase I noted that one solution of medium problem in my room uses Floyd-Warshall. I thought "Oh, why haven't I thought about it during coding phase? Much shorter than those DFSes!", but then I noted that unexpectedly this infamous order of loops is not correct. It went like this: ~~~~~ FOR(x, n) FOR(y, n) FOR(z, n) dis[x][y] = min(dis[x][y], dis[x][z] + dis[z][y]); ~~~~~ while everyone should know that FOR(z,n) should be the outer loop, not the inner one. I tried to hack this solution, so I inputted graph 0-3-2-1, however my test was rejected, because problem was about trees and there was a constraint that parent of vertex $i$ should be less than $i$ and I didn't have time to come up with another testcase. Unexpectedly, this solution passed systests! I thought that its author is very lucky. However it turns out that for trees with this constraint this order of loop result in computing correct ...

Full text and comments »

Hack me! (CF Round #263, Div. 2) Welcome again! I decided to split statistics for both division. Post for first division <strike>will be added later</strike> is <a href="http://codeforces.com/blog/entry/13572">here</a>. So, let's look at hacks in [contest:462]. <small><strike>Some statistics are missing &mdash; I have some problems with downloading all data (Codeforces seems little crowded today). They will be also added later.</strike></small> **Update**: Europe went asleep, so I added missing stats. [cut] <h3>Stats</h3> Problem | Successful hacks | Unsuccessful hacks | Other | Sum | :---:|:---:|:---:|:---:|:---:| [problem:462A] | 5 (17%) | 25 (83%) | 0 (0%) | 30 | [problem:462B] | 1193 (71%) | 188 (11%) | 306 (18%) | 1687 | [problem:462C] | 0 (0%) | 55 (36%) | 98 (64%) | 153 | ### Fastest hackers Problem | Time | Hacker | Defender | Hack :---:|:---:|:---:|:---:|:---:| [problem:462A] | 00:50:08 | [user:ak.bewildered,2014-08-26] | [user:abdohammam95,2014-08-26] | <a href="http://codefo...

Full text and comments »

Editorial for SmallForces Monthly Contest #3 Thank you very much for participating in our contest. Please share your reviews in the comments. We will continuously bring these type of contests for you. Here are solutions with explanations: [A. GobLin and Chess](https://codeforces.com/gym/460558/problem/A) <spoiler summary="Editorial"> In the following question, The Rook can attack the king if the Rook and the King are on the same vertical or horizontal line. It is only possible when $a$ and $x$ are the same or $b$ and $y$ are the same. </spoiler> <spoiler summary="Code"> ```c++ #include <bits/stdc++.h> using namespace std; int main () { int testcase; cin >> testcase; while (testcase--){ int a,b,x,y; cin>>a>>b; cin>>x>>y; if(x == a || y == b){ cout<<"YES"<<endl; } else{ cout<<"NO"<<endl; } } } ``` </spoiler> [B. Odd &mdash; Even Sum](https://codeforces.com/gym/460558/problem/B) <spo...

Full text and comments »

[Bug] Invalid testcase(s) for Problem-B from 2022-2023 ICPC, NERC, (Unrated, Online Mirror) I recently encountered [Problem-B BinCoin](https://codeforces.com/contest/1773/problem/B) from **2022-2023 ICPC, NERC, Northern Eurasia Onsite (Unrated, Online Mirror, ICPC Rules, Teams Preferred)** while practicing random 2200 problems. <br> The problem is based on a binary rooted tree generated by the jury, and a random in-order traversal of that tree. I was sure my solution to this problem was reliable. But it seemed to RTE on test-16 (Which in these rounds is not visible). I tried several methods to circumvent the situation to no avail. <spoiler summary="My Approach"> Let $a$, $b$ and $c$ be some $3$ employees then <br> $bac$ or $cab$ is reliably a sub-array (at least any one of them at a time) in each journal if and only if $b$ and $c$ be leaf nodes and have a common parent $a$. And there will always be at-least $1$ such triplet. <spoiler summary="Proof of the 'if and only if' part"> For $bac$ or $cab$ to be a sub-array, it is necessary that at-least one of $b$ or $...

Full text and comments »

Invitation to Gym Contest — Alpha IV (by AlgoRave) <img src="https://i.stack.imgur.com/MZzUW.jpg" height="300px" style="float:right; margin:20px;"/> Hello, Codeforces! I and [user:tanmaytaneja2,2024-01-07] have curated a **Solo Practice Contest** in the gym, [Coding Challenge Alpha IV &mdash; by AlgoRave](https://codeforces.com/contestInvitation/97293b40c6315b5ab123b0f8e145dc19202a4aa3). This is for anyone who loves giving contests and solving problems. This contest will be of most interest upto Expert rated coders, but I would also invite Div. 1 coders to participate as well. For anyone who wants to practice or just wants to go through the problems can register for our contest. Hope you guys will enjoy solving the problems! I would like to thank: - Our problem setters [user:JainWinn,2024-01-07], [user:kaichisaki,2024-01-07], [user:0x4F5F6F,2024-01-07] and _myself_. - Our problem testers [user:tanmaytaneja2,2024-01-07], [user:kaichisaki,2024-01-07] and _myself_. - [user:JainWinn,2024-01-07] for the amazing poster desi...

Full text and comments »

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.com/blog/omeganot) (which was posted a lot sooner than ours). [Novice A/](https://codeforces.com/gym/105066/problem/A)[Advanced A: It's Time to Submit](https://codeforces.com/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...

Full text and comments »

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...

Full text and comments »

CodeAgon By Trilogy 2023 [After-Contest Questions Approach Discussion] Combined Questions **PDF** [Link](https://drive.google.com/file/d/1qyrgxb86YURCe8kCN_Z0WuxlFVsAKm1U/view?usp=share_link) #### Q1) Two Operations **Problem Description** <spoiler summary="Q1">  </spoiler> **Example Test Case + Explanation** <spoiler summary="Q1-TestCase">  </spoiler> #### Q2) Aesthetic Permutation **Problem Description** <spoiler summary="Q2">  </spoiler> **Example Test Case + Explanation** <spoiler summary="Q2-TestCase">  </spoiler> #### Q3) Treasure Hunt in the city **Problem Description** <spoiler summary="Q3-A">  </spoiler> <spoiler summary="Q3-B">...

Full text and comments »

The template generator for competitive programming Hi Codeforces! Today I would like to intoruce my template generator, [online-judge-tools/template-generator](https://github.com/online-judge-tools/template-generator). This program can analyze problems of competitive programming and generate boilerplate codes including input part, output part, MOD, etc. For example, for a probelm <https://codeforces.com/contest/1300/problem/D>, my command `oj-template https://codeforces.com/contest/1300/problem/D` prints the following source code. All of input part and output part is already written in `main` function, and what you need to write is only the `solve` function. ``` c++ #include <bits/stdc++.h> #define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i)) #define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i)) #define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i)) #define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i)) #define ALL(x) ::std::begin(x), ::std::end(x) using namespace std; co...

Full text and comments »

Knapsack DP by looping through capacity first, feat. Python optimisation I was doing AtCoder Educational DP Contest, Knapsack 1: [https://atcoder.jp/contests/dp/tasks/dp_d](https://atcoder.jp/contests/dp/tasks/dp_d) I wanted to loop through capacity instead of looping through each item in the array. All existing solutions that I have found had always looped through each item as the outermost loop. But what if I want to loop through each capacity as the outermost loop? (It is kind of impractical and I tunnel-visioned, but I digress). Here is the solution I came up with: My dp is two dimensional, with the first item of dp[i] being the max value, and the second item storing all the remaining items that we have not used, as a list of tuples. For every capacity we get the remaining items for that capacity, and try to use them. Now we just need to update the states for dp[i + wj] if its larger. The remaining items for dp[i + wj] will just be remaining items of dp[i], with that item removed. <spoiler summary="Here is the code, which TLEs at the 7th te...

Full text and comments »

TOKI Open 2018 Post-Contest Hello! [TOKI Open 2018](http://codeforces.com/blog/entry/59182) has ended. Thank you to everyone who participated the contest. We decided to not consider any participants from the second window whose username is registered on the first window. We also decide to not consider any participants from the second window whose code is very similar to other user's code on the first window. After that, we consider a TOKI Open 2018 participant to be those who made at least one submission on either day. There were a total of 104 participants, which three of them get a fullscore. Congratulation to [user:1021839,2018-05-28], [user:Alex_2oo8,2018-05-28], and [user:zscoder,2018-05-28]. The full result of TOKI Open 2018 is available [here](https://docs.google.com/spreadsheets/d/1wH8FZGwYaDrMDsDaqTvvjMVUF5jmfriRligZgI16yL4/edit?usp=sharing). The skeletons, solutions, problem descriptions, and testcase generators for TOKI Open 2018 are available [here](https://github.com/jonathanirvings/toki...

Full text and comments »

Really weird differences in runtime? — Explanation and tutorial I know the post is a bit long, but I think it is worth to know the whole story. I attempted to solve [div1D](https://codeforces.com/contest/1314/problem/D) from [round #623 (VK Cup)](https://codeforces.com/contest/1314) with a randomized solution (that is one of the official solutions). After writing the code, I wondered how many iterations of this randomized algorithm I could do to fit in TL. So, I generated [a maxtest](https://pastebin.com/raw/Eyakqtsd) (that is, n=80 and k=10 in this task) and I ran it in custom invocation. I saw that I could do 60 000 iterations in about 2.4 &mdash; 2.5 seconds. Good enough, right? After all, the more iterations, the smaller chances of being hacked / getting WA (even though this number of iterations is ridiculous). So I submitted [the code](https://codeforces.com/contest/1314/submission/71715691) (and [here](https://codeforces.com/contest/1314/submission/71814887) is a bit prettier code without templates/defines). As you can see, I got TLE. A...

Full text and comments »

Kill backtracking! <span class="Apple-style-span" style="color: rgb(51, 51, 51); font-family: Georgia, serif; font-size: 13px; line-height: 20px; ">Here's a problem that has appeared at a recent&nbsp;<a href="http://contests.snarknews.info/index.cgi?data=newstape&amp;menu=index&amp;head=index&amp;class=yandex2010&amp;mod=yandex2010" style="color: rgb(153, 153, 153); text-decoration: none; ">contest</a>:&nbsp;We are given a 7 times 7 field where some of the cells have numbers between 0 and 8, inclusive, and all remaining cells have dots. We want to find such allocation of exactly 10 stars to the cells with dots, at most one star per cell, so that each cell with a number has exactly that number of stars in its 8 adjacent cells. Moreover, we will only consider such 7 times 7 fields where such allocation of 10 stars exists and is unique.<br><br>Can you create a testcase for this problem that will kill backtracking solutions? It seems pretty hard to do at such small field, but it is possible!<br><br>Here are ...

Full text and comments »

[Nested Sum] Can you help me with this problem? #### Problem source [problem:104168D2] #### Statement Given an array of $n$ positive integers $a_{1}, a_{2},...,a_{n}$, find the value of $\sum_{i=1}^{n}\sum_{j=i+1}^{n}\sum_{k=j+1}^{n}a_{i}a_{j}a_{k}$ modulo $10^{9}+7$ #### Input The first line of input contains an integer $t$ ($1 \le t \le 10^{4}$). The first line of each test case contains an integer $n$ ($1 \le t \le 10^{5}$), the size of the array. The second line of each test case contains $n$ integers $a_{1}, a_{2},...,a_{n}$ ($1 \le t \le 10^{9}$), the elements of the array. The sum of n over all test cases doesn't exceed $5\cdot 10^{5}$. #### Output For each test case output one line containing one integer, the sum described in the problem modulo $10^{9}+7$ #### Example <spoiler summary="Input"> ~~~~~ 3 1 1 1 4 1 2 3 4 5 5 4 3 1 2 ~~~~~ </spoiler> <spoiler summary="Output"> ~~~~~ 1 50 225 ~~~~~ </spoiler> #### What I've done I have tried to solve this problem for an hour but wh...

Full text and comments »

Knapsack the tutorial -------------------- -------------------- <a name="TOC"></a> > **Teleporter:** **[**[Previous](#status)**]** | | | **[**[Next](#statement)**]** ### <strong> <center style="color:red;"> Table of content </center> </strong> > This blog isnt the best but worth spending time to read it | Teleporter | Description | | :--------------------------------------------------------------- | :-------------------------------------------------------------------------------------------- | | [I. STATEMENT](#statement) | Taking about the problem | | [II. EXAMPLE](#example) | To understand the problem better | | [III. Solution for small number ...

Full text and comments »

How to test interactive problems using mkfifo Interactive problems are rare problems in competitive programming. I think that interactive problems are hard to solve for many guys. Because, testing for your solution is too hard. When testing interactivity, it is necessary to understand the stdin/stdout on your system. In this article, we will cover the following topics, - Basic code for interactive problems. How to do printf debugging. How to do testing by sample file. - The `mkfifo` that you often see in CodeForces user articles. mkfifo does not work on WSL1 as it is, but we will make it work on Windows with WSL1. - Colorful Result - (option) Use zsh + coproc to test without generating intermediate files. - <font color=red>The following examples are all in Python, but will work equally well in C++</font>. Similar articles can be found below. > [eku's article](https://codeforces.com/blog/entry/49490) This is introduction to useful tools (github) for interactive problems. ([user:eku,2020-12-31]) > [Gassa's Comment](h...

Full text and comments »

CP Editor 2.0.3 : Everything you wanted is here Check : https://cpeditor.github.io ================== Hi Guys ! Around a week ago, I released the first version of CP Editor. If you are reading about CP Editor for first time. I request you to read my [previous blog](https://codeforces.com/blog/entry/71673) first. Many user liked it and I got many suggestions about enhancements and some bug reports as well. I liked your over whelming response, it made me happy. Now it's time for me to make you happy. Enough talking, let's get into what's new in CP Editor 2.0. It is a big release and hence a long blog ;-) ##### Dark theme Last time there was a dark theme but it only made the editor dark. So, it wasn't truly dark theme. Now with this new release CP Editor packs a system-wide dark theme. Have a look here  ##### Dependency Updates Just like any other software, CP Editor also have a long acyclic dependencies, and over the weeks many were updat...

Full text and comments »

SPC Round #003 Editorial <p></p> Link to contest : [SPC Round #003](https://codeforces.com/contestInvitation/205bc917cbe2a2aadff6424228fcc04b027cb683) <p></p> ### [A. SPC Gifts](https://codeforces.com/group/xK9ngmaNEM/contest/337838/problem/A) Problem Author : [user:sapta0506,2021-07-25] <spoiler summary="Tutorial"> [tutorial: 337838A] </spoiler> <spoiler summary="Solution Code"> ~~~~~ #include<bits/stdc++.h> using namespace std; #define int long long #define rep(i,a,b) for(int i=a; i<b; ++i) #define all(x) x.begin(),x.end() #define mp make_pair const long long INF=1e18; const int32_t M=1e9+7; const int32_t MM=998244353; const int32_t N = 1e6+1; void solve() { int a,b,k; cin >> a >> b >> k; cout << min(a,b)/k << endl; } int32_t main() { ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); int t; cin >> t; while (t--) solve(); return 0; } ~~~~~ </spoiler> <p></p> ### [B. Void Knight](https://codeforces.com/g...

Full text and comments »

[Tutorial] Sorting with lambda Hello, Codeforces! Today I want to share with you something that often gets brushed off because it's a very basic concept &mdash; sorting. I think that this topic is often overlooked even though it can be very useful. This blog (my first on Codeforces, yaay) is thus rather intended for beginners in C++. I'll describe a technique that makes sorting fast to implement &mdash; lambdas. For simplicity, arrays will always mean `vector` in this blog. There are two main usages of sorting I want to describe: #### 1. Sorting an auxiliary array to keep the original array unchanged. This is often the case when our data is splitted into several separate arrays, that are somehow connected together. This may occur when each type of data is given in separate rows. For example, one array could contain a value of a cell and the other one &mdash; it's color. Say that we want to simultaneously sort both those arrays by value (increasing). In order to do that, we may rather introduce a new a...

Full text and comments »

Need help in these Problems <spoiler summary="Problem 1"> #### Problem Statement 1:<br /> You are given an array A with N integers. Find the total number of good pairs of integers in A. A pair of integer is good if:<br /> - 1 < = i <= N<br /> - 1 <= j <= N<br /> - a[i] * a[j] can be represented as the sum of 2 prime numbers X, Y such that X ^ Y is an even number. (X, Y can be equal, X ^ Y represents bitwise xor between X and Y) #### Constraints:<br /> 1 <= N <= 10^5<br /> 1 <= a[i] <= 10^6 #### Sample TestCases: **Input:**<br /> 1<br /> 4<br /> **Output:**<br /> 1<br /><br /> **Explanation:**<br /> Here we have a = [4] and only 1 pair which is {4, 4} and 4 * 4 can be written as sum of 2 primes 4 * 4 = 16 = 11 + 5, Hence the answer is 1. **Input:**<br /> 1<br /> 1<br /> **Output:**<br /> 0<br /><br /> **Explanation:**<br /> Here only 1 pair is possible which is {1, 1} and 1 * 1 can not be written as the sum of 2 primes. Hence the answer is 0. **Input:**<br /> 3<br /> 2 1 3<br...

Full text and comments »

Tutorial — "Randomized" DP leading to state elimination I was solving [this problem](https://codeforces.com/problemset/problem/739/E) and I came up with an interesting idea which may in some cases be generalized to other DP problems. I don't think it's well known so that motivated me to write this. <spoiler summary="Once you've read the problem, understood it and want to know what I did, continue reading..."> Let's look at the following DP: $d_{i,j,k}$ is the largest expected value if we used $j$ Poke Balls and $k$ Ultra Balls on the first $i$ Pokemon. There are four transitions from each state, corresponding to whether or not we used or didn't use a Poke Ball and an Ultra Ball on the $i$-th Pokemon. Clearly this solution has time complexity $O(n^3)$. However, if we shuffle the input, the optimal solution (imagined as a path through the 3D DP space) will not deviate much from the straight line connecting $(0,0,0)$ and $(n,a,b)$. If we only compute DP values inside a "tube" with some radius $r$ containing this straight line, it will have...

Full text and comments »

CodeRunner(for Windows only):A tool for many online judges. # CodeRunner(for Windows only) # [Github](https://github.com/Davidasx/CodeRunner) (Remember to give me a star!) A tool for many online judges.Processes testcases via [Competitive Companion](https://codeforces.com/blog/entry/60073) and uses [CF-Tool](https://codeforces.com/blog/entry/66552) to compile and test programs. [cut] ## Install First,install and configure [Competitive Companion](https://codeforces.com/blog/entry/60073) and [CF-Tool](https://codeforces.com/blog/entry/66552). **Note:You should configure the pre-script and post-script for the CF-Tool template to compile automatically.** Download crun.exe and coderun.exe and parse2cf.exe(Download the source files if you want to.They're optional.) Then put the files in a folder that's in the environmental variable PATH.(Search that if you don't know what it is.) ## Usage ```powershell coderun [FILENAME]:test code [FILENAME] in the terminal. crun [FILENAME]:test code [FILENAME] in a popup window. ``` *...

Full text and comments »

Distributed Code Jam test script for Windows I have written a bat script for Windows to automate a bit testing DCJ solutions on multiple examples, putting it here, might be helpful to somebody. I've written it to test C++ solutions but in case you write in other languages you should be able to change it easily. script itself: ~~~~~ echo off set PYTHONPATH=C:\Program Files (x86)\Python27\ set DCJ_PATH=c:/Temp/SP/DistributedCodeJam/dcj/dcj.py cls for %%* in (.) do set TaskName=%%~nx* echo %TaskName% for %%f in ("%TaskName% (*).h") do ( echo ---------------------------- echo %%f copy /y "%%f" %TaskName%.h > NUL copy /y "%%f.out" expected.out > NUL for /F "delims=" %%i in (expected.out) do echo EXPECTED: %%i "%PYTHONPATH%\python.exe" "%DCJ_PATH%" test --source=solution.cpp --nodes=3 ) ~~~~~ There are two path variables on top, don't forget to set them appropriately. Here is an output for sandwich problem: ~~~~~ Sandwich ---------------------------- sandwich (1).h EXPECTED: 14 STDO...

Full text and comments »

Knapsack the tutorial -------------------- -------------------- <a name="TOC"></a> > **Teleporter:** **[**[Previous](#status)**]** | | | **[**[Next](#statement)**]** ### <strong> <center style="color:red;"> Table of content </center> </strong> | Teleporter | Description | | :--------------------------------------------------------------- | :-------------------------------------------------------------------------------------------- | | [I. STATEMENT](#statement) | Taking about the problem | | [II. EXAMPLE](#example) | To understand the problem better | | [III. Solution for small number of element &mdash; N](#small_n) | How much will you get in each...

Full text and comments »

JOI Open Contest 2020 Hello everyone! JOI Open Contest 2020 will be held from [Sunday, September 6, 04:00 UTC](https://www.timeanddate.com/worldclock/fixedtime.html?msg=JOI+Open+Contest+2020&iso=20200906T04&p1=1440) to [Monday, September 7, 04:00 UTC](https://www.timeanddate.com/worldclock/fixedtime.html?msg=JOI+Open+Contest+2020&iso=20200907T04&p1=1440). You can start at any time and the duration is basically 5 hours. Note that the duration becomes shorter if you start after [Sunday, September 6, 23:00 UTC](https://www.timeanddate.com/worldclock/fixedtime.html?iso=20200906T23&p1=1440), i.e. less than 5 hours before the contest ends. There will be 3 tasks. Each submitted source program must be written **only** in C++. Problem statements will be provided both in Japanese and in English. You can find more details in [the contest page](https://contests.ioi-jp.org/open-2020/index.html). Past contests are also available in [this page](https://contests.ioi-jp.org/). Since the judge server isn't availabl...

Full text and comments »

Codeforces Round #349 Editorial [problem:667A] To know how much water you consume per second you should divide consumed volume, $v$, by the area of the cup, $\dfrac{\pi d^2} 4$. Then you should compare thisit with $e$. If your speed of drinking is greater, then you'll drink all the water in $\dfrac{h}{\tfrac{4v}{\pi d^2}-e}$ seconds. Otherwise you would never do it. [problem:667B] It is possible to make a convex polygon with given side lengths if and only if a generalized triangle inequality holds: the length of the longest side is less than the sum of lengths of other sides. It is impossible to make a convex polygon from a given set, so there is a side which is longest than (or equals to) than sum of others. Assume it is greater by $k$; then it is sufficient to add a rod of length $k+1$. More, it is clear that adding any shorter length wouldn't satisfy the inequality. Thus the answer for the problem is $\texttt{max}(l_1, \dots, l_n) - (l_1 + \dots + l_n - \texttt{max}(l_1, \dots, l_n)) + 1$. [probl...

Full text and comments »

[Editorial] 0xPPL AlgoBee II By Scaler School Of Technology <spoiler summary="Problem A - Number Theory"> We can utilize the formula for the sum of a geometric progression to compute the sum of divisors raised to the power 69 efficiently. $$ \left(1 + p_1^{69} + p_1^{69*2} + \ldots + p_1^{69*e_1}\right) \times \left(1 + p_2^{69} + p_2^{69*2} + \ldots + p_2^{69*e_2}\right) \times \ldots \times \left(1 + p_n^{69} + p_n^{69*2} + \ldots + p_n^{69*e_n}\right) $$ When computing the sum of divisors of a number, each divisor contributes to the total sum according to its power. For a prime factor $x$ raised to the power $y$, the divisors are of the form $x^0, x^1, x^2, \ldots, x^y$. Notice that these are in a geometric progression. The formula for the sum of a geometric progression is: $$S = \frac{a \cdot (r^n - 1)}{r - 1}$$ <ul> <li><b>S</b>: The sum of the geometric progression.</li> <li><b>a</b>: The first term of the progression (in this case, 1).</li> <li><b>r</b>: The common ratio, which is $x^{69}$.</li> <li>...

Full text and comments »

(AutoCp) Competitive Programming Plugin for Intellij-Based IDEs The starting part of my competitive programming setup felt just ideal with vscode and its amazing [cphelper](https://marketplace.visualstudio.com/items?itemName=DivyanshuAgrawal.competitive-programming-helper) extension. I remember reading articles like "Setting up your C++ competitive programming environment" that got me up in no time. Later, when I heard about Clion, I understood how much it could offer me. This time around CLion the starting part was not ideal but still okay. But I could not find something as simple and straightforward as cphelper in any of the plugins that I looked and most of their docs were clearly not making my setup any simpler. There was no way I could ignore CLion and its amazing features. So, I had to do something and this plugin is what I did. Despite making it easier for me to use, I hope to make it as accessible as possible. It would be very helpful if you could let me know of any issues or suggestions on GitHub by [opening a new issue](https://github...

Full text and comments »

Релиз testlib.h — 0.8.5 **Update: Выпущен новый релиз 0.8.5**. Скачать новую версию вы можете с [сайта проекта](http://code.google.com/p/testlib/). Новая версия внедрена во все сервисы Codeforces и Polygon. Изначально этот пост содержал информацию о девелопмент-версии, но сейчас он используется для описания версии 0.8.5. Библиотека testlib &mdash; самая популярная и развитая библиотека для написания чекеров, генераторов, валидаторов и теперь интеракторов для задач. Первая версия testlib.h была написана мной в 2005-ом, и представляла по большей степени порт testlib.pas на С++. С тех пор многое было улучшено и расширено. В настоящий момент она активно используется в задачах Codeforces, разных этапах Всероссийской олимпиады школьников, многих петрозаводских контестах, всех саратовских соревнованиях и т.д. Вот основные изменения/улучшения. ### Комментарий программы: stdout -> stderr Теперь системные сообщения testlib-программ (чекеров, валидаторов, интеракторов) направляются в стандартный поток ошибо...

Full text and comments »

Bash Script for Stress Testing[Code with explanation] Hello Codeforces community. ~~~~~ Tl;dr: The script is specifically for *Unix and can be used to stress test `C++` solutions. It can be easily modified to work with python or java. To use it in windows you can download Ubuntu terminal which is officially available on Microsoft Store and then use it or you can modify the script to work in cmd by changing the .out files to .exe and a bit of syntax for cmd. ~~~~~ **Note**: If you don't want to read this lengthy blog, just go to [this](https://github.com/bhupixb/Stress-Testing-bash-script) repo and follow the instructions of readme. <br> First let me tell you what stress testing is if you don't know, Stress testing is technique using which we can run our solution (which we think might fail/is failing) on a number of random test cases and match it's output with the output of a solution which is a brute force solution or accepted solution of someone else.<br> If you don't know why and when to use stress testing you can use [...

Full text and comments »

Debugging with random generated tests, with windows script Sometimes when you are getting WA on a problem, possibly due to missing some corner case or a bug in your code, all you really need are the perfect test cases. Of course you don't know the perfect test cases, so you have to resort to something else. And that something else is checking your code on a bunch of randomly generated testcases. I recently learnt about it and so, am writing this so other noobs like me can get a little help. First of all, this isn't an unique idea. I myself learnt about it from [user:errichto,2019-05-03]'s youtube [video](https://youtu.be/JXTVOyQpSGM). You should check it out if you haven't seen it before. So the idea is simple, you will write two new c++ programs, one to generate random test cases. And another to get solution for those test cases, but unlike your actual solution code, this will definitely give the correct answer (perhaps not efficiently/ via brute force). You run the test generator a bunch of times and save the tests in a fine **input.in**....

Full text and comments »

CP Editor 3.2 : CP Editor meets Competitive Companion Check : https://cpeditor.github.io ================== Hi Guys ! You guys are truly amazing. I created CP Editor around 3 months ago just for fun and personal use, never wanted to make it public but anyways, I decided to make it public with [this blog](https://codeforces.com/blog/entry/71673). I got so much love and support that I could not hold myself back from improving it, in following weeks I released the second version in [this blog](https://codeforces.com/blog/entry/71907). Fixing a lot of issues and bringing new features. Let's get into what is new in this release of CP Editor. But first, #### Merry Christmas programmers!! Thanks to [user:ouuan,2019-12-25] for his wonderful contributions. Almost all new features were implemented by him. #### What's New - [**NEW**] Save and restore Input and Expected outputs. Highly requested by [user:IWanna_MightiestDisciple,2019-12-25] [user:ekalavya_k_k_p,2019-12-25] [user:smile_,2019-12-25] [user:Double_Helix,2019-12-25]) ...

Full text and comments »

Balkan Olympiad in Informatics — Day 2 The second day of the Balkan Olympiad in Informatics has finished and the competition went pretty smoothly, there was a minor bug in the tests of the second problem, but it was fixed quickly. [Final results](http://www.boi2015.uni-ruse.bg/competition/results) The tasks in the second day were, in my opinion, more interesting than the first day. Once again here's a link with the problems (from both days): [Tasks](http://www.boi2015.uni-ruse.bg/competition/tasks) **Clarkson** This problem was quite interesting and the solution was based on a suffix structure. Both suffix array and suffix tree were good enough to solve the problem, and building them for O(N log N) or perhaps even O(N log^2 N) was sufficient. The structure was used so you can calculate the function: F[i] &mdash; the largest substring in the first string, starting at index i, that is present in the second string. After this function was computed, binary search for the answer combined with dynamic program...

Full text and comments »

TOKI Open 2017 Post-Contest Hello! [TOKI Open 2017](http://codeforces.com/blog/entry/51512) has ended. Thank you to everyone who participated the contest. We decided to not consider any participants from the second window whose username is registered on the first window. We also decide to not consider any participants from the second window whose code is very similar to other user's code on the first window. After that, we consider a TOKI Open 2017 participant to be those who made at least one submission on either day. There were a total of 109 participants, which four of them get a fullscore. Congratulation to [user:Reyna,2017-05-17], [user:kevinsogo,2017-05-17], [user:pwypeanut,2017-05-17], [user:tuna_salad,2017-05-17]. The full result of TOKI Open 2017 is available [here](https://docs.google.com/spreadsheets/d/1OP76m7dG7uDyngGUm7ilykNmWc660KCHymxfi8OERww/edit?usp=sharing). The skeletons, solutions, problem descriptions, and testcase generators for TOKI Open 2017 are available [here](https://github...

Full text and comments »

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...

Full text and comments »

A2SV AASTU G5 — Contest #8 [Here](https://codeforces.com/contestInvitation/150ae2b6091bfb195b32f32e425f9c230a7795d8) is the mashup link (the problems are from Codeforces' problem set). #### [A. Abenezer's String Problem](https://codeforces.com/gym/499363/problem/A) <spoiler summary = "Solution"> To solve the problem we need to find the character with the highest alphabetical order in our string, since Abenezer will need at least that alphabet size and won't need more. To do this iterate through the string and find the character with the highest alphabetical order. Output the maximum alphabetical order found. The solution can be done in $O(n)$. </spoiler> <spoiler summary="Code"> ```python3 t = int(input()) for _ in range(t): n = int(input()) s = input() ma = 0 for ch in s: ma = max(ma, ord(ch)) print(ma - 96) ``` </spoiler> #### [B. Ruth Wossen The Monster Killer](https://codeforces.com/gym/499363/problem/B) <spoiler summary = "Solution"> We are ...

Full text and comments »

Post-Contest: TOKI OSN Open Contest 2018 Hi Codeforces community! :) [TOKI OSN Open Contest 2018](http://codeforces.com/blog/entry/60263) has ended. Thanks everyone for your participation! :D There were a total of 96 participants: - 21 of them achieved a score in the **gold** cutoff (according to the actual competition of OSN 2018). - 15 of them achieved a score in the **silver** cutoff (according to the actual competition of OSN 2018). - 14 of them achieved a score in the **bronze** cutoff (according to the actual competition of OSN 2018). Congratulation to [user:Yehezkiel,2018-07-08] for winning the contest! The full result of TOKI OSN Open Contest 2018 is available on the [official website](https://osn2018.toki.id/open-results.html). The problems are available for upsolving [here (TLX)](https://training.ia-toki.org/archives/53). The problems discussion (editorial) will be written in Bahasa Indonesia only and still in progress. Fear not, we provide you the full repository of OSN 2018 consisting of the solut...

Full text and comments »

Digit DP "tricks" Prereq: [this digit dp blog](https://codeforces.com/blog/entry/53960) Cut the flag dimension ------------------------- Usually, whatever states you use in the recursive dp function, you will memoize it. And often you will have some thing like this ~~~~~ int memo[pos][...][...][low] ~~~~~ Where `low` is the flag that checks if the current number is already smaller than the considered number. It is totally possible to subtract this dimension (half the memory needed) by manipulating it in the recursive function: Example problem: [Perfect Number](https://codeforces.com/contest/919/problem/B) This is what "normal" code would look like: <spoiler summary="normal code"> ~~~~~ ll mem[20][11][2]; ll dp(int pos, int sum, bool lo) { if(sum > 10) return 0; if(pos == n) return (sum == 10); ll& res = mem[pos][sum][lo]; if(res != -1) return res; res = 0; int mx = lo ? 9 : v[pos]; for(int d = 0; d <= mx; d++) ...

Full text and comments »

TLE in Matrix exponentiation This is how I implement matrix exponentiation [190118918](https://codeforces.com/gym/102644/submission/190118918) (in this example, for the problem [Fibonacci](https://codeforces.com/gym/102644/problem/C)) But I encountered [this](https://www.hackerrank.com/contests/overnite2023/challenges/function-induction) problem before and got TLE after implementing matrix exponentiation. My solution code was: ~~~~~ #include<bits/stdc++.h> using namespace std; #define nl "\n" #define ll long long #define fo(i,n) for(i=0;i<n;i++) #define fop(i,x,n) for(i=x;i<=n;i++) typedef vector<int> vi; typedef vector<ll> vl; const int mod = 1e9+7; const int N = 2e5+5; vector<vl> mul(vector<vl> a,vector<vl> b){ ll n=a.size(),i,j,k; vector<vl> ans(n,vl(n,0)); fo(i,n) fo(j,n) fo(k,n) ans[i][j]=(ans[i][j]+a[i][k]*b[k][j]%mod)%mod; return ans; } vector<vl> mpow(vector<vl> a,ll b){ ll i,n=a.size(); vector<vl> res(n,vl(n,0)); fo(i,n) res[i][i]=1; wh...

Full text and comments »

GRAPH-TESTCASE-VISUALIZER, website where you can visualize the graphs by simply pasting the codeforces testcases. [GRAPH-TESTCASE-VISUALIZER](https://graph-testcases-visualizer.web.app) creates visualized graph using the test cases. Here you can visualize Weighted as well as Unweighted graphs. #### How To Use? 1. Copy the test cases (should be valid) 2. paste in the [PARSER](https://graph-testcases-visualizer.web.app/testcase) in website #### What Are Valid Testcases? 1. **WEIGHTED GRAPHS** * Should be of form (U, V, W) 2. **UNWEIGHTED GRAPHS** * Should be of form (U, V) `U`: `FROM` `V`: `TO` `W`: `WEIGHT`   [Website Link](https://graph-testcases-visualizer.web.app) [Github Link](https://github.com/jhabarsingh/GRAPH-TESTCASE-VISUALIZER) [Report Bug](https://github.com/jhabarsingh/GRAPH-TESTCASE-VISUALIZER/issues) If you like this we...

Full text and comments »

What makes pypy64 slow here? In the recent Goodbye 2021 Round on Problem E my code seems to run a lot slower when running on pypy64 as opposed to regular pypy. The following submissions are identical, with the exception being the language used. [submission:141113239] (pypy3.7 &mdash; AC 732ms) [submission:141185703] (pypy3.8 64bit &mdash; TLE) Running on Custom Invocation on one testcase of size $10^5$ shows that pypy3.7 will take about 250ms whereas pypy3.8-64 will take 5600ms. Profiling my code it seems like the culprit is my find function ~~~~~ #Finds smallest index of segtree such that seg[ind] <= x #Only works if func = min def find(self, x): curr = 1 if self.data[curr] > x: return -1 while curr < self._size: assert self.data[curr] <= x if self.data[2 * curr] <= x: curr = 2 * curr else: curr = 2 * curr + 1 assert self.data[curr] <= x return curr - self._size ~~~~~ Replacing this function w...

Full text and comments »

Testcases of AtCoder All testcases of atcoder problems will be posted here: https://www.dropbox.com/sh/arnpe0ef5wds8cv/AAAk_SECQ2Nc6SVGii3rHX6Fa?dl=0 If you are interested in the rating system, please check rating.pdf at https://www.dropbox.com/sh/zpgcogxmmu84rr8/AADcw6o7M9tJFDgtpqEQQ46Ua?dl=0

Full text and comments »

ICPC Team Practice Contest — Editorial <img src="https://i.imgur.com/9dMa5uV.jpeg" height="300px" style="float:right; margin:20px;"/> Hello, Codeforces! I and [user:0x4F5F6F,2024-02-07] have curated an **ICPC-Styled Team Contest** in the gym, [contest:104955]. The level of questions is _medium_. This is for anyone who loves giving contests and solving problems. The contest will be of most interest to CMs and below. For anyone who wants to practice or just wants to go through the problems can register for our contest [here](https://codeforces.com/contestInvitation/ac3b6f91c4d03f298569a820f95c304dd0cb950f). Hope you will enjoy solving the problems! I would like to thank: - our problem setters [user:vrintle,2024-02-07], [user:0x4F5F6F,2024-02-07], [user:_bLIC_,2024-02-07] and [user:BitWizz,2024-02-07]. - our problem testers [user:BitWizz,2024-02-07], [user:_bLIC_,2024-02-07], [user:0x4F5F6F,2024-02-07], [user:vrintle,2024-02-07] and _myself_. - [user:JainWinn,2024-02-07] for the amazing poster design. **Co...

Full text and comments »

Biweekly contest 1 Editorial [user:Panda_2500,2022-11-14] #### Note from Author: Congrats to all the Winners. Glad to see so much participation. Hope to see you all participate in the next biweekly as well. You can contact me (Abhijit Mishra) for any queries related to the contest or problem discussion. I would recommend first looking at the hints for the problem if your facing logical issue, if you are absolutely clear with logic then move on to look at the solution and the code. efforts will be made towards making code for other languages (Java and Python) available as well. ## [A — Try-logy](https://codeforces.com/gym/408062/problem/A) <br> <spoiler summary="Hints"> <spoiler summary="Hint 1"> Think of the cases in which the team will solve a problem. </spoiler> <spoiler summary="Hint 2"> Repeat **for** the n problems. </spoiler> </spoiler> <spoiler summary="Solution"> A problem will be solved by the team if there are **atleast** two 1s in a row. count this for every row i....

Full text and comments »

[Competitive_Programming] A new tool for competitive programmers بسم الله الرحمن الرحيم **Hello**, I would like to introduce The **Competitive Programming** tool. It provides several useful features for competitive programming. ### **Test your code for testCases:** You can test your code for several test cases at the same time and you can load the test cases supplied in the problem automatically just by pasting the link of the problem in the tool and let it load the test cases for you (This work for Codeforces, Atcoder) <a href="https://ibb.co/qd164bw"><img src="https://i.ibb.co/mGzpYQ7/Screenshot-from-2021-09-26-17-44-45.png" alt="Screenshot-from-2021-09-26-17-44-45" border="0"></a> ### **Submit your solution:** This tool can also submit your solution automatically to your account from the tool itself and load the results of your submission (Accepted, Wrong answer, ..etc) (This work for [codeforces.com](codeforces.com) and [atcoder.jp](atcoder.jp)) <a href="https://ibb.co/C6sXBcb"><img src="https://i.ibb.co/W0pdnhk/Screenshot-fr...

Full text and comments »

Indigo Contest 2023 Unofficial Editorial As the official editorial is promised to come out later, I will write an unofficial editorial for now. Some of the solutions are from my teammate [user:tcmmichaelb139,2023-04-17] orz. Contest: https://www.hackerrank.com/indigo-coding-competition ## Easy These problems are quite trivial, so I will only provide solutions: <spoiler summary="P1"> ~~~~~ n=int(input()) arr=[] for i in range(n):arr.append(input().strip().replace('x','')) for i in range(n): cnt=arr[i].count('y') arr[i]=arr[i].replace('y','') arr[i]+=cnt*'y' arr=sorted(arr,key=lambda x:(-len(x),x)) print('\n'.join(arr)) ~~~~~ </spoiler> <spoiler summary="P2"> Michael's solution: ~~~~~ #include "bits/stdc++.h" using namespace std; string pi = "31415926535897932384626433832... (truncated copy-paste from internet)"; void solve() { string s; cin >> s; for (int i = 0; i < s.length(); i++) if (s[i] != pi[i]) { cout << i << '\n'; r...

Full text and comments »

To resubmit or Not to resubmit Hello CodeForces! Recently, I am thinking about the **resubmission strategy** in CodeForces. Last week I participated in [CodeForces Round #905 (Div.1)](https://codeforces.com/contest/1887), and I successfully solved first 4 problem with ~10 minutes remaining. However, after that, I saw the pretest result again and I noticed that execution time of problem C was 2979/3000ms. Then I decided to speed up the solution of problem C and finally resubmitted just a few seconds before the contest ends. The execution time in pretest was shortened to 2464ms, and all of my solution passed in system test. But the biggest blunder in this contest was resubmission &mdash; the number of testcases in pretest and system test was almost the same, and even my solution before resubmission passed (I confirmed after the contest). Since the score is mainly determined by submission time, my final rank in the contest dropped from ~60th to ~100th, and this made a difference between rating <s>increase</s> ...

Full text and comments »

Introducing Agnocpeed - Desktop app for competitive programming # AGNOCPEED [Agnocpeed](https://github.com/anujdhillxn/agnocpeed) is an OS agnostic desktop app created using Electron + React. User can configure it with their favourite editors, languages (Currently supports C++ and Python) and templates. It is designed such that a competitive programmer can fully focus on problem solving and tries to reduce the barriers such as copying testcases, constantly opening standings page, worrying about the verdict of your latest submissions. ## Build steps Git, NodeJS and NPM must be installed. Then type the following in a terminal to generate a build for your OS. ``` git clone https://github.com/anujdhillxn/agnocpeed.git cd agnocpeed npm install npm run electron:build ``` A Build will be generated in the dist folder. The dist folder will contain an installable as well as the installed app. ## Usage - Run the executable generated by the build. - Read the settings section below. - Select a platform (Codeforces or Atcoder) or choo...

Full text and comments »

Why am I getting stack overflow? + Weird Java behavior + Custom invocation differs from Judge [submission:102615607] gets stack overflow but runs fine locally. I'm generating input according to [this comment](https://codeforces.com/blog/entry/86004?#comment-737940) ([user:bleddest,2020-12-28] correct me if I'm wrong), and I'm using vm arguments `-Xmx1024m -Xss64m`, as suggested by the memory limit and [this blog](https://codeforces.com/blog/entry/79). Just in case testcase 50 was generated differently, I also tried generating input using n = 1e8 which worked fine, albeit taking 150 seconds and requiring a lot more memory. So now I am somewhat confused: Why am I getting stack overflow? <spoiler summary="Input generation"> ```java private String generateInput() { StringBuilder ans = new StringBuilder(); ans.append("1").append("\n"); int n = (int) 1e8, k = 100000; ans.append(n).append(" ").append(k).append("\n"); BigInteger bi = new BigInteger("1".repeat(k), 2); for(int i = 0; i<n; i += k) { ans.append(bi.toString(2)); bi = bi.subtract(Big...

Full text and comments »

JOI Open Contest 2019 Hello everyone! [JOI Open Contest 2019](https://contests.ioi-jp.org/open-2019/index.html) will be held on [July 14. (04:00-09:00 UTC)](https://www.timeanddate.com/worldclock/fixedtime.html?msg=JOI+Open+Contest+2019+-+Round1&iso=20190714T04&p1=1440&ah=5) and [July 14. (10:00-15:00 UTC)](https://www.timeanddate.com/worldclock/fixedtime.html?msg=JOI+Open+Contest+-+Round2&iso=20190714T10&p1=%3A&ah=5). As the tasks in these rounds are the same, you can participate in whichever round you like. The contest duration is 5 hours and there will be 3 tasks. Each submitted source program must be written **only** in C++. Problem statements will be provided both in Japanese and in English. You can find the details in [the contest page](https://contests.ioi-jp.org/open-2019/index.html). The past contests are also available in [this page](https://contests.ioi-jp.org/). Since the judge server isn't available after the contests, please download the testcases when you want to test your code. ...

Full text and comments »

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...

Full text and comments »

CF Debug : Get all small/hack testcases for any CF problem <strike>[cfdebug.org](https://cfdebug.org)</strike> ==> Moved to [cfstress.com](https://cfstress.com/) Hello everyone, have you ever faced a situation where you get a non-AC verdict on a certain testcase, but you are unable to debug your solution because you can't analyze (or view) that large testcase? or you are pretty close to the the solution, but don't want to look at the editorial yet, and wished you had more (small) testcases to brainstorm on paper? or a situation in which you feel you could've debugged your solution better if you could just run them on the hack-testcases (which are usually placed at the end of the test-set)? I've created [<strike>cfdebug.org</strike>](https://cfdebug.org) [cfstress.com](https://cfstress.com/) to help you in the above situations. It's a tool through which you can see all the small/corner testcases for any problem on Codeforces. <strike>By defult, it's sorted by input size (so that it's easier to dry run on paper), but if you get WA on, say ...

Full text and comments »

(Need help) How fill the table with at most 3 different colors in a same column. ### Overview This is just a subproblem that I have learned before. However, I don't have the testcases or the place to submit this. ### Describe Give $2*n$ colors with the their frequency (Each of them have to appear at least once). Sum of all their frequency is $m*n$. Make a table with size $m*n$ ($m$ rows, $n$ column) that minimize the max numbers of different color in each column (And the frequency of color is same above) ? #### Input The first line of input contains two integers $m$ and $n$ $(m, n <= 50)$. The second line contains $2*n$ integers — the frequency of each color. The sum values of them equal exactly $m*n$. ~~~~~ 4 4 1 1 2 2 2 4 1 3 ~~~~~ #### Output Output the table that satisfied the statement above. ~~~~~ 1 7 4 6 2 3 4 6 6 3 5 8 6 8 5 8 ~~~~~ ### Explain - Color 1 has to appear $1$ times; - Color 2 has to appear $1$ times; - Color 3 has to appear $2$ times; - Color 4 has to appear $2$ times; - Color 5 has to appear $2$ times...

Full text and comments »

Locju — Local Judge for testing your solutions and downloading Codeforces test cases <h1>Locju &mdash; Local Judge</h1> Locju is a console controlled software, minded to test locally solutions to competitive programming problems. <br><br> It allows you to judge a C/C++ code, using sample testcases. Your code can throw Accepted, Wrong Answer, Runtime Error, Time Limit Exceed or Compilation Error as a verdict. Locju also has a test case finder functionality. You must write a generator, correct solution and a validator (if needed) to use this function. What it does, is generate a number of testcases and report the verdict for each of them (by comparing with correct solution output). So you can find those testcases in wich your code fails. Furthermore, it has a functionality to download test cases of a given Codeforces Round. <h3>Index</h3> <ol> <li><a href="#requisites">Requisites</a></li> <li><a href="#installation">Installation</a></li> <li><a href="#usage">Usage</a></li> <li><a href="#techused">Technology Used</a></li> <li><a href="#testing">Te...

Full text and comments »

Need help , Please! [ Segment Tree problem, complexity analysis ] I got [this(ADATREE &mdash; Ada and Trees)](https://www.spoj.com/problems/ADATREE/) problem from [morass blog ](https://codeforces.com/blog/entry/55274) segment tree section. I stuck to analyzing the **both time complexity and memory complexity** of this problem in the worst case for this AC solution. **My Solution:** ~~~~~ /// BISMILLAHIR RAHMANIR RAHEEM #include<bits/stdc++.h> using namespace std; #define MUHAMMAD ios::sync_with_stdio(0);cin.tie(0); #define all(x) (x).begin(), (x).end() using ll = long long; const ll N = 3e5 + 5; vector < ll > tr[N<<2]; ll n; ll arr[N]; ll q; ll x; vector < ll > merge( vector<ll> a , vector<ll> b ){ vector<ll> order; while( a.size() and b.size() ){ int x = a.back(); int y = b.back(); if ( x <= y ) { order.push_back ( x ); a.pop_back(); } else { order.push_back ( y ); b.pop_back(); } } while(a.size()) order.push_ba...

Full text and comments »

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.com/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...

Full text and comments »

Maximal Square leetcode dp Hi, I was solving this dp question (Maximal square from leetcode). [Question LINK](https://leetcode.com/problems/maximal-square/) Let a be the input array.<br> The correct recurrence relation goes like: <br/> ``` dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + 1 ``` <br/> <spoiler summary="Correct code"> ~~~~~ #include <bits/stdc++.h> using namespace std; #define ll long long #ifdef NAYAK #include "/mnt/D/dual/c/debug.h" #else #define DEBUG(x...); #endif #define SPEEDUP ios_base::sync_with_stdio(false);cin.tie(NULL); #define MOD 1000000007 int a[1001][1001],dp[1001][1001]; int rec(int r,int c){ if(a[r][c]==0)return 0; if(dp[r][c]!=-1)return dp[r][c]; int ans=1; if(r>0 && c>0){ int len=min(rec(r-1,c-1),min(rec(r-1,c),rec(r,c-1))); ans=max(ans,1+len); } return dp[r][c]=ans; } void CLEAN(){ int n,m; scanf("%d %d",&n,&m); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ scanf("%d",&a[i][j]); dp[i][j]=-1; ...

Full text and comments »

AlgoUtsav 2024 | Editorial  We'd like to thank you all for participating in the contest and hope you enjoyed it. Hope to see you again next year! The tutorial for problem B will be added soon. --- <h2>[problem:509001A]</h2> Idea: [user:ninjamayank,2024-03-19] <spoiler summary="Solution"> The solution to this problem required **binary search on answer with 2D prefix sum**. First we binary search on the threshold. For a chosen threshold we create a new grid with values greater than or equal to $k$, set to $1$, and others to $0$. Next, we make a 2D prefix grid of size $n$ x $n$ for the new matrix containing values $0$ and $1$. Now we iterate over all possible $k$ x $k$ grids and get the sum using the prefix matrix. If the sum equals $k^2$ the chosen threshold is valid. We can continue the search for the maximum threshold further according to the validity of the chosen one. The overall time-complexity is $O(n^2...

Full text and comments »

Sampleforces : A tool to get additional sample input/output for CF problems **TL;DR**: I've created a tool using which you can get additional sample input/output (for recent problems), which you can then analyze on paper to help you get closer to the solution. Check it out at [cfstress.com](https://cfstress.com/) 1. You come up with an approach, and since you are too impatient, start implementing it. Your code passes the sample testcase, but it gets **WA** on Pretest 2. However, if you'd have 2 or 3 more sample test cases, you would've either abandoned the implementation after spotting the flaw, or you would've been more careful while coding, keeping those extra samples in mind. 2. You are at a loss of idea, and you turn to the editorial for hints. But not all editorials have hints, and the comment section has spoilers. If you work out more sample testcases on paper, it'd get you a bit closer to the solution idea. (Not true for all problems, but it's a good strategy in general). You just need to have patience. 3. You read an editorial and instantly commen...

Full text and comments »

Partial scoring subtask in Polygon Hey all! I'm trying to make an OI-style interactive question in Polygon for a school contest, and the score should depend on the number of queries used by the solution in the worst case. For the first few subtasks, the solution must use at most `X` queries (`X` depends on the subtask). The scoring for these first few subtasks works. However, for the final subtask, I'm trying to make a partial scoring subtask, where the score for the subtask should depend on the maximum number of queries used in any testcase in the subtask (score should be `30 - the maximum number of queries used`). Here is an example, in case it helps: Let's say that the final subtask has 4 testcases. In testcases #1 and #2, the solution used 5 queries, in testcase #3, the solution used 9 queries, and in testcase #4, the solution used 15 queries. Then, as 15 was the maximum number of queries used in any testcase, the score for the subtask should be `30 - 15 = 15`. So far, in the checker, I've tried to use `...

Full text and comments »

How to solve this problem ?!! I'm trying to solve [Farthest Nodes in a Tree (II)](https://lightoj.com/problem/farthest-nodes-in-a-tree-ii) Problem in java . it's from lightOj. But I'm getting MLE(it takes 151552 KB memory). How to solve it using java.?? <spoiler summary="code:"> ~~~~~ import java.util.ArrayList; import java.util.Scanner; import java.io.IOException; import java.io.PrintWriter; public class FarthestNodesinaTree { public static void main(String args[]) throws IOException { Scanner scan = new Scanner(System.in); int t = scan.nextInt(); int q = 1; PrintWriter out = new PrintWriter(System.out); while (t-- > 0) { mx = 0; short n = (short) scan.nextInt(); ArrayList<Node>[] node = new ArrayList[n]; for (int i = 0; i < n; i++) { node[i] = new ArrayList<Node>(); } for (int i = 0; i < n - 1; i++) { addEdge((short) scan.nextInt(), (short)...

Full text and comments »

A Recap of My First Year in CodeForces Hello all on Codeforces! ------------------ It’s been just over a full year since I created my Codeforces account. Since then a lot has happened on my Codeforces journey so far. With everything that’s happened I want to look back at how I got to my current point, share what I learned in the process, recap some of my best moments, and laugh at whatever I was thinking on a few of these contests, because a lot happened. The only issue is that there’s no way I’m going to detail all **60** contests I took part in 2022. Instead I’ve chosen to “award” the 9 most memorable contests, wheter it be because I did exceedingly well or self destructed in almost hilarious fashion. A few notes before I begin: No full solutions for any problems are shown in this post but there are code snippets and discussions that are spoilers for these problems. I apologize in advance. ### First Contest &mdash; [Hello 2022](https://codeforces.com/contest/1621) This was the first contest held in 2022, ...

Full text and comments »

A2SV Gen 4 - Camp Contest 2 Editorial [problem:430380A] <spoiler summary="Hint"> Try Binary Search. </spoiler> <spoiler summary="Solution"> Use binary search to find the position of the smallest name larger than the given name. </spoiler> <spoiler summary="Code 1"> ~~~~~ from sys import stdin n = int(stdin.readline().strip()) queue = list(stdin.readline().strip().split()) q = int(stdin.readline().strip()) for _ in range(q): left, right = 0, n &mdash; 1 val = stdin.readline().strip() best = len(queue) while left <= right: mid = (left + right) // 2 if queue[mid] < val: left = mid + 1 else: best = mid right = mid - 1 print(best) ~~~~~ </spoiler> <spoiler summary="Code 2"> ~~~~~ from sys import stdin import n = int(stdin.readline().strip()) queue = list(stdin.readline().strip().split()) q = int(stdin.readline().strip()) for _ in range(q): left, right = 0, n &mdash; 1 ...

Full text and comments »

New stress test tool in the competitive programming tool **Hello**, I would like to introduce that I added the **stress test tool** in the [competitive programming tool](https://codeforces.com/blog/entry/95349) (If you don't know it please read that blog first). This tool will generate test cases and compare the output of your program and the output of the accepted or the brute-force program. **To open it click F8 from the main app.** <a href="https://ibb.co/H41h5hm"><img src="https://i.ibb.co/W5qVmVS/1.png" alt="1" border="0"></a> - In the **Accepted solution** write the name of the accepted solution or the brute-force solution you created. and choose the language of it(C++, Java, Python) - In the **Hacking solution** write the name of the file that you trying to test. (and chose its language) - In the **Test case generator** write the name of the generator file you created (and the language of that file will be the language you selected in the main app) - Write the URL of the problem (This will use the URL as a source ...

Full text and comments »

How are these two codes different? [problem:1848A] Hello CF! Could you explain to me why these two codes output different results? ### Problem 1848A: Vika and Her Friends #### My Code: ~~~~~ #include <iostream> #include <vector> using namespace std; typedef long long ll; void solve() { ll n, m, k; //Size of mall and # of Vika's friends ll x, y; //Vika's coordinate cin >> n >> m >> k >> x >> y; //For each of vika's friends, check whether they are in the same square as her. If so, print NO for(int i = 0; i < k; i++) { int xx, yy; cin >> xx; cin >> yy; //!!! PROBLEM SEEMS TO BE HERE vvv!!! if((x + y) % 2 == (xx + yy) % 2) { cout << "NO" << endl; return; } } cout << "YES" << endl; //!!! PROBLEM SEEMS TO BE HERE ^^^!!! } int main() { int t; cin >> t; while(t--) { solve(); } } ~~~~~ #### Editorial's code: ~~~~~ #include <bits/stdc++.h> using namespace std; ...

Full text and comments »