Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

 
 
 
 

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

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

Results

 
 
 
 
1.
By DrSwad, history, 2 years ago, In English
A Beautiful Technique for Some XOR Related Problems ## Inspiration I'm very excited about this blog, as it took me quite a lot of effort and scavenging through the internet to completely grasp the concept of this technique(That's probably because I have almost zero knowledge in Linear Algebra or I'm just plain dumb). So I feel like I genuinely conquered a challenge, and I really want to share it with someone. But there's no way my CP friends circle will believe it, they'll think I'm just trying to show off :P So here I am, sharing it on CF. I also created a [personal blog](https://drschwad.github.io/), so that if I ever feel like sharing something again(not only about CP), I can write a blog there. I also added this same post [there](https://drschwad.github.io/2019-08-06-z2-space-xor-trick/), you can read it there if you prefer dark theme. I'll be pleased to hear any thoughts on the blog or if I can improve it in some way ^\_^ ## Introduction Since it concerns Linear Algebra, there needs to be a lot of formal stuff going on ...
A Beautiful Technique for Some XOR Related Problems, [there](https://drschwad.github.io/2019-08-06-z2-space-xor-trick/), you can read it there if you prefer dark, get a different possible xor of some subset. So, the answer would be $2^\text{size of basis, this purpose, we use property $1$ to slightly modify any new vectors before inserting it in the basis

Read more »

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

 
 
 
 
2.
By parveen1981, history, 5 months ago, In English
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...
) - [XOR Hashing [TUTORIAL]](https://codeforces.com/blog/entry/85900) - [[Tutorial] Easy

Read more »

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

 
 
 
 
3.
By turzo_sawroop, history, 7 weeks ago, In English
Every Possible Bitwise Equations we could Make After recently concluded hacker cup qualification round I thought I would take a little rest from problem solving.But as I have some geniuses like [user:srlabib,2021-08-31] around me I couldn't resist myself from thinking about some **Bitwise** **Equations!!!** Most of the part is done by [user:srlabib,2021-08-31] and I also contributed some from my side ( Especially the last one ) : - a+b = a|b + a&b Now this is a very basic thing.This was a very crucial part in the last contests's problem D ( Take a Guess ).But how did we get this? Suppose we have two binary numbers 1010 and 0101, there is no chance of any carry in binary addition.In that case we can write : a+b =a|b But when we have carry, suppose we have : 1101(a) and 0101(b) then a & b works as the carry which we add further and the equation turns into : a+b=a|b + a&b Now I will talk about the sum-xor property : - a+b=a⊕b+2(a&b) Well where does it come from? It comes from the first equation that ...
further and the equation turns into : a+b=a|b + a&b Now I will talk about the sum-xor, Now I will talk about the sum-xor property :

Read more »

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

 
 
 
 
4.
By JaySharma1048576, 3 months ago, In English
Codeforces Round #730 (Div. 2) Editorial #### [A: Exciting Bets](https://codeforces.com/contest/1543/problem/A) <spoiler summary="Hint 1"> $GCD(a,b)=GCD(a-b,b)$ if $a>b$ </spoiler> <spoiler summary="Hint 2"> $a-b$ does not change by applying any operation. However, $b$ can be changed arbitrarily. </spoiler> <spoiler summary="Tutorial"> If $a=b$, the fans can get an infinite amount of excitement, and we can achieve this by applying the first operation infinite times. Otherwise, the maximum excitement the fans can get is $g=\lvert a-b\rvert$ and the minimum number of moves required to achieve it is $min(a\bmod g,g-a\bmod g)$. <spoiler summary="Proof"> Without loss of generality, assume $a>b$ otherwise we can swap $a$ and $b$. We know that $GCD(a,b) = GCD(a-b,b)$. Notice that no matter how many times we apply any operation, the value of $a-b$ does not change. We can arbitrarily change the value of $b$ to a multiple of $a-b$ by applying the operations. In this way, we can achieve a $GCD$ equal to $a-b$. Now, ...
The generalised $k$-itwise XOR does not satisfy the Self-Inverse, Try to use the self-inverse property of Bitwise XOR, i.e.

Read more »

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

 
 
 
 
5.
By ItsNear, history, 3 years ago, In English
Are we close to machines solving ICPC problems? Hi, all, I with few other folks at [NEAR](http://near.ai/blog) work on teaching machines to program. A particularly exciting sub-project of that is teaching machines to solve competitive programming problems. In this post I would like to give a quick overview of where the state of the art is today, what the major challenges are, why this is not a popular area of research, and how the CodeForces community can help to address some of the issues the program synthesis community is facing today. We also have a certain budged allocated for this project, and we are paying to the CodeForces members who help us with some data annotation challenges. We have paid more than $10k in our first two annotation projects, and are launching three more projects today. Scroll to the end if you are interested. Competitive programming as a benchmark ====================================== With the emergence of deep learning, neural networks started performing almost at a human level in many ta...
collected, only few had used that particular property of XOR in a similar way, and only a few dozen, no external knowledge (such as properties of XOR or triangles) is needed to write the solution given, Out of 50k problems that we have collected, only few had used that particular property of XOR

Read more »

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

 
 
 
 
6.
By ATSTNG, history, 2 years ago, In English
[Tutorial] Matroid intersection in simple words **[This article is also available in [Russian](https://codeforces.com/blog/entry/69287?locale=ru)]** Hello, CodeForces. I think that matroids are beautiful and powerful concept, however, not really well known in competitive programming. I’ve discovered matroids at 2019 Petrozavodsk Winter Training Camp. There was a problem that clearly cannot be solved using usual techniques I knew, editorial for this problem was just these three words “just matroid intersection”. Back then it took me more than 2 days of upsolving to find all the information and details I need and implement solution that gets Accepted on this. And it took way longer to actually understand why does it work and exactly how does it work. (I still hesitate in some details.) Of course, it is not hard to google up all the definitions and some related articles, but in my opinion they all are focused more on mathematical part of theory, strict proofs in some not really obvious but short ways, and observing only ke...
basis by third axiomatic property). Directly from previous, no basis is a subset of other basis. Any

Read more »

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

 
 
 
 
7.
By YoyOyoYOy000y000, history, 20 months ago, In English
Centroid Decomposition on a tree(Beginner) ## When Centroid Decomposition comes? 1. Suppose a problem says that how many paths have a length exactly k in a tree. 2. Or, how many paths have xor k. 3. Sum of all xor path in a tree. 4. update a node Black to white or white to black. now query the shortest path from a node to a white node. etc. **So, it is clear, when a paths problem comes then we can use Centroid Decomposition.** **For a single node query or from a specific node, DSU on Tree may do it.** ## Algorithm: ### 1. Find a centroid of current tree T. `What is Centroid? ` Simply Centroid is a node if we delete it. It makes some subtrees where every subtree size must be less than **sz/2** { sz is the size of the current tree T.} `How can we find it?` => Take a node random node of current tree T. Now if it's every subtree size less than sz/2. Then it is a centroid. => If not, go to the highest size of the subtree. **Note: In a tree only two Centroid possible F...
total complexity **NlogN** . 2. Any path property like distance/xor/sum/etc. we can compute

Read more »

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

 
 
 
 
8.
By kazama460, 5 months ago, In English
(almost) Every Algorithms & Data Structures you needed to learn , with practice problems Hello guys this is <a href="https://www.youtube.com/channel/UC0zvY3yIBQTrSutsV-4yscQ?view_as=subscriber"> CodeNCode </a> and as you guys know I have been working for more than 3 years on Data Structures and algorithms courses. So I thought let's compile it to one place and share so it can be helpful to everyone. <h3>List of Courses</h3> <div class="spoiler"> <b class="spoiler-title"><h5> Basic Algorithms </h5></b> <div class="spoiler-content" style="display: none;"> <ul> <li><a href="https://www.youtube.com/watch?v=NoDYJ7Ks_M0">L01 : Why you should learn binary search</a></li> <li><a href="https://www.youtube.com/watch?v=3vMpagKkqrc">L02 : Understanding Core of Binary Search</a></li> <li><a href="https://www.youtube.com/watch?v=-IMyOkNLRoY">L03 : Monk's encounter with polynomial (HackerEarth)</a></li> <li><a href="https://www.youtube.com/watch?v=FJXZ4Zt8SOk">Ternary String (Codeforces)</a></li> ...
) * L04 : XOR and its <https://www.youtube.com/watch?v=0n5p8o-smKE>, ://www.youtube.com/watch?v=0n5p8o-smKE">L04 : XOR and its properties *

Read more »

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

 
 
 
 
9.
By Shisuko, history, 3 years ago, In English
The Intuition Behind NIM and Grundy Numbers in Combinatorial Game Theory There are already many wonderful resources online for learning the basics to combinatorial game theory, but the intention I have for _this_ guide in particular is to try to make them more intuitive. Why does XOR work for Nim? Why does mex produce the Grundy numbers? When it was taught to me, it was more or less just as 'magic' to memorize, but now I think I have a decent understanding of why they are true, so now that I have a grasp of the intuition behind it, I decided I should record my thoughts into a blog. Nim games ================== Suppose we are playing a Nim game. As we know, Nim games usually follow this sort of template: - There are $n$ piles of stones, and each pile contains $p_1, p_2, p_3, \cdots p_n$ stones, where each of the $p_i$ is some nonnegative integer. This collection of piles defines our game state. - There are two players who take turns removing stones. The current turn player may remove as many stones as they wish, so long as all the stones come f...
integers! In fact, take a look at that last property in particular, that $A \oplus A = 0$. The inverse, the XOR came from (the self-inverse property) and where the Grundy numbers being mex came from (mex, I hope this guide helped you understand where the XOR came from (the self-inverseproperty

Read more »

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

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

Read more »

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

 
 
 
 
11.
By nubir345, 12 months ago, In English
Tricks that I learnt while practicing ### This blog is for personal use. You can check it out if you want. #### As many people are checking out this blog, I thought of adding problems for some of the tricks. Tricks ================== 1. Sum-Xor property: $ a+b = a \oplus b + 2(a\And b) $. Extended Version with two equations: $a+b=a\vert b + a\And b$ <b>AND</b> $a \oplus b = a\vert b - a\And b$ [Problem 1](https://atcoder.jp/contests/abc050/tasks/arc066_b) [Problem 2](https://codeforces.com/problemset/problem/1325/D) 2. Upto $10^{12}$ there can be atmost $300$ non-prime numbers between any two consecutive prime numbers. 3. Any even number greater than $2$ can be split into two prime numbers. [Problem1](https://codeforces.com/contest/735/problem/D) [Problem 2](https://atcoder.jp/contests/arc080/tasks/arc080_d) 4. Sometimes it is better to write a brute force / linear search solution because its overall complexity can be less. [Problem 1](https://codeforces.com/contest/1267/problem/J) 5. When $A \leq B$ then $\lfloor...
================== 1. Sum-Xor property: $ a+b = a \oplus b + 2(a\And b) $. Extended Version with two equations: $a+b

Read more »

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

 
 
 
 
12.
By sirknightingfail, history, 3 years ago, In English
A blog on the Sprague-Grundy Theorem So, I ended up making a talk on Sprague-Grundy as part of a club at my school, and thought that the denizens of codeforces would appreciate it. As follows is roughly what was on the handout, which goes over Sprague-Grundy along with the application of its theory to Nim. As this is my first blog post on Codeforces, please do let me know if there are any mistakes in formatting. I hope you find this interesting, as writing and explaining this helped me understand how to apply it to problems. This handout was written as more math-oriented, so it may be a bit heavy. The exercises are left unsolved, as they are intended to be worked through by the reader. If you just want to get to what the Sprague-Grundy is defined as, search for "The Sprague-Grundy function of a game" after reading how games were defined. Way too much theory ============================= A necessary definition of games ------------------------------- For this talk, a game will be a two-player sequential game o...
can get really large for relatively simple games. Definition of XOR ----------------- Some more, , but it can be proven inductively on the value of $\mathbb{MT}(S)$ from the property of the MEX function, Definition of XOR ----------------- Some more definitions need to be examined before we can get

Read more »

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

 
 
 
 
13.
By ccbestgirl, 16 months ago, In English
How to solve XOR related problems? Is there some trick? Because I feel like its trial and error. I saw one question where they asked us to find the missing number in the range of 1 to n, I had no idea how to do it with xor. The solution was to first find the xor of all elements from 1 to n, then the xor of the elements that we were given and then the xor of these both. How to come to this solution? Because I feel like this solution was found by trial and error. I don't even get how to approach these problems. What do I need to know before solving such problems? Is there some property that I don't know?
How to solve XOR related problems?, us to find the missing number in the range of 1 to n, I had no idea how to do it withxor, ? Is there some property that I don't know?

Read more »

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

 
 
 
 
14.
By sdssudhu, history, 4 years ago, In English
An alternative trick to solve many HLD problems using basic dfs I use this post to try and explain an alternative to HLD that I have been using for more than a couple of months. As many of you might be familiar HLD is a very tough thing to implement and is time-taking and must be implemented carefully. Also if HLD sums are asked in short contests then it is going to be difficult to implement. Hence I came up with this technique. I will try and explain this concept with the [july long contest problem](https://www.codechef.com/JULY17/problems/PSHTTR). In this problem the value of number of nodes is given to be 10^5 which means maximum depth of the tree is 10^5 (worst case). What I do is I perform a dfs in the tree and for every node whose depth%1000=1, I store the values of all its ancestors. In worst case the memory complexity is (1000+2000+...10^5)= 1000(1+2+3+....+100) = 5*10^6. After this I sort all these values and take a prefix xor. Now for each query I have to travel up atmost 1000 ancestors and arrive at an ancestor whose ...
and V(source and destination). Because of the property of XOR all the values of the ancestors

Read more »

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

 
 
 
 
15.
By rishabhk965, history, 19 months ago, In English
Bit Manipulation TRICKS Bit manipulation is generally faster because CPU directly supports these operations. Some of the very common use case bit hacks: 1) Swapping two numbers: x = x ^ y y = x ^ y x = x ^ y How does it work? Because of XOR property y^(x^y) = x. and x^(x^y) = y. (be aware that it is not actually faster than the general extra variable swap, as it can’t achieve instruction parallelism.) 2) Find min(max) of two numbers(very efficient method): min = y ^ ((x^y) & -(x < y)) How it works? (lets assume x = 3 and y = 4, min should be x) First the last part: -(x < y), if x < y it becomes -(1). 2’s complement if of -1 is 1111(how? 1’s complement+1). If x > y it becomes -(0) => 0000. Second part: ((x^y) & 1111) `and`ing any number with all one return the same number, so (x^y) & 1111 => (x^y). Third and final part, y ^ (x^y) by xor property it should be equal to x. 3) Mod of sum of two numbers:(normal method for mod of n is (x+y) % n). z = x + y ...
^ y How does it work? Because of XOR property y^(x^y) = x. and x^(x^y) = y. (be aware, Because of XOR property y^(x^y) = x. and x^(x^y) = y. (be aware that it is not actually faster than, Third and final part, y ^ (x^y) by xor property it should be equal to x.

Read more »

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

 
 
 
 
16.
By Edvard, history, 5 years ago, translation, In English
Editorial of Educational Codeforces Round 14 ### [problem:691A] The problem was suggested and prepared by Arthur Jaworski [user:KingArthur,2016-07-18]. In this problem you should simply check the conditions from the problem statement. <spoiler summary="С++ solution"> ~~~~~ const int N = 1010; int n, a[N]; bool read() { if (!(cin >> n)) return false; forn(i, n) assert(cin >> a[i]); return true; } void solve() { int cnt = accumulate(a, a + n, 0); if (n == 1) puts(cnt == 1 ? "YES" : "NO"); else puts(cnt == n - 1 ? "YES" : "NO"); } ~~~~~ </spoiler> Complexity: $O(n)$. ### [problem:691B] The problem was suggested by Nikita Melnikov [user:nickmeller,2016-07-18]. In this problem you should simply find the symmetric letters by picture and also observe that the pairs $(b, d)$ and $(p, q)$ is the symmteric reflections. <spoiler summary="C++ solution"> ~~~~~ string s; bool read() { return !!getline(cin, s); } string symmetric = "AHIMOoTUVvWwXxY"; map<char, char> opposite = {{'...
Let $z_{ij}$ be the number of xor-sequences of length $i$ with the last element equal to $a_j, }$ be the number of xor-sequences of length $i$ with the last element equal to $a_j$. Let $g_{ij}$ be equal

Read more »

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

 
 
 
 
17.
By prophet_ov_darkness, 4 years ago, In English
[GYM] 2017 Bangladesh National High School Programming Contest ( National Round, Senior Group ), NHSPC 2017 Tutorial Tutorials are written by corresponding problem authors. I'm just assembling all those tutorials in one place. ### [problem:101353A] Problem Author: [user:raida_ash,2017-04-20], Tester: [user:khairat,2017-04-20] It is a simple ad-hoc problem. We can solve it in $\mathcal{O}(n)$. Simply iterate over all the bottles and add the amount of liquid spilled to the answer. <spoiler summary="Problem Author's Solution"> ~~~~~ #include <bits/stdc++.h> using namespace std; main() { //freopen("in1.txt","r",stdin); //freopen("out1.txt","w",stdout); int n,m,c[100005],t; long long int ans; scanf("%d",&t); while(t--) { ans = 0; scanf("%d %d",&n,&m); for (int i=0; i<n; i++) { scanf("%d",&c[i]); ans += ceil((double)((c[i]*1.0)/m))*m - c[i]; } printf("%lld\n",ans); } return 0; } ~~~~~ </spoiler> ### [problem:101353B] Problem Author: [user:tanzon0xA5,201...
a losing state. That means the first player wants to move such that the xor -sum becomes zero. Now, the first player wants to move such that the xor-sum becomes zero. Now note the properties of axor

Read more »

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

 
 
 
 
18.
By Alex_2oo8, 6 years ago, translation, In English
Editorial for CROC 2016 Finals and Codeforces Round #347 [problem:664A] -------------- Author of the idea &mdash; [user:GlebsHP,2016-04-17] We examine two cases: 1. $a = b$ &mdash; the segment consists of a single number, hence the answer is $a$. 2. $a < b$ &mdash; we have $gcd(a, a + 1, a + 2, \dots, b) = gcd(gcd(a, a + 1), a + 2, \dots, b) = gcd(1, a + 2, \dots, b) = 1$. <spoiler summary="Code"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { string a, b; cin >> a >> b; if (a == b) cout << a; else cout << 1; return 0; } ~~~~~ </spoiler> [problem:663A] -------------- Author of the idea &mdash; [user:gen,2016-04-17] First we check whether any solution exists at all. For that purpose, we calculate the number of positive (the first one and any other with the $+$ sign) and negative elements (with the $-$ sign) in the sum. Let them be $pos$ and $neg$, respectively. Then the minimum value of the sum that can be possibly obtained is equal to $min = (1\,\cdot\,pos -...
if and only if the $xor$-sum of all numbers is $0$. Therefore the problem essentially asks to calculate, After this procedure we get a set that contains $k$ zeros and $n - k$ numbers with theproperty

Read more »

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

 
 
 
 
19.
By usernameson, history, 5 years ago, In English
Function Range Trick #### Disclaimer I do not know if this technique has another name. I came up with it to solve specific types of problems but it probably has been done by many others before. #### The situation Assume we are given a sequence of numbers $a_{1},a_{2},\ldots,a_{n-1},a_{n}$ and we have a function $f$ that is well defined for all sequences of numbers with the property $f(b_{1},\ldots,b_{m}) = f(f(b_{1},\ldots,b_{m-1}),b_{m})$ for any sequence b and the range of $f$ has size $K$, which is relatively small. Our goal is to rearrange the numbers $a_{1},\ldots,a_{n}$ so that when the sequence is entered into $f$ in this order the value of $f$ is optimised (minimised or maximised). #### The solution If we try to brute force all permutations of the sequence there are $n!$ options which is usually too slow. However what we can do is use dynamic programming and for each sequence ending in $a_{j}$ with m terms store all possible values of f. Since we know the range of f is K at each step we ar...
0 and 255 inclusive. Next xor clearly satisfies the property required for $f$ given above, $ that is well defined for all sequences of numbers with the property $f(b_{1},\ldots,b_{m}) = f(f

Read more »

Tags dp, math
 
 
 
 
  • Vote: I like it
  • +39
  • Vote: I do not like it

 
 
 
 
20.
By emorgan5289, 10 months ago, In English
[Tutorial] Slight Generalization of Grundy Numbers **Prerequisites**: Grundy numbers (aka nimbers, I will refer to them as Grundy numbers), the connection of Grundy numbers to mex and bitwise xor. **Note about mex**: We know the the mex of a set of non-negative integers is the smallest non-negative integer which is not in the set. This definition works fine for any proper subset of $\mathbb{N}$, since $\text{mex}(S)=\min(\mathbb{N}\setminus S)$, and min is well-defined for any non-empty subset of $\mathbb{N}$. However, the minimum of an empty set is not well-defined, so neither is $\text{mex}(\mathbb{N})$, so we will define a new object $\omega=\text{mex}(\mathbb{N})$. Most of the properties of this object as it relates to mex are pretty straight-forward, for example <br><br> $$ \text{mex}(\mathbb{N}\cup\{\omega\}) = \omega+1 $$ $$ \text{mex}(\{a\omega+b\,|\,a,b\in\mathbb{N}\}) = \omega^2 $$ **Games with Finite States**: Given any finite impartial game (i.e. an impartial game which is guaranteed to terminate in a finite number o...
), the connection of Grundy numbers to mex and bitwise xor. **Note about mex**: We know the the mex of a set

Read more »

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

 
 
 
 
21.
By TheScrasse, history, 11 months ago, In English
Unofficial hints for Codeforces Round #682 (Div. 2) (A — D) As promised, here are some (nested) hints for Codeforces Round #682 (Div. 2). [problem:1438A] <spoiler summary="Hint 1"> Solve some small tests on paper. <spoiler summary="Hint 2"> Can you make the sum of each subarray equal to its length? </spoiler> </spoiler> [problem:1438B] <spoiler summary="Hint 1"> Suppose that the answer is `NO`. Which property should hold for the array $a$? <spoiler summary="Hint 2"> What happens if $l_1 = r_1$? <spoiler summary="Hint 3"> The answer is `YES` if there is a pair of equal elements in the array $b$. What happens if there are no equal elements? <spoiler summary="Hint 4"> Look at the binary representation of the sum of each subarray. Are there equal binary representations? </spoiler> </spoiler> </spoiler> </spoiler> [problem:1438C] <spoiler summary="Hint 1"> Solve on paper ~~~~~ 3 3 1 1 1 1 1 1 1 1 1 ~~~~~ <br> <spoiler summary="Hint 2"> Now solve ~~~~~ 3 3 2 1 1 1 1 2 2 1 2 ~~~~~...
] Suppose that the answer is `NO`. Which property should hold

Read more »

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

 
 
 
 
22.
By adamant, 5 years ago, translation, In English
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...
and answer queries of $\relax k^{th}$ largest subset xor: [link](http://ideone.com/LLtY4q

Read more »

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

 
 
 
 
23.
By galen_colin, 14 months ago, In English
Hybrid Tutorial #-1: Heavy-Light Decomposition **[Here](https://www.youtube.com/watch?v=_G_LMuLWMaI&list=PLDjGkpToBsYDx4GWu2u87sTqt6ICELz-T) is a playlist of all hybrid tutorials I've done.** # "Intro" _Timestamp: [00:00](https://youtu.be/_G_LMuLWMaI)_ Hi! Definitely not inspired by [this comment](https://codeforces.com/blog/entry/81086?#comment-675431), I've decided to try something that seems relatively novel &mdash; combining a blog and video tutorial into one, in a "hybrid" fashion. Both should be usable independently, but they will have the same "flow" and structure so you can reference both for concepts that are harder to grasp, and the two will supplement each other. The goal of these is to be **complete** &mdash; beneficial for both video and blog lovers, as well as full of enough information that anyone without much of an idea of what the concept is should be able to fully understand. There will be code as well, however, I very highly recommend not looking at it, but rather working out the implementation for yours...
tree problem with two types of queries: * Compute the XOR of values on the subarray from $l

Read more »

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

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

Read more »

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

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

Read more »

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

 
 
 
 
26.
By adamant, history, 4 months ago, In English
Subset convolution interpretation Hi everyone! Recently [user:aryanc403,2021-06-24] [brought up](https://codeforces.com/blog/entry/92128) a topic of subset convolution and some operations related to it. This inspired me to write this blog entry as existing explanations on how it works seemed unintuitive for me. I believe that having viable interpretations of how things work is of extreme importance as it greatly simplifies understanding and allows us to reproduce some results without lust learning them by heart. Also this approach **allows us to easily and intuitively generalize subset convolution** to sum over $i \cup j = k$ _and_ $|i \cap j|=l$, while in competitive programming we usually only do it for $|i \cap j|=0$. Enjoy the reading! <br> [cut] <br> Subset convolution $a \star b$ is defined as follows, let $a=(a_0, ..., a_{2^n-1})$ and $b=(b_0, ..., b_{2^n-1})$. Then \begin{equation} (a \star b)_k = \sum\limits_{i\subset k} a_i b_{k \setminus i} \end{equation} That is, $k$-th term of this con...
, let's take a step back and recall what we're doing in "or" and "xor" convolutions. For "or" convolution

Read more »

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

 
 
 
 
27.
By prudent, history, 3 years ago, In English
[SOLVED] Property between XorSum and Sum of segment Question is solved, please ignore this post ============================================ Why if **xor sum** of segment is equal to **sum** of segment, this condition is also satisfied for all **sub**segments of original segment? I know that it's true when all bits in numbers are unique, but is it the only case when it's true, and if it is, then why?
[SOLVED] Property between XorSum and Sum of segment, if **xor sum** of segment is equal to **sum** of segment, this condition is also satisfied for all, Why if **xor sum** of segment is equal to **sum** of segment, this condition is also satisfied

Read more »

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

 
 
 
 
28.
By gepardo, history, 4 years ago, In English
Sqrt-tree: answering queries in O(1) with O(NloglogN) preprocessing. Hello, Codeforces! Some time ago I invented an interesting data structure and I'd like to share it with the community. Maybe, it was known before, and if you knew about it before my blog post, please share the link to the source. # What can the data structure do? Given an array $a$ that contains $n$ elements and the operation $op$ that satisfies associative property: $(x\ op\ y) op\ z = x\ op (y\ op\ z)$ is true for every $x$, $y$ and $z$. So, such operations as $gcd$, $\min$, $\max$, sum, multiplication, $and$, $or$, $xor$, etc. satisfy these conditions. Also we have some queries $l, r$. For each query, we need to find $a_l\ op\ a_{l+1}\ op\ \dots op\ a_r$. Let's call such queries $q(l, r)$. My data structure can process such queries in $O(1)$ time with $O(n \cdot \log \log n)$ preprocessing time and $O(n \cdot \log \log n)$ memory. # How it works? [cut] # ## 1. Sqrt Let's do a sqrt-decomposition. We divide our array in $\sqrt{n}$ blocks, each block ha...
$a$ that contains $n$ elements and the operation $op$ that satisfies associativeproperty: $(x\ op\ y) op\ z

Read more »

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

 
 
 
 
29.
By Uppercase, history, 13 months ago, In English
A place where you can find binary equalities / inequalities and properties. Hello! Reading an AtCoder editorial I found an interesting equality(a + b − (a xor b) = 2 × (a and b)) and I was wondering if there is a website or a book where you can find a lot of properties of the binary system similar to this one. Could you please help me with a reference?
Hello! Reading an AtCoder editorial I found an interesting equality(a + b − (a xor b) = 2

Read more »

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

 
 
 
 
30.
By Spheniscine, history, 12 months ago, In English
"Splitmixes" Pseudorandom Permuter, aka "WS-APHF" Forgive the quirkiness of the title; I am not aware of a name for this concept, therefore I just made a few up. This blogpost is about a particular way to construct what I call a "pseudorandom permuter". It is distinct from a regular pseudorandom number generator (PRNG) in that it is constructed such that the sequence will never repeat until all $M = 2^k$ integers in its machine-integer state space (32- or 64-bit) has been used. In other words, it's a way to produce a permutation of $[0, M)$ that's (hopefully) statistically indistinguishable from a truly random permutation. The generator is made up of two parts, a "discrete Weyl sequence", and an "avalanching perfect hash function". A "discrete Weyl sequence" is defined by a parameterized function $W_{s, \gamma}: [0, M) \rightarrow [0, M)$ where the $i$-th member of the sequence is $W_{s, \gamma}(i) = (s + \gamma \cdot i) \mod M$. The two parameters can be chosen using a standard random number generator, with the caveat that $...
property*, which is that flipping one bit in the input should flip roughly half the bits of the output

Read more »

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

 
 
 
 
31.
By vitux, 7 years ago, translation, In English
Codeforces Round #262 (Div. 2) Editorial [problem:460A] At this problem you need to model what written in statements. Also, it can be proved, that answer can be calculated using formula: $n + \lfloor\frac{n - 1}{m - 1}\rfloor$ , where $\lfloor x \rfloor$ is the integer part of $x$. [submission:7536107] [problem:460B] Obviously $S(x)$ can take only integer values and $ 1 \le S(x) \le 81 $. Let's check $S(x)$ from $1$ to $81$, and calculate $ B*S(x)^{A} + C$. After that if sum of digits of this number is equal to $S(x)$, it is positive and less than $10^9$, than it is a solution. There could be bug because of using C++ pow() function. [submission:7536153] [problem:460C] Note,that answer is positive integer not greater than $10^9+10^5$. Using binary search on answer, we will find answer. Really, we can check in $O(n)$ if some height is achievable. We go from left to right. For current flower we calculate how much times it need to be watered to stand not lower than checking value. If cuurent flower nee...
$. Else, if $k = 1$, obviously that answer is $l$. If $k = 2$, answer is $1$, because $xor$ of numbers

Read more »

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

 
 
 
 
32.
By cgy4ever, 7 years ago, In English
Codeforces Round #270 Editorial [problem:472A] One way to solve this is by bruteforce: there are O(n) different ways to decomose n as sum of two number. If we can check if a number is a prime in O(1) then the whole algorithm can run in O(n). You can use Sieve of Eratosthenes to do the pre-calculation. And another way is try to prove this theorem. The prove is simple: if n is odd number, then 9 and (n-9) is an answer (n-9 is an even number at least 4, so a composite number), and if n is even number, then 8 and (n-8) is an answer (n-8 is an even number at least 4, also must be a composite number). [problem:472B] This task can be solve by greedy: the k people with highest floor goes together, and next k people with highest floor goes together and so on. So the answer is 2 * ((f[n]-1) + (f[n-k]-1) + (f[n-2k]-1) + ...) . It is a bit tricky to prove the correctness of greedy, since people can get off the elevator and take it again. We can give a lower bound of the answer by flow analysis: between floor i ...
algebra and notice the operation of xor on 32 bit integers equals to + operation in a 32 dimension

Read more »

Tutorial of Codeforces Round #270
 
 
 
 
  • Vote: I like it
  • +137
  • Vote: I do not like it

 
 
 
 
33.
By fchirica, 8 years ago, In English
Codeforces Round #198 — Editorial [problem:340A] ------------------ You are given a range $[A, B]$. You're asked to compute fast how many numbers in the range are divisible by both $x$ and $y$. I'll present here an $O(log(max(x, y))$ solution. We made tests low so other not optimal solutions to pass as well. The solution refers to the original problem, where $x, y \le 10^9$. Firstly, we can simplify the problem. Suppose we can calculate how many numbers are divisible in range $[1, X]$ by both $x$ and $y$. Can this solve our task? The answer is yes. All numbers in range $[1, B]$ divisible by both numbers should be counted, except the numbers lower than $A$ (1, 2, ..., A &mdash; 1). But, as you can see, numbers lower than A divisible by both numbers are actually numbers from range [1, A &mdash; 1]. So the answer of our task is f(B) &mdash; f(A &mdash; 1), where f(X) is how many numbers from 1, 2, ..., X are divisible by both x and y. For calculate in $O(log(max(x, y))$ the f(X) we need some math. If you don't ...
on the paper, you should find this property: **Lemma 1** Suppose we choose 2 indices i and j

Read more »

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

 
 
 
 
34.
By MazzForces, history, 3 years ago, In English
2 Special cases of Gaussian [Tutorial] Hello Codeforces. Today I'm writing about a Math topic that is really simple, but resources are limited. SLAE stands for system of linear algebraic equations. Basically, consider we have a set of equations of the form : $ a_0 \cdot x_0 + a_1 \cdot x_1 + a_2 \cdot x_2 + ... + a_{n-1} \cdot x_{n-1} = val_0 $ $ b_0 \cdot x_0 + b_1 \cdot x_1 + b_2 \cdot x_2 + ....+ b_{n-1} \cdot x_{n-1} = val_1 $ $ c_0 \cdot x_0 + c_1 \cdot x_1 + c_2 \cdot x_2 + ....+ c_{n-1} \cdot x_{n-1} = val_2 $ $ ..... $ Note that all $ a,b,c ... $ are real-valued arrays and all $ val_i , x_i $ are arbitrary reals. Realize how $ x_0, x_1 , ... x_{n-1} $ appear in each of the equations. In the post below, it is assumed we are dealing with reals, and not only integers. Now, we want to find values of $ [ x_0 , x_1 ... x_{n-1} ] $ that satisfy each of the given equations listed, **given** all $ a,b,c...$ and $ val_i$. The simplest method to find such solutions is to use **Gaussian Eliminat...
$ 2 $ $ 1 \oplus 1 = 0 = 1+1 $ mod $ 2 $ So, xor is just bit-wise addition mod $2$. We can

Read more »

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

 
 
 
 
35.
By adamant, history, 4 months ago, In English
Associativity and general identity testing Hi everyone! Five days have passed since my [previous post](https://codeforces.com/blog/entry/91610) which was generally well received, so I'll continue doing posts like this for time being. Abstract algebra is among my favorite subjects. One particular thing I find impressive is the associativity of binary operations. One of [harder problems](https://codeforces.com/gym/102129/problem/B) from my contests revolves around this property as you need to construct an operation with a given number of non-associative triples. This time I want to talk about how one can check this property for both groups and arbitrary magmas. First part of my post is about Light's associativity test and how it can be used to deterministically check whether an operation defines a group in $O(n^2 \log n)$. Second part of the post is about Rajagopalan and Schulman probabilistic identity testing which allows to test associativity in $O(n^2 \log n \log \delta^{-1})$ where $\delta$ is error tolerance. Finall...
) from my contests revolves around this property as you need to construct an operation with a given

Read more »

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

 
 
 
 
36.
By prackode, history, 5 months ago, In English
Pursuit_Of_Accepted 1.0 Editorial [A-Staircase](https://codeforces.com/group/HDYhSeyrua/contest/327097/problem/A)<br> Authors: [user:prackode,2021-05-07],[user:_NICkk,2021-05-07] <spoiler summary="Tutorial"> The answer contains such elements $a_i$ that $a_i+1=1$ since Chutki starts counting $1,2,3...$ again. Also add to the answer the last element $a_n$. </spoiler> <spoiler summary="Solution (C++)"> ~~~~~ #include <bits/stdc++.h> #define int long long #define lop(i,a,b,c) for (int i=a;i<b;i+=c) #define rlop(i,a,b,c) for (int i=a-1;i>=b;i-=c) #define prii pair <int,int> #define PB push_back #define S second #define F first #define B begin() #define E end() using namespace std; /*......................................................................*/ void solve(){ int n;cin>>n; int arr[n+1];vector <int> vec;int p=0; lop(i,0,n,1){ cin>>arr[i]; if (arr[i]>p)p=arr[i]; else { vec.PB(p);p=1; } }vec.PB(p); cout<<vec.size()<<"\n"; lop (i,0,vec.size(),1)cout<<vec[i]<<" ...
(a[-1]) print(len(ans)) print(*ans) ~~~~~ [B-XOR It](https://codeforces.com/group

Read more »

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

 
 
 
 
37.
By -Morass-, history, 4 years ago, In English
Problem Topics Good Day to you! I've been asked to make some topic-wise list of problems I've solved. Even though I couldn't involve all problems, I've tried to involve at least "few" problems at each topic I thought up (I'm sorry if I forgot about something "easy"). I've alredy made such list once anyway I've tried to include more problems now &mdash; so here it is: <spoiler summary="aho"> http://www.spoj.com/problems/ADAJOBS/ URI 2226 (5) //[NICE][NUMBERS][DP] http://www.spoj.com/problems/SUB_PROB/en/ http://codeforces.com/contest/696/problem/D 8 http://www.spoj.com/problems/AHOCUR/ 5 //Aho-Corassic + DP https://www.codechef.com/problems/LYRC (5) //Sample aho-brute-force http://codeforces.com/problemset/problem/346/B //Proposed by [user:bradyawn,2019-08-03] </spoiler> <spoiler summary="automat"> 6861 [LA] //CYK UVA 10679 //Suffix Automat http://www.spoj.com/problems/STRMATCH/ //Suffix Automat &mdash; trie might do too http://www.spoj.com/problems/NSUBST...
/problem/F (6) //[VERY NICE][DP] http://codeforces.com/gym/101908/problem/I (3) //[EASY][XOR] http

Read more »

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

 
 
 
 
38.
By fchirica, 8 years ago, In English
Codeforces Round #191 — Tutorial [problem:327A] I’ll present here the O(N ^ 3) algorithm, which is enough to solve this task. Then, for those interested, I’ll show a method to achieve O(N) complexity. **O(N ^ 3) method:** The first thing to observe is that constrains are slow enough to allow a brute force algorithm. Using brute force, I can calculate for each possible single move the number of 1s resulting after applying it and take maximum. For consider each move, I can just generate with 2 FOR loops all indices i, j such as i <= j. So far we have O(N ^ 2) complexity. Suppose I have now 2 fixed vaIues i and j. I need to calculate variable cnt (initially 0) representing the number of ones if I do the move. For do this, I choose another indice k to go in a[] array (taking O(N) time, making the total of O(N ^ 3) complexity). We have two cases: either k is in range [i, j] (this means i <= k AND k <= j) or not (if that condition is not met). If it’s in range, then it gets flipped, so we add to count variable 1 – ...
in a[] array. So the above solution is correct also. [problem:327C] **Property :** A number

Read more »

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

 
 
 
 
39.
By Zlobober, 10 years ago, translation, In English
CodeForces Beta Round #73 div. 1 analysis (particulary with div. 2) <span style="font-size: 10.0pt;font-family: Arial;color: rgb(0,0,0);background-color: transparent;font-weight: normal;font-style: normal;text-decoration: underline;vertical-align: baseline;">Problem DIV1-A, Div2-C. Trains.</span><br /><span style="font-size: 10.0pt;font-family: Arial;color: rgb(0,0,0);background-color: transparent;font-weight: normal;font-style: normal;text-decoration: none;vertical-align: baseline;">This problem can be approached from two sides - from a programmer's perspective and a mathematician's one. We consider both approaches.</span><br /><span style="font-size: 10.0pt;font-family: Arial;color: rgb(0,0,0);background-color: transparent;font-weight: normal;font-style: normal;text-decoration: none;vertical-align: baseline;"> </span><br /><span style="font-size: 10.0pt;font-family: Arial;color: rgb(0,0,0);background-color: transparent;font-weight: normal;font-style: normal;text-decoration: none;vertical-align: baseline;">First, let's write some general propositio...
;">You can try to find a Grundy's function by the definition if we xor all the required values

Read more »

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

 
 
 
 
40.
By rising_sea, history, 12 months ago, In English
"Tricks" I learned while practicing Disclaimer: I personally don't find learning tricks to be all that interesting, not responsible for any rating drops LOLOLOL, also I'm a bit lazy so there are prob mistakes in here #### Translate (AKA immediate implementation problem) 1. The problem is obvious that it should just be some data structures e.g. Segment tree [problem:474F] 2. Just DP, e.g. [problem:489F] #### Converting from brute force 1. Sometimes it just works ??? this works especially well if you notice the input is extremely small 2. Meet in the middle to be square root smaller [problem: 525E], [problem: 1006F] 3. Backtracking to prune states 4. Memoization (this is just dp lol) #### Look at something in a new way 1. Remove what seems to be impossible, NO it’s not cause you don’t know some fancy technique, just try you best to convert the impossibility into something familiar!! 2. ROOT THE TREE, probably a third of random tree problems on cf can be solved with this, it’s pretty powerful, eithe...
2. PIE 3. WLOG one side is bigger 4. TRIE for non obvious xor problem, tho this is a bit overused

Read more »

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

 
 
 
 
41.
By sirknightingfail, history, 3 years ago, In English
More on Sprague-Grundy: Code, Exercises, Solution outlines, Proof. This is a follow-up blog to [this talk](https://codeforces.com/blog/entry/63054) Please let me know if there are any errors. I might not be able to reply rapidly as it is finals week for me.\ The previous post doesn't exactly explain how to actually work out the solutions to Sprague-Grundy problems, or how to code them. Within this follow-up blog, I shall attempt to explain some of my thought process on working through Sprague-Grundy and similar problems, as well as including some code. First, some pseudo-code of calculating the Sprague-Grundy, and how to find the MEX. <spoiler summary="Recursive Sprague-Grundy"> ~~~~~ # g is defined as a game (set of games), MAX is the maximum possible Sprague-Grundy value. define SG(g): # Make a set of sprague-grundy values seen = new boolean[MAX+1] for x in g: # It is important to also check if SG(x) fits inside of the bounds of the array, # And to ignore it if it does not. seen[SG(x)]=true curr = 0 w...
is that every number $x<2^{k-2}$ can be written as a xor of $j\leq k-1$ different stacks of size

Read more »

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

 
 
 
 
42.
By boleyn.su, 8 years ago, In English
Codeforces Round #221 Tutorial [problem:376A] writer: [user:boleyn.su,2013-12-25] O(n): Let mid = position of ^ Let value(x) = x if x is a digit , 0 otherwise. Let sum = value(i-th char)*(i-mid) If sum = 0 then answer = balance Else if sum<0 then answer = left Else answer = right [problem:376B] writer: [user:oGhost,2013-12-25] O(n^4): Let f[i][j] = how many money i owes j \#It can be proved we only need to loop n times. Loop n times do: For i,j,k in [1..n] If f[i][j]>0 and f[j][k]>0 then Let delta = min (f[i][j], f[j][k]) Decrease f[i][j] and f[j][k] by delta Increase f[i][k] by delta Answer will be sum{f[i][j]} O(m+n): Let owe[i] = 0 for all i \#Suppose there is an agnecy to help people with debts. \#If you owe someone, you give money to the agency. \#If someone owes you, you get money from the agency. For each ai, bi, ci Increase owe[ai] by ci Decrease owe[bi] by ci Ansewr will be sum{owe[i]|owe[i]>0} [problem:...
). But in fact due to the property of this problem, using simplex algorithm to solve linear programming

Read more »

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

 
 
 
 
43.
By KADR, 11 years ago, translation, In English
All-Ukrainian School Olympiad in Informatics: editorial (A,B,C,D,E,F) <p></p><div>The editorial is now completed.</div><div><br></div><div><div><b>Problem A: Gift (Roman Iedemskyi)</b></div><div><br></div><div>Suppose that the pair $(A,B)$ is an optimal solution, where $A$ is the number of gold coins in a gift and $B$ is a number of silver coins. It is easy to see &nbsp;that there exist two (probably equal) indexes $i$ and $j$ such that $g_i=A$ and $s_j=B$. It is true, because in the other case we could decrease either $A$ or $B$ without changing connectivity of the graph.</div><div><br></div><div>Let $R(A,B)$ be the graph in which for all $i$ the following statement holds: $g_i \leq A \wedge s_i \leq B$.</div><div><br></div><div>Let $T(A)$ be the weighted graph in which for all edges $g_i \leq A$. For each edge $i$ we will assign a weight equal to $s_i$. Let's find a spanning tree of this graph, which has the property that its maximal edge is minimal possible. It can be shown that for the fixed $A$ the minimal value of $B$ for which graph $R(A,B)$ is st...
$. Let's find a spanning tree of this graph, which has the property that its maximal edge is minimal

Read more »

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

 
 
 
 
44.
By matrix, 7 years ago, In English
Codeforces Round #282 Editorial [problem:495A] For each digit $x$ you can count the number of digits $y$ that because of some broken sticks $x$ is shown instead of $y$ by hand. for example when $x = 3$, $y$ can be $3$, $8$ and $9$. Let's denote this number by $a_x$. Then if the input is $xy$ (the first digit shown in the counter is $x$ and the second is $y$) the answer will be $a_x \times a_y$. [problem:495B] - If $a < b$ then there is no answer since $a \operatorname{mod} x \le a < b$. - If $a = b$ then $x$ can be any integer larger than $a$. so there are infinite number of answers to the equation. - The only remaining case is when $a > b$. Suppose $x$ is an answer to our equation. Then $x | a - b$. Also since $a \operatorname{mod} x = b$ then $b < x$. These conditions are necessary and sufficient as well. So the answer is number of divisors of $a - b$ which are strictly greater than $b$ which can be solved in $O(\sqrt{a - b})$. [problem:494A] Consider a string consisting of '(' and ')' characters. ...
the first player has a winning strategy if and only if the xor of $g_{i, j}$ for every cell $(i, j

Read more »

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

 
 
 
 
45.
By kartik8800, 17 months ago, In English
CSES Range Queries section editorial Hello Codeforces, In this blog I will try to write a well detailed editorial for the CSES Range Queries section. The motivation for this editorial comes from https://codeforces.com/blog/entry/70018. Quoting [user:icecuber,2020-05-09] "I think [CSES](https://cses.fi/problemset/) is a nice collection of important CP problems, and would like it to have editorials. Without editorials users will get stuck on problems, and give up without learning the solution. I think this slows down learning significantly compared to solving problems with editorials. Therefore, I encourage others who want to contribute, to write editorials for other sections of CSES." So here I am writing an editorial for the range queries section. If you find any error or maybe have a better solution to some problem please do share. Range Sum Queries I ================== Given array is A[1..N], for each query of form (L,R) we need to output A[L] + A[L+1] + ... + A[R].<br> Define an array Prefix such that ...
) for building segtree and QlogN for Q queries. Range Xor Queries

Read more »

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

 
 
 
 
46.
By pi37, history, 6 years ago, In English
Codeforces Round #334 Editorial Problem 0: Richard has been infected with bovine spongiform encephalopathy. Help Kevin understand what he's saying! [Div 2 A](http://codeforces.com/contest/604/problem/A) ------------------------------------------------------ **Hint:** Just do it! But if you're having trouble, try doing your computations using only integers. This problem is straightforward implementation---just code what's described in the problem statement. However, floating point error is one place where you can trip up. Avoid it by rounding (adding $0.5$ before casting to int), or by doing all calculations with integers. The latter is possible since $250$ always divides the maximum point value of a problem. Thus when we rewrite our formula for score as $\max\left(3\cdot x/10, \left(250-m\right)\cdot x/250\right)$, it is easy to check that we only have integers as intermediate values. **Code:** http://codeforces.com/contest/604/submission/14608458 [Div 2 B](http://codeforces.com/contest/604/problem/B...
piles of a game, then the value assigned to that total game state is the xor of the values of each

Read more »

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

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

Read more »

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

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

Read more »

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

 
 
 
 
49.
By Xellos, 8 years ago, In English
Samara SAU ACM ICPC 2013-2014 Quarterfinal Qualification Contest: Editorial ### A. The Power of the Dark Side (difficulty: easy) Let's sort the parameters of every Jedi: $a \ge b \ge c$. The "coverted" Jedi obviously wants to use his strongest 2 parameters ($a_k,b_k$) against the opponent's weakest 2 ($b_i,c_i$) to get 2 victories as assuredly as possible; besides, the optimal order is $a_k$ against $b_i$ and $b_k$ against $c_i$, because if he can win when using them in the opposite order, then he'll win after swapping them, too. So we want to find all Jedis that have $a_k > b_i$ and $b_k > c_i$ for all $i$. That's simple, because those are the same conditions as $a_k > B=\max(b_i)$ and $b_k > C=\max(c_i)$. When processing the input, we can count $B$, $C$ and then we just check for every Jedi if he satisfies these 2 conditions, in linear time. I decided during the contest to code a solution which is a bit slower, but more powerful &mdash; it allows us to answer stronger versions of this problem like "which Jedis can we choose, if we're satisfied with...
the pairs by the first property, and process them in that order; now, we only need to count already

Read more »

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

 
 
 
 
50.
By Michael, 8 years ago, translation, In English
Yandex.Algorithm Qualification Round Analysis Qualification Round and its analysis were prepared by [user:Chmel_Tolstiy,2013-07-11], [user:aropan,2013-07-11], [user:Romka,2013-07-11], [user:SobolS,2013-07-11], [user:Ra16bit,2013-07-11], [user:snarknews,2013-07-11] and [user:Gassa,2013-07-11]. 1732 participants have started in the Qualification Round of Yandex.Algorithm, 1606 of them have made at least one attempt, 1558 have solved at least one problem. Interestingly, the number of registered participants was 3397 which is almost twice as much as the number of participants who have started the round. We don't know why is that. As the qualification round was a virtual contest, participants could choose the most convenient time to compete. The maximum number of participants online (around 280) was at the start, the minimum number &mdash; between 3 a.m. and 4 a.m. Moscow time (around 20 participants). First one chronologically who solved all 6 problems was **Scott.Ai** from China; all problems were submitted "open". Soon **i.met...
from game theory that position in such game is losing if $\mathrm{xor}$ of numbers of atoms in all

Read more »

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

 
 
 
 
51.
By ll931110, 9 years ago, In English
5587
iterate from the nearest multiple of 4 till N One property of the xor is that AxorBxorB

Read more »

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