All You Need is Randomly Guessing — How to Improve at Codeforces I hope [my previous blog](https://codeforces.me/blog/entry/126310) has convinced you that the best way to improve at Codeforces is to be more Russian, i.e. to improve your math capability. Unfortunately, humble mortals such as you and I are not gifted with the talent that esteemed Russian grandmasters such as 74TrAkToR had: _Surely, it is beneficial to have a code reference for many algorithms and data structures, but I also think that just superficially knowing the algorithm and maybe having implemented it once or twice before is sufficient to use it without a reference?_ _— Some other Codeforces grandmaster_ Therefore, in this blog I will explore the dark side of Russian-ness — randomly guessing — that is forsaken by every Russian grandmaster of the light side I know. However, it has been very helpful to me, and I hope that it serves you well, too. ## Example 1 I will start by using an example to demonstrate my thought process. This problem [1923C](h...

Full text and comments »

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

Full text and comments »

[Tutorial] Supporting Priority-Queue-like Undoing on DS _Good morning!_ In this blog, I will present an online algorithm that can perform priority-queue-like undoing on a data structure, given a few assumptions. I will also present and solve a generalization of that problem. For context, I highly recommend reading this blog that shows how to solve the easier problem of queue-like undoing. That blog gave me the inspiration for the trick I will describe here, but I will still try to write this blog so that it can be understood without it. Thank you [user:Noam527,2023-01-08] for introducing such a great trick to the competitive programming community. [[Tutorial] Supporting Queue-like Undoing on DS](https://codeforces.me/blog/entry/83467) Acknowledgment ----------------- Huge thanks go to [user:peltorator,2023-02-20] for hosting a [blog contest](https://codeforces.me/blog/entry/110840). His generous prize of $300 got many people to write blogs on new, interesting ideas, and it was one of the main reasons I wrote this blog. I'm...

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 »

Kapun's algorithm I'd like to share this one unpopular but awesome algorithm that I only heard a mention of once. Kapun's algorithm finds a hash collision for moduli as large as $10^{18}$. I know, we have *lots* of algorithms that do much better than that (and I'm writing an article on that at the moment, keep tuned), but Kapun's algorithm is really surprising in its simplicity. That its correctness is so difficult to prove is of more surprise even. Here we go. A polynomial hash of a string $s$ is defined as $$ H(s) = s_0 b^0 + s_1 b^1 + s_2 b^2 + \dots + s_{n-1} b^{n-1} \pmod M. $$ We want to find two strings with the same polynomial hash using only two characters: $0$ and $1$. We can reformulate this problem in another way. Let $a_i = b^i \mod M$, then we want to find two distinct subsets of $a$ with the same sum modulo $M$. Now *forget about the modulus*: let's just find two subsets with the same sum. Firstly, when is this possible? There are $2^n$ possible subsets and $n(M - 1) -...

Full text and comments »

Editorial of Codeforces Round 958 (Div. 2) Thanks for participation! **Update**: added alternative solutions/proofs for A,B,D,F [problem:1988A] <spoiler summary="Hint 1"> The optimal sequence of operations is very simple. </spoiler> <spoiler summary="Solution"> The optimal sequence of operations is adding $k-1$ 1-s into the set each time, at the same time decreasing $n$ by $k-1$. This implies that the answer is $\lceil \frac{n-1}{k-1}\rceil$. <spoiler summary="Why?"> I failed to find a Div2-A level proof. If you have a simpler proof please share it in the comments. Consider the number of elements that is $\equiv 1\pmod{(k-1)}$ in the set. The number of such elements increase by at most $k-1$ in each operation, and the aforementioned sequence of operation achieves the maximum increment. --- A simpler proof in the comments: consider the number of elements in the set. It increases by at most $k-1$ each time, and our construction reaches the maximum increment. </spoiler> </spoiler> <spoiler summar...

Full text and comments »

Counterexample to IOI Sphinx model code So I was trying to upsolve IOI 2024 Q6 Sphinx. In the editorial phase 2 states to split the condensed graph into two sets, and perform binary search on these sets for every colour, to determine which components have what colour. However, each binary search needs $\log N\approx8$ queries to perform the actual binary search, along with an additional query to "confirm" that no other component in the set has that colour. Along with the rest of the solution, this gives a query count of $3N+a+N\log N$, where $a$ is the number of monochromatic components. This means that, in the worst case, the solution would take $4N+N\log N$, which is up to $3000$ queries, more than is allowed in the problem. At first, I thought that there would be some amortisation which keeps the query count under the limit of $2750$ queries, but then I made the following construction: Consider the test case with $N=250$ vertices, all with different colours. Then, the graph is constructed by taking the first 248 vertic...

Full text and comments »

Codeforces Round 1010 (Div. 1, Div. 2, based on Zhili Cup 2025) Editorial Sorry for the late editorial. Our problem setters were so exhausted with the offline competition yesterday that they really need some good rest. Despite the unexpected and unpleasant incidents that occurred, we are truly surprised and grateful that so many of you still participated in this competition! We sincerely hope you enjoyed it! (Gratitude for all you guys from [user:Ecrade_,2025-03-16]: I felt so heartbroken when I heard about the unexpected issues, but seeing so many people in the comments comforting us, sharing thoughtful and positive messages that showed genuine empathy, and continuing to fully support our competition even after the wasted time, I was deeply moved. Thank you all! Codeforces truly embodies such a positive and uplifting community spirit!) [problem:2082A] <br> Idea: [user:Ecrade_,2025-03-16] <spoiler summary="Hint"> Do we really have to consider the problem on the whole matrix? </spoiler> <spoiler summary="Solution"> Let $r$ be the num...

Full text and comments »

Run-twice (aka communication) problems with Polygon and testlib.h ### Introduction _Run-twice_ problems (also called _multipass_ or _communication_ problems) are problems in which your program is executed twice. Here are some examples: - [problem:2054A] from the TON marathon. - Problems D, G and K from [Universal Cup Season 2 Stage 5](https://assets.ucup.ac/statements/statements-2-5.pdf). - All problems from [Universal Cup Season 2 Stage 16](https://assets.ucup.ac/statements/statements-2-16.pdf). - [Flash](https://boi2019.eio.ee/wp-content/uploads/2019/04/flash.en_.pdf) from BOI 2019 (this one is actually more complicated, but the premise is the same &mdash; there are multiple instances of your program which cannot share data except through the interactor. As you can see, there are many ways this format can be used, but the common themes are encoding/decoding, compression/decompression, constructing a bijection and similar ideas. The general principle is that you have to implement two functions and the second function has to somehow use t...

Full text and comments »

EPIC Institute of Technology Round Summer 2024 (Div. 1 + Div. 2) Editorial Hope you liked the problems! We apologize for the (very?) weak tests in H. Editorials for problems will be added over time (and hints), for now, please take a look at the available hints and model solutions. <spoiler summary="Easter eggs"> <spoiler summary="A"> ForceCodes is a reference CrossCode, you should try it. </spoiler> <spoiler summary="C"> Basil is one of the characters in OMORI, you should also try it. </spoiler> <spoiler summary="D"> "World is Mine" is one of Hatsune Miku's most well known songs, and a fan-made MV has a lot of cakes in it) I originally wanted to make the characters names Miku and Sweetheart(from OMORI), but decided to stick to Alice and Bob to keep the statement clean. </spoiler> <spoiler summary="E"> The epigraph is a reference to KonoSuba. </spoiler> <spoiler summary="H"> The epigraph is a quote from Celeste (you should try it), and the title is a reference to one of it's locations, Mirror Temple, but only now there are fumo...

Full text and comments »

EPIC Institute of Technology Round Summer 2025 (Codeforces Round 1036, Div. 1 + Div. 2) Editorial Thanks for participation! We hope you loved the contest. #### [problem:2124A] Problem Credits: [user:Lilypad,2025-07-01] <br> <spoiler summary="Hint"> When is there definitely *not* a solution? </spoiler> <spoiler summary="Solution"> First, note that since relative order is preserved no matter which elements are deleted, if $a$ is originally sorted in nondecreasing order, the array cannot be a derangement no matter which elements are deleted. If $a$ is not sorted, we can note that any two elements that form an inversion pair satisfies the requirements. The total runtime is $O(n)$. </spoiler> <spoiler summary="Code"> ``` #include <bits/stdc++.h> using namespace std; void solve(){ int n; cin >> n; vector<int> arr(n); for(auto &x : arr) cin >> x; for(int i = 0; i < n; i++){ for(int j = i + 1; j < n; j++){ if(arr[i] > arr[j]){ cout << "YES\n2\n"; cout << arr[i] << " " << a...

Full text and comments »

Solutions for Codeforces Beta Round #65 (Div. 2) <b>A.</b> In this problem you can just do what is written in the statement. Let read all words. For each of them compute its length $L$, its the first and the last letter. If $L&gt;10$, output word without any changes, otherwise output the first letter, next $L-2$ and finally the last letter.<br>[cut]<br><b>B.</b> At first, compute $z = \sum_{i=1}^n a_i$. It equals $\lfloor mnk / 100 \rfloor$, where $\lfloor x \rfloor$ is rounding down. Next we fill first $\lfloor z/k \rfloor$ squares with a saturation $k$. $(\lfloor z/k \rfloor +1)$-th square (if it exists) we fill in a saturation $z-\lfloor z/k \rfloor k$. All other squares we leave with a saturation $0$.<br><br><b>C.</b> Define an <i>good</i> polygon as a regular polygon which has a knight in a good mood in every of its vertex. Side of polygon we will measure in arcs which is obtained by dividing border of round table with knights.<br><br>Freeze the length of the side. Let this length equals $k$. Observe that the regular polygon wit...

Full text and comments »

Codeforces Round 1068 (Div. 2) Editorial [2173A-Sleeping Through Classes](https://codeforces.me/contest/2173/problem/A) Idea & Solution: [user:HHH666666,2025-12-05] <spoiler summary="Tutorial"> From the statement we can conclude that a class can be slept through $\textbf{if and only if}$: 1. The class itself is not an important class. 2. The class is not within $k$ classes after any important class. Here's an $O(nk)$ approach: We directly simulate the process: for each important class at position $i$, mark positions $i+1, i+2, \dots, \min(i+k, n)$ as “must stay awake”. After processing all important classes, count the classes that are neither important nor marked. This $O(nk)$ solution is acceptable under the constraints. There's also an $O(n)$ solution: For each unimportant class, we only need to focus on the nearest important class before it. Thus we maintain a variable $last$ storing the index of the most recent important class (or $-\infty$ if none seen yet), then for each $i$ from $1$ to $n$, if it's...

Full text and comments »

Alternative approach to CF #718 H - Hack me please! I had a different approach to H that results in very short, but incorrect code ([submission:114044595], [submission:114044982]). I also have a few versions which I don't know how to hack ([submission:114142853], [submission:114141339], [submission:114141392]). Can anyone hack these or prove they're correct? The main idea is to use strong LP duality: the problem is unsatisfiable if and only if there is some linear combination of the input constraints such that all variables cancel and the constants give a contradiction (e.g. $0 \le -1$). We can try to simplify this by only checking all "extremal" feasible linear combinations, i.e. linear combinations on the convex hull of all linear combinations whose variables completely cancel. Here, I came up with the (false) hypothesis that any such extremal linear combination must include 2 "neighboring" constraints which we can treat as a relaxation, e.g. we use both $y_{i-1}^+$ and $z_{i}^+$; these can be "merged" into a (possibly tighter)...

Full text and comments »

[Tutorial] Next Smaller Jumping (NSJ) Do you know the _monotonic stack_? You’ll learn something easier to understand with **shorter code**! We’re going to discuss a common fundamental problem that you may face as part of other problems. The _Next Smaller Element (NSE)_ problem. **Problem Statement** Given an array $a$, for each index $i$, find $next_i$, which is the first index to the right of $i$ that is smaller than $a_i$. **Example** Let's say $a = [5, 8, 2, 6, 7, 9, 1, 2]$. The output (zero-based) is $next = [2, 2, 6, 6, 6, 6, 7, 7]$.  ## NSJ Algorithm Let’s begin with a simple, **non-optimal** solution. ~~~~~ for (int i = n - 1; i >= 0; --i) { next[i] = i + 1; while (next[i] != n && a[i] <= a[next[i]]) ++next[i]; } ~~~~~ The time complexity of the above code is $\mathcal{O}(n^2)$. What if I reduce it to $\mathcal{O}(n)$ by changing only **one line**? _Think before you continue..._ <br> <br> ...

Full text and comments »

(Solved)Can someone help me find a counterexample on Atcoder beginner problem F? Problem : https://atcoder.jp/contests/abc171/tasks/abc171_f Ill explain my idea below with the first example. _______ o ___________ o ________ f __________ we are able to place letters in the 4 slots here. Lets say that we place a letters on the first slot, b letters on the second, c letters on the third, and d letters on the fourth slot. therefore, a+b+c+d = n. The first slot is free to place slot -> we have 26^a ways to put it. The second slot, third slot, fourth slots have a restriction; you cannot place the letter that is at the left of the slot. (you can't place o in the second, third slot, you can't place f in the fourth slot) -> by this restriction, we can prevent duplicates being counted. -> ex) ooaoaaof -> this will be only counted one time. -> therefore, there's 25^(b+c+d) = 25^(n-a) ways to put in the slots. if a is 0, b+c+d = n. the ways to distribute numbers to b, c, d is H(3,n)=C(3+n-1, n). if a is 1, b+c+d = n-1. the ways to distribute ...

Full text and comments »

My question about CERC 2016 Problem G (Sorry for my poor English. >_<) (Sorry for my poor English. >_<) (Sorry for my poor English. >_<) First of all, here are some links about CERC2016: [1] The contest page in CF: https://codeforces.me/gym/101173 [2] The official tutorial: https://cerc.hsin.hr/2016/tasks/cerc2016_presentation.pdf --- The text I put below is from page 117 of the official tutorial. > Finally, we'll revise our gap-finding algorithm, not to visit both children when the split would result in two tiles that look the same with respect to intersecting with the polygon. Instead we visit only one children, but create twice as many gaps in that branch. It can be shown that this way we'll only visit $O(nm^2)$ states. ... It mentioned that "this way we'll only visit $O(nm^2)$ states". I have spent several hours on trying to prove this. However, I can't prove it. And it seems to have some counterexamples. Maybe it is a counterexample: Let's assume that $m \approx 2 ^ 8 \times 4, n...

Full text and comments »

A note on a nowcoder problem -- Centroid decomposition (点分治) Nowcoder problem (Chinese) [link](https://ac.nowcoder.com/acm/contest/51721/E). The submission is private because I don't want to publish my Nowcoder account, but you can copy the code at the end of this blog and paste it to the answer sheet, it will get AC. [English version](https://codeforces.me/blog/entry/114434) First I would like to thank [user:ShaoNianTongXue5307,2023-03-28] for his idea! This is a learning note, most for myself. Most of this blog is not original. **Part 1: Problem Statement:** A tree $T=(V, E)$ has $n$ vertices and $n-1$ edges, the weight of each vertex $i$ is $a_i$. For each edge $e$, you can determine its direction, i.e., for two vertices $u, v$, there are two states: $u \rightarrow v$ and $v \rightarrow u$. There are $2^{n-1}$ states in total. For each state $S$, we define $f(S)$ as $f(S) := \sum\limits_{(u, v) \in V \times V, v\,\text{is reachable from}\,u} |a_u - a_v|$. Compute the sum of $f(S)$ over all $2^{n-1}$ states $S$, mo...

Full text and comments »

Codeforces Round #275 Editorial ## [problem:483A] Problem author [user:gridnevvvit,2014-10-25] This problem has two possible solutions: 1. Let's handle all possible triples and check every of them for being a counterexample. This solution works with asymptotics $O(n ^ {3} log A)$ 2. Handle only a few cases. It could be done like this: ~~~~ if (l % 2 != 0) l++; if (l + 2 > r) out.println(-1); else out.println(l + " " + (l + 1) + " " + (l + 2)); ~~~~ Jury's solution: [submission:8394832] ## [problem:483B] Problem author [user:gridnevvvit,2014-10-25] Jury's solution is using binary search. First, you can notice that if you can make presents with numbers $1, 2, \ldots, v$ then you can make presents with numbers $1, 2, \ldots, v, v + 1$ too. Let $f(v)$ be the function returning true or false: is it right, that you can make presents with numbers $1, 2, \ldots, v$. Let $f_1$ be the number of numbers divisible by $x$, $f_2$ &mdash; the number of numbe...

Full text and comments »

Finding the Diameter of a Polygon using Two pointers and Monotone Chain Let me state my opinions before we start the explaining the actual algorithm &mdash; I honestly prefer Monotone Chain over Graham Scan. Its simplicity in implementation is the most important reason, though I have other reasons such as the ability to find the upper hull and the lower hull separately. For people who are already accustomed to Rotating Calipers, you can do it the way you used to, and you will still find the same results. This algorithm is for the people who find the Rotating Calipers' concept hard to understand. ---- Just yesterday, I came up with a way to find the diameter of a polygon (the distance of the farthest pair) using Two pointers and Monotone Chain. I knew I could already do it using Rotating Calipers, but I found the concept quite hard to understand and implement. Therefore, I came up with a method myself. This method may be equivalent to Rotating Calipers in its result (I would be happy if I can extend it to other tasks), so remind me if it is. First,...

Full text and comments »

[Tool] stress.ojcloud.net — a free online stress tester **TL;DR:** I built **[stress.ojcloud.net](https://stress.ojcloud.net)** — a free online stress tester for competitive programmers. Paste your `main`, `brute`, and `gen` into three tabs, hit Run, and it streams per-test verdicts and stops at the first counterexample with `Input / Main Output / Brute Output` side-by-side. No signup, no install, 8 languages (C++ 03/11/14/17/20, C, Python/PyPy, Java, Kotlin, Go, Rust). ## Hello, Codeforces! If you've been doing CP for more than a week, you already know the routine. You submit, you get `Wrong answer on pretest 2`, the test is hidden, and your solution is 300 lines long. You open a terminal, `mkdir stress`, write the same `while true; do ./gen > in; ./a.out < in > out1; ./brute < in > out2; diff out1 out2 || break; done` you've written a hundred times, realize you forgot to seed the generator, rewrite it, forget to recompile `brute`, finally see a diff, and now you're squinting at 2000 random numbers trying to minimize the counterexamp...

Full text and comments »

Union find tree without ranks The traditional implementation of union find tree (aka disjoint set) utilizes rank compression &mdash; this is the code with it. ~~~~~ int parent[1000], rank[1000]; int find(int x){ return parent[x] = (parent[x] == x ? x : find(parent[x])); } void Union(int p, int q){ p = find(p); q = find(q); if(rank[p] < rank[q]) parent[p] = q; else parent[q] = p; if(rank[p] == rank[q]) rank[p]++; } ~~~~~ But in competitive programming, I found out that the rank compression was useless. Without rank compression, the code was shorter, and even the program ran faster. This is my implementation without rank compression. ~~~~~ int parent[1000]; void Union(int p, int q){ parent[find(p)] = find(q); } ~~~~~ and for some cases, I found implementing rank compression is quite hard (maybe impossible). I will give you a sample problem : "Given a tree T, you should process Q queries &mdash; "paint the edge's value into x (>0) from path s to ...

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.me/blog/entry/14801). Previous posts can be found [here](http://codeforces.me/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 »

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.me/contest/1621) This was the first contest held in 2022, ...

Full text and comments »

On Input Formatting and How Lists are Represented in Input Files When preparing the problems for the February 25th NA ICPC regionals, we had some discussion around how lists should be formatted when given as input to contestants. The primary argument motivating some design decisions was consistency &mdash; namely that all lists should be formatted the same way, where a list should be expressed by starting with the length of the list, $n$, and then writing $n$ lines, one item per line. This is pretty standard and for most problems, this is the convention that most problems use for most lists. The main counterexample to this case seems to be when the list is a list of integers. A lot of problems, when confronted with a list of $n$ integers, will write out the list as one line of $n$ space-separated integers. This seems to be the meta for most contests, though I have not looked very carefully at this so this assumption may be wrong. NA ICPC is one of the contests that generally follows line-delimited lists of integers. Here's my question to t...

Full text and comments »

Noob needs help with his code :) code with details, appreciate any feedback! https://codeforces.me/contest/1335/problem/E1 When I run the test, it keeps going well, and suddenly it fails on test 10 data 596 or something, so I cannot see what test case is causing the problem. Im asking for help after 3+hours of coding ! Id really appreciate any help. Source code below, with detail; ------ It works on almost all cases, but there seems to be a counterexample that I seem to be missing. Thanks :) ~~~~~ #include <iostream> #include <vector> using namespace std; int min_num(int a, int b) { return a<b ? a : b; } void solve() { int n; int a[200002]; vector<int> cnt[202]; int ccnt[200002]={0,}; cin >>n; int i,j,k; for(i=1 ; i<=n ; i++) { cin >>a[i]; cnt[a[i]].push_back(i); //this cnt stores the location of each number //ex) 1 1 3 3 2 1 -> cnt[1] = 1, 2, 6 cnt[2] = 5, cnt[3] = 3, 4 ccnt[a[i]]++; } int cntmax = 0; for(i=1 ; i<=200000 ; i++) if(cntmax < ccn...

Full text and comments »

The art of finding counterexamples OK! Now you have an approach to solving a problem, but wait! Will this always work? Is there any counterexample that fails this algorithm? These are the questions that I constantly face nowadays. Let me elaborate on this with some examples: [Empty Graph](https://codeforces.me/contest/1712/problem/D): In this problem, the first approach that I came up with was to just assign 10^9 to k smallest numbers. Of course, this was wrong, but I couldn't find a counterexample and I had to ask a friend. [Maximize the minimum](https://www.codechef.com/submit/MAXTHEMIN?tab=statement): One of the approaches that came to my mind was to assign the maximum value of adjacent elements and do it k times. (tho it was a bit easier to find counterexamples for this approach) There are two ways(that I know) that one can use to verify a solution: 1. Prove it mathematically (using induction, contradiction, etc). 2. Find a counterexample I have talked about this to some of the people(who are doi...

Full text and comments »

How to solve problems in pseudocode with github copilot. Background: Github recently released [github copilot](https://copilot.github.com/), a code-generation tool. Ever since I got access to it, I've been relentlessly toying with it and testing its capabilities. <br> During this, I found that copilot has the ability to not only synthesize original code, but also translate code from one form to another, such as from python to c++, from code using one naming convention to another, and even to and from pseudocode. <br> By taking this capability to the extreme, we can write the solution for a CP problem in pseudocode and translate it to working c++ by spamming enter and tab. Step 1: Paste in your preferred template, and write an outline in pseudocode ------------------ For example, here is an outline I wrote for [this problem](https://codeforces.me/gym/103118/problem/M) <br> I prefer to write my solutions as functions, with input data passed in as parameters, because I use a different technique for the input code, so I want it separ...

Full text and comments »

Translation of the article by ko_osaga on Kinetic Segment Tree. I hear a lot about this topic but could not find any resources in Russian or English, so I decided to translate an article by [user:ko_osaga,2024-06-13]. This translation may contain many inaccuracies, and it lacks the links available in the original article. This article presents a new segment tree, called the Kinetic Segment Tree. An element is considered Kinetic if it moves over time, i.e., if the element represents a linear or polynomial function. Segment trees are often found in competitions, as are Kinetic elements (e.g., the convex hull trick), so studying their combination can also be useful. It is also worth noting that Kinetic properties can be identified even in problems not directly related to Kinetic elements (e.g., using CHT in DP optimization), and consider how the Kinetic Segment Tree can be applied. This data structure has already been mentioned in articles on Codeforces, but I recently found time for a more thorough study. At the time of writing, the Kinetic ...

Full text and comments »

Rectangle Shrinking: A range-set based method, and an advertisement for CFStress! Problem: [Rectangle Shrinking](https://codeforces.me/problemset/problem/1782/e) Part 1: **Notations** $x$: A brick. $x_i$ denotes the part of $x$ belonging to the $i$-th floor. For example, if $x.u=1,\,x.d=2$, then $x_1.u=x_1.d=1$, $x_2.u=x_2.d=2$, and $x_1.l=x_2.l=x.l$, $x_1.r=x_2.r=x.r$. $A_i,\,i=1,2$: The set of bricks whose $u=d=i$. $B$: The set of bricks whose $u=1,\,d=2$. $\texttt{Remove}$: Remove a brick $x$. $\texttt{Shrink}$: Shrink a brick $x$ to another **non-empty** brick. $\texttt{Keep}$: Keep a brick $x$ unchanged. Note that in our solution we may operate on a part of brick. For example, for a brick $x \in B$, we may $\texttt{Keep}\,x_1$ while $\texttt{Remove}\,x_2$. Part 2: **Idea** $\texttt{Shrink}$ing $x \in B$ is troublesome. If you shrink $x_1$, you have to shrink $x_2$ in the same way, i.e., $x_1$ has to be aligned with $x_2$. So is there a solution that only performs $\texttt{Remove}$ and $\texttt{Keep}$ on every $x \in B$? But that i...

Full text and comments »

Making the shortest distance between two given nodes a certain number by modifying edge-weights In yesterday's [LeetCode Weekly Contest 346](https://leetcode.com/contest/weekly-contest-346/), nearly no contestant solved the 4th problem successfully. Here is the problem, [Modify Graph Edge Weights](https://leetcode.com/problems/modify-graph-edge-weights/description/): Given an **undirected, weighted, connected** graph with `n` nodes ($1 <= n <= 100$) and `m` edges ($1 <= m <= \frac{n(n + 1)}{2}$). All edges have weight in $[1, 10^{7}]$, but some have weight $-1$, denoting that **you are to assign that edge some positive weight in** $[1, 2 * 10^{9}]$. Now, you are also given two nodes `source` and `destination`, as well as a positive integer `target` ($1 <= target <= 10^{9}$). **Find ANY assignment of edge weights that make the shortest distance from `source` to `destination` exactly `target`**, or report that there is no such assignment. **My own idea:** - Firstly, if the shortest distance from `source` to `destination` is less than `target` without considering any cus...

Full text and comments »

Non-bipartite matchings, (in)correct algorithm Hello everyone! I thought that maybe someone on Codeforces can help me find an error or build a counterexample. If you remember matchings in non-bipartite graphs, then the problem with Kuhn's algorithm is as follows: we need to find an augmenting path, but we can arrive at the desired vertex via an edge of the wrong type, mark it as visited, and leave. 1. First attempt to solve the problem: do a dfs on vertices of the form `(v, flag)`, where `flag` is the type of edge we arrived by. Obviously, this doesn't work: we can go through both `(v, false)` and `(v, true)` because they are different vertices, but then our augmenting path in the original graph is not simple, and we haven't actually found an augmenting path. 2. Second attempt to solve the problem: do the same thing as before, but explicitly forbid dfs to go to vertices that have already been visited (are on the path from the start to the current vertex), even if they were visited with a different flag. Something like this...

Full text and comments »

Problem E-Routing in the Nebius Round: Devil is in the details According to [clist.by](https://clist.by/problems/), the estimated rating of [problem E-Routing](https://codeforces.me/contest/1804/problem/E) is about 2500. I don't think this problem requires a very clever mind, but it contains a lot of evil details that might hinder you from solving it. You might ask me any questions about this problem. [Submission](https://codeforces.me/contest/1804/submission/197357246) is given in the bottom. **Evil detail 1**: You should pay attention to the memory limit. Many people tend to put lots of emphasis on time limit but ignore the memory limit. In this problem, the memory limit is a little bit tight. You will get MLE if you use a large array (e.g., `int dp[1<<20][20][20]`). Key idea: use a bitset. For example, `std::bitset` or a dynamic bitset. You might use the dynamic bitset in my submission. `std::bitset` is static because its size is given by the template parameter during the compiling period. In this problem, both static and dynamic bitsets a...

Full text and comments »

On finding geometric median with ternary searches Hello community! Please consider the following two problems. Given $N$ points on 2D plane, we need to calculate: A) Coordinates of a new point such that the sum of Euclidean distances from that point to all of given points is minimal ([Geometric median finding problem](https://en.wikipedia.org/wiki/Geometric_median)); B) The index of one of initial points such that the sum of Euclidean distances from that point to all other given points is minimal ([Medoid finding problem](https://en.wikipedia.org/wiki/Medoid)). My first hypothesis claims that problem (A) could be solved in $O(N\log^2(C))$ time (and $C$ is the absolute value of the maximal coordinate of point) with two nested ternary searches. It is so because of Euclidean distance between given point and some other point is a convex function, and the sum of convex functions is still a convex function, so we can find the global extremum point with ternary search. I believe I saw that idea a time or two as a suggested so...

Full text and comments »

Trouble with a variant of 2014F: Sheriff's Defence This problem was the first time I encountered a problem of DP on trees, and even with a decent amount of practice in DP, the states similar to that of "maximim score in the subtree of j considering j is taken or not", did not occur to me during the contest probably because such a state breaks quite easily when the coins are taken from let's say all the neighbours at a distance of <= 2. This is the best I could come up with for the above variation: <spoiler summary="given a tree and it's node values, you can pick a node but all it's neighbours upto a distance of 2 gets subtracted by c, find max sum of node values you can achieve "> ``` #include <bits/stdc++.h> using namespace std; using i64 = long long; void solve() { int n, c; cin >> n >> c; vector<vector<int>> adj (n); vector<int> a (n); for (int i = 0; i < n; ++i) cin >> a[i]; for (int i = 0; i < n - 1; ++i) { int u, v; cin >> u >> v; --u, --v; adj[u].push_back(v); ...

Full text and comments »

What is the scope of the Sprague-Grundy theorem? As I understand it, the Sprague-Grundy theorem states that, under the operation of combining games in parallel, every impartial game can be reduced to a game of Nim. I see that the definition itself specifies this parallel combination operator explicitly: two impartial games G and G' are assigned the same nimber iff for all games H, G + H and G' + H have the same outcome (here, + denotes the parallel combination operator)---this definition is from [Wikipedia](https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem#Equivalence). However, what about other methods of combining games? For instance, we combine two games A and B such that they are still played in parallel, but as soon as a player has no moves left in A, they instantly lose, regardless of the position of B. In general, can we still treat games A and B as their corresponding nimbers? If so, why? If not, what's a counterexample? EDIT (which I added in a comment below): More precisely, my question is: Let $n(G)...

Full text and comments »

Alternate Implementation of Li Chao Tree? I recently found an implementation of Li Chao tree [in this ICPC notebook](https://github.com/imeplusplus/icpc-notebook/blob/master/data-structures/ita_lichao.cpp), and it is quite different than the implementations I have seen before. Usually, I see the `insert_line` method implemented in a way similar to that described [in this cp-algorithms.com article](https://cp-algorithms.com/geometry/convex_hull_trick.html#li-chao-tree), where you recur either on the left child or the right child depending on if the new line is above or below the current line at the midpoint of the interval. However in this implementation, they recur on **both** the left and the right child, but they stop recurring once the new line is completely below or completely above the current line in that node. Does this implementation still handle inserting lines in $O(\log n)$ time in the worst case? I tried using this implementation [on the Frog 3 problem on AtCoder](https://atcoder.jp/contests/dp/submissions/33645...

Full text and comments »

Java and Python's sort is buggy See here: - http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/ - https://github.com/abstools/java-timsort-bug The bug is also present in CF's Java 7 (I didn't test Java 8 or Python). However, it seems that this cannot be used to hack Java or Python solutions, because the minimum size of a counterexample is 67108864 (67 million), too much to give in input. I guess that's a good thing -- imagine the mess this would create!

Full text and comments »

Can anyone help me with the time complexity of this? | Greedy Ascent So, I was solving leetcode 1901 i.e. Find a Peak Element II. Here's the link to the problem:[leetcode 1901](https://leetcode.com/problems/find-a-peak-element-ii/) I wrote a code which follows this approach: 1. Start from the top-left cell (0, 0). 2. Check its four neighbors (up, down, left, right). 3. If the current cell is greater than all valid neighbors, we've found a peak. 4. Otherwise, move to the largest neighboring cell. 5. Repeat until a peak is reached. The code I wrote was this: ``` class Solution { public: vector<int> findPeakGrid(vector<vector<int>>& mat) { int n = mat.size(); int m = mat[0].size(); int i = 0, j = 0; int dx[] = {-1, 0, 1, 0}; int dy[] = {0, 1, 0, -1}; while (true) { int ni = i; int nj = j; for (int k = 0; k < 4; k++) { int x = i + dx[k]; int y = j + dy[k]; if (x >= 0 && x...

Full text and comments »

CEOI — 2015 day1 prob1 — Potemkin Cycle UPDATE : THE CODE IS AC NOW, THERE WAS SOME MISTAKES IN IMPLEMENTATION. [AC code](https://oj.uz/submission/115896) Hi, I have been trying [this](https://oj.uz/problem/view/CEOI15_indcyc) problem, and I have an alternate solution to the editorial as follows: Form a new graph, with nodes as (prevNode, currNode), to keep track of which node we are coming from. There will be an edge from (A,B) to (B,C) in the new graph if A-B-C is not a 3-cycle in the original graph. Now, after forming this graph, find a cycle in it. This will correspond to a cycle in my orginal graph too. Now i claim that in this cycle of my original graph, there will be no 3 consecutive nodes that form a 3-cycle, due to the constraint of edge on my new graph. So the cross edges that we will have will divide my cycle into sectors with more than 3 nodes. Hence outputting any such sector should be fine. However, I am getting WA on most of my cases. The code is printing "no", which i found was that it was indeed...

Full text and comments »

Resources on SPFA Hi! I'd like to do ask the wise men of Codeforces if they know any resources related to SPFA (Shortest Path Finding Algorithm). The short description of the algorithm can be found in [user:Princeofpersia,2020-04-02]'s blog:  According to [this comment](http://codeforces.me/blog/entry/16221?#comment-211370) by [user:romanandreev,2020-04-02] it works on average in $O(m log n)$, but there are counterexamples. Is anyone aware of any papers trying to tackle SPFA complexity?

Full text and comments »

CPIDE — free online compiler and judge for competitive programming Hi everyone, I got tired of constantly switching between my editor, terminal, and `input.txt` while practicing competitive programming, so I built a small web judge for myself and decided to make it public: **https://cpide.me** CPIDE is a free in-browser competitive programming IDE and judge. Features - Monaco Editor (the same editor used by VS Code) with themes, font ligatures, and optional Vim keybindings - Compile and run with Ctrl + R - AC / WA / TLE / RE / CE verdicts with runtime and peak memory per test - Codeforces-style output comparison (trailing whitespace ignored) - Wrong Answer shows the first difference, plus a full side-by-side diff of expected vs. your output - Multiple test cases, separate code and tests for every problem - Multiple files per problem — keep a helper header or brute.cpp next to your solution; the open tab is what runs - Code formatter (Shift+Alt+F, or format-on-save) - Built-in snippets (DSU, Fenwick, Dijkstra, sieve, binary exponenti...

Full text and comments »

Baltic BOI 2017 #1: Political Development Hi all :') I've recently solved 2017 Baltic BOI Day 1 #1 Political Development ([D here](http://www.boi2017.org/wp-content/uploads/2017/05/tasks-en.pdf) The algorithm to find the max clique here is as follows: ~~~~~ while (graph not empty): pick any vertex with min degree if the vertex and some subset of neighbors of it form a clique, check if it's larger than the ones we found so far remove the vertex ~~~~~ But I propose an alternate solution to finding max clique: ~~~~~ while (graph not empty): pick any vertex with min degree if the vertex and all neighbors of it form a clique, check if it's larger than the ones we found so far remove the vertex ~~~~~ I *know* it's wrong (because it's a polynomial time), but every time I try to find a counterexample, I can never do so. Can someone provide a counterexample for my 2nd algorithm to the max clique problem (or prove it, then we have P=NP!) Thanks, minimario

Full text and comments »

Is my construction for this problem correct? Any counterexample? Body: I am solving this problem:[problem:1474B] We need to find the smallest integer a such that: a has at least 4 divisors the difference between any two divisors of a is at least d My idea is to construct a as: a = p⋅q where: p is the smallest prime such that p≥d+1 q is the smallest prime such that q≥p+d Then I output a=p⋅q. [submission:373450651] This works for all samples I tested, but I am not fully sure about correctness for all d. Can someone confirm if this construction is always optimal, or provide a counterexample if it fails?

Full text and comments »

Problems that I authored so far Since competitive programming is dying, and I'm almost retired, so it's time to review the problems I authored. Hi everyone! I wanted to write such a blog for a long time, motivated by similar blogs, [by](https://codeforces.me/blog/entry/113093) [user:antontrygubO_o,2023-02-25], [by](https://codeforces.me/blog/entry/108940) [user:adamant,2023-02-25] and [by](https://codeforces.me/blog/entry/108595) [user:tibinyte,2023-02-25]. This is not a super-comprehensive list. I set many shit problems that I don't want to share for some local contests. It can be long, and I'm not sure if I have finished half of them yet. The number of asterisks after the label indicates the recommendation levels. One asterisk means this problem is worth reading. Two asterisks mean this problem is one of my favorite problems, Three asterisks mean this problem is one of my best problems. | # | Date | Problem | Contest | Comment | | ---- | ----------- | --------------------------------------------...

Full text and comments »

Need help with a problem This problem has been bugging me since morning today. I have a number K, and an array A with N elements. I can merge any amount of numbers in the array such that each element in the end is at least K. I want to merge minimum number of elements to achieve this, or in other words the final array should have maximum size. Let's say $K = 6$ and $A = [4, 4, 5, 5, 6, 7, 9]$ (here size = $N = 7$) I have this proposed solution which I have not been able to prove/disprove with several random outputs. The solution is: consider the subset of A containing all the elements which are less than K, which for this A is $A' = [4, 4, 5, 5]$, (size = $N' = 4$), my solution is: $$\text{maximum size} = N - N' + \min\left( \frac{N'}{2}, \frac{\sum A'[i]}{K} \right) $$ For the given example, max length = 3 + min(2, 3) = 5, which corresponds to 9, 9, 6, 7, 9 after merging the 4s and 5s. If anyone can help me give a counterexample or help me prove the solution, please do so.

Full text and comments »

How many digits are there in a number in certain base? Why the logarithmic formula doesn't work here? How many digits are there in a number n in a base b? There is a well-known theorem for that. You know it's floor(logb(n))+1. We calculate it as floor(log10(n)/log10(b))+1 as you can find it through the basics of the logarithm. As you see it's a well-known formula and obviously your logic will say it must work for every number. Why? The floor of the logarithm of a number n is actually largest power of b which is not greater than n. So if we want to calculate the number of digits in the binary representation of a n, it should be floor(log2(n))+1. Using this, I calculate the length of the binary representation of a number for a long time. But today I encountered some counterexample of this. I solved the problem [problem:1362C]. My first submission ([submission:82557478])got WA in the last case(case 21) during the system test. I just counted the length of the binary representation and then did some work there. The value of n was 576460752303423485. Here the logarithmic ...

Full text and comments »

Need help with proving greedy 1400 https://codeforces.me/contest/2033/problem/C I tried to solve this problem and didn't come up with anything good, except a huge non-working solution. I looked at Editorial &mdash; I still didn't understand. I went to ask ChatGPT &mdash; I still didn't understand, it was written too briefly. I spent 5 hours and only came to an "intuitive" understanding, where I agree with the facts because I can't find a counterexample, but not because it has been proven that the opposite does not exist. Please help me prove this greedy. I can't come to terms with it until I fully understand it :(

Full text and comments »

Competitive Programmes's Handbook problem In Chapter DP from permutations to subsets, there is a problem about elevators. There is an elevator with maximum weight x, and n people with known weights who want to get from the ground floor to the top floor. What is the minimum number of rides needed if the people enter the elevator in an optimal order? I found one solution, it is to find the subset of people with maximum weight we can send every time and send those elements. I think it's time complexity works for n <= 20. It seems incorrect but I couldn't find any counterexample. Is there any counterexample?

Full text and comments »

Bound on the number of different sums of consecutive elements in an arbitrary array Today, I tried [F2. Same Sum Blocks (Hard) from Codeforces Round #547 (Div. 3)](https://codeforces.me/problemset/problem/1141/F2). Since $n$ can be as large as $1500$, I was struggling to come up with an $O(n^2)$ but I failed. When I read the editorial, surprisingly, I found out that the writer's solution is $O(n^3)$. They used a `Hashmap` to speedup the whole process, and it seems that the number of different summation values of consecutive elements will be less than $n^2$. Though I cannot find any counterexample such that different sub-array sums can be as large as $n^2$ (or at least as large as $\frac{n \times (n - 1)}{2}$), I cannot convince myself an $O(n^3)$ approach can pass the system test. I was wondering if you have any analysis to demonstrate that the optimization (using `Hashmap`) is sufficient, or if you know any bound on the number of different summation of consecutive elements in an arbitrary array.

Full text and comments »

Round #269, Problem C Hi this is about problem http://codeforces.me/contest/471/problem/C In the tutorial it shows that (N+F)%3==0 is needed for a house with F floors to be valid. But I don't understand how this condition is enough for the requirement that "each floor has fewer rooms than the floor below it". I mean, suppose we have make F=3 floors from 6 rooms. Then those floors can be arranged as having 3,2,1 rooms, which meet the requirement. But we could wrongly arrange the house as having 2,2,2 rooms as well. In both cases (N+F)%3==0. In this example it doesn't matter. But how do we know in some case we would not be counting a wrong configuration of floors? Of course I cannot come up with a counterexample, I'm sure the tutorial is correct, but I just don't understand how "divisible by 3" also implies "decreasing rooms on each floor". Thanks!

Full text and comments »

AC with a “suspicious” DP — looking for counterexamples / hacks Codeforces Round 1077 (Div. 2)——D. Shortest Statement Ever Because I do not find a dp solution, so I write one by myself, and it gets AC verdict. [submission:360662700] However, I feel a little strange about my solution, because I think there are some flaws, but I cannot find counterexamples. So, please help me review my code and solution. I'm glad about my solution to be hacked.

Full text and comments »

What is wrong with my solution? Hello CF community, I am stuck on problem ([Cost of the Array](https://codeforces.me/contest/2059/problem/B)). My solution is getting wrong answer on test case 2 and I am not sure why. My submission : [304400545](https://codeforces.me/contest/2059/submission/304400545) Any counterexample for the above solution? Thanks.

Full text and comments »

 Where is the mistake???  ### Hi guys!! Again, really need your help !!! I am solving this puzzle: http://i056.radikal.ru/1509/4e/391ff8e79aec.png Here is an example: ~~~~~ Sample Input 1 3 1 3 4 3 6 7 6 3 4 6 7 6 Sample Output 16 ~~~~~ Here's my solution: http://pastebin.ubuntu.com/12589123/ but it is wrong ((((( Help pozhalusta find counterexamples, the atoms in a rocking chair, I'm late but want solve ((((((

Full text and comments »

UPDATED:Wondering another conclusion to CF2229D Now I'm wondering if the sufficient&necessary constraint for min(a1,b1)=1 is that, the number of (1,1) pairs is greater than the number of (0,0) pairs. It seems to be right...? Still, any counterexamples? QwQ Thanks.

Full text and comments »

Codeforces Round #839 - Problem G - Gaining Rating My solution gets a wrong answer verdict, but I can't think of a counterexample. Here's my solution &mdash; https://codeforces.me/contest/1772/submission/190133399. I have used 0-indexing, and have set the extra last element of the input to +inf in order to avoid bounds checking. Can anyone give me a counterexample?

Full text and comments »

How to prove the time complexity of splay tree? Hi guys,<br> I have learn splay tree for a while and read a lot of tutorial and I found that different tutorial have different explanation but the strange thing is they have the same proof about the time complexity of splay operation.<br> When i see the proof,there is always one sentence **"First let us use the potential method,then let potential function be log(size(n))"** but why?<br> Is that related to the observation?Some of the math theorem happen same thing,through the result we already observe that the theorem is correct but haven't prove it then the problem become how to prove a theorem which is already correct(or at least can't found a counterexample) then there will be a lot of not logic operation just for prove the theorem.Does the splay tree happen same condition?<br> Thank for you reading,if you know the answer please teach me.

Full text and comments »

How come this solution works? [CSES Cyclic Array] https://cses.fi/problemset/task/1191 https://github.com/Jonathan-Uy/CSES-Solutions/blob/main/Additional%20Problems/Cyclic%20Array.cpp This solution does make intuitive sense but I'm also struggling to figure out how it's literally true for every single case. It really feels like there must exist some edge case/counterexample for it.

Full text and comments »

Is Levenshtein distance related to largest common subsequence? I don't have proof but i have gut feeling that , suppose s1 is string which needs to be converted to s2 then we can keep the largest common subsequence in s1 as it is and edit distance is number of elements we need to replace/remove/insert. ``` For example : s1 = "adjsjvnejnv" s2 = "djpppne" ``` Here LCS is "djne" , now we need to remove 3 element string "jnv" at right side of "djne" ,we can replace "sjv" with "ppp" in s1 and and we can delete "a" from s1. so total edit distance is 3+3+1 = 7 . Idea is to replace or delete elements inbetween the elements of LCS and add or remove elements from right and left part of LCS . I am not able to prove it . Can someone provide counterexample or proof ?

Full text and comments »

Interesting Matrix problem **You have $nXn$ matrix filled with numbers,you have to pick $n$ numbers from it such that their sum is maximal and no $2$ are in same column or row.** My guesses after 20 mins: I tried greedy algorithm,sorting each row and memorizing column of each number in new sorted matrix and now I would take largest in each row and if $2$ are in same column I would pick larger and move pointer for row of lower one to next largest number,but no can do,found counterexample,we can pick lower one if number behind greater number is much larger then number behind lower number...

Full text and comments »