Educational Codeforces Round 142 Editorial [problem:1792A] Idea: [user:BledDest,2023-01-25] <spoiler summary="Tutorial"> [tutorial:1792A] </spoiler> <spoiler summary="Solution (Neon)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { int t; cin >> t; while (t--) { int n; cin >> n; int cnt1 = 0; for (int i = 0; i < n; ++i) { int x; cin >> x; cnt1 += (x == 1); } cout << n - cnt1 / 2 << '\n'; } } ~~~~~ </spoiler> [problem:1792B] Idea: [user:BledDest,2023-01-25] <spoiler summary="Tutorial"> [tutorial:1792B] </spoiler> <spoiler summary="Solution (awoo)"> ~~~~~ for _ in range(int(input())): a1, a2, a3, a4 = map(int, input().split()) if a1 == 0: print(1) else: print(a1 + min(a2, a3) * 2 + min(a1 + 1, abs(a2 - a3) + a4)) ~~~~~ </spoiler> [problem:1792C] Idea: [user:BledDest,2023-01-25] <spoiler summary="Tutorial"> [tutorial:1792C] </spoiler> <spoiler summary="Solut...

Full text and comments »

Editorial — Codeforces Round #685 [problem:1451A] <spoiler summary="Tutorial"> [tutorial:1451A] </spoiler> <spoiler summary="Code (C++)"> ~~~~~ #include <bits/stdc++.h> using namespace std; int32_t main() { ios::sync_with_stdio(0); cin.tie(0); int t, n; cin >> t; while(t--) { cin >> n; cout << (n <= 3? n-1 : 2 + (n&1)) << '\n'; } return 0; } ~~~~~ </spoiler> <spoiler summary="Code (Java)"> ~~~~~ import java.util.*; import java.util.ArrayList; public class Main { public static void main(String args[]) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); for(int i = 0; i < t; i++) { int n = sc.nextInt(); System.out.println(Math.min(2 + (n & 1), n - 1)); } } } ~~~~~ </spoiler> Idea by [user:ridbit10,2020-11-21] [problem:1451B] <spoiler summary="Tutorial"> [tutorial:1451B] </spoiler> <spoiler summary="Code (C++)"> ~~~~~ #include <bits/...

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 »

Intro to Staircase Nim + Editorial for HackerRank "Move the Coins" Let's learn about Staircase Nim by solving [move the coins](https://www.hackerrank.com/contests/world-codesprint-april/challenges/move-the-coins) problem that appeared in HackerRank April World Codesprint. Among the problems I have ever created, its one of my favorites. If you don't want to solve that problem but want to learn about staircase-nim, just read the first part of this blog. Let's start with some backgrounds. **Staircase Nim** This problem is a variation of Staircase Nim problem, which is a not-very-well-known variation of classic Nim problem. If you don't know what Nim Game is, I suggest you first to learn about it. In Staircase Nim, there is a staircase with n steps, indexed from $0$ to $n-1$. In each step, there are zero or more coins. See the figure below:  Two players play in turns. In his/her move a player can choose a step $i>0$ and move one or more coins to s...

Full text and comments »

Editorial of Codeforces Round 963 (Div. 2) [problem:1993A] <spoiler summary="Hint"> What is the pattern of Tim's answer sheet that can give him maximum score? </spoiler> <spoiler summary="Solution"> Let's say there are $n$ problems take $A$ as the answer, therefore he can only get $n$ points with the answer $A$. The same is correct for $B$, $C$ and $D$. Therefore, the maximum score can be achieved is $min(n, A) + min(n, B) + min(n, C) + min(n, D)$. Time complexity: $O(4n)$ </spoiler> <spoiler summary="Code (python)"> ~~~~~ t = int(input()) for _ in range(t): n = int(input()) s = input() print(sum(min(n, s.count(c)) for c in "ABCD")) ~~~~~ </spoiler> [problem:1993B] <spoiler summary="Hint 1"> Find a way to make all the elements even. Then odd. </spoiler> <spoiler summary="Hint 2"> In the worst case, the number of operations required is the number of even elements + 1. Why? </spoiler> <spoiler summary="Solution"> First, if all elements already have the same parity, we don'...

Full text and comments »

Maintain subtree information using link/cut trees In the tutorial of [problem:1172E], I didn't write things on how to maintain subtree information, because I thought it was a popular trick. However, through [user:tmwilliamlin168,2019-06-12]'s [comment](/blog/entry/67511?#comment-518361), I realized that this trick may be not so common in other countries, so I decided to write a blog on it. This blog will tell you how to maintain subtree information using LCT, with solutions on some problems, so you should know LCT before reading this blog. ## Main Idea The main idea is simple: record the sum of information of "virtual subtrees", where the "virtual subtrees" refers to the subtrees except the one in the Splay.  In the picture, $1$, $2$, $6$, $10$ are in a Splay, while $8$ and $12$ are in another. The "virtual subtrees" of $1$ is $3$ and $4$, the "virtual subtrees" of $4$ is $7$ and $8$, the node $8$ has no "virtual subtree". You need to update the i...

Full text and comments »

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

Full text and comments »

Divide by Zero 4.0 Summary ##Statistics Total Users/Teams who have made a submission: **754** Total Submissions: **4212** Number of distinct users/teams with correct submissions: **498** [Contest Link]( https://www.codechef.com/DIBZ2016) [Feedback form](http://goo.gl/forms/cMY4KZLEJV) --- ##Winners <li>Rank 1: [user:Sumeet.Varma,2016-01-31]</li> <li>Rank 2: [user:amankedia1994,2016-01-31]</li> <li>Rank 3: [user:PrashantM,2016-01-31]</li> --- The Editorials of the following problems are prepared by me, [user:aditya1495,2016-01-31] and [user:_shil,2016-01-31]. --- ##Shil and RasenShuriken (setter: [user:_shil,2016-01-31])<br> Total number of pairs such that their product is even. Count total number of odd numbers = x.<br> Product of two numbers is odd if the both numbers are odd.<br> Ans = **N*(N-1)/2 &mdash; x*(x-1)/2** --- ##Shil Loves Exclusive Or (setter: [user:_shil,2016-01-31])<br> Use the fact that Xor of 2x and 2x+1 is 1.<br> Therefore xo...

Full text and comments »

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

Full text and comments »

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

Full text and comments »

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

Full text and comments »

xorsum(AMXOR) on codechef I have been trying to solve [this](https://www.google.co.in/url?sa=t&rct=j&q=&esrc=s&source=web&cd=1&cad=rja&uact=8&ved=0ahUKEwjRodGi9t7UAhXMKY8KHVyPCZIQFggqMAA&url=https%3A%2F%2Fwww.codechef.com%2Fproblems%2FAMXOR&usg=AFQjCNGfYjKhHz1N_IIXUzcaDHMDvlimUw) on Codechef for some days but i donot find [editorial](http://discuss.codechef.com/problems/AMXOR) pretty clear ... ** The problem statement goes as follows ** Chef has a sequence of N positive integers { a1, a2, a3, ... aN }. The Sous Chef wants to choose another sequence of N non-negative integers { b1, b2, b3, ... bN } such that The bitwise xor sum of these 2 sequences is equal i.e, a1 ^ a2 ^ a3 ^ ... aN = b1 ^ b2 ^ b3 ^ ... bN for each i, bi ≤ ai. ** I am not getting how to avoid recounting of subsequences or to be more precise what does "one" or "zero" denote in editorial...so if someone could provide example to explain this(though there are few comments on editorial page but still if somebody can explain it better...

Full text and comments »

Finding Rightmost Set Bit For an Number Is finding rightmost set bit by this approach wrong. ~~~~~ int ans=xorsum,int rightmost=0; while(ans){ int mask=1<<i; if(ans&mask){ break; } ans=ans>>1; i++; } rightmost=1<<i; ~~~~~ My code gave WA for some test cases when I used this code snippet to find rightmost set bit.It worked when I removed this with `rightmost=xorsum&(-xorsum)` can anyone please why the above got snippet may not work.

Full text and comments »

Doubt in game theory misere type nim games hey , i have a doubt regarding misere nim games .. to find the condition for losing position .. i have an approach which is giving me a wrong answer it s like this assign grundy number for each individual pile of size k and it will be k-1 since in our case a pile of size 1 is our terminal position (so for 1 grundy(1)=0 remaining elements grundy(k)=k-1 by ) so if the xorsum of all grundy numbers is 0 then it is a losing position else it is a winning position( according to some sprague grundy theorem i understood only some part of it ) .. but this approach is giving me wrong answer and i have searched over the internet and found some other approach it's like count no of one s and do something.......to get answer .. I want to know why my approach is wrong ....Is it okay to think about misere him games as normal nim games with the terminal position changed...or can't we apply sprage grundy theorem for misere games ?? link to the question :http://www.spoj.com/problems/MMMG...

Full text and comments »

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

Full text and comments »