Fun fact, you can also write dynamic_bitset<__uint128_t> which is technically $$$O(\frac{n}{128})$$$! 260859954

Organizers aren't answering questions in the contest system so I will ask here:

1) In order to compute the perfect sum $$$S_e$$$, do we read input values as fp64 (double) or something more precise?
2) What happens when we convert fp16 infinity back to fp64? Does it become infinity or e.g. the max fp16 value?

pinging @ICPCNews

I doubt it will be faster, because __uint128_t is not a native type (the CPU can only handle integers up to 64 bits). Basically the compiler thinks __uint128_t is two uint64_ts, and operations involving __uint128_ts are translated to multiple instructions handling uint64_ts.

#include <cstdint>
std::uint64_t add64(std::uint64_t a, std::uint64_t b) { return a + b; }
__uint128_t add128(__uint128_t a, __uint128_t b) { return a + b; }

0000000000000000 <_Z5add64mm>:
   0:	48 8d 04 37          	lea    rax,[rdi+rsi*1]
   4:	c3                   	ret
   5:	66 66 2e 0f 1f 84 00 	data16 cs nop WORD PTR [rax+rax*1+0x0]
   c:	00 00 00 00 

0000000000000010 <_Z6add128oo>:
  10:	48 89 f0             	mov    rax,rsi
  13:	49 89 f8             	mov    r8,rdi
  16:	48 89 c7             	mov    rdi,rax
  19:	48 89 d0             	mov    rax,rdx
  1c:	48 89 ca             	mov    rdx,rcx
  1f:	4c 01 c0             	add    rax,r8
  22:	48 11 fa             	adc    rdx,rdi
  25:	c3                   	ret

In your solution, it is not just a vector, but a vector of vectors. And the test where it fails seems to have m=1, in other words you have a vector of a lot of vectors of size 1. So my theory is: vector itself has some overhead to store its size, capacity etc, so creating a vector of size 1 uses overhead+1 operations, but assigning a vector of size 1 to another vector of size 1 takes just 1 operation. So with the vector outside the lambda you have n operations, and with vector inside the lambda you have n*(overhead+1) operations.

Türkiye's team:

• Efe Güngör (efex12)
• Teoman Ata Korkmaz (tte0)
• Yunus Emre Artal (PieArmy)
• Mustafa Selim Özekinci (meLearnCode)

Note: they added more features to dynamic_bitset in a newer Boost version, but they haven't been added to GCC yet. So that's why I linked an older version of Boost's docs.

The fifth Huawei-CF optimization challenge was on the midway... Participants were still guessing evaluation details...

What a strong team! Good luck going for Türkiye's 4th gold.

Why the mention date of tolbi is newbie, his max is international master?

Thank you for participation! We hope you enjoyed the problems.

The editorial is currently unfinished, you can view the partial version here (all problems except H and J). We will post the full editorial on CF tomorrow.

Azerbaijan's team:

• Fuad Garayev (fuad720)
• Huseyn Agayev (Huseyn123)
• Aykhan Damirli (dmraykhan)
• Tahir Aliyev (Tahirliyev)

I think that the problem is that till now not so many countries have held selections i.e Ukraine selections camp will start only in a 2 days

I hope erray gets the right color this time.

I also asked questions, but organizers aren't answering the questions...

The announcement says "When a value is fp64 or fp32, we just use the native data types." , but I don't think this is very clear. This is because IEEE 754 allows several different rounding algorithms, as explained in https://en.wikipedia.org/wiki/IEEE_754#Rounding_rules , and is dependent on languages or compilers. (Python users may be in trouble because it doesn't support fp32 calculation in build-in functions.)

And some of mine tester's solutions while editorial is still in progress can be checked here.

My best guess is the following: the expected sum S_e is the exact sum of input values converted to binary64. The tester has a bug, and does not calculate the sum correctly for 3 of the 76 test cases.

Nummer_64 will win IOI2024!!

I have the result that there are $$$11219$$$ patterns to be considered for $$$6$$$ problems case. I ran the following C++ program for half an hour. In this case, the maximum point value was $$$30$$$.

#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

string to_string(const vector<int>& arr) {
	string res = "[";
	for (int i = 0; i < arr.size(); i++) {
		if (i != 0) {
			res += ", ";
		}
		res += to_string(arr[i]);
	}
	res += "]";
	return res;
}

int contain(int n, const vector<int>& g1, const vector<int>& g2) {
	int z = *max_element(g1.begin(), g1.end()) + 1;
	const int INF = 1012345678;
	vector<int> l(z, INF), r(z, -INF);
	for (int i = 0; i < n; i++) {
		l[g1[i]] = min(l[g1[i]], g2[i]);
		r[g1[i]] = max(r[g1[i]], g2[i]);
	}
	for (int i = 1; i < z; i++) {
		if (l[i] <= r[i - 1]) {
			return false;
		}
	}
	return true;
}

int main() {
	const int N = 6;
	const int LIMIT = 48; // Maximum determinant of 5x5 (-1, 1)-matrix
	string code = string(LIMIT - 1, 'o') + string(N, 'x');
	vector<pair<vector<int>, vector<int> > > pack;
	do {
		vector<int> v;
		int cur = 1;
		for (int i = 0; i < (LIMIT - 1) + N; i++) {
			if (code[i] == 'o') cur++;
			else v.push_back(cur);
		}
		vector<int> score(1 << N);
		for (int i = 0; i < (1 << N); i++) {
			for (int j = 0; j < N; j++) {
				score[i] += ((i >> j) & 1) * v[j];
			}
		}
		vector<int> comp = score;
		sort(comp.begin(), comp.end());
		comp.erase(unique(comp.begin(), comp.end()), comp.end());
		vector<int> g(1 << N);
		for (int i = 0; i < (1 << N); i++) {
			g[i] = lower_bound(comp.begin(), comp.end(), score[i]) - comp.begin();
		}
		pack.push_back(make_pair(g, v));
	} while (next_permutation(code.begin(), code.end()));
	sort(pack.begin(), pack.end());
	vector<vector<int> > groups;
	vector<vector<int> > levels;
	int pack_pre = 0;
	for (int i = 1; i <= pack.size(); i++) {
		if (i == pack.size() || pack[i - 1].first != pack[i].first) {
			groups.push_back(pack[pack_pre].first);
			levels.push_back(pack[pack_pre].second);
			for (int j = pack_pre + 1; j < i; j++) {
				for (int k = N - 1; k >= 0; k--) {
					if (levels.back()[k] != pack[j].second[k]) {
						if (levels.back()[k] > pack[j].second[k]) {
							levels.back() = pack[j].second;
						}
						break;
					}
				}
			}
			pack_pre = i;
		}
	}
	int Z = groups.size();
	vector<int> perm(Z);
	for (int i = 0; i < Z; i++) {
		perm[i] = i;
	}
	sort(perm.begin(), perm.end(), [&](int va, int vb) {
		for (int i = N - 1; i >= 0; i--) {
			if (levels[va][i] != levels[vb][i]) {
				return levels[va][i] < levels[vb][i];
			}
		}
		return false;
	});
	cerr << "Z = " << Z << endl;
	vector<bool> valid(Z, true);
	vector<int> idx;
	for (int i = 0; i < Z; i++) {
		if (valid[perm[i]]) {
			for (int j = 0; j < Z; j++) {
				if (j != i && valid[perm[j]] && contain(1 << N, groups[perm[j]], groups[perm[i]])) {
					valid[perm[i]] = false;
					break;
				}
			}
			if (valid[perm[i]]) {
				cout << "order = " << to_string(groups[perm[i]]) << ", scores = " << to_string(levels[perm[i]]) << endl;
				cerr << i << endl;
				idx.push_back(perm[i]);
				for (int j = 0; j < Z; j++) {
					if (j != perm[i] && valid[j] && contain(1 << N, groups[perm[i]], groups[j])) {
						valid[j] = false;
					}
				}
			}
		}
	}
	cerr << "idx.size() = " << idx.size() << endl;
	return 0;
}

Computing $$$f_7$$$ seems difficult. Did anyone try it?

evenvalue will win APIO 2024!

who became fifth at TST? wondering about the 5th place curse...

We can do that after the world final. Before that, we all need each other in a healthy state.

good luck for all participants

I'm in Hangzhou now, where it's held. Good luck!

I also suffered from the long queue last year, but unfortunately we always participate in the very first hours of the window and I don't have influence over this

Kinda delusional I would say

plot twist: he was downvoting

Username checks out

I was born in December 2008 ((((

You are 100% right! I changed the 2D vector to 1D, vector, and despite the defining the vector inside the loop, it was AC. 260881136

I learned a valuable lesson about overhead and debugging. Thanks!

PieArmy will win EJOI 2024!!!

I think the term "contiguous memory locations" clearly points to the memory location and for int data type in an array, 1024 and 1028 are considered contiguous. But for a BST, nodes allocated on the heap aren't on contiguous memory locations.

I think it may be related to the Cpp version on VS code, so you need update your C++ standard in VS Code to C++11 or later, where the initializer list is supported.

Try this

You can view them here.

You are 1 week late.

My second time participating Kotlin Heroes with 4 problems solved and D in the last (two) minutes!

The problems are really nice and it's fun to play with the syntax, hope the other rating contests can bring such excitement. Thanks AtCoder Custom Test as my Kotlin compiler!

Thank you guys for the cool contest!

Yes. There can be, but in general, in all of these olympiads, there is a fairly large reliance on sportsmanship or self honesty, like the team leader of any team gets the problems a lot earlier in both IOI and IMO (I don't know about other olympiads, but at least for these two I do know for sure), and if they want to, they can pretty easily share it with their team. But this obviously goes against the spirit of the olympiad (and in fact, I think for most countries, even if the team leader did that, no student would be willing to cheat), so like there's not a huge reliance on fully cheating proof regulation. Of course, they try their best, but in the end, it falls to the participants themselves to uphold the spirit of the olympiads.

In this case, when the result is a product of $$$G$$$ sums, then assuming the data is sufficiently mixed that the sums are uniformly distributed, the probability that none are zero is $$$(1-1/MOD)^G \approx 1-G/MOD$$$, so it's not very likely to turn out zero by coincidence.

However, when the result is a product of sums, we should assume that it's possible. It doesn't even need extra special effort, the sums are 0 at the start! We can write code naturally to express the result as $$$0^k \cdot p$$$ with $$$p \neq 0$$$, and update $$$k$$$ and $$$p$$$ when a sum changes.

Most of the time, the result is a product of very few variables, so we tend to calculate results by multiplying new values of those variables instead of always calculating their modular inverses. In that case, it can still end up zero, it's just not visible as a source of bugs.

orz libobil

If you've already had enough practice, then just participate in rated contests frequently and you may reach expert even less than 2 months. I'm also new in CP(but I've learnt C programming and practiced for about one year) and registered my account several weeks ago and I'm now expert.

For 1), I have a simple algorithm that computes $$$S_e$$$. It may not give the theoretical $$$S_e$$$, but it seems to give the same $$$S_e$$$ as the evaluator. It may be that "as precisely as we can" != "as precisely as possible". I'm not sure I'm allowed to reveal more details.

I have no idea for 2).

Yes, he need stop, it is already written at the pilot course policy that,

You confirm that you will not in anyway distribute solutions

All 0 attemts left :)

I have to say that the most important thing to notice is to participate when the server is not heavily in queue. The problems are not bad but the queue (at least for 2023 when I was a participant and 2021 from what I heard) was unbearable.

https://mirror.codeforces.com/catalog

see General Advice/How to practice?

Copy from GeeksForGeeks. XD

In Russia T-shirts ships you my frend

List<T>.split when

I don't think there are SIMD instructions that can be usable to directly compute 128-bit values, at least on x86-64. For example, there's no instruction that compute "add with carry" which is necessary to compute 128-bit additions.

As I've shown in my experiment, GCC actually generates two adding instructions for a 128-bit addition (on x86-64). I tried various compile options but the compiler did not use SIMD at all. Similarly, a 128-bit multiplication expands to 3 multiplying instructions and 2 adding instructions, and a 128-bit division even becomes a library function call. It might be possible to use SIMD on bitwise operations, but GCC doesn't use SIMD for them, either. See this assembly output in Compiler Explorer.

True, I was thinking specifically for bitwise operations, where the fact that SIMD is packed multiple data doesn't matter. There's no bitset addition in principle.

Note that even some seemingly "elementary" bitset operations must be split into multiple assembly operations. Typical example: shifts, a massive pain in the ass to implement correctly.

☠️

This doesn't answer my doubts :(

1) I'm asking about the definition of $$$S_e$$$, which organizers calculate "as precisely as [they] can". Is it the sum of input values, each rounded to binary64 first? Or is it the precise sum of input values, only at the end rounded to binary 64?

2) What happens when we convert fp16 infinity back to fp64?

My country is also participating in the first hours of the first day of the window and this leaves me really surprised as it seems like the people who can determine the participate time doesn't learn from their own mistakes.

Congratulations!

Why not

“Fi( in) Aman(protection) -illah(Allah's) “

The problems can be solved on Eolymp.

Azerbaijan's team:

• Ahmed Gambarli (coolboy19521)
• Hasan Valiyev (Hasanv)
• Muhammedali Ahmadov (suleymancakir)
• Vagif Seyidzada (Hugs-From_adicto)

Auto comment: topic has been updated by moemen_pro (previous revision, new revision, compare).

Auto comment: topic has been updated by moemen_pro (previous revision, new revision, compare).

It doesn't even need extra special effort, the sums are 0 at the start!

Unfortunelly, me (and I think) and other people who made this mistake printed 0 until all poles can actually fall, and then started calculating when we don't have any real 0 (the ones that are 0 without mod).

Now I can see why this was just a lazy way solving this corner case.

Well, actually the wrong assumption was that the sum of non-zero number of fractions $$$\frac{1}{2^{d_{i}}}$$$ modulo large prime number is never 0. This is why we handled zero number of addends separately. Not as lazy as it seems :)

Us bro. It took me a lot of WA and RTE to figure out this case. Apparently people who directly bashed DS didn't had to handle to this case separately.

Yes. Bitsets in general help optimize $$$O(n^2)$$$ solutions

Nah you'd win

you should have gone for the head .

no.

Brazil's team:

• Pedro Rey (_rey) — 2nd time at IOI, 2 attempts left

• Arthur Lobo (LoboLobo) — 2nd time at IOI, 0 attempts left

• Felipe Lalic (Lalic) — 1st time at IOI, 0 attempts left

• Maria Clara (clarinha) — 1st time at IOI, 4 attempts left

.

It seems to be consistent with C++ double and float.

I don't think there is any such shortcut withuot hardwork. You just have to practice more and more on various rating range problems.

For anyone who wants to solve and learn more variations and techniques: https://mirror.codeforces.com/edu/course/2/lesson/6

I learnt about this while solving the same problem, redeclaring the 2-D vectors again and again N times leads to TLE first due to extra time being taken for memory allocation. When values are assigned instead of creating a new 2-D vector everytime then it's way faster.

When you define modulo as #define or constexpr or const, it becomes a constant value, doing modulo operations with a constant value is faster as compiler uses https://en.wikipedia.org/wiki/Barrett_reduction.

On the other hand doing modulo operations with an integer is slower since compiler performs normal division.

congrats for all teams who get medals

Check the about section in the website. Normally medium is enough.

As a first-time participant, I chose a relatively early participation time unaware of this issue :(

Hopefully the queue isn't that bad.

Why not Why

"... I'm not sure I'm allowed to reveal more details..."

Once the contest comes to an end, feel free to reveal all the details (procedure, source code, etc.) :). I'm eager to see a good solution in action.

I agree. evenvalue orz.

I wonder if using this can help pass some problems in $$$O(n^{2})$$$. Is this the case?

evenvalue I agree2.(2 is even) Hence by evenvalue thm, he will win APIO 2024!

Everyone who gives APIO 2024 is a winner!

I hope NeroZein doesn't clown like he did in TST day 2

2024 is even, which means evenvalue will win APIO 2024!

In which level you have to be to get at least bronze in APIO? (first time participating)

Instead of doing all that, you should run around with sticks and hit each other and see who is the last one standing. I believe that Shayan would win and it wouldn't be close.

:) Congratulations!

Good luck with that.

will there be a live raffle draw or will it be only mailed to the winners?

orz amin_2008

This is a serious suggestion btw cuz it is true shenanigans. Plus exercise increases cognitive ability, probably more so than solving problems 1000 points below your rating. Imma be mad disappointed if I click on the stream and I don't see something like this happening.

this contest was totally fixed and made me bored. abc352 is one of the boring contests ever. abc352 fixing and boring. abc353 is genuine and much interesting with sigma problems.

Counld you tell me how to fix a bad mindset?Thank you!!!

Well what I started doing is giving contests but this time not caring about rating, even if it means dropping 100 points in my rating, another think I started doing is trying to focus on Div.2 C while the contest is running even if I couldn't solve B or A, I would just skip them if it takes more than 30 minutes and start focusing on C (the one that i cant solve).

Also I started to take my sleep time seriously because it was one of the main reasons why I don't perform well in contests and get discouraged.

Hope it helped and if you have more question I would be happy to answer.

Also good luck, you will get there and once again, don't look at other peoples' rating changes, everyone is different.

feeling motivated after reading your text.Congrats !

Congratulations, and you're right, that is absolutely the way you should think.

bro I think that you are stucked at a particular rating for a very long time because you are just solving 800 level problems when I just viewed your profile you have solved a very less amount of problems solved of 1200>= what's your view on this

I believe that the problem here is that you are not solving harder problems, for example: you have solved 250+ problems of 800's but only 9 of 1500 problems, if you start solving harder problems i promise you the results is going to be better

good luck.

Congratulations!

Great Blog. Congratulations.