Extending from your idea, if we can upload an additional file template.cpp, CF can generate a dynamically-linked library which only needs to be compiled one time and can be reused in different problems. This will reduce judging time in contests.

Doesn't the code for floor(logb(x)) cause an infinite loop?

Times New Roman

Another problem: INC 2022 C — Powers of Two

Why would you expect both submissions to receive the same verdict when upper_bound does a different thing from lower_bound?

Try finding the diameter and centroid in the following tree:

20
1 2
2 3
3 4
4 5
5 6
6 7
4 8
8 9
8 10
8 11
8 12
8 13
8 14
8 15
8 16
8 17
8 18
8 19
8 20

Add #define _GLIBCXX_DEBUG on the top of your code before #include's.

int p = power(3, n);
for (int i = 0; i < p; ++i) {
    for (int j = i, k = 0; k < n; j /= 3, ++k) {
        cout << j % 3;
    }
    cout << "\n";
}

Similar to the power of two version but you can't use the bitwise operation here. You can also replace 3 with other positive integer to get a more generalized version.

You shouldn't compare floating-point values using the == operator.

I resubmit your WA 13 C++17 (64) solution and get AC by turning on excess precision, but I wouldn't recommend relying on this method to get AC though.

I don't know why your code compiles on clang. If you look at your submission, your code generates warning about non-const comparator:

In file included from ./Main.cpp:1:
/usr/lib/llvm-10/bin/../include/c++/v1/set:602:30: warning: the specified comparator type does not provide a viable const call operator [-Wuser-defined-warnings]
        static_assert(sizeof(__diagnose_non_const_comparator<_Key, _Compare>()), "");
                             ^
./Main.cpp:39:17: note: in instantiation of member function 'std::__1::set<node, comp, std::__1::allocator<node> >::~set' requested here
set<node, comp> card;
                ^
/usr/lib/llvm-10/bin/../include/c++/v1/__tree:976:5: note: from 'diagnose_if' attribute on '__diagnose_non_const_comparator<node, comp>':
    _LIBCPP_DIAGNOSE_WARNING(!std::__invokable<_Compare const&, _Tp const&, _Tp const&>::value,
    ^                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/lib/llvm-10/bin/../include/c++/v1/__config:1297:21: note: expanded from macro '_LIBCPP_DIAGNOSE_WARNING'
     __attribute__((diagnose_if(__VA_ARGS__, "warning")))
                    ^           ~~~~~~~~~~~
1 warning generated.

These are const member functions, which are not allowed to:

• modify the member variables inside its struct/class
• call any member function which is non-const

You can find more explanations here.

Comparator used in STL algorithms/containers is expected to be const member functions because it does not make sense to modify values inside a comparator.

Use this comparator:

struct comp{
    bool operator()(node a, node b) const {
        return (a.top < b.top);
    }
};

Adding either of #define _GLIBCXX_ASSERTIONS or #define _GLIBCXX_DEBUG "fix" the issue. Don't know why.

Is there any advantage in using unsigned long long instead of std::bitset?

How to handle the cycle in the DP when adding digit $$$0$$$ repeatedly?

Don't give them ideas!!!

Array index out of bounds.

Is it faster?

	auto cmp = [&dist](const int &a, const int &b)
	{
		return dist[a] > dist[b];
	};

	priority_queue<int, vector<int>, decltype(cmp)> pq(cmp);

I don't think you can write the comparator this way. If you update the value of dist[v], the order of nodes which are already inside pq prior to the update, will not automatically reorder themselves based on the new value of dist[v].

More detailed explanation here.

I added my code with assertions:

• priority_queue: 152769275
• set: 152769530

Thanks for the reply!

Of course, whether the template-recursive call will actually be executed does depend on n, but that's perfectly allowed!

This is what initially confuses me because the value of n is not known and therefore we can't know if the recursion will actually stop. But after playing around with the code, I suppose the compiler more or less only cares about the number of possible calls, whether it is finite and within the allowed depth.

... and std::min is constexpr since C++14*

So that is why it doesn't work on C++11 (the ternary operator method works well though).

How does this work? Shouldn't the value of n be known at compile time? This looks like magic to me.

Consider the simpler version of the problem:

Given an array $$$A$$$ of $$$N$$$ integers, you need to find $$$K$$$-th maximum sum subsequence of fixed size $$$L \leq N$$$.

For example, if $$$A = [9, 6, 4, 2, -1, -3]$$$, these are the subsequences of size $$$L = 3$$$ sorted by their sum:

Among all $$$\binom{N}{L}$$$ subsequences, the $$$3$$$-rd subsequence is $$$[9, 4, 2]$$$. This simpler version of the problem can be solved using Fracturing Search.

By inserting $$$N$$$ $$$0$$$'s into $$$A$$$, I was trying to reduce the original problem into the simpler version. Now, we are trying to find the $$$K$$$-th maximum sum subsequence of fixed size $$$N$$$ from the new array $$$A$$$ (new length is $$$2N$$$).

Using the previous example, $$$A$$$ would now become $$$[9, 6, 4, 2, \underbrace{0, 0, 0, 0, 0, 0}_{N}, -1, -3]$$$ and these would be its length $$$N$$$ subsequences:

However, this approach is apparently wrong because we would end up with a total of $$$\binom{2N}{N}$$$ subsequences instead of $$$2^N$$$ subsequences.

If we insist on solving the original problem using Fracturing Search, we would have to run $$$N$$$ separate fracturing searches simultaneously for each $$$1 \leq L \leq N$$$ and maintain it using something like Segment Tree.

I think this can be solved using Fracturing Search. To handle the different sizes of each possible subset, we can insert $$$n$$$ $$$0$$$'s into the array. Thus, on your example, $$$(8, 4, 2), (8, 4), (8, 2)$$$ can be seen as $$$(8, 4, 2), (8, 4, 0), (8, 2, 0)$$$. CMIIW.

You can solve it using Digit DP.

His CE 148547473 is suspicious. The code fails to compile because there is unknown keyword xlate, which is supposed to be template. I'm quite sure he used the find & replace functionality to replace temp into x, and not notice that he accidentaly changed the template's.

I added small changes to your solution and got Accepted. 147993909

Don't keep updating your blog with small changes every few minutes just to force it to stay on the recent actions.

You only added a single newline on your latest revision...

I'm using Windows and stdout isn't always flushed only when the program exits. Sometimes if the output is a quite long, stdout might get flushed before the program exits (and I don't usually use std::endl).

First of all, let's discuss the problem where $$$n=1$$$ and $$$a_1=1$$$.

The huge pictures in 2A slow down the loading of the page. The coordinates and sizes of the example triangles are not that large and there are extra space that could have been cropped out.

ISTP

If OP uses the same password on different websites, the attacker might be able to access the other accounts by getting the password of OP's Codeforces account. Moreover, the OP has his email shown to public on his profile.

You misread the problem. You need to assign the value $$$a_{l+k+i}$$$ to $$$a_{l+i}$$$, not the other way around.

In the solution of 2D/1B: $$$[x\le a_i\le y]$$$

What is the name of this square bracket expression? It seems to me that $$$[\text{true}] = 1$$$ and $$$[\text{false}] = 0$$$.

Edit: Iverson bracket

IMO "dynamic segment tree" is more suitable because we dynamically allocate memory for the segment tree. Whereas "implicit segment tree" might cause confusion as there is another term implicit graph, which is not anything close to this segment tree we are talking about.

Your solutions only works if user_ids is a permutation of $$$0, 1, ..., n-1$$$.

I think it is because of Microsoft Visual C++.

You will have to wait.

Um_nik is now worth $$$1$$$ cyan.

You can see that easily as you have two nested loop any of them have logN complexity.

But the inner for loop is not reset on every iteration of the outer for loop (the pointer i and j can only go up in the tree), so it should be $$$O(\log N)$$$ right? Similiar to how two pointer is $$$O(N)$$$.

for (int i = 0, j = 0; i < n; ++i) {
  while (j <= i && ...) {
    ++j;
  }
  ...
}

I try implementing the RMQ BIT (queries and updates in $$$O(\log N)$$$) though I am not sure if my implementation is fully correct. I have tried it on the following problems and it seems to be working fine.

• CF EDU Segment Tree, part 1, step 1, problem B, submission link (click here if you are unable to view the submission)
• CSES — Dynamic Range Minimum Queries, submission link

Could you explain how? From what I've read from cp-algorithms, we can only do the update if the new value is not greater than the current value.

Are you surprised to know that BIT can be used for arbitrary RMQ not only prefix?

For minimum query on prefix, is it possible to perform updates using arbitrary values?

My idea is to use stable sorting algorithm to sort the given integers based on their signedness. Thus, the array $$$[2, -2, 1]$$$ can be seen as $$$[+, -, +]$$$ or $$$[1, 0, 1]$$$.

I guess you are looking for stable sort. I don't think it is possible to solve the problem in $$$O(n)$$$ time and $$$O(1)$$$ space unless there are some specific constraints. CMIIW

I think the other person was trying to accuse you of cheating if you didn't help him on the other problems.

Can 131830101 be hacked? I didn't stop the while (k--) loop even after the queue (q in my code) is empty and my solution has extra $$$\log N$$$ factor because of std::set.

int p[] = {-1, n};
while (p[1] - p[0] > 1) {
    p[!f(p[0] + p[1] >> 1)] = p[0] + p[1] >> 1;
}
// p[0] == largest i such that f(i) is true
// p[1] == least i such that f(i) is false

It is possible but you will have to maintain the priority_queue manually using make_heap, push_heap, and pop_heap.

https://ideone.com/jBJc9w

MSI Dragon Center

Note the title of the blog.

Could you post the old editorial page without the edits? There were several helpful (at least for me) discussions about GCD and solution of 1549D - Integers Have Friends without segment tree and sparse table.

How can using long long instead of int cause WA?

i++ vs ++i.

8
16 14 13 13 12 10 9 3

Correct answer is 45, while your code outputs 48.

I found someone else's solution using greedy for problem D.

https://atcoder.jp/contests/abc204/submissions/23253738

Ignore.

These built-in functions promote the first two operands into infinite precision signed type and perform addition on those promoted operands.

Does anyone know where I can find more about this?

Open Telegram (joke).

You don't actually need to store the distances in a separate array and then sort it later. You can keep track of the current minimum distance and update it accordingly.

You also don't have to check whether you picked the same portal twice as the cost from $$$(1, 1)$$$ to $$$(n, m)$$$ without using any portal will be strictly cheaper.

115297135

The explanation counts the sheep starting from $$$1$$$ ($$$x_1, x_2, \dots$$$), while the code counts the sheep starting from $$$0$$$ (the variable cur).

In problem E:

Note that in the optimal solution the sheep with the number $$$m = \lceil\frac{n}{2}\rceil$$$ will not make moves.

Shouldn't $$$m = \lceil\frac{k}{2}\rceil$$$?

You don't need to check for that case because going from $$$(1, 1)$$$ to $$$(n, m)$$$ without using any portal will be strictly cheaper than using the same portal twice.

The code if (v[i]&mn != mn) is equivalent to if (v[i] & (mn != mn)). Check C++ operator precedence .

abaa

112208235

I changed scanf(" %s", &arr) to scanf("%s", &arr) and got AC. I have also ever faced similiar bug, but I don't understand the cause as well. Maybe somebody else might be able to explain.

For each vertice $$$v$$$ in the tree, calculate the absolute difference between the value of $$$v$$$ and the values of $$$v$$$'s predecessor and successor. Predecessor of $$$v$$$ is the vertice with the largest value smaller than the value of $$$v$$$ and successor of $$$v$$$ is the vertice with the least value larger than the value of $$$v$$$.

If $$$k = n \cdot n$$$, isn't it the same as the bruteforce bubble sort approach?

Can you give some numbers on how much faster WSL is (compared to CMD) on your local environment?

Hi. Could you implement the following features? Thanks in advance.

1. Custom keybinding for Detached Run (if possible, other editor functionalities too).

2. When I press Shift + Home, all the characters before the cursor will be selected, including the tab/space for the indentation. Can you fix it so only the characters after the indent are selected?

3. Detached Run without compiling, only running the executable in the terminal window.

Stars and bars

Imagine you need to fill a sequence of integers of size $$$10$$$ using only $$$1$$$, $$$2$$$, or $$$3$$$ so that the sequence is non-decreasing. As they are non-decreasing, all $$$1$$$'s have to appear in front of all $$$2$$$'s and so on, so we don't need to care about the order of these integers and we need only the number of occurences of each $$$1$$$, $$$2$$$, and $$$3$$$. Thus, we need to find number of solution of: $$$count_1 + count_2 + count_3 = 10$$$, with $$$count_0, count_1, count_2 \geq 0$$$.

Thank you. Apparently the link to the contest page is located on the top of the Overview page.

How do I register and participate? I opened the Contests page but there are only previous contests there.

Oops, I forgot that it is for 2020 only.

I think there is a bug. My highest rating increase is +151 but your website shows +101, which is my second highest rating increase. Also, my peak is 1791 while your website says 1789.

UPD: There is no bug.

Can anyone tell me why this didn't work for E?
Code

UPD: Fixed. Thanks Lain _______

Does this shorten compilation time?

In my laptop, there is a pre-installed app that could switch my laptop between performance/battery mode (not the one from Windows Settings/Control Panel). Compiling a hello world program (with bits/stdc++.h precompiled) takes 0.3-0.5s on performance mode and 1.2-1.4s on battery mode. Turning off Windows Defender reduces the compilation time by ~0.1s in my case.

I precompute the lowest prime factor for each $$$a_i$$$ (similiar to Sieve of Eratosthenes), then factorization can be done in $$$O(log_{a_i})$$$ by repeatedly dividing $$$a_i$$$ by its lowest prime factor (I think drayc's method is faster though).

103630714 (vector<int> lpf(N + 1))

Custom invocation.

Solve backtracking problems, especially those with lengthy implementation.

rainboy writes everything in C.

103495429

Do not use endl.

I think he is talking about div1B.

I wrote my solution here.

1. Ask everyone to stand (make $$$h_i \leq w_i$$$ for every $$$i$$$).
2. Sort them based on $$$h_i$$$ then $$$w_i$$$.
3. Now we know that the $$$i$$$-th person is at least as tall as all of the people who come before him ($$$h_i \geq h_j$$$ for every $$$j \lt i$$$).
4. Iterate through everyone and find the largest $$$j$$$ such that $$$j$$$-th person is strictly shorter than the $$$i$$$-th person ($$$h_i \gt h_j$$$). As they are already sorted, now we know that the $$$i$$$-th person is also taller than all of the people who stand in front of $$$j$$$-th person.
5. Now we have $$$j$$$ possible candidates that can be placed in front of $$$i$$$-th person. We no longer have to check whether they are shorter than $$$i$$$-th person or not, because we already know that from the previous step.
6. We need to find among the $$$j$$$ possible candidates, is there a person who is thinner than the $$$i$$$-th person. There could be more than one person who fits the criteria, so we will just greedily pick the thinnest person among those $$$j$$$ people and check if the thinnest person is thinner than $$$i$$$-th person.

I think reports could be implemented similiar to Recent actions tab. When a submission is reported, it would be displayed publicly in the Recent reports tab (sorted by the number of reports) and anyone will be able to check the reported submission. Similiar to contribution, a submission reported by higher rated users should also receive higher number of reports. Other features could be added to further improve the accuracy of reported submissions, e.g. 10 contest participations.

Could you predict my rating? Thanks in advance.
alwyn

Custom invocation.

To precompile the header:
g++ -std=c++17 -other-flags-here stdc++.h

To use the precompiled header:
g++ -std=c++17 -other-flags-here -o file_name.exe file_name.cpp

To check if gcc actually used the precompiled header:
g++ -H -std=c++17 -other-flags-here -o file_name.exe file_name.cpp

Make sure to compile your code with the same flags used to precompile the header.

Okay I was wrong. Thanks for pointing out.

NVM

Thanks for sharing. This can actually help during hacking phase.

In problem D1 and D2 of Codeforces Round 671 (Div. 2).

What is pretest 6 for div-2 D?

Can you share the problem and your submission? Since I learnt about std::function, I've always used it every time I need to write recursive code and have never gotten TLE or noticed significant slowdown in runtime.

And if anyone knows about cases where std::function doesn't work (too slow, etc), please let me know.