My submission — 277424035
My submission — 277339480
My submission — 277423597
2001D - Longest Max Min Subsequence
My submission — 277427421
2001E1 - Deterministic Heap (Easy Version)
My submission — 277431412
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3676 |
| 2 | Kevin114514 | 3659 |
| 3 | jiangly | 3640 |
| 4 | turmax | 3450 |
| 5 | tourist | 3408 |
| 6 | strapple | 3360 |
| 7 | Um_nik | 3354 |
| 8 | squareOf105 | 3348 |
| 9 | maroonrk | 3312 |
| 10 | idontwannadothis…e | 3191 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 153 |
| 2 | nik_exists | 151 |
| 3 | maroonrk | 150 |
| 4 | maspy | 149 |
| 5 | AmShZ | 146 |
| 6 | Um_nik | 143 |
| 7 | Errichto | 139 |
| 8 | adamant | 135 |
| 9 | BledDest | 134 |
| 10 | cry | 130 |
Let v be the element that remains when all the elements are equal.
What is the minimum no of operations required?
Let the number of times v be present in the array is fv.
Because we will have to delete all the elements not equal to v, the minimum no of operations required will be n — fv.
It turns out that this minimum is the answer ie we should never delete any element equal to v from the array.
Since we want the minimum number of operations required, we should choose the element with the maximum value of fv.
My submission — 277424035
Let $$$c_i$$$ be the index such that $$$p[c_i] = i$$$.
Lets look at $$$c_{i}$$$ and $$$c_{i+1}$$$.
If $$$c_{i} \lt c_{i+1}$$$,
Then when typewriter 1 writes $$$i$$$, it can also write $$$i+1$$$ without using carriage return operations, and typewriter 2 writes $$$i$$$; it will have to use carriage return operations for writing $$$i+1$$$.
Similar case for $$$c_{i} \gt c_{i+1}$$$
The sum of carriage return operations required by both typewriters will be $$$n-1$$$
The answer is -1 when $$$n$$$ is even.
For odd $$$N$$$, following pattern works
$$${1,3,5,7,9,11,10,8,6,4,2}$$$
My submission — 277339480
How can you check if U and V have an edge connecting them?
Notice that the answer for query(U,V) is the midpoint of the path between U and V.
In case the path has even elements, it returns an element close to U.
U and V will be connected by an edge if and only if Query(U,V) returns U.
Let's root tree at 1.
We will try to find the parents of all nodes.
Query(1,Y), let the result be MID1.
Now Query(MID1,Y), let the result be MID2.
Now Query(MID2,Y), let the result be MID3.
Keep going until Query(MIDK,Y) returns MIDK.
In that case, MIDK will be the parent of Y.
My submission — 277423597
2001D - Longest Max Min Subsequence
The length of the required sequence if no distinct elements in A.
We will greedily build the required sequence.
When we select an odd index element for S, we will try to choose an element as large as possible.
When we select an even index element for S, we will try to choose an element as small as possible.
Let the index of the last taken element be $$$i$$$,
and R be the largest possible index such that A[R...N] contains all the elements not chosen so far.
In case of odd index element for S, select the largest not chosen element in A[i+1...R]
In case of even index element for S, select the smallest not chosen element in A[i+1...R]
We can use a segment tree to query for the minimum and maximum range, and in the case of ties, we should choose the element with the smaller index.
Once we have selected an element in S, we should remove all its occurrences from the segment tree.
My submission — 277427421
2001E1 - Deterministic Heap (Easy Version)
Let's define 3 dp.
$$$dpValid[h][k]$$$ as the no of valid max heap trees of height h, and value on root is k.
$$$dpValidChild[h][k]$$$ as the no of valid max heap trees of height h, and value on root is k, and we have not done any operations on root yet.
$$$dpWays[h][k]$$$ as the no of different trees of height h, and value on root is k.
My submission — 277431412
Can the answer be YES if $$$N \ge 3$$$?
My submission — 276684814
In one of the optimal answer all the removed edges will be in some continous range.
My submission — 276687609
Let $$$S = A+B$$$.
Then $$$ A - B = 2*A-S = S - 2*B$$$
So Alice, should try to make her sum as large as possible, and Bob should try to make his sum as large as possible.1
If we sort $$$A$$$ in descending order. $$$A_1 \ge A_2 \ge ..... \ ge A_{N-1} \ge A_N$$$
Now, alice will take $$$A_1, A_3, .... $$$, and bob will take $$$A_2, A_4, .... $$$
Bob should only increase the piles which increases his score.
$$$A_2$$$ can be increase by $$$A_1 - A_2$$$ after which sorted order will change and Bob will not be able to increase score further.
My submission — 276689378
For each color $$$c$$$ and each node $$$u$$$ we can find the nearest nodes $$$i_u$$$ and $$$j_u$$$ such that $$$i_u \le u \le j_u$$$, $$$i_u,j_u$$$ are reachable from $$$u$$$ and $$$i_u,j_u$$$ have color $$$c$$$.
In shortest path, we will go through $$$x - \gt i_x | j_x - \gt i_y | j_y - \gt y$$$.
Try out this for all 4 colors.
My submission — 276697311
Its an practice problem on how to solve Nim game problems. Checkout Game Theory
My submission — 276702173
Exercise find out the bug in 276586233. I'm not sure if its hackable or not.
We do not need both the types of operations, we can either always merge or split, both of these are equivalent.
Look at both the sides of middle in palindrome.
If we are merging 2 elements on left side in optimal answer, we can replace this operations with splitting the mirror element on right side.
I will always merge now. My goal is to count the maximum no of elements I can get such that the final array is palindrome.
Let the final length be $$$f$$$, and initial length be $$$L$$$.
No of operations will be $$$L - f$$$
Lets say we want to find no of operations for subarray $$$L,R$$$.
First element will be obtained by merging some prefix, and last element will be obtained by merging some suffix. Let the first element of final array be $$$S$$$, ie last element of final array will also be $$$S$$$.
Let the $$$i,j$$$ be the subarray for remaining elements.
First element is subarray $$$L,i-1$$$ and last element is subarray $$$j+1,R$$$.
Let $$$P$$$ be the prefix sum for $$$A$$$.
Notice that $$$P_{i-1} - P_{L-1} = P_{R} - P_{j} = S$$$, suffling around we can get.
$$$P_{i-1} + P_{j} = P_{R} + P_{L-1}$$$,
So we can ground subarray based on $$$P_{R} + P_{L-1}$$$, and try to calculate answers for all subarrays with same value.
Let $$$dp_{L,R}$$$ be the maximum no of final elements we can get for subarray $$$L,R$$$.
$$$dp_{L,R} = 2 + \max dp_{i,j}$$$, among all $$$L /le i /le j /le R$$$ with condition on prefix sum mentioned above.
After grouping subarray with equal value of $$$P_{R} + P_{L-1}$$$, for processing a particular group, we can do sweep line algorithm with range max segment tree.
My submission — 276706737
I'm currently live discussion the problems.
I will add problemwise timestamp after the discussion stream.
You can join in if something in this blog is unclear or there are more questions.
Split the string such that A is interger formed using first 2 char.
Split the string such that B is interger formed using remaining.
A should be equal to 10, $$$2 \le B$$$, and 3rd char must not be 0.
One can use built in string to int functions. stoll
My submission — 276111053
Maintain set of seats occupied so far.
Then x is valid, if set is empty, or x-1 or x+1 is present in set.
My submission — 276114559
2000C - Numeric String Template
If length of s is not equal to n, the answer is NO.
Maintain pairing charToInt and intToChar.
First check is there exists an integer assigned to current char, and print NO if its not equal to current integer.
Then check is there exists an char assigned to current integer, and print NO if its not equal to current char.
Now, create pairing if required.
My submission — 276126482
We can first find the optimal matching and then do operations.
Greedy works.
We should try to match first L with last R.
We should try to match second L with second last R.
so on....
You prefix sums for finding range sum in $$$O(1)$$$.
My submission — 276137058
2000E - Photoshoot for Gorillas
For each cells we can find how may squares it can be a part of.
Greedy. Put maximum no to the cell that is part of maximum no of rectanges.
My submission — 276261729
2000F - Color Rows and Columns
For a rectangle $$$L*W$$$ if we paint $$$x$$$ rows and $$$y$$$ columns, minimum no of operations we need is $$$x*W+y*L-x*y$$$ operations.
We can first calculate minimum no of operations required if we want to earn $$$i$$$ points using this rectangle. $$$0 \le i \le L+W$$$
$$$dp_{i,j}$$$ denotes minimum no of operations required to earn $$$j$$$ points using first $$$i$$$ cells.
2000G - Call During the Journey
Lets say we have a blackbox function $$$f(t)$$$ which returns true if we can reach node $$$N$$$ if we start at time $$$t$$$.
If maximum leave time is $$$T$$$, then notice that -
- $$$f(t)$$$ is true for $$$ t \le T$$$, and
- $$$f(t)$$$ is false for $$$ t \gt T$$$
To check if we can reach node $$$N$$$ if we start at time $$$t$$$, we can use dijkstra algorithm with some modifications.
My submission — 276211659
2000H - Ksyusha and the Loaded Set
Notice that the answer will be one among $$$x+1$$$ for all the elements $$$x$$$ currently present in the set.
So for all of these nos $$$d$$$ we should maintain maximum $$$k$$$ such that $$$d, d + 1, \ldots, d + (k - 1)$$$ are not present in set.
We can ignore rest of the nos by assigning k=0 for remaining nos.
Maintain the set of no currently present.
When we want to add or remove some element $$$x$$$ from set -
We can use lower_bound, and then we can do it++ or it--, to find element just more than $$$x$$$ and just less than $$$x$$$ (say $$$y$$$) still present in the set.
Notice that maximum $$$k$$$ changes only for $$$x+1$$$ and $$$y+1$$$
To find the first element $$$\ge K$$$ for third query.
We can either do a binary search again or Walk on a Segment Tree to remove one $$$logN$$$ factor.
My submission — 276196913
1998A - Find K Distinct Points with Fixed Center
Chose $$$A_1 = (K*X_C,K*Y_C)$$$.
The remaining points such that sum of x coordinates and y coordinates is 0.
My submission — 275541733
1998B - Minimize Equal Sum Subarrays
Sum of all elements will be equal in both permutations.
So no of such $$$(i,j)$$$ is atleast 1.
Can you find a permutation $$$Q$$$ such that this count remains 1?
Set $$$Q_i = 1$$$ if $$$P_i = N$$$,
Set $$$Q_i = 1 + P_i$$$ if $$$P_i \lt N$$$, otherwise
Set $$$Q_i = P_{(i+1) \mod N}$$$
My submission — 275547485
1998C - Perform Operations to Maximize Score
My solution is a bit overkill, check out neal submission 275613185
Lets forget about $$$A_i$$$ and focus on $$$C_i$$$ first.
If we have and array of $$$N-1$$$ elements $$$A_i$$$ and binary array of $$$N-1$$$ elements $$$B_i$$$.
What is the maximum median we can get using atmax $$$K$$$ operations?
We can binary search for median.
We can directly count how many elements are more than mid, and how many elements we can make more than median.
Using segment tree, walk on segment tree and blah blah blah............
My submission — 275635373
1998E1 - Eliminating Balls With Merging (Easy Version)
Notice that at any point all the elements are sum of continous subarray.
Define a function solve(L,R) which returns true, if we can convert element with weight $$$\sum A_L+A_{L+1}+....+A_{R}$$$ into an element with weight $$$\sum A$$$
Use greedy, for fixed index $$$L$$$ and $$$R$$$, find a minimum $$$nxtL$$$ such that $$$\sum A_{nxtL} + A_{nxtL+1} + ... + A_{L-1} \le A_L+A_{L+1}+....+A_{R}$$$, make a direct jump to $$$nxtL,R$$$ segment.
Do similar for $$$nxtR$$$, and memorise all the answer of solve function.
My submission — 275608667
1998E2 - Eliminating Balls With Merging (Hard Version)
For each element $$$j$$$ there is a range $$$(L_j,R_j)$$$ in which it can be present as last elemt.
Modify the Solve function to now return what is the minimum index $$$L_j$$$, instead of boolean earlier.
Basically find minimum $$$L_j$$$ such that element $$$j$$$ can become $$$\sum A_1+A_2+...A_{Lj}$$$
Also for each index $$$i$$$ precalcute how much right it can go.
Use this to calculate $$$R_j$$$ based on $$$L_j$$$.
Otherway around you can also return this range in your solve function.
My submission — 275619707
$$$N/10$$$ will give you the digit at tenth place.
$$$N\%10$$$ will give you the digit at ones place.
My submission — 274717610
We can bruteforce all the possible rounds.
The possible pairings are -
My submission — 274958241
Alex can shower on one of the following times
- Before the first task
- Between any two tasks
- After all tasks
We should check if any of these break is $$$\ge S$$$
My submission — 274959892
Solve for the case when there are no ?.
392. Is Subsequence
If you look closely at algorithm in hint 1, notice that whenever we get ? in S, we can replace it with the char we want to match in T.
My submission — 274963318
For each no count the no of $$$\lfloor \frac{y}{3} \rfloor$$$ operations we will require to make it 0.
Make one of the nos 0. Then chose that no as $$$X$$$. $$$3*0 = 0$$$
Let $$$C$$$ be the no of operations we have done to get first $$$0$$$. Notice that we have multipled some other nos by $$$3$$$, $$$C$$$ times. So to make them equal to original no, we will have to do $$$C$$$ more operations with them as $$$Y$$$, and $$$X=0$$$
Notice that no of operations required to make $$$L$$$ equal to 0 $$$\le$$$ Notice that no of operations required to make $$$L+1$$$ equal to 0
So in optimal case, we should make $$$L$$$ equal to $$$0$$$ first, then make all the other nos $$$0$$$
To count the sum of no of operations required to make everything in range $$$L$$$ to $$$R$$$ equal to 0, use prefix sum
My submission — 274967855
Notice that we only need the no of 0s and no of 1s in subsequence to find the median.
So fix the no of 0s and 1s in subsequence and count the no of subsequences.
My submission — 274970725
What is the fastest way to check if a particular no exists in a sorted array or not?
Also notice that $$$log_2(999) = 10$$$.
Notorious coincidence?
I think not.
Lets query for area of of $$$A*A$$$ square instead of a rectangle.
If the checker returns $$$A*A$$$, we know that the missing no $$$\gt A$$$
If the checker returns $$$(A+1)*(A+1)$$$, we know that the missing no $$$\le A$$$
Looks similar to how we search in a sorted array?
My submission — 274972155
Also notice that $$$log_3(999) = 7$$$.
Notorious coincidence?
I think not.
Solution is similar to ternary search
Instead of one mid in binary search lets have 2 mids.
Divide $$$[L,R]$$$ range into almost 3 equal parts and see in which range missing no lies.
If we have 2 nos $$$A,B$$$ such that $$$L \lt A \lt B \lt R$$$.
Area of rectange will be $$$(A+1)*(B+1)$$$ is missing no lies between $$$[0,A]$$$
Area of rectange will be $$$A*(B+1)$$$ is missing no lies between $$$[A+1,B]$$$
Area of rectange will be $$$A*B)$$$ is missing no lies between $$$[B+1,1000]$$$
My submission — 274973808
Sum of odd and even is odd.
So we will have to remove even nos if array does not contain same parity in starting.
Most of the times we should do this type of operation -
Pick maximum odd no and minimum even no and do the operation.
If you cannot do the above operation pick maximum odd no and maximum even no and do the operation.
Now, you can always do the previous mentioned operation.
For any time $$$t \ge max(a_i)$$$, the set of lights on at time $$$t$$$ is same as set of lights that are on at $$$t+2*K$$$
So, the answer is always between $$$max(a_i)$$$ and $$$2*K+max(a_i)$$$, if it exists.
Because the pattern keeps repeating.
We can also find find the length of final array, and we can also find how many of the remaining elements must be $$$\ge$$$ median.
Let $$$F(X)$$$ be the maximum count of no we can have in the final array that are $$$\ge X$$$.
If we have this blackbox function, then we can binary search on the answer.
For calculating $$$F(X)$$$
If we create a new array C, where $$$C_i = 1$$$ if $$$A_i \ge X$$$, and $$$0$$$ otherwise.
Our problem reduces to finding maximum sum of C, we can get.
Lets create one $$$K* \left \lceil \frac{N}{K} \right \rceil$$$, matrix $$$M$$$, where $$$M_{ij} = C_{i*K+j}$$$.
On paths from $$$(0,0)$$$ to $$$(\frac{N}{K},N\%K)$$$, if we take only one element from each vertical column, the problem reduces to finding maximum sum of elements.
Solve for $$$N=1$$$
Notice, how are elements changing.
$$$A=(3,2,5,6,4)$$$, XOR of all elements $$$=6$$$.
Apply operation on first column. This changes to
$$$A=(6,2,5,6,4)$$$, XOR of all elements $$$=3$$$.
Apply operation on third column. This changes to
$$$A=(6,2,3,6,4)$$$, XOR of all elements $$$=5$$$.
Notice this is just swapping one element with XOR as an extra variable.
and so on.....
So among these $$$M+1$$$ elements, which final $$$M$$$ elements to keep, we can obtain any order of these $$$M$$$ elements.
One overkill approach to find minimum sum of absolute difference will by solving Travelling salesman problem
Now, you can do this independently for rows and columns.
Decide which $$$N$$$ rows and $$$M$$$ columns to take among $$$N+1$$$ rows and $$$M+1$$$ columns.
Then solve TSP, independently for rows and columns.
1993F1 - Dyn-scripted Robot (Easy Version)
Rows and columns are independent.
Let $$$cnt_{i}$$$ be the difference between no of $$$L$$$ and $$$R$$$, after first $$$i$$$ instructions.
Now, can you find the necessary and sufficient conditions when robot will be at $$$X=0$$$ and $$$X=W$$$?
Robot will at $$$X=0$$$ when $$$cnt_{i} \equiv 0 \mod 2*W$$$.
Robot will at $$$X=W$$$ when $$$cnt_{i} \equiv W \mod 2*W$$$.
When you insert a new character, cost of only 2 elements changes.
Type of cells that can split into 3 components has a fixed pattern.
You can always ensure that any prefix of odd length does not contains more than one extra opening bracket.
First read all the queries.
Group all queries with same $$$X$$$ together and try to answer them in one go.
For a fixed value of $$$K$$$, you can binary search to find the $$$j*k^{th}$$$ monster, the fight after which level will change.
Use Merge sort tree along with binary search for $$$O((N+Q)*log^4N)$$$ solution.
Walk on a Segment Tree to remove one $$$logN$$$ factor.
1991A - Maximize the Last Element
Find minimum possible value of each $$$A_i$$$, then check if it gives you $$$B$$$
Can you decrease maximum by half in one operation?
The answer is always <= 4.
If $$$u$$$ and $$$v$$$ both have same remainder when divided by 4, then $$$u \oplus v$$$ is a multiple of $$$4$$$.
What should be alice strategy?
Alice should always chose color 1 and 2.
When can Bob color all the vertices using 2 colors?
Bob can color all the vertices using just 2 colors if graph is Bipartite graph
Play as Bob if graph is Bipartite graph and Alice otherwise.
The answer is always YES, if $$$R-L \gt C$$$ for some $$$C$$$
Greedily take Cow as long as you can.
Just print all index $$$A[i*K][j*K]$$$
Bruteforce works, now analyse why it works.
Replace all 0 with -1. Now all segments with equal 0 and 1 have zero sum.
Instead of counting segments inside each range. For each substring with zero sum, count segments it is a part of.
Greedy, always take the index with maximum value of $$$A-i$$$
Binary search on the value you will add in $$$k^{th}$$$ operation.
Delete one road, now path between any pair of friends is unique. Try to count paths which do not lie between any pair of friends.
Given an array A, and multiple queries $$$L_i$$$ and $$$R_i$$$. Can you find the minimum value in this range, and how many times it appears?
A follow-up on Topcoder and Competitive Programming.
TCO 2023 will be the last TCO?
(Virtual) TopCoder Open 2023 Finals cancelled as well.
I found the following announcement on topcoder discord.

Hello everyone! I'm happy to announce the 27th stage of the 2nd Universal Cup. It will be held from April 6 to April 7. You can choose between one of seven possible time windows.
The problems were originally used in the ICPC Contests prepared by our team. Namely (ICPC India Online Round, Kanpur Regional, Chennai Regional, Amritapuri Regional, and Asia West Continent Final). If you participated, please refrain from participating in this stage of the Universal Cup.
We are planning to organise one more stage using the remaining contest problems.
Setters and Testers: kevinsogo Shisuko jtnydv25 IceKnight1093 aryanc403 Dragonado xennygrimmato ritul_kr_singh kshitij_sodani PraveenDhinwa Vichitr mexomerf JaySharma1048576 T1duS magga rivalq
We would like to give a special thanks to the CodeDrills teams (deepa_panwar Balajiganapathi Vichitr) for developing & sharing the contest with us. Thank you!
Universal Cup is a non-profit organization dedicated to providing trainings for competitive programming teams. Up to now, there are more than 700 teams from all over the world registering for Universal Cup.
A more detailed introduction: https://codeforces.me/blog/entry/118679
Register a new team: https://ucup.ac/register (the registration request will be processed before each stage)
Results of the past stages: https://ucup.ac/results
Terms: https://ucup.ac/terms
Ratings: https://ucup.ac/rating
You will be able to participate in the UCup contest in the following time windows:
02:00 (UTC) on Saturday — 07:00 (UTC) on Saturday
05:00 (UTC) on Saturday — 10:00 (UTC) on Saturday
08:00 (UTC) on Saturday — 13:00 (UTC) on Saturday
11:00 (UTC) on Saturday — 16:00 (UTC) on Saturday
13:00 (UTC) on Saturday — 18:00 (UTC) on Saturday
15:00 (UTC) on Saturday — 20:00 (UTC) on Saturday
18:00 (UTC) on Saturday — 23:00 (UTC) on Saturday
Hi Codeforces,
ICPC Amritapuri 2023 Regionals Round will happen this Sunday on CodeDrills.
Live commentary: We will be live on ICPCLive channel. We will start once the contest starts.
P.S. — All of the problems will be non-interactive, please read the guide of interactive problems before the contest.
P.P.S. — Some problems may have subtasks, so choose problem-solving order wisely.

Upd: We are live now. Sorry for the initial hiccups.
Upd 2: Closing ceremony and solution discussion stream — https://youtu.be/txbyFVl5kBg
Hello everyone,
Upd: Livestream has been scheduled. Time in your timezone. You can tune in here. Upd2: We recorded it with live audience today. Audio was lagging at some places. I will edit it by next week and upload it.
I wanted to share some exciting news with you. Recently, I launched my YouTube channel and created a community Discord server. Up until now, I've mainly focused on hosting post-contest discussion streams on my channel. However, I have plans to diversify the content.
To kick things off, I'm thrilled to announce that I've invited my arch-rival, and my best friend, TheOneYouWant, to join me for an Ask Me Anything (AMA) session on my channel. We are planning to record this AMA sometime next month.
Shubham (aka TheOneYouWant) is one of my best friends I've met through CP. He started CP after taking a programming class at IITB, and soon became obsessed — he ended up qualifying for WF thrice! After graduating from IITB, he went to grad school at Stanford, and now works as a software developer at a quant firm in New York. He's enjoyed teaching through his years; he used to teach for math olympiads through undergrad, and was head TA for algorithms in grad school. In his free time, Shubham likes to read manga, play badminton, and write blogs. Often, he's thinking about the next random thing to get obsessed with...
Feel free to ask anything you're curious about, although he can't guarantee he'll answer every question. If you're interested in following TheOneYouWant on his journey/reading more about his thoughts, consider following him on Twitter here and his blog here.
Hi Codeforces,
ICPC Kanpur 2023 Regionals Round will happen this Saturday on CodeDrills.
Live commentary: We will be live on codedrills youtube channel. We will start once the contest starts.
P.S. — All of the problems will be non-interactive, please read the guide of interactive problems before the contest.
P.P.S. — Some problems may have subtasks, so choose problem-solving order wisely.
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
int main(void) {
std::set<int> s;
return 0;
}
It fails to compile with error In file included from /usr/include/c++/13.1.1/string:43, from /usr/include/c++/13.1.1/bitset:52, from /usr/include/c++/13.1.1/x86_64-pc-linux-gnu/bits/stdc++.h:52, from a.cpp:2: /usr/include/c++/13.1.1/bits/allocator.h: In destructor ‘std::_Rb_tree<int, int, std::_Identity<int>, std::less<int>, std::allocator<int> >::_Rb_tree_impl<std::less<int>, true>::~_Rb_tree_impl()’: /usr/include/c++/13.1.1/bits/allocator.h:184:7: error: inlining failed in call to ‘always_inline’ ‘std::allocator< <template-parameter-1-1> >::~allocator() noexcept [with _Tp = std::_Rb_tree_node<int>]’: target specific option mismatch 184 | ~allocator() _GLIBCXX_NOTHROW { } | ^ In file included from /usr/include/c++/13.1.1/map:62, from /usr/include/c++/13.1.1/x86_64-pc-linux-gnu/bits/stdc++.h:152: /usr/include/c++/13.1.1/bits/stl_tree.h:662:16: note: called from here 662 | struct _Rb_tree_impl
Compilation command — time g++ -static -DONLINE_JUDGE -O2 -std=c++20 $$${file} -o $$${file}.exe
G++/GCC version g++ (GCC) 13.1.1 20230429 Copyright (C) 2023 Free Software Foundation, Inc. This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
When, where and how to report it?
Update: GCC Bugzilla
Hi Codeforces,
ICPC Asia West Continent Final Contest 2022 will happen ~10 hrs from now on CodeDrills.
Live commentary: We will be live on codedrills youtube channel. We will start once contest starts.
Contest Details
P.S. — All of the problems will be non-interactive, please read the guide of interactive problems before the contest.
P.P.S. — Some problems may have subtasks, so choose problem-solving order wisely.
Update: Live ranklist
We plan to start live commentary 1 hr into the contest. Commentry URL
Update 2 — Credits
Chief Judge: Jatin jtnydv25 Yadav
Setters: Jatin jtnydv25 Yadav, Nishank IceKnight1093 Suresh, Jeroen Op de jeroenodb Beek, Vsevolod sevlll777 Lepeshov, Arul flamestorm Kolla
Testers (excluding setters): Aryan aryanc403 Choudhary, Chaithanya Dragonado Shyam, Vaibhav xennygrimmato Tulsyan, Ritul Kumar ritul_kr_singh Singh, Kshitij kshitij_sodani Sodani, Praveen PraveenDhinwa Dhinwa, Siddhartha gravito12345 Srivastava, Konstantin miagkov Miagkov
Codedrills platform: Deepa deepa_panwar Panwar, Balajiganapathi Balajiganapathi S, Swati Panwar, Vichitr Vichitr Gandas
Rcd: Prof. Phalguni Gupta
Results
Final ranklist
1. facelessmen3.0 (IIT Kanpur) — satyam343 udhavvarma03 avi0000
2. Ab_Ki_Baar (IIT Kharagpur) — professor_flux harsh639 RahulChugh
3. Yorozuya Forever (IIT Madras) — Teja-Smart blitztage Nisanth
We will try to hold one universal cup stage based on Amritapuri (Regionals+Online), and Asia West Finals problems.
Hi Codeforces,
ICPC Amritapuri 2022 Regionals Round is happening right now on Codedrills.
Live ranklist: https://icpc.codedrills.io/contests/icpc-amritapuri-2022-regional-round/scoreboard
Live commentary: We will be live on codedrills youtube channel. We will be starting soon.
Update: We are live now.
Contest Details
- Contest Link — ICPC Amritapuri 2022 Regionals Round
- Date & Time — 2 April 2023, Sunday, 9:00 IST
- Duration — 5 Hours
- There will be 12 problems to solve
- Will follow standard ICPC scoring system (20 minutes penalty and 1 point per problem)
- The questions may not be sorted by difficulty
- Contest link — https://icpc.codedrills.io/contests/icpc-amritapuri-2022-regional-round
Edit — Credits
Chief Judge: Jatin jtnydv25 Yadav
Setters: Janmansh janmansh Agarwal, Aryan aryanc403 Choudhary, Jatin jtnydv25 Yadav, Chaithanya Dragonado Shyam, Vaibhav xennygrimmato Tulsyan, Mukesh Kumar, Jatin rivalq Garg, Vaibhav gvaibhav21 Gosain, Harris gamegame Leung
Testers (excluding setters): Aswin aswinashok44 Ashok, Mayank katana_handler Pugalia, Nishank IceKnight1093 Suresh, Ritul Kumar ritul_kr_singh Singh, Kshitij kshitij_sodani Sodani, Abhay Pratap abhayps Singh, Mohan Raghu mohanraghug Garimella, Ankur ankurkayal Kayal, Praveen PraveenDhinwa Dhinwa, Sai sinus_070 Avinash, Siddhartha gravito12345 Srivastava, Osama ......-......... Saleh, Anil marksman_ Kumar, Masood Alam
Platform Coordinators: Deepa deepa_panwar Panwar, Balajiganapathi Balajiganapathi S, Swati Panwar, Vichitr Vichitr Gandas
RCD: Maheshwara anandoham Chaitanya
Edit 2: Results
1. Paradigm Shift (IIT Indore) — codebuster_10 s_jaskaran_s nishkarsh
2. AuditPass (IIT Delhi) — tamajitbuba islingr magga
3. :(){ :|:& };: (BITS Pilani, Hyderabad Campus) — ExplodingFreeze JeevanJyot the_hyp0cr1t3
4. Maanzar (IIT Patna) — 100gods AwakeAnay TimeWarp101

Hi everyone,
We are looking for problem-setters to join the ICPC Asia West Finals 2022-23 panel and contribute interesting tasks. If you or anyone you know is interested, please fill this form. You are also welcome to join the team to help in testing, task preparation etc.
Problem setters would be paid with the following per-problem rates (difficulty determined by the contest admin)
For preparation, setting amount is split half-half between author and preparer.
Update: I removed tester compensation because I'm unsure how it will be distributed among multiple testers.
Update2: The judge does not have support for interactive problems, so we won't be able to accept those proposals either.
Update 2 — Thanks adamant for his Subset convolution interpretation blog. It does simplifies a lot of things.
Update 1 -
Let's consider this problem -
We have a function subset_convolution(A,B) it gives us Subset Sum Convolution of two sets $$$A, B$$$.
Let's say we array $$$A$$$ with $$$A[0]=1$$$ and we want to find A^K defined as $$$A$$$ convoluted with itself $$$K$$$ times.A^2 = subset_convolution(A,A)A^3 = subset_convolution(A^2,A)
...A^k = subset_convolution(A^{k-1},A)
The best I can think right now is using something on lines of fast exponential to achieve $$$O(log K*N^2*2^N)$$$ time where $$$2^N$$$ is the size of A. Also, there exist some solutions $$$O(N^3*2^N)$$$ using the fact that the majority of the multiplications will be with A[0] and permutations & combinations.
But it can be done in $$$O(N^2*2^N)$$$ using tricks well known at some places. Idk why it works tho.
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
TLDR — Just me rambling about the old ARC problem I was solving for the last 3 days. Something "set power series" similar to "power series for polynomials" I came across and I have an iota idea about it right now. Also amplifying some unanswered bugaboo related to it in the discussion of that ARC round. Spoiler is just very very briefly mention different solutions I had for ARC105F problem.
I vced ARC 105. Then while upsolving/reading the editorial of F — Lights Out on Connected Graph along with comments on discussion page. I came across a non trivial solution to that problem by Elegia under the view of "set power series".
It took me multiple readings of atcoder editorial to come up with one $$$O(2^n*m+n*3^n)$$$ soln then I was able to verify equations mentioned along with defined logarithm (by sheaf) of 'set power series' would indeed give a correct solution for this problem. But it's too slow here.
At first, I tried doing some minor optimisations to pass it since it just had an extra "n" factor compared to intended time complexity and "n" was just 17 here. Nothing worked out. The next day I optimised that subset convolution and came up with an $$$O(2^n*m+n^4*2^n)$$$ soln I was expecting an AC since it should be faster than the previous soln. But again TLE. Later I looked at some redundant calculation in that subset convolution solution and was able to optimise it to get one $$$O(2^n*m+n^3*2^n)$$$ soln. It barely gets an AC.
Then I looked at the fastest solution to that problem and came across maroonrk's submission of that problem. I was counting ordered partitions in that logarithm and dividing by $$$|P|!$$$, while counting them as unordered would remove that extra "n". One more day, I had $$$O(2^n*m+3^n)$$$ soln (the one mentioned in editorial) and $$$O(2^n*m+n^2*2^n)$$$ soln (the one mentioned by Elegia).
So I now have 5 different solutions for this problem but the story doesn't end here especially because of dario2994's and mmaxio's comments.

The logarithm of 'set power series' is a function $$$g(x)=\sum_{S} g_{S} x^{S}$$$ such that $$$f(x) = \sum_{S} (\sum_{\mathcal{P}} \prod_{P_i \in \mathcal{P}} g_{P_i}) x^{S}$$$, where the inner summation goes over all unordered partitions $$$P$$$ of $$$S$$$.

dario2994 submission on the same problem implements a small library for subsets with functions namely and/or/xor/subset convolutions along with log and exp of set power series.
(First to answer dario2994 comment — Yes, there does exist a clever way (and maroonrk's submission) to compute subset convolution.)
I did asked some of my friends and seniors doing MATH major — where can I read formal definitions of "set power series" since googling it just gave me useless results and none of them ever heard it.
Q1 — What exactly is the definition of exp of set power series? (One implemented by dario2994 and mentioned by mmaxio). Where can I read about more similar definitions?
mmaxio mentions Lu Kaifeng's report, googling about his report along with keywords such as "set power series" doesn't yield helpful results. But then I came across this blog. It has a code snippet and mentions For details, please refer to the 2015 Proceedings of the National Training Team Lu Kaifeng, "The Properties and Application of Set Power Series and Its Fast Algorithm".
It's a 17 page report published in 2015 in Chinese, I wasn't able to find an English version. Hence must be a well-known problem in China and hence a "trivial solution" by Elegia. I tried auto translating it using the method mentioned by z4120 in Auto-translated Chinese national IOI training team report papers but I messed up a step somewhere and ended up with just Chinese translated into Chinese, would really appreciate it if someone can translate it for me.
Q2 — mmaxio's comment looks like you can apply any function to the set power series by applying it to a "ranked" vector for each mask independently makes me much more interested in this. It opens the door to a hell of a lot of possibilities here (a reason for this blog here) integration, derivative, inverse, square root to name some among similar operations on polynomials and series.
I do remember the day when I learnt about the inverse and square root of a polynomial and was overwhelmed by it. On that day, I just concluded that "polynomials are just numbers". Later I have seen some problems which even used dp states as polynomials instead of integers. The observation "polynomials are just numbers" makes it easy for me to understand those editorials and those problems do excite me these days. Something similar for sets will for sure generalize it further.
Publishing this blog with the expectation that I would find more material to read about it since Google isn't my friend here.
Update 1 (solution) —
Just like polynomials exp(K*log(A)) simply works here. Don't ask me why because that's the whole point of this blog.
Proof by AC
Notification, when someone in your friend list writes a comment or creates a blog, is too annoying. Can someone make it opt-in?
/cc geranazavr555 MikeMirzayanov
Update 1: Apologies to 1595 people who got pinged due to this blog.
Update 2: I just realised codechef advertised their upcoming contest to 9298 people without spending a single penny. GG.
The 20th round of the first vintage Universal Cup is happening the weekend of June 17th. The contest is based on the Asia West Championship and Asia Amritapuri (Regionals+Online) problems.
As always, there are three time windows for you to join:
Please note that you can see two scoreboards in DOMjudge. The 'Local Scoreboard' shows the standings ONLY IN THE CURRENT TIME WINDOW. And the 'Combined Scoreboard' shows all participants, including the onsite participants, and the cup participants in the previous time windows.
Contest link: https://domjudge.qoj.ac/
Universal Cup Scoreboard: https://qoj.ac/ucup/scoreboard
About Universal Cup:
Universal Cup is a non-profit organization dedicated to providing trainings for competitive programming teams. Up to now, there are more than 600 teams from all over the world registering for Universal Cup.
A more detailed introduction: https://codeforces.me/blog/entry/111672
Register a new team: https://ucup.ac/register (the registration request will be processed before each stage)
Results of the past stages: https://ucup.ac/results
Terms: https://ucup.ac/terms
Ratings: https://ucup.ac/rating
hmehta didnt made an announcement on CF :/
SRM 756 will be held today.(in less than 30 mins) Atleast topcoder site says so.
Time: 16:30 UTC+5:30, April 25, 2019
Lets discuss problems after the contest.
MikeMirzayanov
Can you please add an unofficial checkbox on a user profiles contest page (e.g. — My Profile's Contest Page) similar to the submissions page.
Unofficial contests can include Unrated, out of competition contests. And maybe virtual participation as well.
Thank you.
We are trying to add our first gym contest for members of our college in our CF group.
We have added problems on polygon platform.
For adding problem in group We came across https://codeforces.me/blog/entry/10077?locale=en . We have followed preliminaries of Polygon and up to step 2 of CF.
For the third step, we need one directory at ftp://taskbook.codeforces.com . Unfortunately, it is showing the following error.
→ External storage error
The external storage was offline or malfunctioned during the last contest update. Please wait for some time, then go to the contest edit page and click "Save changes" to synchronize data
MikeMirzayanov please fix this issue asap. So that we can add problems for our group. We are planning to start the contest by Thursday evening. And we have less than 24 hrs.
We express gratitude to MikeMirzayanov and the rest of the team for the great Codeforces and the wonderful Polygon platform.
Upd: Issue was fixed within 15 minutes after this blog.
Maybe It was due to this blog or they were already working on it.
| Название |
|---|


