Hi guys, here's an update. The pools have been resolved!

Here you can see real and predicted top5.

I invoked withdrawal for winners. (Except for one guy, who did it himself xd).

I also gave 10k tokens to those who lost everything.

If the hackercup happens, I'll host predictions for it too. It should be even more fun.

The pool was closed 3 hours before conteset. I was afriad that the contest would start too early. In hindsight, 1h before would be more reasonable.

I see a lot of people claimed toke s but haven't placed a bet, please don't forget.

There was some issue with tx submission, now it works.

UPD: I improved gas fee calculation, some transactions used to fail because of this. Now it should be better!

The first workout is free

Does this apply if I'm living in another hotel :eyes:

I think if you want to convince people who disagree with you attacking them is a bad idea. And when you stylize the counter points LiEK tHis I can only read it as "I'm convinced everybody who thinks this counterpoint is valid has 69iq".

I'm very disappointed with the editorial writers for not including this proof.

The most straightforward proof is obtained by considering the image of function $$$f(i, x)$$$ — the answer after considering $$$i$$$ elements, if $$$a_1 = x$$$.

$$$|f(i, [L; L + len])| \lt = |sqrt(len)|$$$.

This can be shown using the inequality $$$sqrt(a+x)-sqrt(x) \lt =sqrt(a)-sqrt(0)$$$, this is because sqrt is a concave function, this is a very intuitive claim, you can kind of guess this by looking at the sqrt(x) plot.

With this we can show that $$$|f(i, [0; 10^{18}])| \lt = 10^{18/2^i}$$$.

However this isn't a complete proof as the RHS will approach 1, but never actually reach it so it could be that $$$f(0) = x-eps, f(1) = x, f(10^{18}) = x+1$$$.

Let's say we already know that f(i, x) takes only 3 values, the thing is either $$$\left \lfloor{\sqrt{x}}\right \rfloor = \left \lfloor{\sqrt{x+1}}\right \rfloor$$$ or $$$\left \lfloor{\sqrt{x+1}}\right \rfloor = \left \lfloor{\sqrt{x+2}}\right \rfloor $$$, so $$$f(i+1, x)$$$ will only take 2 values.

Problem F in $$$O((n+q)log(q))$$$. This is a bit of a necropost but I think the solutoin is interesting and I don't see any comments about it.

Let's analyze the piecewise function mentioned in the editorial, but only on the values [0; p — 1]. It will be 2 line segments with slope 1 and the image will be some segment [L; L + p — 1].

So f(x) will have the form of f(x) = L + (x + S — L) % p. Or the smallest integer >= p with correct remainder.

Here x % p denotes remainder in range [0; p — 1];

Turns out it's easy to incrementally update the functions parameters L and S if you think about it:

L + k < 0 -> L + k
L + K >= 0 -> min(L + k - p, 0)

S is just range sum.

So to solve the problem we can go in increasing order of right endpoint and maintain a treap of L values for all queries. The BST needs to support val+=x and val=0.

For those wondering why you have 9 on cosinus peoblem. Try reading negative numbers incorrectly. First read the integer part(with minus), then read the fractional part(as positive number) and ADD them. So when you see -1.1 solve the problem for -1.0 + 0.1 = -0.9.

Upd: 0.9 -> -0.9, a typo

What's the intended complexity for cookies? The best I can think of is O(mS*dsu_complexity(S)) but I get TLE.

A binary version of problem D has appeared on codeforces before. Here is the link.

There are some open source tools that make similar graphs. Have you checked out TLE bot code(;plot rating in particular)?

:rage:

At least, prove consistency.

Sir, can you give proofs please?

Why is the prize distribution so weird :/ For example, 1000th and 101st places are totally different levels of skills, I believe it would be better if they were distributed like global round points.

Oh fuck this is an old blog ... I saw it in recent actions and commented without reading oops sorry

Great job! This is a very simple concept that is usually hidden behind way too much math jargon. I'm not saying math is bad, but this is a beginner friendly topic and not all beginners on a CP site know math. I don't think I've seen any explanations accessible to small schoolboys till now.

Anyways here's something I'd like to add, the magic algo:

for(auto& i : basis)
	x = min(x, x^i);
if(x)
	basis.push_back(x);

x will become the smallest value you can get by xor-ing x with values that can be represented using that basis. In particular, if x = 0, then we could represent this number before and there is no need to add it to the basis. This short algo works the same way — every number will have some unique bit others don't but I will not rigorously prove it here.

And of course, there must be some exercises.

https://atcoder.jp/contests/abc141/tasks/abc141_f

https://atcoder.jp/contests/abc236/tasks/abc236_f

https://codeforces.me/problemset/problem/1101/G

https://atcoder.jp/contests/agc045/tasks/agc045_a

https://codeforces.me/problemset/problem/1100/F

https://atcoder.jp/contests/abc223/tasks/abc223_h

https://codeforces.me/problemset/problem/895/C

https://codeforces.me/problemset/problem/959/F

https://codeforces.me/contest/587/problem/E

...

There is a cf problem were you have n nim piles, for i-th pile it is either of size a_i or b_i with equal probability. What is the probability of you winning? Unfortunately I can't find it anymore.

This topic is very common so there should be a million more problems, but I am too lazy so I request other people to share.

On the topic of NEAR. Users who had registered on the site before the contest, did you get your prizes? I personally didn't although I've filled the form. Did I do something wrong?

SEGDIV: do a[i] = rng(), while array is bad, then increase i.

Did you know that const ll inf = 1e18 + 23; is the same as const ll inf = 1e18;? That's how I almost didn't solve Ex... I guess I will stick to const ll inf = 1ll<<60 from now on.

Sir may we expect a part 2

What's the most awkward encounter with a fan you've ever had?

CF has a lot of features which only become available as you get more rating(adding contests to gym, making public groups, streams, trusting users, calendar & catalog editing etc...).

This makes me wonder, what kinds of superpowers do headquarters users have?

Now I can beg for likes without begging for contribution:

I request likes

BTW the widget is displayed as usual text when previewing comments, is that intended?

I found the reason for TLE, leaving it here so that people reading don't ever make the same mistake.

This has to be one of the dumbest reasons for TLE I encountered in a long time.

I decided that instead of using

for(int bit = 0; bit < 2*k; bit+=2)
//use 1<<bit here

I should use

for(int bit = 1; bit < (1<<(2*k)); bit *= 2)
//use bit here

Changing the later to former makes my code 2 times faster it seems.

I should have known that division slows my code down by a lot. But it is a bit easier for me to work with the slower version, and it has never let me down before so I didn't know the effect is that big. So it has became a habit and I do it automatically QaQ.

My solution for F had intended complexity but a terrible constant it seems. First I computed answer mod 998244353 which was fast enough but I got WA. Then I realized that I need to print the real answer but my code got TLE with long longs :/.

how to do NOL_LESS? My n*sqrt*log solution with fft passes in 0.69/2seconds. But I hope you have a solution with adequate complexity.

Problem E has an N*sqrtN*logN solution which is good enough to pass system tests but can be hacked. I hacked 1 and 2

Please format your blogs properly & don't forget to mention such important details next time. You should put some effort into describing your problem if you want to get help.

Well, the first code is O(N*sqrt(N)) because j goes from 1 to sqrt(i).

Second code is O(sum n/i^2) we know that O(sum n/i) = O(nlog(n)) therefore your second code is way faster asymptotically.

for (int i = start; i <= end; ++i). This part makes your code n^2

Overflow? int i, j; when i is around N, j is around N*N in the second implementation. So sometimes it gets negative and you do many iterations.

You avoid overflow in the first implementation because j*j increases by 2*j+1 each iteration so j*j doesn't go over N + O(sqrt(N))

Using VPN is so troublesome, how will you collect the prize as non-Indian. I'd rather ask a trusted person to submit my solutions and split $$$. And if the prize is not money then this option is even more convenient!

I should elaborate. If two teams solve the same set of problems/tests. The more skilled one is going to do it faster, therefore have some time left to try other problems. Therefore they are more likely to make submissions after the last AC. And sometimes, they are not going to debug their code in time. So you are saying "team who solved 5 problems in 3:30 hours is better than the team that solved 5 in 3:00 hours but then failed to debug problem 6". You are just penaltizing skill and adding randomness to the standings IMO.

If multiple teams have the same score, the ranking will be determined based on the time of the last submission. There will be no penalty for incorrect submissions, but a submission will still count for tie-breaking purposes even if it does not increase the score of the team.

What sort of insane tie breaker is this?

You count good pairs over all permutations(not permutations).

Permutation [1, 2, 3] adds 2 to the answer: pairs (1, 2) (2, 3)

Permutation [1, 3, 2] : (1, 3)

Permutation [2, 1, 3] : (2, 3)

Permutation [2, 3, 1] : (2, 3)

Div1A statement is ?????????????????????????????????????????????????????

You should see this too...

In fact this thing TLEs on n=40 locally most of the times but cf reruns TLE submissions so I had to make n larger.

K*re khar

No sir, I only 2600 cuz cheating

Hi don't mind me im just a cloud

Bruh no

its very far from linear actually

I didn't think much but Im certain that you should make p long long. Its possible for it to keep overflowing and doing a lot of interactions.

Dont use ceil because 2+eps might be ceilied to 3. As a rule of thumb avoid floats when you can in CP. It is not UB, mingw 32bit is configured to use excess precision by default it means that it will do all the operations in 80 bit float or sth like that. 64 bit one isn't it seems.

It's worth pointing out that the conjecture is verified up to a fairly large value. I think, that in most cp problems your numbers dont go larter than that.

If you are willing to setup a vpn to access discord you should check this out.

Then why can't I access my favorite group anymore? :(((((((

Nice

add after declaring v.reserve(n*m);

As i said most normal ppl have 64bit compilers. gnu c++17 is the 32 bit mingw version with excess precision. MinGW is such a mess idk if its a cf problem or all mingw 32 versions problem

Uh i don't think its a reliable check, you should check against floor as well. ceil(1+1e-10)=2. Inconsistency is probably caused by excess precision which is enabled by default on 32 bit mingw.

P.S. what you probably wanna look at is Theorem 2 which is exactly what you are asking about.

This might be relevant: Floyd-Warshall works with any order of loops in at most 3 iterations. https://arxiv.org/pdf/1904.01210.pdf

While it's quite cool. I think it is way too limited to be useful :( Looks like it breaks if you have lazy or a harder operation. For example, $$$ \prod_{i=l}^{i=r} a_i \mod M$$$ (64 bit multiplications are pain in the ass, aren't they?). One thing I wanted to try but never actually did is trees with more than 2 children(base 4,8). Have you tried that, does it suck?

I think it has something to do with formatting. Try to submit after making font & color the same for all lines. Or at least replace bits/stdc++.h with bt bits/extc++.h.

I have participated in another april fools type contest by zscoder and it was quite cool. The best part was a person spoiling the solution to an unsolved problem in a discord chat without reading it. Looking forward to participating in this one too.

Is there a possibility of the online IOI being postponed to the later months of the summer? Are participants getting the worst of both worlds(close to exams & online)?

Hello sir. I dont understand how you get o(n) complexity wouldn't it be O(n)? I am declining in cp(see my last delta) so I might need further elaboration.

Other than that I think you should add more newlines (<br> or 2 newlines) to make it more accessible for beginners.

Here is a more detailed explanation

So I printed (max(n,m)+k-1 choose k-1) instead of k^max(n, m) in D and failed to see this bug for 10 mins. Cost me over 1100 places :thonkms:

Not "d&c dp". Just d&c to solve for all k. solve for l, mid and mid+1,r also keep flags indicating whether you took border elemenets. Then merging is a bunch of min convolutions of convex arrays which can be done using greedy for convex arrays.

How to do F?

Also this!

Or you can be smart and [loosen constraints]https://atcoder.jp/contests/abc162/tasks/abc162_f).

Actually I knew about this problem & knew that there is a stupid greedy but I hate greedy so I asserted the fact that the function is convex. And came up with 2 solutions d&c and alien's trick. I later proved both convexity and greedy by modeling the problem as mcf (hopefully correctly).

Output Limit Exceeded

As a tester I upvoted and demand my positive delta

quality conent

Let's have a 9 problem round!

Liked and subscribed

Yes 11(out of 11)

why are you asking?

How to increase my rating by exactly one point?

Indeed, path in max spanning tree doesn't maximize maximum edge on paths.

However it does maximize minimum edge on path. It's obvious that spanning tree built with kruskal's satisfies this property. To prove for any mst consider a path from u to v which is has strictly better than the one in mst. Remove min edge from u->v path in mst the graph still stays connected because the other path only uses edges >min adding one(not any, but 1 is enough since tree will have 2 connected components and the graph is still connected) of the edges from the other path will make this graph connected and this edge will be strictly larger the one we removed. Therefore our st wasn't mst, a contradition. (This proof doesn't work for max edge because we can't guarantee that mst will have greater cost after doing this)

I believe you can consider back edges used(edges / mst edges) in the path and conclude that it's optimal to use only one through tedious casework. Here's a simpler method. Let's consider this "naive" algorithm: Fix max edge (u, v) and greedily find a path from u to v which maximizes minimum edge weight on path and doesn't use that edge. Using the above property you can see that it's the same as maximizing weight(u, v) + cost of u->v path in MST of Graph / (u, v) edge. Turns out this spanning tree can be obtained by doing this: remove (u, v) and add the cheapest edge which will make the graph connected. 1 operation is enough because if we do 2+ at least one operation clearly doesn't involve (u, v) so if it's good then it would also mean that our current st is not mst. It's not hard to see that your algo is a smart way of considering all the possible operations.

It turned out to be much messier than I expected. Should've used proof by intimidation.

Seems like this problem is stolen

How so orz?

tmw orz indeed

Remembering credentials isn't easy indeed, but you can always rely on your browser storing this data.

Many of the alt accounts top the standing page which are created minutes before the contest.

Yes, because they can. I'm saying that if people couldn't create a brand new alt before the contest, what would stop them from creating 5 alts the same day so they have enough alts for the next few months. It doesn't take much effort to do so. Temporary emails are free and coming up with a handle isn't hard either.

Only in rare scenario a new user will come and start competing in a contest.

Can you back this claim up with some numbers?

I registered my account five mins before the contest. Just because I wanted to participate in a fucking contest. Your suggestion would only decrease people's enthusiasm. Moreover, it would lead to people creating several alts at a time so they always have a new one.

Can you kindly elaborate on how you came to this conclusion great sir?????

Something similar happened to me. In gr9 my last submission(with 20s left) was a compilation error, because I had to add #define int long long in order to fix overflow and forgot to change int main() to something else. I would've finally escaped orange yesterday if that didn't happen.

As a Maripium fan, I want to start an orz chain.

Maripium orz.

Both articles have enough code to understand and modify the approach...

Use this https://codeforces.me/blog/entry/11080. Or maintain a segtree where a_x = no of elements equal to x then slightly modify technique from this article https://cp-algorithms.com/data_structures/segment_tree.html (Counting the number of zeros, searching for the k -th zero section) to find k-th element or just binary search.

Did he at least send you his btc address before banning?

Has been sent 6 minutes ago

Please send a more recent screenshot, or is it just an ad of your btc wallet?

Yes I can definitely help! If you are not happy with your ability to solve AB why don't you practice AB? Solve a B, then analyze where did you overcomplicate it. Repeat.

tl;dr

If your mashup is private then there is no way for stopstalk to fetch the submission from it

I sit in front of a mirror with a big pink marker and I write on my face

Don't bully me mr got + on global 9 :sob:

Hi daniil

No u! I spent the whole day trying to improve my score on a problem by 2 points which I failed to do how can you orz such a brick?

tuwuna orz

P. S. let's start an orz chain

https://codeforces.me/contest/850/problem/B I think this problem is a generalization of the one you are trying to sovle unless I misread somethinig(which I do pretty often)

i tried it for 2 hrs

~~ Rookie numbers make that 5 times more~~

So I skimmed through your code:

Your probably should change 2*n to 4*n

You store everything as int but sum can overflow i guess

Sometimes add update can be stacked on top of set update and you are always stacking it into add updates

3 3
0 0 0
2 1 2 1
1 1 2 1
3 1 1

Your code prints one because in the second query you add 1 to sum lazy, which is in fact overwritten by set lazy(from query 1). Instead you should have added 1 to set lazy so the operation becomes "set to two".

Keeping two lazy tags can mess with order instead I suggest storing one tag, and it's type.

Here's a short implementation of this idea

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1<<18;
using ll = long long;
struct ctx {//store info about lazy updates
	//0 - no update
	//1 - set update
	//2 - add update
	int upd_type = 0;
	ll val = 0;
};
ctx merge(ctx a, ctx b) {//we assume b happened after a and we're stacking b on top of a
	if(b.upd_type == 2)//in case b is add update we stack it on the previous update keeping it's type or setting it to 2 if it was 0
		return {a.upd_type ? a.upd_type : 2, a.val + b.val};
	return b.upd_type ? b : a;//if b is 0 we keep a, if b is 1 we overwrite the previous updates
}
struct node {//stores sum and lazy info
	ll val = 0;
	ctx lazy;
};
node merge(node a, node b) {//empty lazy and sum = sum of children
	a.val += b.val;
	a.lazy = ctx();
	return a;
}
node tree[4 * maxn];
void push(int v, int l, int r) {
	if(tree[v].lazy.upd_type == 2)//the lazy is an add update
		tree[v].val += tree[v].lazy.val * (r - l + 1);
	if(tree[v].lazy.upd_type == 1)//the lazy is a set update
		tree[v].val = tree[v].lazy.val * (r - l + 1);
	if(l != r) {//if the node has children we propagate the lazy
		for(auto ch : {2*v, 2*v + 1})
			tree[ch].lazy = merge(tree[ch].lazy, tree[v].lazy);
	}
	tree[v].lazy = ctx();//reset the lazy
}
void update(int v, int l, int r, int ql, int qr, ctx u) {
	push(v, l, r);//pushing everywehere
	if(qr < l || ql > r) return;//out of range => exit
	if(ql <= l && r <= qr) {//completely in range put lazy tag and immediately push it so that we can update the parent
		tree[v].lazy = merge(tree[v].lazy, u);
		push(v, l, r);
		return;
	}
	int mid = (l + r)/2;//going further
	update(2*v, l, mid, ql, qr, u);
	update(2*v + 1, mid + 1, r, ql, qr, u);
	tree[v] = merge(tree[2*v], tree[2*v + 1]);//updating this node's value children are up to date because we always push
}
node get(int v, int l, int r, int ql, int qr) {//I find node corresponding to range instead of sum, it's more practical and is useful in harder problmes
	push(v, l, r);//pushing everywehere
	if(qr < l || ql > r) return node();//out of range return 0 sum
	if(ql <= l && r <= qr) return tree[v];//completely in range return this node
	int mid = (l + r)/2;
	return merge(get(2*v, l, mid, ql, qr), get(2*v + 1, mid + 1, r, ql, qr));//merge something from the left child and something from the right child
}
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n, q;
	cin >> n >> q;
	for(int t, i = 1; i <= n; i++) {
		cin >> t;//2 - update type, t - value
		update(1, 1, n, i, i, {2, t});//To not implement build function I interpret initial values as add updates
		//since we have everything set to 0 we can act like segtree is initialized with them
	}
	for(int t, l, r, x; q--;) {
		cin >> t;
		if(t < 3) {
			cin >> l >> r >> x;//t^3 - update type, x - value
			update(1, 1, n, l, r, {t^3, x});//^3 turns 2 to 1 and 1 to 2 because I use different labels for update types in my ctx class
		} else {
			cin >> l >> r;
			cout << get(1, 1, n, l, r).val << '\n';
		}
	}
	return 0;
}

So

1. Your code contains a lot of hindi comments which makes it irritating to read

2. You use different spacing techniques (3 spaces in main, 2 spaces in segtree).

3. You don't add any spaces after ,,|,& et.

4. You have weird blank lines.

5. You have like a million debugging lines.

6. You are using weird loop defines.

...

You could have removed useless stuff and run a formatting tool on your code to make it somewhat readable. Why should total strangers help you if you can't even do that? What are you expecting by throwing this pile of ugly code at people? You even have a testcase which your code doesn't work on I think you should debug by yourself. And why is this blog at +4? I'd argue such stuff should be forbidden on cf at best.

Ass a 100% legit(no SMS, free) red codir I will gaid you sirr. You shud gibb LeetCode Biweekly Contests sir. They are much gud to u're skill. Jtz reccomendid too do Al the koshans from LeetCode not onl BiWeekly but zeey be best koshans LeetCode haz.

Iff my amaazin tips help you mike syre to support me finnancialli your can DM me for detals

https://godbolt.org/ — use this website to investigate such stuff. As you can see there is no assembler corresponding to loops. However, if you replace if(i != j) with if(i != j + 1), you can see that asm suddenly becomes much more complicated. Conclusion: compiler indeed optimizes the loops away. I recommend you to play around with this stuff as you seem pretty interested in it. Another example of optimization:

#include "iostream"
using namespace std;

long long n;

int main() {
    cin >> n;
    long long a = 0;
    for(int i = 0; i < n; i++) a += 69ll*n + 420;
    cout << a;
}

From length of assembler codes you can guess that only MVC and Clang, contrary to GCC don't optimize this loop to a formula. And even GCC wouldn't optimize (a += 69ll*n + 420) %= 228. You can confirm those results using Costum Invocation. Go ahead and play around with this stuff!

By solving fuckinng problems and removing this blog before you completely ruin your contribution. Or at least not bumping it with those regular edits.

As I have said it's just extra characters in most cases.

tl;dr no unless args are constexpr

I've just googled constexpr function c++ cppreference(very good, recommend to use, superior to cplusplus.com) says: The constexpr specifier declares that it is possible to evaluate the value of the function or variable at compile time.

So, if you call this function with non constexpr arguments, you will see no improvement, which I verified using costum invocation feature of CF. However you might wanna do some stuff crazy like this.

Now I'd like to ask for upvotes