I'll just leave this here:

#include <bits/stdc++.h>
using namespace std;

struct _in {
    template<class T> operator T() {
        T x;
        cin >> x;
        return x;
    }
} in;

int main() {
    vector a(in, 0.0);
    for (auto& x : a) x = in;
    string s = in;
    cout << s << ' ' << a[2] << '\n';
}

Try with input

5
0.1 0.2 0.3 0.4 0.5
hello

Have a nice day

Tonight, I will pick twelve 3000 rated problems I haven't solved yet, try solving them, and track my progress. As usual, I will not look at editorials. Hopefully I will be able to solve them all before the year ends. I will not make this my highest priority and I won't try too hard. I will keep solving other problems in the meantime.

The problems are:

1. 341E - Candies Game (solved Jan 14, 12 days)
2. 843E - Maximum Flow
3. 1250D - Conference Problem (solved Jan 5, 3 days)
4. 573D - Bear and Cavalry (solved Jan 6, 4 days)
5. 1290D - Coffee Varieties (hard version) (solved Jan 8, 6 days)
6. 568E - Longest Increasing Subsequence
7. 788D - Finding lines (solved Jan 14, 12 days)
8. 698F - Coprime Permutation (solved Jan 3, 1 day)
9. 1342F - Make It Ascending (solved Jan 4, 2 days)
10. 1236F - Alice and the Cactus (solved Jan 3, 1 day)
11. 533A - Berland Miners (solved Jan 16, 14 days)
12. 1411F - The Thorny Path (solved Jan 22, 20 days)

My thoughts on the problems I have solved:

More coming soon!

Hi Codeforces, I want to tell you an interesting story.

There was this problem: 1264E - Beautiful League, the contest took place on December 5th, 2019. Now, I know it's not extremely hard, and its rating is "only" 2700, possibly lowered by the fact that it was known to some contestants from some other site. However, for some reason, I just couldn't come up with a solution, and I didn't want to read the editorial. I tried a few greedy approaches, and one of them even got to test case 206: 66478537.

So, this problem remained a mystery. I remember taking walks when I was bored, and sometimes thinking about this problem to try and solve it. But I just couldn't. I tried revisiting it at least 10 times over the past two years. It was one of my favorite problems to think about when I had some time to waste.

So anyway, after New Year celebrations, I went to sleep but I just couldn't fall asleep. Normally when this happens I pick up a problem and think about it until either I solve it or I fall asleep. So I picked up one problem, though it was quite easy (at least for me) and I solved it pretty quickly while lying in bed. It's this problem, if anyone cares: 1608D - Dominoes.

I still couldn't fall asleep, so I decided, why not try that old graph triangles problem? The idea was, there's no way I'll solve it, so I'll fall asleep quite easily. But to my shock, I did come up with just the right idea this time, and after some time I had the complete solution, all while lying in bed. I was very excited and happy about it but of course, I still couldn't fall asleep. So eventually I did fall asleep from sheer tiredness and the next day I implemented them both and got AC on the first try.

The moral of the story:

• I need to read a few more 3000+ problems and remember them, as backup.
• Revisiting old problems will eventually work if you give it enough time, especially if you keep solving other problems in the meantime.
• No pain no gain

Thank you for bearing with me

Never write binary search again*!

Often, solving a problem involves finding the smallest integer satisfying some predicate. The C++20 Ranges library allows us to run generic algorithms on ranges. Ranges can be backed by real data, such as ranges constructed from std::vectors, or they could be purely logical, such as std::ranges::iota_view.

This class can construct views given two values. In case those values are integers, the constructed range supports random-access, meaning that random-access algorithms such as std::ranges::lower_bound can run efficiently i.e. in $$$O(\log n)$$$. For example, std::ranges::iota_view(0, 5) returns a view representing integers $$$[0, 1, 2, 3, 4]$$$.

If you need to find the smallest integer value $$$v$$$ between $$$l$$$ and $$$r-1$$$ inclusive satisfying a predicate $$$p$$$ with the binary search property, or $$$r$$$ if it doesn't exist, you can do this in one line of C++ code:

auto v = *std::ranges::lower_bound(std::ranges::iota_view(l, r), true, {}, p);

The first argument of lower_bound is the range. We'll run our search on integers in $$$[l, r)$$$. The second argument is the projected value we'll be looking for — true, since we want the predicate to be true. The third value is the comparison we'll run on projected values. By default it is std::less<boolean>, it can be used in binary search since false < true is true in C++. It is important to note that your predicate $$$p$$$ must satisfy the binary search property: $$$p(x)$$$ implies $$$p(x+1)$$$ on the searched range. In other words, $$$p$$$ returns false for the first few (possibly zero) values, then it returns true and keeps returning true as you increase the argument. The last argument is the projection. This can be a function that accepts an integer as an argument, and returns a boolean. Often this will be a lambda expression.

The best part is that everything is inlined by the C++ compiler, making it as efficient, or even better than writing binary search manually.

For an example, check out my solution for 1589D - Guess the Permutation: 136076858

I'd also mention that std::ranges::iota_view can also be used in a range for-loop, making the code very easy to write if you give it a shorter name like I did in my submission.

*Mind you, this doesn't work on floats.

Take a look at this snippet:

#include <iostream>
#include <string>
using namespace std;

template<const char* tag>
struct html_element {
  string s;

  template<typename... Args>
  html_element(Args... args) : s((... + (string)args)) {}

  operator string() { return string("<") + tag + ">" + s + "</" + tag + ">"; }
};

const char html_c[] = "html";
const char body_c[] = "body";
const char h2_c[] = "h2";

using html = html_element<html_c>;
using body = html_element<body_c>;
using h2 = html_element<h2_c>;

int main() {
  string doc{
    html{
      body{
        h2{ "hello" },
        h2{ "world" }
      }
    }
  };

  cout << doc << '\n';
}

Thank you for your attention

Hi everyone,

The second round (qualifiers for the finals) of the contest organized by Bending Spoons was held today. The problemset was very interesting and challenging, although it's currently hidden by the organizers, I think I can recall most of it from memory.

https://www.codechef.com/BENDSP02

Let's discuss the problems in the comments. Here are the abridged statements. They may not be 100% accurate.

Problem 1: Given $$$n$$$ nonzero vectors with integer coordinates and different directions, find $$$n$$$ points such that the $$$i$$$-th point is in the same direction as the $$$i$$$-th given vector (looking from the origin), and these $$$n$$$ points are the vertices of a strictly convex polygon (in some order). $$$|v_i|, n \leq 50$$$, printed points can have coordinates up to $$$10^9$$$ by abs. value.

Problem 2: Given a directed graph on $$$n$$$ nodes, each edge is labeled with a positive integer. You start from node $$$1$$$ with energy $$$0$$$. When traversing an edge with label $$$x$$$, your energy becomes $$$e' := e/2+x$$$. For each node, find the infimum of the set of values of energy you can have in that node, or $$$-1$$$ if it is unreachable. $$$n, m \leq 100000$$$

Problem 3: This problem was interactive, there's an $$$n \times m$$$ board, where $$$n \leq m$$$ and both $$$n,m$$$ are odd, and it's tiled with $$$(nm-1)/2$$$ dominos (so exactly one field is not tiled), the arrangement of dominos is not known to you. You can ask about a field and as a reply you get the other field covered by the same domino, or some special value meaning that the field is not tiled. Figure out which field is not tiled by asking no more than $$$n(ceil(\log_2(m/n)) + 3)$$$ queries. The interactor may be adaptive. $$$n,m \leq 1000$$$

Problem 4: Given an array, in one move you must choose a subarray $$$[l,r]$$$ of length at least two, add $$$(r-l+1)$$$ times the minimum element of that subarray to your score, and replace those $$$r-l+1$$$ elements with one element, their sum. The game is finished when there's only one element left. What's the highest score you can attain? $$$n \leq 60$$$, $$$|a_i| \leq 10^9$$$, so, elements can be negative. In one subtask, all elements are nonnegative.

Problem 5: Given a rooted tree, for each node $$$u$$$ compute the number of ways to pick a set of paths (can be empty) starting from $$$u$$$ and going away from the root, such that any two of these paths intersect only in $$$u$$$, and the XOR of their lengths (measured in number of edges) is zero. Find the answer mod $$$998244353$$$. $$$n \leq 500000$$$.

Recently, in Codeforces Round 677 (Div. 3) I made a lot of hacks on problem F, and naturally, several users contacted me asking for the testcase I used. The problem is that even if I wanted to, I couldn't reply to all of them quickly, because CF imposes a limit of sending a message to 2 distinct users per hour, and even that seems to be implemented incorrectly, as I could only send one reply to one user, even though I only replied to two of them in total.

Can someone from CF HQ check whether this is implemented correctly and, if possible, implement a feature where message replies don't count towards the 2 persons per hour limit.

As the founder and CEO of Tadija Sebez fan club, I'm extremely happy to announce that TadijaSebez has won the Gold medal at the 2020 IOI! And not just gold, he also matched the score of Ildar Gainullin! 8th place!

After all these years, he's the first to bring a gold medal to Serbia. This is his final IOI, so hopefully he will continue on this path and get a Gold medal at the ICPC World finals sometime soon.

We're all very proud of you and your achievements!

TadijaSebez orz orz orz

The pattern of memory accesses plays a huge role in determining the actual running time of an algorithm. Many of you already know this fact, but do you know how big the difference can be? Take a moment to study this code:

#include <bits/stdc++.h>
using namespace std;
using namespace chrono;

vector<int> generate_random(int n) {
	mt19937 eng;
	vector<int> a(n);
	iota(a.begin(), a.end(), 0);
	shuffle(a.begin(), a.end(), eng);
	return a;
}

vector<int> generate_cycle(int n) {
	vector<int> a(n);
	iota(a.begin(), a.end(), 1);
	a[n-1] = 0;
	return a;
}

int main() {
	int n, t, q, z = 0;
	cin >> n >> t >> q;
	auto a = (t ? generate_cycle(n) : generate_random(n));

	auto start = high_resolution_clock::now();
	while (q--) {
		int x = q % n;
		for (int i=0; i<n; i++)
			x = a[x];
		z += x;
	}
	duration<double> dur = high_resolution_clock::now() - start;
	cout << "Time: " << dur.count() << '\n';
    cout << z << '\n';
}

The program performs $$$q$$$ walks of length $$$n$$$ on a permutation graph. With $$$t=0$$$, the permutation is randomly generated and with $$$t=1$$$ it's a cycle $$$0\rightarrow 1\rightarrow 2 \rightarrow \ldots \rightarrow (n-1) \rightarrow 0$$$.

Now try running this code using custom invocation with the following input: 10000000 0 10, and then 10000000 1 10. Can you guess the running time in both cases? Surely it won't take more than one second as there are only 100M memory reads... Also, you can probably guess that the second one will be faster, but exactly how much faster?

By the way, if I leave out printing $$$z$$$, the second part runs instantly, because the compiler correctly deduces that the entire while loop is unnecessary!

Tips to optimize your memory access patterns:

1. Avoid using multiple arrays to represent complex data structures. Instead, use arrays of structs. In particular, this applies to segment trees where you have to keep multiple numbers per node. There are cases where the difference is insignificant.

2. Use smaller data types. Using long long everywhere may slow your program down for multiple reasons, one of them is because your memory accesses will be more spread out = less cache friendly.

3. Try switching rows/columns of matrices. Make sure that the innermost loop runs on the last dimension of the matrix. In particular, when multiplying matrices, transposing the second matrix significantly reduces the running time.

Feel free to add suggestions!

I was solving this problem and I came up with an interesting idea which may in some cases be generalized to other DP problems. I don't think it's well known so that motivated me to write this.

When I submit a code, I get the error message "You cannot submit the same code twice", although this is clearly not the case. As far as I can see, I'm not the only person affected.

Hopefully this will be resolved quickly.

Does anyone have the problems, test cases and full results from this year's International Zhautykov Olympiad?

Congratulations to the winners! Pajaraja we are proud of you!

Some problems from ICPC-style contests or other online mirrors where texts are not added are missing. The lengths are not exact and are merely good estimates, for example, formulas are counted with three dollar signs at both the beginning and the end. Sample tests and notes (everything below samples) are not counted.

Here's the list:

1. (4426 bytes) 39G - Inverse Function
2. (4470 bytes) 1089J - JS Minification
3. (4591 bytes) 89B - Widget Library
4. (4619 bytes) 175F - Gnomes of Might and Magic
5. (4629 bytes) 523B - Mean Requests
6. (4911 bytes) 642A - Scheduler for Invokers
7. (5197 bytes) 1070B - Berkomnadzor
8. (5803 bytes) 1044B - Intersecting Subtrees
9. (6688 bytes) 921/01 — Labyrinth-1
10. (10637 bytes) 927A - BuberPool Taxi Optimization

I also have the list of 10 problems with the shortest statements, but all of them are from April's fools contests, I'll publish it when I filter them out. Well, all except this one: 401E - Olympic Games.

I've never seen anyone use this in competitive programming (or anywhere really) but it might be useful:

In C++ you can use the basic_string class template instead of vector for "simple" types [1]. It works just like vector but also allows you to use a few convenient member functions and operators just like with strings, most notably operator+ and operator+=. See the following code:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    basic_string<int> a;

    cin >> n;
    for (int i=0; i<n; i++) {
        int x;
        cin >> x;
        a += x;
    }

    a += a;
    a = a.substr(n/2, n);

    cout << (a + a).find({1, 2, 1}) << '\n';
}

[1] Although I'm not 100% sure, "simple" is any primitive type, std::pair of simple types, etc. Do not use this with vectors, strings, sets, maps and similar types. And for this reason please don't typedef vector as basic_string.

Today was supposed to be my day...

I needed only a single point of rating to become a grandmaster once again. And I had the best round of my life, taking the 6th place. Perhaps I would have skipped GM entirely and jumped straight into IGM, but to no avail. Of course, I also lost the chance to win a prize.

Sometimes, because of such events, which, unfortunately, happen all too often here on Codeforces, I'm thinking about abandoning CF for good. But I won't. I want everyone reading this to know that we all have bad days and bad rounds, and even if something as unfortunate as what happened to me today happens to you, you shouldn't give up. Your rating and material awards are not as important as your actual skill. And even if you never reach your desired rating or color or even skill level, the experience you'll have gained will last a lifetime. By participating in Codeforces rounds, you're always a winner.

-I

Hello CodeForces!

I know this happened to everyone — you made an interesting mathematical/algorithmic/whatever discovery and you were very proud of it and later you realized it's already well known. What's your story?

I'll start:

I discovered a variant of Mo's algorithm around 4 years ago. I was solving the following problem: Given a static array a₁, ..., a_n and q = O(n) queries. You are allowed to solve them offline. Each query has the form (l, r) and you're supposed to answer, if you were take all the numbers from a_l, ..., a_r, extract them into another array and then sort that array, what would be the sum of all elements at odd indexes?

This is how I was thinking: If all the queries could be ordered such that both their left ends and right ends form an increasing sequence, you could answer all those queries by adding/removing elements from some augmented balanced binary tree or segment tree in O(nlogn). Then again, the same is true when all the queries can be ordered such that their left ends form an increasing and right ends form a decreasing sequence. So, why not decompose the set of queries into such sequences? When we sort the queries by their left end, this becomes equivalent to decomposing an array of numbers (right ends) into several increasing/decreasing subsequences. Then I remembered a theorem which states that, in an array of n² + 1 numbers, there is always an increasing subsequence or a decreasing subsequence of length n + 1 — this means that we can decompose any array into such sequences, in time — perhaps there is a better algorithm but this was good enough for my problem. The final complexity is — there are sequences of queries and each one can be solved in .

Also, what were your silly childhood discoveries?

I remember discovering, when I was around 7, that in some apartments you could run around in a circle through a sequence of doors while in others you can't — and I really loved those where you can! Later I found out that they were equivalent to cyclic/acyclic graphs.

Do you really hate tree rotations? This blog post is for you!

Recently, I've been solving 768G - The Winds of Winter and I came up with a solution which is so ridiculously overengineered that I think it deserves its own blog post!

I don't want to go over all the details of the solution. Instead, I want to demonstrate a nice way to implement and apply Persistent Set and Persistent Array data structures and share a few ideas some may find interesting.

Basically, what I wanted to do is compute for each node x of the rooted tree a set, which would contain the sizes of all subtrees of x. In other words, if we denote sz(y) — the size of the subtree rooted at y, I want to compute the set for all x. We also want this set to have some lower_bound and upper_bound functionality.

Obviously, just storing these sets in a normal way would require O(n²) memory, so we need another approach. Let's use the same idea that we use when building persistent arrays. A persistent array of size 2^k, k > 0 will just have two pointers to persistent arrays of size 2^k - 1. A persistent array of size 1 will only store data. Our persistent set will be implemented as a persistent array of size at least N whose only elements are 0, 1. Positions at which there is an element shall have value 1, others shall have 0. In addition to the two pointers, each array node will also store the sum of all values. Basically our structure looks a lot like a persistent segment tree. This will allow us to implement lower_bound and upper_bound in . I used class templates to save some memory — this is another interesting idea and a topic on its own.

When you want to insert a number into the set, you don't actually insert it into the set, instead, you create a copy of the set and insert it there. The copying will create additional nodes and will take time. Here's the code:

this_t* insert(int x) {
  this_t* tmp = new this_t(*this);

  if (x < H)
    tmp->left = tmp->left->insert(x);
  else
    tmp->right = tmp->right->insert(x - H);

  tmp->total = tmp->left->total + tmp->right->total;
  return tmp;
}

this_t is the alias for pa<T, order>, the data type of the class for persistent sets. This is basically a persistent array of length 2^order. The first line just creates a shallow copy of the set the we are in. H is equal to half of the size of the current set. If x is less than this number, it means that this new value should be inserted into the left half. Otherwise, insert it into the right half. Again, insertion does not change the original but returns a copy, so we store that copy into tmp->left or tmp->right. We then recompute the total and return the temporary variable. Simple as that! The stopping condition is implemented in the class pa<T, 0>, see my submission 29446581 for more details.

But this is not all! We also need to be able to quickly merge two sets in our original problem! This appears impossible to do efficiently at first, but is actually quite simple and works very fast under some circumstances.

Let's see how we can merge (find the union of) two sets A and B. If one of the sets is empty, we return the other one. Otherwise, just merge the left half of B with the left half of A and the right half of B with the right half of A. Now you're probably asking yourself, how does this even make sense? This is obviously O(n) — and you're right, but, in the original problem, you will be merging small sets most of the time, and when one of the sets you merge is small (let's say it has g elements), this operation will create at most new nodes and take time. To understand this, think of what happens when one of the sets has 1, 2, or 3 elements.

Here's the code:

this_t* merge(this_t* arr) {
  if (arr->total == 0)
    return this;

  if (this->total == 0)
    return arr;

  this_t* tmp = new this_t(*this);
  tmp->left = tmp->left->merge(arr->left);
  tmp->right = tmp->right->merge(arr->right);

  return tmp;
}

When we calculate the sets on a tree, each set element will be merged into another set at most times so the complexity (both time and memory) is . You now have access to all the sets, for each node.

Last, but not least, let's see how lower_bound is computed. This, of course, does not create new nodes and should take time. We define lower_bound(x) as the smallest element y in the set such that y ≥ x. If such an element does not exist, we return the capacity of the set. Here's one possible implementation:

int lower_bound(int x) {
  if (total == 0)
    return 2*H;

  if (x < H) {
    int p = left->lower_bound(x);
    if (p == H) {
      return H + right->lower_bound(0);
    else
      return p;
  } else
    return H + right->lower_bound(x - H);
}

The problem here is that we sometimes call lower_bound in both directions. Fortunately, it is not so tragic, the actual complexity here really is . Why is that so? If the lower bound y for x does not exist, let's take y = N - 1 where N is the capacity of the set. We'll only visit array vertices which correspond to array segments which contain x or y and there's at most of them. We may also visit some others but we will exit immediately as their total is 0.

This concludes the tutorial for this implementation of persistent sets.

But why didn't you just use a segment tree for the problem? After all, you are given a rooted tree, you can flatten it by assigning DFS numbers...

As it turns out, the sets of sizes of subtrees of nodes are not the only thing I needed to compute. I also needed to compute , and also . Also, I wanted to try a new approach and see if it's efficient enough. And as it turns out, it is! :)

Here's the code: 29446581. Unfortunately, many comments are in Serbian and some names are meaningless.

Remark 1. It's also relatively easy to implement the order statistic query (find the kth largest element in the set).

Remark 2. You can also extend this to a multiset or a map<int, ?>.

Remark 3. You can save even more memory by delaying the creation of a subarray until it is needed, similar to the implicit segment tree. This allows us to create sets which can contain the full range of integers or even long longs, not just ones in a relatively small range, like 10⁵.

Remark 4. You can accelerate finding the union or intersection of sets if you also store a hash value of each subarray. Then, only merge two sets if their hashes differ. This works particularly well if you often need to merge similar sets (those which differ in only a few elements). In the original problem this was not needed but it's a nice idea nonetheless.

The contest was well balanced — scores for tasks were very close to standard scores. I hope you will find this editorial useful.

A :: k-String

Count the occurrences of each character. If any character appears a number of times not divisible by K, obviously, there is no solution. Otherwise, form the solution by first making the string B. The string B can be any string with the following property: if some character ch appears q times in the string B, the same character appears q***K** times in the given string. Now, just print that string K times.

B :: Special Offer! Super Price 999 Bourles!

The following observation will help you code the solution:

The largest number smaller than p ending with at least k nines is p - p MOD 10^k - 1 If the result turns out to be -1 , you can not reach a positive number with k or more nines. I will not explain the solution in detail — be careful when coding and have all the task statements in mind.

C :: Color Stripe

There are two cases to consider , when K=2 and when K>2. For K=2 there are only two possible solutions: the string "ABABAB..." and "BABABA..."

For both strings, simply count the number of differences between it and the given string and print a string with fewer differences.

For K>2 , decompose the string into contiguous single-colored sequences. Observe one such sequence. If it has an odd number of characters, say 2m+1, replace m characters with some other character in the following fashion:

AAAAA

becomes

ABABA

It can be observed that by changing less than m characters doesn't remove all pairs of adjacent identical characters. Similarly, for sequences of even length, say 2m characters, observe a character in the original string right after the last character of the observed sequence, and choose a character different from both. Example:

AAAAAAB

becomes

ACACACB

Again, it is sufficient and necessary to change m characters.

D :: Choosing Capital for Treeland

Arbitrarily root the tree at some vertex, say vertex 1. Now, all the edges are oriented either up (towards the root) or down (away from it). We will call upwards oriented edges red, and downwards oriented edges green. Now, with a single depth-first search, for each vertex, calculate its distance from the root (in number of edges) and the number of red edges along the path to the root. Also, count the number of red edges in the entire tree.

Now comes the interesting part: Observe that all edges outside the path from the root to vert should turn green, and those on the path should turn red.

The number of edges that need to be flipped if vert is chosen as a capital is given by:

RedEntireTree - 2*RedOnPath[vert] + RootDistance[vert]

E :: Parking Lot

Use a heap to maintain sequences of empty parking spaces as intervals. The comparison function for such intervals should return an interval which could store a car farthest from any other car, and if there is a tie, it should return the leftmost such interval. When inserting a car, pop the heap, look at the interval, place a car in the corresponding space and push two new intervals onto the heap. When removing a car, you should be able to find the two intervals which end at that car, remove them from the heap and push a new interval which forms when the two merge.