"Let It Rot" will win everything!

When are you writing a top tree tutorial?

here we go again:
https://zibada.guru/finals/

separate pages:
https://zibada.guru/finals/2022/
https://zibada.guru/finals/2023/

It's a very common question, that has already appeared multiple times in Codeforces blogs.

unordered_map gives you O(1) complexity on average, while map gives O(logn). Seems that unordered_map is better in such case, but at what cost does it provide such complexity?

How to prevent this? Everything described here.

And the same thing works for unordered_set and similar data structures as well. As a rule of thumb, if you don't know how to prevent your solution from getting hacked using unstable data structures — use their stable analogues, but not them.

ordered_set and just set are different data structures from STL, don't confuse them with each other.

Solution with set has got TLE because, once again, on random data unstable structures as unordered_set give better performance, but it applies only and only on tasks with closed solutions. If solutions are opened — wait for successful hack.

Very often when your solution can't pass because of the additional logn it's either because your idea is inefficient or because your implementation is inefficient. It's very rare when task requires to use unstable data structures with no alternatives to them

Scoreboard

I won two TON coins in CodeTON Round 8, but now I don't know how I can receive them. I have a TON account

and also I updated my wallet before April 16 UTC.

What can I do beside just waiting?

Will be there any live contest mirror? Can you please share the link?

47th mipt

But what the OP said here is the other way around, Unordered got accepted and ordered got TLE

On their main website icpc.global, they have a link to an online mirror: https://onlinejudge.icpc.global/. The icpc.global website top-left menu has pretty useful links :).

why not spbsu

why skipped, cheater? 256497006

Are you a narcissist? Always commenting for your friend (or maybe your main?) absolute-mess. Two comments in screenshot below. Upping his blog in the comment above too

Thank you! Also, I guess, at https://www.youtube.com/watch?v=wJRh62s5frE there should be an opportunity to look at our screen, and at https://www.youtube.com/watch?v=an5sBhtktaE there should be a stream.

Either MIT or Peking U will win the 46th

Either Peking U or Harbour Space will win the 47th

2x Jagiellonian

I'm in Egypt right now and I didn't bring my laptop there, so I can't update the blog until I get back. I'll probably do a final update when I get back to my country. Good luck to all the teams!

Dont worry, i am in the same boat

When can we expect the prize money ?

Unfortunately there seems to be a bug in the generator of this problem. It is not deterministic (produces different tests for the same command line arguments), and Codeforces is not able to put up with this fact. The best thing to do could probably be to contact the authors of this problem and ask to fix it, but unfortunately the problem is so old that it is unlikely that something will be done. So, unfortunately, better just try to find some newer problems.

Yeah, I certainly consider this algorithm as from The Book. In purely aesthetical measure, there are very few algorithms with higher beauty. While I do see the intuition of this "level" structure, I also fully agree that the invariants are very delicate.

I just regard the top tree as a good abstraction of a dynamic tree scheme, but here, it's important to note that vanilla LCT would not work. If you try to implement the find_first and update operations in LCT, you will probably just reinvent the top tree. Most literature gets around this limitation by storing cyclic Euler Tours in a BBST (known as Euler Tour Trees), but I do not prefer this, as ETT has limited usage outside of this algorithm and is honestly just painful to implement.

But a mirror's supposed to be a live contest?

You're welcome! I think you may get a medal in few hours. I'm a big fan of your casts and rounds' explanations

wow

no

BigBadBully is now higher rated than you :o

Enjoyed every problem, thanks to CodeChef.

you won't

I personally believe it is vice versa — use unordered_map if you do not really need the elements to be stored in the sorted order.

Yes, there is a danger of hacks, but, firstly, the cure is not very complicated (one of the commenters already gave a link to a comprehensive material), secondly, I suppose the problem is maybe exaggerated. I believe I don't even have an anti-anti-hash test protection in my template, but I still have never been hacked this way.

For me personally a logical line of behavior looks like this: just use unordered_map like hacks don't exist. And only if someone hacks your solution or it fails system tests, then probably it is worth researching into this problem further.

If you want to be secure and prefer to put on an extra layer of protection, better read https://codeforces.com/blog/entry/62393, add some needed lines to your code and never remember again about unordered_map being hackable.

Bro, you need to train

Skill issue, the blog is also long, uninteresting, and you should provide a tldr;

This is a really nice comment

Stream by tourist

Hangzhou Dianzi U

Looks like the intersection of the problemsets is 5 problems. Shame. Now for training purposes you have to choose one or the other.

Many people do not know who Shayan actually is, he's done much valuable efforts in INOI and has been a great idol and teacher for Iranian students, ask him about INOI, the efforts he's done, team selection test,...

I won't

feeling so dumb after reading editorial for append array :(

Why is the Mirror linking to tourist's twitch?

all the best, you are gonna have a blast tomorrow :)

around $$$10^4$$$ dollars for the first place

I meant the regular set.

Got your point thanks, but what do you say about using custom hash functions ?

Using custom hash functions allows you to modify unordered_set hashing so that it's less likely to be hacked.

Here's my template:

mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct custom_hash {
  	static uint64_t splitmix64(uint64_t x) {
   	 	x += 0x9e3779b97f4a7c15;
    	x = (x^(x>>30))*0xbf58476d1ce4e5b9;
    	x = (x^(x>>27))*0x94d049bb133111eb;
    	return x^(x>>31);
  	}	

  	size_t operator()(uint64_t x) const {
    	static const uint64_t FIXED_RANDOM = rng();
    	return splitmix64(x+FIXED_RANDOM);
  	}
};

template<typename T> using safe_set = unordered_set<T, custom_hash>;

Please note that not everything is able to be given a hash, so only stick to basic data types such as int, string etc.

why you always say sir sir sir

What about you, will you take the place?

Star button does not appear if you are logged out
Moreover if you are logged in other tabs like settings and favourites also appear along with blogs, teams etc.

you are the kind of guy to shit talk blogs that are useless yet posting the most useless shit ever

Nice set of problems,although E was easy for its place.

then we will be together even in our failure uwu

Available now, 47th PS 46th PS

There are different problems but some intersections as well with some shuffle, but overall they aren't identical.

i can't find it

is solving from ladders good or the problemset is better

wasted 1.5 hr on this and finally quit the contest

In normal case, if u can solve 50% of a set of problems then it's suitable for u. So I suggest u keep practising and move on when u can solve it easily. But problem rating is not an accurate thing so I suggest u practising problems in a rating range rather than a number(for example,me 2100~2400). Good luck!

who else wants him back to competitive programming?

Best of luck! May your teamwork, skills, and determination lead you to success.

wow the script still works!

looking forward to the excellent problems and exciting contest :D

0, most don't have cf accounts

Does being a grad student count as being in college?

Best of luck ! "May the algorithms be with you! Your problem-solving skills are legendary, use them to conquer the World Finals!"

Definitely, NO. You can notice the different solve counts on 46th and 47th scoreboards even problems letters A->K 47 P->Z 46

But there might be some intersections

Valuable insights. Thank you, but i think not all gym contests can be cloned.

How Grandmaster manages his/her time during a coding competition, Asking about specific time management techniques, such as how they prioritize problems, allocate time for each problem, and handle unexpected challenges or bugs efficiently, could provide valuable insights for other participants looking to improve their competition performance.

Wish you all the best in ICPC.

I cheer for SPbSU, but I believe the probability of HSE winning is Higher (and, to be honest, I cheer for them not less).

As a problem setter, I highly recommend participating in this contest...

I think we should all orz evenvalue for good luck and high score! I'll start: evenvalue orz.

When you hit a point of mental fatigue, it's crucial to pause and take breaks.

Well said, When I was pupil I spent months trying nonstop to reach specialist and get into new topics, For the topics I tried to learn I didn't get most of it and for the rate it dropped to newbie, I took a little rest and I went from newbie to pupil in a matter of days.

Sorry for necroposting. I was solving problem E and got ml14 then I did some optimizations and got AC. After that, I looked for the editorial and author's code. The code was the same with my solution that got ml14. So I copied it and submitted it in C++ 20 (GCC 13-64) and surprisingly this got ml14 too. Then I resubmitted it in C++ 17 and got AC. Why it could get ml?

If you're using unordered_map or unordered_set you MUST have them anyway. I've already gave a link to the blog that gives comprehensive information about which exactly function you should use, so I won't duplicate it.

About what orz said: I completely agree with him in terms of competitive programming. When you have the prewritten protection code then it's much better to use unordered_map or unordered_set if you only don't need the sorted elements in these structures. Also, most of the time, you really don't need anti-anti-hack protection, because it's very rare now that someone will try to fetch the random and write the test based on it, because it's enormously time consuming and it doesn't cost it.

If you look in my solutions, then you will see that it's very rare when I'm using such structures, and I have an explanation for this as well. Actually, I've a couple of reasons:

1. You can't use random hashing in real programming, and I'm trying to write my code as clear as possible and as similar to what you would write in reality (without including the principles of OOP, this is unnecessary in conditions of contests), so these structures are bad for me and I use them only when I really can't think of something else.
2. If I can't solve the problem without them then either I can't solve problem efficiently at all or problem was designed to be solved in only one way, which is enough to consider (for me) most of the time the problem annoying and boring, and I really don't like such problems.

On the homepage, icpc.global there is a menu in the topleft, it contains two items which are both "Online Judge" :). One leads to a dead link, one leads to https://onlinejudge.icpc.global/register, which looks like an online mirror of both world finals. It seems to start one hour after the start of onsite the contest.

Edit: It seems that after I looked at the site earlier today, they have changed it to only one working "Online Judge" link.

ahhh icpc... never change :)

And i give up after 1 or 2 submissions ;(

Either MIT or Peking U will win the 46th

Either Peking U or Harbour Space will win the 47th

650 problems solved, of these 650, 350 are for beginners 800

Yes, exactly.

You could even find the optimal solution in $$$O(N^3)$$$ or even better in $$$O(N^2)$$$ using $$$DP$$$.

Really the 3rd question was too bad

What do you mean by “You can't use random hashing in real programming”?

meme

Most of the problems in this round had pretty much similar difficulty levels, as our more difficult problems were used up in CodeRed Finals :-)

The line It is guaranteed that the sum of n over all test cases does not exceed 10^5 is a very important line. The line means that there are T integers $$$n_1, n_2, ..., n_T$$$, $$$n_i$$$ being the $$$n$$$ in i-th test case and $$$n_1 + n_2 + ... + n_T <= 10^5$$$. Now, inputting T integers $$$n_1, n_2, ..., n_T$$$ is easy. But, there are $$$n_i$$$ more numbers in the i-th test case but as we know that sum of all $$$n_i <= 10^5$$$, then we are just inputting at most $$$T + 10^5$$$ numbers, which can be easily done in 1 second.

So basically the complexity will be O(T+n) not O(t*n)

Am I the only fool in the planet who solved Good Binary String Problem through Dp?

my dp solution

Love it

let dpi be the max prefix sum up to i no subarray sum ending at i is 
min(A[i] + A[i - 1], pref[i] - dp[i - 2])

#include<bits/stdc++.h>
using namespace std; 
char nl = '\n';
using i64 = long long;

void solve(int t) {
    // cout << "test #" << t << nl;
    int n; cin >> n;
    vector<i64> A(n);
    for(auto& a : A) cin >> a;
    if(n == 1) {
        cout << A[0] << nl; return;
    }
    i64 mn = A[0] + A[1];
    for(int i = 1; i < n; i++) A[i] += A[i - 1];
    vector<i64> pref = A;
    for(int i = 1; i < n; i++) {
        pref[i] = max(pref[i], pref[i - 1]);
    }
    for(int i = 2; i < n; i++) {
        mn = min(mn, A[i]);
        mn = min(mn, A[i] - pref[i - 2]);
    }
    i64 sum = A[n - 1];
    sum -= mn;
    sum += llabs(mn);
    cout << sum << nl;
} 

int main() {
    int tt = 1;
    cin >> tt;
    for(int t = 1; t <= tt; t++) solve(t);
}

vectordp(N,INF);

dp[0]=0;

int mn=INF;

for(int i = 1 ; i < n ;i++)

dp[i]=min( dp[i-1] + a[i] , a[i -1] + a[i] );

mn =min (mn , dp[i] );

As a tester, problems are very interesting and definitely not NP-complete.

1. We don't know anything about problems before the beginning of the contest(
2. Not, only one team per contest. 2022-2023 season of regional contest qualified with extra selection rules

https://codeforces.com/blog/entry/128590?#comment-1141460

Thank you and same to you!

Worst Contest Ever.

People get codes accepted by hard coding test case.

Test cases were also wrong in this contest

Question 3 should be removed from contest.

NGL cash is much needed right now

46th nru hse

Due to Covid ICPC WF Moscow was rescheduled to October 2021. In Luxor are hosted both ICPC Finals of 46 and 47 seasons (2021-2022 regionals and 2022-2023).

evenvalue orz pls bless me with good luck

dont learn any algos / ds until u encounter them in more than (5 — 10)% of the problems u are solving , and also u can try solving really hard problems for you for example problems 600-800 above your rating u'll most likely see the tutorial for more than 90% of them but it builds strong intuition and gives many ideas to start thinking from also it kills the fear u have and simplifies everything for you

• For second Don't know why when i submitted the code got wrong answer but running same code on custom input was getting correct answer. (10 10) was appearing at start and guess what 10 was not even the input array.
• For third I checked both DSU + cycle still was getting WA(Is there something I missed).
• For last question greedy would work? My dumb ass was stuck on bitmask DP after seeing the constraints(TLEs).

got AC, thanks dude :D

ok but i perfer sort(v.rbegin(), v.rend());

What an inspiring story...