Perhaps today and/or tomorrow due to a power outage there may be disruptions in the work of Codeforces and Polygon. Please do not plan any important events during this time. If there are details or the exact time, we will definitely publish them. Estimated time of maintenance: from 2 Aug, 16:00 (UTC) to 2 Aug, 20:00 (UTC). ×

 
 
 
 

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 zscoder, history, 15 months ago, In English
[Tutorial] Generating Functions in Competitive Programming (Part 1) Hi everyone! Inspired by the recent [Codeforces Round 641](https://codeforces.com/contest/1349), I decided to write an introductory tutorial on generating functions here. I am by no means an expert in generating functions so I will write about what I currently know about them. [user:MiFaFaOvO,2020-05-15] has written a really interesting [blog](https://codeforces.com/blog/entry/76447) here on Codeforces about more advanced applications of generating functions, but I think there is no English tutorial on the basics of this topic yet (or at least on CP sites). Thus, I would like to share about this topic here. I plan to split this tutorial into two parts. The first part (this post) will be an introduction to generating functions for those who have never learned about them at all, and some standard examples and showcases of generating functions. The second part will be a collection of several applications of generating functions in CP-style problems. If you are already familiar with ge...
are easier to count. For a fixed subset of white cells $S$, denote $N(S)$ as the number of ways to place $n, conditions are usually harder to count while "at least" conditions are easier to count. For a fixedsubset, We relate $n_{k}$ with $e_{k}$. Consider a subset $T$ of size $t$ and a way to place $n$ non

Read more »

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

 
 
 
 
2.
By MikeMirzayanov, 5 months ago, In English
Codeforces: Results of 2020 [list some changes and improvements] Hello, Codeforces! I understand that 2021 has been going on for a long time, but here I have picked up a subset of some of the improvements that the Codeforces team made in 2020. Soon I will publish numbers (no, charts) with statistics for 2020. In the meantime, I bring to your attention a list of changes and improvements. By the way, this is a decent list. This is about half to a quarter of all changes. It's just that other changes are more often somewhere in the internals of the system and are not visible to users. Please read this list. Each item is the effort of someone from the team. Thanks to [user:geranazavr555,2021-03-14], [user:kuviman,2021-03-14] and [user:cannor147,2021-03-14] for their efforts. You've made our platform better! Well, by the way, I don't quit programming and many improvements were made by me. The items on the list are written in a concise and informal form, many of the items I just copied from commit messages from git. If you want more details &mdash...
picked up a subset of some of the improvements that the Codeforces team made in 2020. Soon I, I understand that 2021 has been going on for a long time, but here I have picked up asubset

Read more »

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

 
 
 
 
3.
By adamant, history, 6 weeks 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...
Subset convolution interpretation, of subset convolution and some operations related to it., ,\dots,x_n]/\langle x_1^2, \dots, x_n^2\rangle$ for "subset" convolution, - $R[\varepsilon][x_1,\dots, . In this way, coefficient near $z^0$ will still correspond to subset convolution and coefficient near $z^l x, Also this approach **allows us to easily and intuitively generalize subset convolution** to sum, Now before working with subset convolution, let's take a step back and recall what we're doing, Now comes the "subset" convolution. We need some value such that $x^0 x^0 = x^0$, $x^0 x^1 = x^1, That being said, subset convolution also has a nice intuitive interpretation which is nothing more, \begin{equation} (a \star b)_k = \sum\limits_{i\subset k} a_i b_{k \setminus i} \end{equation}

Read more »

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

 
 
 
 
4.
By ATSTNG, history, 23 months 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...
box in such way that we cannot choose non-empty subset of selected numbers with xor-sum equal to $0, function $r(S)$ that tells maximum size of independent subset for some $S$, which issubset of ground, storing it as some information about each subset (it will result in exponential memory consumption). We, without gaining independence. No circuit is a subset of another circuit (otherwise we can remove some, ). Directly from previous, no basis is a subset of other basis. Any independent set is asubset of some, **Bipartite graph maximum matching.** Well known problem, you are given bipartite graph findsubset, **Matroid on a subset of ground set.** We can limit ground set of matroid to its subset without, **Uniform matroid.** Matroid that considers subset $S$ independent if size of $S$ is not greater, 1. Empty set is independent. 2. Any subset of independent set is independent. 3. If independent, 1. Rank of subset cannot be greater than size of this subset. 2. Rank of independentsubset, Key observation here is that we cannot choose subset of numbers with zero xor-sum if and only, \langle X, I \right\rangle$ gives a classification for each subset of $X$ to be either _independent_, subset of $X$ to be either _independent_ or _dependent_ (included in $I$ or not included in $I, subset of previous vertices, but it is not considered to be a shortcut because graph is oriented

Read more »

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

 
 
 
 
5.
By sidhant, 19 months ago, In English
Tutorial on Zeta Transform, Mobius Transform and Subset Sum Convolution **Pre-requisite**: Go through the Zeta/SOS DP/Yate's DP blog [here](https://codeforces.com/blog/entry/45223) **Source**: This blog post is an aggregation of the explanation done by [user:arjunarul,2019-12-26] in this [video](https://youtu.be/UOTCTbm1NrQ?list=PLi0ZM-RCX5nsTc2Z6woHr5qoF6n3b-thO), a comment by [user:rajat1603,2019-12-26] [here](https://codeforces.com/blog/entry/57250?#comment-409117) and the paper on [Fast Subset Convolution](http://people.csail.mit.edu/rrw/presentations/subset-conv.pdf) **Notation**: 1. set $s$ and mask $s$ are used interchangeably meaning the same thing. 2. $a \setminus b$ would mean set subtraction, i.e subtracting set $b$ from set $a$. 3. $|s|$ refers to the cardinality, i.e the size of the set $s$. 4. $\sum_{s' \subseteq s} f(s')$ refers to summing function $f$ over all possible subsets (aka submasks) $s'$ of $s$. **Aim**: Given functions $f$ and $g$ both from $[0, 2^n)$ to integers. Can be represented as arrays $f[]$ and $g[]$ r...
Tutorial on Zeta Transform, Mobius Transform and Subset Sum Convolution, algorithms for Mobius transform and Subset Sum convolution yourself. Maybe deriving Mobius transform, of the transform, i.e if the subset $s$ is of odd cardinality then this tranform negates it, otherwise it does, ) and the paper on [Fast Subset Convolution](http://people.csail.mit.edu/rrw/presentations/subset-conv.pdf), -409117) and the paper on [Fast Subset Convolution](http://people.csail.mit.edu/rrw/presentations/subset, 2. Mobius Transform (i.e inclusion exclusion sum over subset): $\mu(f(s)) = \sum_{s' \subseteq s, 3. Subset Sum Convolution: $f \circ g(s) = \sum_{s' \subseteq s} f(s')g(s \setminus s')$, $\forall, Now the next is subset sum convolution., Problems mentioned in SOS blog, [here](https://codeforces.com/blog/entry/45223) and forSubset Sum, Theorem 3 implies that subset sum convolution can be done by applying SOS and Inverse SOS DP $N, stores the sum of where $a$ is a subset of $s$, $b$ is a subset of $s$ and $|a| + |b| = |s|$. If we

Read more »

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

 
 
 
 
6.
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...
http://www.spoj.com/problems/SUBSET/ (5) //VERY NICE — 3^10 (^2 but not exactly) (+ sorting)

Read more »

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

 
 
 
 
7.
By bholagabbar, 6 years ago, In English
BitMasking & Subset Listing for Absolute Beginners I happened to write an answer on Quora yesterday for **'How to list all the subsets of a set where elements need not be necessarily unique'**. http://qr.ae/fwOCc Though several tutorials already exist, here is my 'simplified' version solving the above problem using bitmasking because personally, I was really confused when i learnt this first. Also, this is my first attempt at writing something. Please feel free to comment/criticize and please upvote if you liked the explanation :) More than often, problems where you feel the answer can be found after brute forcing through all the subsets, have smarter and more efficient solutions using Dynamic Programming. Have a look at an Introduction to the Knapsack Problem and Dynamic Programming: http://www.cs.rit.edu/~zjb/courses/800/lec7.pdf That aside, if n is reasonably small, you CAN use BruteForce and list down all the subsets in the process. As mentioned, we will use the technique of BitMasking. Alright, so lets start by trying ...
BitMasking & Subset Listing for Absolute Beginners, this element in our 'i'th subset 5. Done. I was very confused when I learnt this the first time, to (2^n)-1 cursub="Current Subset Contains Elements: " for j in range(0,n): if((1<, ) for the number 'i'. 4. If it is, then we include this element in our 'i'th subset 5. Done., Obviously, what the point of just listing down the subset? You would want to perform certain

Read more »

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

 
 
 
 
8.
By zscoder, history, 5 years ago, In English
[Tutorial] Non-trivial DP Tricks and Techniques Hi everyone! Today I want to share some DP tricks and techniques that I have seen from some problems. I think this will be helpful for those who just started doing DP. Sometimes the tutorials are very brief and assumes the reader already understand the technique so it will be hard for people who are new to the technique to understand it. Note : You should know how to do basic DP before reading the post DP + Bitmasks ------------------ This is actually a very well-known technique and most people should already know this. This trick is usually used when one of the variables have very small constraints that can allow exponential solutions. The classic example is applying it to solve the Travelling Salesman Problem in $O(n^{2} \cdot 2^{n})$ time. We let $dp[i][j]$ be the minimum time needed to visit the vertices in the set denoted by $i$ and ending at vertex $j$. Note that $i$ will iterate through all possible subsets of the vertices and thus the number of states is $O(2^{n} \cdo...
Firstly, note that $\prod(a_{i} + A) = \sum_{s \subset \{0, 1, ..., n - 1\}} A^{n - |s|} \cdot, } - 1$. How do we know which elements belong to a subset denoted by $i$? We write $i$ in its binary, }$) is equal to the subset denoted by $j$. Let $f[x]$ denote the set of prime factors of $x$. Since $b_, }$. Indeed, this is just a result of the formula above, where we iterate through all possiblesubset sizes

Read more »

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

 
 
 
 
9.
By Errichto, 3 years ago, In English
Sums and Expected Value — part 1 part 2: https://codeforces.com/blog/entry/62792 Watch my lecture-stream tomorrow (Thursday) at [14:00 CEST](https://www.timeanddate.com/worldclock/fixedtime.html?msg=EV+lecture+1&iso=20181025T14&p1=262) &mdash; <s>[https://www.youtube.com/watch?v=qdlPY37MBPo](https://www.youtube.com/watch?v=qdlPY37MBPo)</s> [https://www.youtube.com/watch?v=U_h3IjreRek](https://www.youtube.com/watch?v=U_h3IjreRek). I will go through theory and problems from this blog. The only prerequisite is knowing what is probability. The next (harder) part on Monday. The video will be available later, with timestamps for each problem &mdash; so you don't have to watch everything. ### Definition of EV Let's say we bought a lottery ticket for 2$. We will win 10$ with probability 10%, and 20$ with p-bility 2%. On average, it gives us $0.1 \cdot 10 + 0.02 \cdot 20 = 1.4$, so we are worse off after buying the ticket. The computed average is called the expected value. The expected value (EV, expecta...
\le 10^5$). We choose a random subset of vertices, what gives us a new (small) convex polygon. Find, , uniformly at random. Find EV of the difference between the maximum and minimum element in thesubset, . Find EV of the difference between the maximum and minimum element in the subset. Equivalently

Read more »

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

 
 
 
 
10.
By kushal.p1699, history, 3 months ago, In English
Generating Subsets (Recursion) Hi all, I'm so excited to write my first blog here. Last week I was helping my friend in tracing the recursion problem called **Generating subset**. He had the code snippet, but he was not able to understand the flow of the program. So, I tried to explain the logic to him. I'm happy that, my explanation made him clear on his doubts. I thought of sharing my explanation on tracing this problem by writing a new blog. **Problem statement:** <br> Generate the subsets of given **N** elements using recursion. **Input:** <br> 1 2 3 **output:** <br> 1 2 3 <br> 1 2 <br> 1 3 <br> 1 <br> 2 3 <br> 2 <br> 3 <br> **Explanation:** <br> Subsets of [1,2,3] is null, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}. **code:** <br> ~~~~~ #include <bits/stdc++.h> using namespace std; vector<int> subset; void solve(int a[], int n, int index) { if(index == n){ // print the subset for(int i=0; i<subset.size(); i++){ cout << subset[i] << " "; ...
the recursion problem called **Generating subset**. He had the code snippet, but he was not able, Last week I was helping my friend in tracing the recursion problem called **Generatingsubset, vector subset; void solve(int a[], int n, int index) { if(index == n){ // print

Read more »

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

 
 
 
 
11.
By Ripatti, 11 years ago, translation, In English
A little bit of classics: dynamic programming over subsets and paths in graphs <i>Author thanks </i><a href="../../../profile/adamax" title="Капитан adamax" class="rated-user user-yellow">adamax</a><i> <span class="short_text" id="result_box"><span style="" title="">for translation this article into English.</span></span></i><br><br><b>Introduction</b><br>After <a href="http://codeforces.ru/blog/entry/331">Codeforces Beta Round #11</a> several participants expressed a wish to read something about problems similar to <a href="http://codeforces.ru/contest/11/problem/D">problem D</a> of that round. The author of this article, for the purpose of helping them, tried searching for such information, but to his surprise couldn't find anything on the Internet. It is not known whether the search was not thorough or there's really nothing out there, but (just in case) the author decided to write his own article on this topic.<br><br>In some sense this article may be regarded as a tutorial for the <a href="http://codeforces.ru/contest/11/problem/D">problem D</a> from Beta R...
modify the previous algorithm. Let $dp[mask][i]$ be the number of Hamiltonian walks on thesubset, part of the expression is the subset of vertices $j$, for which there exists a Hamiltonian walk over, starts, assume that it starts at 0. Now use solution 1 for the subset of vertices, changing, the subset $mask$ which ends in the vertex $i$. DP is the following: $dp[mask][i]=1$, if $count, walks over the subset $mask$, starting at the vertex $first(mask)$ and ending at the vertex $i$. DP, DP over subsets Consider a set of elements numbered from 0 to $N-1$. Each subset, Let $dp'[mask]$ be the mask of the subset consisting of those vertices $j$ for which there exists, So $dp[mask][i]$ contains the length of the shortest Hamiltonian walk over the subset $mask, The method is to assign a value to each mask (and, therefore, to each subset) and compute, subset of this set can be encoded by a sequence of $N$ bits (we will call this sequence "a mask"). The $i

Read more »

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

 
 
 
 
12.
By ed1d1a8d, 7 years ago, In English
Complexity of Merging Subsets on Trees Last weekend (March 1-2) the 2014 HackerRank 101 Hack took place. In particular, a problem named [Coloring Tree](https://www.hackerrank.com/contests/101feb14/challenges/coloring-tree) was present. Basically, the problem gives you a tree where each vertex is assigned a color and asks you queries where you have to find the number of distinct colors in a particular subtree. My approach was to compute the number of distinct colors for every subtree using a DFS traverse of the tree. My algorithm went through the tree, and for every vertex it computed a set (`std::set`) of all the distinct elements within its subtree. I accomplished this for every vertex using the following steps: 1. Compute the sets for each of the children of the current vertex. 2. Merge the children together by inserting all elements of the child sets within the subtree into the set of the largest child. (NOTE: Do not copy the set of the largest child. Simply insert the rest of the elements such that the number of ...

Read more »

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

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

Read more »

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

 
 
 
 
14.
By AliceH1226, history, 2 years ago, In English
Why the number of subsets with gcd divisible by 2 is 2^cnt-1, while the total number of subsets is 2n. Why minus one when calculating the number of the formal subsets? 585E &mdash; Present for Vitalik the Philatelist The problem has been prepared by gridnevvvit. Let's calculate the number of subsets with gcd equal to 1 — value A. Let's do that using principle of inclusions-exclusions: firstly we say that all subsets is good. The total number of subsets is equal to 2n. Now let's subtract subsets with gcd divisible by 2. The number of that subsets is equal to 2cnt2 - 1 (cnti is the number of numbers that is divisable by i). Next we should subtract 2cnt3 - 1. Subsets with gcd divisible by 4 we already counted with number two. Next we should subtract 2cnt5 - 1. Now we should notice that subsets with gcd divisible by 6 we already processed twice: firstly with number 2, then with — 3, so let's add the number of these subsets 2cnt6 - 1. If we continue this process we will get, that for all numbers d we should add the value μ(d)(2cntd - 1), where μ(d) is equals to 0, if d is divisible by square of some prime, 1, if the number of primes in factorization...

Read more »

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

 
 
 
 
15.
By Xellos, history, 6 years ago, In English
Codeforces Round #333 — editorial ### Hints: [div2A](#div2A): Try conversions between bases. [div2B](#div2B): Solve a simpler version of the problem where $A_{i+1} \neq A_i$ for all $i$. [div1A](#div1A): What are the shortest paths of the vehicles? what's the shorter of those paths? [div1B](#div1B): Forget about the ceiling function. Draw points $(i,A[i])$ and lines between them &mdash; what's the Lipschitz constant geometrically? [div1C](#div1C): Some dynamic programming. Definitely not for the exp. score of one person &mdash; look at fixed scores instead. [div1D](#div1D): Compute $dif(v)$ in $O(N)$ (without hashing) and then solve the problem in $O(N^2)$. You need some smart merges. [div1E](#div1E): Can you solve the problem without events of type 1 or 2? Also, how about solving it offline &mdash; as queries on subsets. ![ ](https://i.imgur.com/bnWmD60.png) ### <a name="div2A"></a>Div. 2 A: Two Bases ------------------------------------ It's easy to compare two numbers if the same bas...
over time. We'll solve it offline — each query (event of type 3) is asked about asubset, $ is asked on some subset $S_q$ of exhibits.

Read more »

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

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

Read more »

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

 
 
 
 
17.
By neal, 11 months ago, In English
Unofficial Editorial for Educational Round 94 (Div. 2) Haven't done one of these for a while! Here are my approaches to the problems: #### [problem:1400A] We just need to make sure our string of $n$ characters matches each of the $n$ substrings in at least one spot. The easiest way to do this is to take every other character from $s$. Code: [submission:90908018] Another fun solution: we can generate random strings and check them until we find one that matches everything. This works because the probability of failing to match any particular substring is $\frac{1}{2^n}$, so as $n$ gets bigger the probability of failing gets extremely low. Code: [submission:90999219] #### [problem:1400B] First iterate on the number of swords we will personally take. Then we should greedily take as many war axes as we can until we run out of money. At this point, our follower needs to take as many items as possible. They can do this by greedily taking whichever of swords or war axes are cheaper until they run out, followed by taking the more expensi...
in that component and check whether the subset is a valid choice (i.e., is an independent set). We can

Read more »

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

 
 
 
 
18.
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 ...
3. There doesn't exist a non-empty subset of segments such that bitwise-xor of the numbers from, get a different possible xor of some subset. So, the answer would be $2^\text{size of basis, is the maximum possible xor of the elements of some subset of $S?$ [Link to the source](https, the set of all possible xor-sums of elements from a subset of $S.$ There are two types of queries, , because for each subset of the $(l - b)$ non-basis vectors in the prefix, we find a unique linear, . Then, observe that, every possible xor of the numbers from some non-empty subset of these segments can

Read more »

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

 
 
 
 
19.
By art-hack, 11 months ago, In English
Generating subsets of size K using bits Hi Everyone, I encountered this subproblem in a problem. Suppose we are given an array of integers of size N and want to generate subsets of size K from it. I used this simple backtracking approach to generate the combinations of size K. <spoiler summary="Backtracking Code"> ~~~~~ #include "bits/stdc++.h" using namespace std; void generatesubsets(vector<int> choices, int current, int K, vector<int> selected=vector<int>()){ if(choices.size()-current<K-selected.size()) return; if(selected.size()==K){ //process subset for(auto i:selected) cout<<i<<" "; cout<<endl; return; } if(current==choices.size()) return; selected.push_back(choices[current]); generatesubsets(choices,current+1,K,selected); selected.pop_back(); generatesubsets(choices,current+1,K,selected); } int main() { ios::sync_with_stdio(0); cin.tie(0); vector<int> v{1,2,3,4,5,6,7,8,9,10}; generate...
()) return; if(selected.size()==K){ //process subset for(auto i:selected, ){ //process subset for(auto i:selected) cout<, ++) { if(__builtin_popcount(b)!=K) continue; vector subset; for (int i = 0; i

Read more »

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

 
 
 
 
20.
By Karan2116, history, 5 years ago, In English
Everything About Dynamic Programming **I decided to gather some good material on the web related to DP and found some good explanation by svg on topcoder forums..Hence wrote this blog.Will format it when i get time.** ![ ](http://codeforces.com/predownloaded/2c/af/2caf058ab9cf6db0f875c573fb0d6e73de572122.png) **Problem:** About 25% of all SRM problems have the "Dynamic Programming" category tag. The DP problems are popular among problemsetters because each DP problem is original in some sense and you have to think hard to invent the solution for it. Since dynamic programming is so popular, it is perhaps the most important method to master in algorithm competitions. The easiest way to learn the DP principle is by examples. The current recipe contains a few DP examples, but unexperienced reader is advised to refer to other DP tutorials to make the understanding easier. You can find a lot of DP examples and explanations in an excellent tutorial Dynamic Programming: From novice to advanced by Dumitru. The purpose ...
adds some elements to the current subset, but does not subtract any. So result for each state (s

Read more »

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

 
 
 
 
21.
By Lakh, history, 5 weeks ago, In English
Help needed in subset sum variation using XOR operation ~~~~~ You are visiting a fair in byteland. You are shopping and want to buy Q items. Each item cost exactly B[i] amount of money. You have no money but you have a magical bag on which you can apply an operation any times you want. In bag there are N integers denoted by array A. In one operation, You choose two integer X Y from A and deposit all of the amount of money M you have, this will magically increase your money by X ⊕ Y. Note: You have to deposit all money you have otherwise you will be exiled from Byteland for your greed. Also, shopkeepers have no change, So you have to pay exact amount. :p Treating each item as independent and starting with 0 amount of money, Can you find if we can buy each item? Problem Constraints 2 ≤ N ≤ 1000 1 ≤ A[i] ≤ 10000 1 ≤ Q ≤ 100000 0 ≤ B[i] ≤ 10^9 Input Format First argument contains an integer array A of size N. Second argument contains an integer array B of size Q. Output Format Return a binary string of size Q containing i as...
Help needed in subset sum variation using XOR operation, if there exists some subset in the XOR_ARRAY whose sum is equal to the required value. Seems likesubset, need to find if there exists some subset in the XOR_ARRAY whose sum is equal to the required value

Read more »

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

 
 
 
 
22.
By RomeoFantastik, history, 18 months ago, In English
Subset Dynamic Programming Editorial - Round #585 Div.2 E Hello, everyone! I have just brushed off my **Subset Dynamic Programming** knowledge by solving the problem [Marbles](https://codeforces.com/contest/1215/problem/E) (Div.2 E) from Round #585. Very nice problem and a perfect example of how this technique comes into play when you need to try out each possible permutation or combination of elements in order to find an optimal one. **Rite of passage:** 1. n is really big, buuuut.. why are there only 20 different colours? Should be backtracking or Subset Dynamic Programming! 2. Each possible solution corresponds to a permutation of these 20 colors. Usually, if I find a brute force approach which tries each possible permutation, I'm pretty confident I can use Subset Dynamic Programming to reduce the time complexity from O(k!) to O(2^k) or maybe O(2^k * k). 3. Looks like the mask is going to represent the subset of colors I have added into my permutation. 4. At each step, I will find a color which was not added yet and I...
Subset Dynamic Programming Editorial - Round #585 Div.2 E, a brute force approach which tries each possible permutation, I'm pretty confident I can useSubset, or Subset Dynamic Programming!, 3. Looks like the mask is going to represent the subset of colors I have added into my permutation., 4. At each step, I will find a color which was not added yet and I update the subset containing, Hello, everyone! I have just brushed off my **Subset Dynamic Programming** knowledge by solving, Here is the link to my **video tutorial**: [Codeforces Problem — Marbles ( Subset Dynamic, I have just brushed off my **Subset Dynamic Programming** knowledge by solving the problem [Marbles

Read more »

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

 
 
 
 
23.
By sar0603, history, 8 months ago, In English
Bitmasking Subset Generation of Subset ~~~~~ //S = bitmask representation of available subset //{1,2,3} ,S = 3 means only {2,3} are available since binary(3) = 0 1 1 ~~~~~ ~~~~~ for (int G = S; G != 0 ; G = (G - 1) & S) ~~~~~ This one liner generates subset of a subset in bit representation form. Would be grateful if anyone can give any intuition or explain the above line. Dont want to mug this up. Eg: ~~~~~ The subset = 1110 The subsets of subset : 1110 1100 1010 1000 0110 0100 0010 ~~~~~
Bitmasking Subset Generation of Subset, Eg: ~~~~~ The subset = 1110 The subsets of subset : 1110 1100 1010 1000 0110 0100 0010 ~~~~~, This one liner generates subset of a subset in bit representation form. Would be grateful if anyone, ~~~~~ //S = bitmask representation of available subset //{1,2,3} ,S = 3 means only {2,3

Read more »

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

 
 
 
 
24.
By Scofield11, history, 2 years ago, In English
Find all subsets withing given range For a given array $a_i$ , we need to find all subsets withing given range [A,B]. For an array consisting of $a_1$ and $a_2$ all subsets are: {},{$a_1$},{$a_2$},{$a_1$,$a_2$}. Their sums are 0, $a_1$, $a_2$, $a_1$+$a_2$. Input: ~~~~~ 3 -1 2 1 -2 3 ~~~~~ Output: ~~~~~ 5 ~~~~~ The 5 subsets that fit between -1 and 2 are : {} , {$a_1$},{$a_1$,$a_2$},{$a_1$,$a_2$,$a_3$},{$a_2$,$a_3$}. I did the math and I think I got the task, I got how to solve it, I just don't know how to implement it. My way is calculating the sum of all elements, and then reducing each element at a time to produce more subsets, and from those subsets to produce even more (unique of course) subsets, all while checking if each subset is within range of given [A,B], but I don't know how to implement it, I've never done this type of a task before. My way would have time complexity of O(2^n) and constraints on this program are 1<n<=34, -2e7 <= $a_i$ <= 2e7, -5e8 <= $a_i$ <= 5e8, would this ev...
checking if each subset is within range of given [A,B], but I don't know how to implement it, I've never, ) subsets, all while checking if each subset is within range of given [A,B], but I don't know how

Read more »

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

 
 
 
 
25.
By Retired_MiFaFaOvO, history, 3 years ago, In English
A problem collection (Spoiler Alert) SPOILER ALERT : If you didn't solve the problems in NEERC and you want to enjoy the problems, please don't read. <spoiler summary="Spoiler"> It looks there are few problems about general graph matching in the community. And there are a few teams who solved problem B in NEERC both online and onsite. However, the reduction from maximum cost perfection matching to this problem is simple to me. So I want to share some problems for practice. You can find the template [here](http://uoj.ac/problem/81/statistics) and [here](http://uoj.ac/problem/79/statistics). The [shortest code](http://uoj.ac/submission/282287) of the maximum cost matching problem is about 5.7k. There is a simple way to find the cardinality of the maximum matching, which is half of the rank of the Tutte matrix. We can use Gaussian elimination to compute the rank of a matrix. By the way, if the maximum cost is no more than $W$, we can also find the maximum cost matching by Tutte matrix and polynomial interp...
2. Given an undirected weighted graph $G$, find a minimum weight subset $E$ such that each vertex, 7. Two matching. Given an undirected weighted graph $G$, find a minimum weight subset $E

Read more »

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

 
 
 
 
26.
By KADR, 10 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...
1. $M' \subset M$

Read more »

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

 
 
 
 
27.
By slowerThanSnail, history, 21 month(s) ago, In English
Count no. of subsets having xor k Hi everyone, recenetly there was a hiring [challenge](https://www.hackerearth.com/challenges/hiring/jpmc-se-2019/) by JP Morgan on HackerEarth, and this problem was there. <br> **Problem statement :** <br> Given an array of N integers and an integer k, <br> let cnt1 = no. of subsets of array whose XOR is less than k, <br> cnt2 = no. of subsets of array whose XOR is equal to k, and <br> cnt3 = no. of subsets of array whose XOR is greater than k. <br> <br> You have to print value of expression : (cnt1 * cnt2) + (cnt2 * cnt3) + (cnt3 * cnt1) &mdash; (cnt1 + cnt2 + cnt3)<sup>2</sup> . <br> <br> **Constraints :** <br> 1 <= N, k, A[i] <= 100000. <br> There is O(maxVal * N) [solution](https://www.geeksforgeeks.org/count-number-of-subsets-having-a-particular-xor-value/) but obviously it's not feasible for given constraints. How to solve it with better time/space complexity ? <br> **Edit:** We had to print exp % 10<sup>9</sup> + 7. <br> **Edit 2:** Seems like I wrot...

Read more »

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

 
 
 
 
28.
By _maverick, history, 3 years ago, In English
Optimisation for a subset problem I faced this question among the challenges in another platform. I was unable to optimise my solution for this problem with it's constraints to pass within the time limit during the contest. The contest has ended and I feel it's time to learn. #### Question : You're given an array of size N. You need to generate all subsets for the given array. For each subset you need to OR it's minimum and the maximum element and add it to the result. You need to finally output the result after performing the mentioned operation for all it's subsets. Since the result can be large, output the result MOD by (10^9)+7. **Constraints :** 1<=N<=(2*(10^5)) Let Ai be the values of the array where 1<=i<=N 1<=Ai<=1000 #### My Approach : Since the problem demands to OR the minimum and maximum of each subset, I started by sorting the given array. Since the minimum element would have to appear with all the higher elements it pairs with, and the second minimum element would have to pair wi...
Optimisation for a subset problem, . You need to generate all subsets for the given array. For each subset you need to OR it's minimum, Since the problem demands to OR the minimum and maximum of each subset, I started by sorting, subset you need to OR it's minimum and the maximum element and add it to the result. You need

Read more »

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

 
 
 
 
29.
By AlexanderBolshakov, 10 years ago, In Russian
Subset Sum Problem - оптимизация <p>Собственно, расскажу о своей проблеме. SSP мне попалась в задаче J с финала ACM 2011 года. Я написал динамику по аналогии с рюкзаком за O(n) памяти и O(n * k) = O(n ^ (4/3)) времени (n - максимальное число, которое нужно разложить на слагаемые, k - количество элементов во множестве). Каким образом можно улучшить асимптотику? Можно ли как-то использовать две следующих вещи: а) множество состоит из квадратно-пирамидальных чисел, б) для разложения произвольного числа из промежутка [1; 1000000] требуется в худшем случае 6 чисел?</p><p>UPD. Буду особенно рад услышать финалистов :).</p><p>UPD2. От NEERC'а в прошлом году в финал вышли 13 команд, если не ошибаюсь, все они J решили. Почему такая гробовая тишина?</p><p>UPD3. По <a href="http://codeforces.ru/blog/entry/3485#comment-69863">комментарию</a> Артема я понял, что мое решение на финале бы прошло. Теперь буду рад услышать тех, кто загнали задачу <a href="http://livearchive.onlinejudge.org/">на испанском сервере</a> в ТЛ 3 секунды.</p>...
Subset Sum Problem - оптимизация

Read more »

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

 
 
 
 
30.
By mohamedeltair, history, 2 years ago, In English
Guaranteeing valid chosen segments in (Zero XOR Subset)-less problem? The question is about this problem: [(Zero XOR Subset)-less](https://codeforces.com/contest/1101/problem/G). The problem's editorial describes the solution as follows: First let $pr[x]=array[1] \oplus array[2] \oplus … \oplus array[x]$. If we divided the array into $k$ segments, where the right boundaries of these segments are (in increasing order) $i_{1}, i_{2}, …, i_{k}$ ($i_{k}$ must be $n$), Every segments subset-xor can be represented as $pr[i_{j}]$ subset-xor. Therefore besides maximizing $k$, we want to guarantee that the any $pr[i_{j}]$ non-empty subset has a non-zero XOR-sum. So we calculate the basis size of $pr[1], pr[2], …, pr[n]$ numbers (binary vectors) under $GF(2)$. Because the basis size will represent the maximum $k$ such that all $pr[i_{j}]$ are linearly independent under $GF(2)$ (no $pr[i_{j}]$ non-empty subset has a zero XOR-sum). My question is: from the calculated basis size $k$, we know that we can choose $k$ linearly independent (under $GF(2)$) $pr[i_{...
Guaranteeing valid chosen segments in (Zero XOR Subset)-less problem?, The question is about this problem: [(Zero XOR Subset )-less](https://codeforces.com/contest/1101, }, …, i_{k}$ ($i_{k}$ must be $n$), Every segments subset-xor can be represented as $pr[i_{j}]$subset

Read more »

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

 
 
 
 
31.
By fchirica, 8 years ago, In English
Codeforces Round #225 — Editorial [problem:384A] ================== Usually, when you don’t have any idea how to approach a problem, a good try is to take some small examples. So let’s see how it looks for N = 1, 2, 3, 4 and 5. With C I noted the coder and with * I noted an empty cell. ![ ](http://s28.postimg.org/8z1d7k399/New_Bitmap_Image.png) By now you should note that answer is N ^ 2 / 2 when N is even and (N ^ 2 + 1) / 2 when N is odd. Good. Generally, after you find a possible solution by taking examples, you need to prove it, then you can code it. In order to proof it, one needs to do following steps: 1/ prove you can always build a solution having N ^ 2 / 2 (or (N ^ 2 + 1) / 2) pieces. 2/ prove that N ^ 2 / 2 (or (N ^ 2 + 1) / 2) is maximal number – no other bigger solution can be obtained. For proof 1/ imagine you do coloring like in a chess table. ![ ](http://s27.postimg.org/ysqhphx0z/New_Bitmap_Image.png) The key observation is that by placing all coders on black squares of tab...
a is a letter from subset. Second, compute sum of |a, b|, where both a and b are letters from set. Third, is a subset of X (we can set some bits from X from 1 to 0 in order to obtain mask). For a mask, letters in 2 groups: first 12 letters and last 12 letters. The answer for a subset is sum of double, , but for last 12 letters (e.g. subset {a, c, d} corresponds to bitmask 2^0 + 2^2 + 2^3 = 13 in first half

Read more »

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

 
 
 
 
32.
By Abinash, 7 years ago, In English
Good Blog Post Resources about Algorithm and Data Structures There are many good blogs in **Codeforces Blog** where people describes about different **Algorithm and Data Structures** . Lets gather all the resources about **Algorithm and Data Structures** Explanations. You can comment bellow the link and about it . I will always update that post gather new resources.Hope ,its help all and inspire all to write new blog post in future :) Last added blogs link will have a tag **(New)** Resources: **C++ STL** [C++ STL: Policy based data structures]( /blog/entry/11080) [C++ STL: Policy based data structures. Part 2]( /blog/entry/13279) **String Processing** [Suffix tree. Basics. Building in O(nlogn)]( /blog/entry/11337) [Z Algorithm]( /blog/entry/3107) [Great resource for string algorithms]( /blog/entry/8008) [Aho-Corasick algorithm. Construction]( /blog/entry/14854) [Suffix tree. Ukkonen's algorithm](/blog/entry/16780) [On suffix automaton (and tree)](/blog/entry/22420) **New** **Data Structur...

Read more »

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

 
 
 
 
33.
By Kuroni, history, 18 months ago, In English
Codeforces Round #616 Editorial Hello everyone, this is the editorial for [contest:1290] and [contest:1291]! Along with the solution to each problem, we will have the theme and easter egg solution as well! I hope you all enjoyed our problems ( ´ ▽ ` )b [problem:1291A] Author: [user:265918,2020-02-02] <spoiler summary="Tutorial"> [tutorial:1291A] </spoiler> <spoiler summary="Implementation"> ~~~~~ #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int t; cin >> t; while (t--) { int n; cin >> n; string s; cin >> s; int odd = 0; for (char c : s) if ((c - '0') & 1) odd++; if (odd <= 1) { cout << "-1\n"; continue; } int cnt = 0; for (char c : s) { if ((c - '0') & 1) { cout << c; cnt++; } if (cnt == 2) break; } cout << '\n'; } return 0; } ~~~~~ </spoiler> [problem:1291B] Author: [user:hugopm,2020-02-02...
const int lim = 1000*1000 + 5; int nbElem, nbSub; vector subset[lim]; int side[lim]; int, for (int sub = 0; sub < nbSub; ++sub) { int st; cin >> st; subset[sub].resize(st, void dfs(int nod) { cnt[nod][side[nod]] = 1; for (int elem : subset[nod

Read more »

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

 
 
 
 
34.
By M.Mahdi, 5 years ago, In English
Codeforces Round #360 Editorial [+ Challenges!] Hi again! If you notice typos or errors, please send a private message. ### [688A: Opponents](http://codeforces.com/contest/688/problem/A) #### Solution Let's find out for each row of the given matrix if it is completely consisting of _ones_ or not. Make another array $canWin$, and set $canWin_i$ equal to one if the $i$-th row consists at least one _zero_. Then the problem is to find the maximum subsegment of $canWin$ array, consisting only ones. It can be solved by finding for each element of $canWin$, the closest zero to it from left. The complexity of this solution is $O(nd)$, but the limits allow you to solve the problem in $O(nd^2)$ by iterating over all possible subsegments and check if each one of them is full of _ones_ or not. <spoiler summary="C++ code"> ~~~~~ // . .. ... .... ..... be name khoda ..... .... ... .. . \\ #include <bits/stdc++.h> using namespace std; inline int in() { int x; scanf("%d", &x); return x; } const int N = 202; int ...
#### Solution Let $dp_{i, j, k}$ be true if and only if there exists a subset of the first $i, , the values $x$ such that for every subset of coins with the sum $k$, there exists asubset of this subset, - The $i$-th coin is not used in the subsets. - The $i$-th coin is used in the subset to make $j

Read more »

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

 
 
 
 
35.
By tejas.pandey, 7 years ago, In English
sum of all elements of all the subsets in power set Ankit has a set of numbers and has recently studied set theory. He has created a power set of this set and is writing a program to compute sum of all elements of all the subsets in power set. Power set of a set S is defined as set of all possible subsets of S. Set S consist of all the number from 1 to N. You need to calculate this sum for a given n. Example: Given N=3, S={1,2,3} P(S) = {{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}} answer = (1)+(2)+(3)+(1+2)+(1+3)+(2+3)+(1+2+3) = 24 Input First line has T, the total number of test cases. The next T lines contains a number N in each line. Output T lines giving answer as defined in the question for each N. Constraints 1<=T<=42 1<=N<=42 Sample Input 1 3 Sample Output 24 I have used bitmask to generate all the subsets to calculate the sum but it is giving tle. But i have seen people using below code but unable to understand the logic. ~~~~~ #include<stdio.h> int main() { int t; s...

Read more »

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

 
 
 
 
36.
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...
basis in such space and answer queries of $\relax k^{th}$ largest subset xor: [link](http://ideone.com

Read more »

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

 
 
 
 
37.
By ditoly, history, 3 years ago, In English
Codeforces Round #511 Editorial Hi, here is the editorial. Sorry for a long waiting. Have you enjoyed this round? I hope so. I know there are many things not so good and making some people unhappy :( I'm very sorry about that. Since this is my first round, I have many things not taken into consideration or done badly. I will try to improve them if I have my next round (I hope). Let's talk about the problems. The problems are mainly prepared by me, [user:ditoly,2018-09-22], which can be seen in D1D as "Little D". Also, my friends [user:ACMLCZH,2018-09-22] ("Little C") and [user:FallDream,2018-09-22] ("Mr. F", I don't know whether this name can explain Chinese word "F大爷" well, maybe "Master F" is better?) provided great helps. The statements are mainly written by me (with the help of [user:300iq,2018-09-22] and [user:cyand1317,2018-09-22] and some others, thanks!). My English is not so good, so it's frequent that I just understand the problem but other people get AC :( So I try to explain the problems in short st...
of integers can be divided by $p$ is the maximum size of the subset., , what about subset convolution?, A common, artful, interesting solution for subset convolutions! Even though it can solve, First we divide all numbers by GCD of them. Then we should find a subset with maximum number

Read more »

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

 
 
 
 
38.
By Ahnaf.Shahriar.Asif, history, 2 years ago, In English
DP Tutorial and Problem List Today I've listed some DP tutorials and problems. Actually, I made it for my personal practice. But I think It may Help others too. Update: I write stuff [Here](https://duoblogger.github.io) in Bengali. I probably have one or two basic DP tutorials too. If you understand Bengali, it may help. **Note: If you have some other tutorial links and nice problems, mention them. I'll add them here. It'll help me too.** ## Dynamic programming: * [Topcoder Tutorial](https://www.topcoder.com/community/competitive-programming/tutorials/dynamic-programming-from-novice-to-advanced/) * [Dynamic Programming,from novice to advanced](https://www.cnblogs.com/drizzlecrj/archive/2007/10/26/939159.html) * [Learn DP and other tricks](https://www.codechef.com/certification/data-structures-and-algorithms/prepare#foundation) * [Non-trivial DP tricks](https://codeforces.com/blog/entry/47764) * [Everything about Dynamic Programming](https://codeforces.com/blog/entry/43256) * [Digit DP 1](https://...
and K — Subset ](https://www.hackerearth.com/practice/basic-programming/implementation/basics

Read more »

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

 
 
 
 
39.
By vedhant, history, 11 months ago, In English
Bitmasks and subsets - Video tutorial Hi Codeforces Community, I have created a [video](https://youtu.be/Z3RfT93-vlI) where I will be covering over the **basics of bitmasking** and how to generate all subsets of a given set using bitmasking. In addition, I also cover a **clever trick** to iterate over all subsets of a given subset, also known as **submask enumeration**. If you are not familiar with bitmasking and/or submask enumeration, I hope this video will help you understand them. - Video link -> https://youtu.be/Z3RfT93-vlI Happy coding!
bitmasking. In addition, I also cover a **clever trick** to iterate over all subsets of a givensubset, cover a **clever trick** to iterate over all subsets of a given subset, also known as **submask

Read more »

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

 
 
 
 
40.
By I_Remember_Olya_ashmelev, history, 3 years ago, translation, In English
Codeforces Round #491 (Div.2), Editorial [problem:991A] <spoiler summary="Editorial"> There are 4 groups of students &mdash; those who visited only the first restaurant, who visited only the second, who visited both places and who stayed at home. One of the easiest ways to detect all the incorrect situations is to calculate number of students in each group. For the first group it is $A-C$, for the second: $B-C$, for the third: $C$ and for the fourth: $N-A-B+C$. Now we must just to check that there are non-negative numbers in the first three groups and the positive number for the last group. If such conditions are met the answer is the number of students in the fourth group. ~~~~~ int n1 = a - c; int n2 = b - c; int n3 = c; int n4 = n - n1 - n2 - n3; if (n1 >= 0 && n2 >= 0 && n3 >= 0 && n4 > 0) cout << n4; else cout << -1; ~~~~~ In general you are recommended to view [inclusion–exclusion principle](https://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle). Moreover the limitatio...
a subset of digits of the number seen by Vasya. It is possible to iterate through all the subsets in $2, where $k$ — total number of digits in the subset and $c_i$ — number of digits $i$:

Read more »

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

 
 
 
 
41.
By CleRIC, 8 years ago, translation, In English
Codeforces Round #226 (Div. 2) — Editorial [problem:385A] In this task required to understand that the answer max($a[i] - a[i - 1] - c$),$i$ = $2..n$ and don't forget that the answer not negative as Bear can not borrow in the debt barrel of honey. [problem:385B] In this problem you could write a better solution than the naive. To do this, you can iterate through the first cycle of the left index $l$ considered substring and the second cycle of the right index $r$ considered substring $(l \le r)$. If any position has been substring "bear", means all the strings $x(l,j)$ $(i \le j)$, also contain "bear" as a substring. So we can add to the answer $|s| - j + 1$ and exit from the second cycle. Also needed to understand, that if the string $x(l,j)$ was not a substring "bear", then in row $x(l,j + 1)$ substring "bear" could appear only in the last four characters. [problem:385C] In order to solve given problem, contestant should solve several subproblems : 1) First one is to compute amount of entries of eac...
for subsets of floodlights. Each subset would be represented as integer where $k$ bit would be $1$ if $k, For example, $dp[6]$ — ($6$ — $110_{2}$) is optimal answer for subset from $2$ and $3

Read more »

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

 
 
 
 
42.
By Ripatti, 10 years ago, translation, In English
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...
Compute the first dp dp1[mask]->sum. For each subset calculate sum of numbers of all atoms

Read more »

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

 
 
 
 
43.
By priyesh001, 4 years ago, In English
Two subsets with maximum equal sum Given an array S of N positive integers, divide the array into two subsets such that the sums of subsets is maximum and equal. **It is not necessary to include all the elements in the two subsets. Same element should not appear in both the subsets.** The output of the program should be the maximum possible sum. ~~~~~ Constraints: 1 <= N <= 50 1 <= S[i] <= 1000 Sum of elements of S will not be greater than 1000. Example: Input: 5 2 3 4 1 6 Output: 8 {Explanation: The two subsets with maximum sum are [1,3,4] and [2,6]} ~~~~~ I found this question in one of the interview challenge. I used the traditional sum of subsets logic to find all the possible sum for n elements and then tried to reconstruct non-overlapping subsets for a sum from the 2D DP array. I couldn't get all tc to pass. Is there any better easier solution for this?

Read more »

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

 
 
 
 
44.
By Night_Lord, history, 7 months ago, In English
Subset sum algorithm but with greater or equal sum In a subset sum problem always we have to find a subset which equals a given sum. Like in this example if $A=[1,2,3,4,5,15,21]$ and $sum=8$. Then the optimal subset would be [3,5]. But what if we consider all greater or equal subsets ? Like $[15]$,$[21]$ these are the minimum element subsets with sum greater or equals the given sum. How can I implement it? Although general subset sum algorithm I learnt is- ~~~~~ bool T[n+1][sum+1]; for(int j=1;j<=sum;++j) { T[0][j]=false; } for(int i=0;i<=n;++i) { T[i][0]=true; } for(int i=1;i<=n;++i) { for(int j=1;j<=sum;++j) { if(arr[i-1]>j) T[i][j]=T[i-1][j]; else T[i][j]=T[i-1][j]||T[i-1][j-arr[i-1]]; } } ~~~~~ Can I able to change some snipets of code and get my output value or I have to learn something else. Thanks in advance.
Subset sum algorithm but with greater or equal sum, Although general subset sum algorithm I learnt is-

Read more »

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

 
 
 
 
45.
By Lewin, history, 6 years ago, In English
Wunder Fund Round 2016 Editorials I hope you enjoyed the contest! Let me know if you find any errors below. Thanks for participating. Short solutions: - Slime Combining: You can just do what's described in the statement. Or, maybe you can do something with the binary representation of the number. - Guess the permutation: Find out where 1 should go. Then, find out where 2 should go, and so on. - Constellation: Start with a triangle and break it up. Or, choose a point and look at angles. Or, sort by x coordinate. - Hamiltonian Spanning Tree: Two cases: X > Y and X <= Y. For X > Y we can almost always avoid the spanning tree edges. For X <= Y we can do something greedy. - Robot Arm: Make a segment tree on segments. A segment is basically just a linear transformation, which can be described with three numbers. - Double Knapsack: Make the problem harder. Let's say I want a consecutive sublist of both lists that have equal sums. Then use pigeonhole principle to get an answer. - Combining Slimes: Use conditional e...
replace "set" with "array", and "subset" with "consecutive subarray".

Read more »

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