Hello, Codeforces!

I participated at the Dhaka World Finals last month, and decided to write a blog about it. It's been a while since I've written, so I also decided to talk about a few other things: Indian regionals, Moscow World Finals, NAC, etc. So read on to know how I qualified for 3 World Finals across 2 continents and 6 different teammates, how my teammates got COVID at Moscow (and I was about to participate solo), getting the best rank IIT Bombay has ever gotten with a man down, and absolute devastation at Dhaka. I try to give an insight into the non-programming aspects as far as possible, while also trying to highlight the things to take away from the programming parts.

The blog can be found here. Thanks to aryanc403 and lucasxia01 for testing the blog. Please let me know what you think!

We invite you to participate in CodeChef’s August Lunchtime, this Saturday, 28th August.

Time: 7:30 PM — 10:30 PM IST.

The contest will be rated for all three Divisions. The August Lunchtime comes with our new prize structure for global & Indian participants. More details are given below.

Joining us on the problem setting panel are:

• Setters: Kumar Angesh angesh Singh, Jatin rivalq_loves_me Garg, Danny dannyboy20031204 Boy, Hemanth hemanth_ram Ram, Rahul Kumar, Janmansh janmansh Agarwal, Pratik i.am.pratik Kumar, Daanish Mahajan

• Testers: Anay AwakeAnay Karnik, Soumyaditya socho Choudhuri

• Statement Verifier: Jakub Xellos Safin

• Editorialists: Mohan Mohan_abhyas Abhyas

• Contest Admins: Shubham TheOneYouWant Anand Jain, Radoslav radoslav11 Dimitrov

• Head Admin: Alex Um_nik Danilyuk

• Video Editorialists: Chirayu Chirayu Jain, Prachi agarwal19 Agarwal, Darshan darshancool25 Lokhande, Yashodhan ay21 Agnihotri, Shivam Bohra, Aryan Agarwala, Meet myth_gemphir Singh Gambhir, Rajarshi RestingRajarshi Basu, Adhish ak2006 Kancharla

• Mandarin Translator: Huang Ying

• Russian Translator: Fedor Mediocrity Korobeinikov

• Bengali Translator: Sakib SakibAbrar Abrar

• Vietnamese Translator: Team VNOI

Prizes:

Global Rank List:

Top 10 global Division One users will get $100 each.
Non-Indians will receive the prize via money transfer to their account.
Indian users will receive Amazon vouchers for the amount converted in INR.

Indian Rank List:

Top ten Indian Division One coders to get Amazon Vouchers worth Rs. 3750 each.
The rest in the top 100 get Amazon Vouchers worth Rs. 1500 each.
First-time winners in Div 2 who make it to the top 200 for the first time get Amazon Vouchers worth Rs. 750 each.
First-time winners in Div 3 players who make it to the top 200 for the first time get Amazon Vouchers worth Rs. 750 each.

However, everything else about our previous Laddu system for Lunchtime will continue without any change. To call out specifically, the top 10 school students in Div 1 of Lunchtime will continue to get Laddus as well as the cash/Amazon vouchers as per the new system.

The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

If you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Hope to see you participating. Good Luck!

Note: Usually, there is no bound on the stack limit, and is equal to the total memory limit of 1.5 GB. But due to a system configuration issue, the stack limit for C++ is temporarily set to 8MB. So, if you believe that your code requires larger stack limit, please include this in your code — https://codeforces.net/blog/entry/15866

Today, participants registered for the ICPC Amritapuri regionals received the following mail excerpt:

"We all are going through tough times in our lives. Education & work have been disrupted equally. I was trying to host the ICPC Regional in the month of July but got delayed because of some technical reasons. Now, the decision has been made at ICPC Headquarters to host the world finals at Moscow during the first two weeks of October. Chances are that the teams qualifying in the 2020 Regional (the current contest, to be held in August 2021) may be qualified for the Moscow World Finals. The contest will be held on August 14th 06:00 PM. In that case, we can have only one round of the contest to qualify for the World Finals to be held at Moscow."

This makes it seem like the WF2021 will be merged with WF2020, and it is called the "Moscow World Finals". This, ofcourse, opens up a can of worms — what will happen to individuals who qualify through different teams, for instance? Will multiple teams from the same university be allowed to participate, or will the ones who qualified for WF2021 be retroactively disqualified? Or are just the locations the same, and we will have two different competitions at Moscow? Will our eligibility ages etc be extended to allow us to qualify for another World Finals?

If anyone has more information — please, let the rest of us know.

Hi everyone,

I started writing a blog on my experience at the Indian ICPC Regionals of 2019-20 (the previous season as of this post) slightly more than a year back here. I stopped after 2 blogposts due to various reasons: World Finals not happening, our team losing interest in CP in general, and I kind of wanted to finish the series after the whole season arc was completed. With both my teammates retiring before this season and World Finals finally looking possible in October, I decided to revive it, so I would be able to publish a final post after WF and be done with this season :D. This seemed like the best time to post, since Amrita regionals has it's online round on 10th July, so many teams would probably be up-solving old regionals, and it might be interesting to compare how you performed vs how we did in the contest setting — what mistakes we made, and what you should avoid. It's also a nice way to preserve my memories, and to hype people up for onsite regionals hopefully, whenever they happen :).

You can read the blog here. Thanks to aryanc403 and Whiplash99 for "testing" the blogpost and making sure I didn't make major blunders!

Thanks for reading, and hope the read is enjoyable! :)

Hello everyone,

Since the practice round doesn't seem to provide a scoreboard, I'd like to open this thread to discuss scores and possible approaches for the problem. We got the following scores after some mostly trivial ideas:

• A: 65
• B: 13,328
• C: 702,974,812
• D: 7,602,227
• E: 10,477,632
• Total: 721,068,064

We mostly did some greedies, followed by randomly taking a small subset and computing best answer for that subset. I tried to use max weight bipartite matching but failed to make it work well; I don't have fast codes for max weight general matching, which could have been used to compute "good" pairs of pizzas. Did anyone manage to make this approach work or have a better idea which gave significantly better score?

Hello, everyone! It was a delight for us to have you participate in our contest. We hope you enjoyed the problems! Here, we present to you the solutions of the problems. I have also prepared some memes for you to enjoy — disclaimer: not all of them were created by me.

Author of this problem was Ashishgup.

#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
 
const int N = 2e5 + 5;
 
int n, x;
int a[N], f[2];
 
int32_t main()
{
	IOS;
	int t;
	cin >> t;
	while(t--)
	{
	    f[0] = f[1] = 0;
    	cin >> n >> x;
    	for(int i = 1; i <= n; i++)
    	{
    		cin >> a[i];
    		f[a[i] % 2]++;
    	}
    	bool flag = 0;
    	for(int i = 1; i <= f[1] && i <= x; i += 2) //Fix no of odd
    	{
    		int have = f[0], need = x - i;
    		if(need <= f[0])
    	        flag = 1;
    	}
    	if(flag)
    	    cout << "Yes" << endl;
    	else
    	    cout << "No" << endl;
	}
	return 0;
}

Author of this problem was Ashishgup.

#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
 
const int N = 1e5 + 5;
 
int32_t main()
{
	IOS;
	int t;
	cin >> t;
	while(t--)
	{
		string s;
		cin >> s;
		int suf0 = 0, suf1 = 0;
		for(auto &it:s)
		{
			suf0 += (it == '0');
			suf1 += (it == '1');
		}
		int ans = min(suf0, suf1); //Make whole string 0/1
		int pref0 = 0, pref1 = 0;
		for(auto &it:s)
		{
			pref0 += (it == '0'), suf0 -= (it == '0');
			pref1 += (it == '1'), suf1 -= (it == '1');
			//Cost of making string 0*1*
			ans = min(ans, pref1 + suf0);
			//Cost of making string 1*0*
			ans = min(ans, pref0 + suf1);
		}
		cout << ans << endl;
	}
	return 0;
}

Author of this problem was TheOneYouWant.

#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
 
const int N = 2e5 + 5;
 
int n, x;
int deg[N];
vector<int> g[N];
 
int32_t main()
{
	IOS;
	int t;
	cin >> t;
	while(t--)
	{
		memset(deg, 0, sizeof(deg));
		cin >> n >> x;
		for(int i = 1; i <= n - 1; i++)
		{
			int u, v;
			cin >> u >> v;
			deg[u]++, deg[v]++;
		}
		if(deg[x] <= 1)
			cout << "Ayush" << endl;
		else
		{
			if(n % 2)
				cout << "Ashish" << endl;
			else
				cout << "Ayush" << endl;
		}
	}
	return 0;
}

Author of this problem was FastestFinger.

#include<bits/stdc++.h>
using namespace std;
 
#define vint vector<int>
 
int interact(vint S){
	cout << "? " << S.size() << ' ';
	for(int i : S)
		cout << i << ' ';
	cout << endl;
	int x;
	cin >> x;
	return x;
}
 
vint get_complement(vint v, int n){
	vint ask, occur(n + 1);
	for(int i : v)
		occur[i] = 1;
	for(int i = 1; i <= n; i++)
		if(!occur[i])
			ask.push_back(i);
	return ask;
}
 
int main(){
	int tc;
	cin >> tc;
	while(tc--){
		int n, k;
		cin >> n >> k;
		vector<vint> S(k);
		vint ans(k);
		for(int i = 0; i < k; i++){
			int c;
			cin >> c;
			S[i].resize(c);
			for(int j = 0; j < c; j++)
				cin >> S[i][j];
		}
		vint ask;
		for(int i = 1; i <= n; i++)
			ask.push_back(i);
		int max_element = interact(ask);
		//find subset with max element
		int st = 0, en = k - 1;
		while(st < en){
			int mid = (st + en) / 2;
			ask.clear();
			for(int i = 0; i <= mid; i++)
				for(int j : S[i])
					ask.push_back(j);
			int x = interact(ask);
			if(x == max_element)
				en = mid;
			else st = mid + 1;
		}
		ask = get_complement(S[st], n);
		for(int i = 0; i < k; i++)
			if(i == st)
				ans[i] = interact(ask);
			else ans[i] = max_element;
		cout << "! ";
		for(int i : ans)
			cout << i << ' ';
		cout << endl;
		string correct;
		cin >> correct;
	}
}

Author of this problem was Ashishgup.

#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
 
const int N = 2e5 + 5;
 
int n, cost = 0;
int arr[N], b[N], c[N];
vector<int> g[N];
 
pair<int, int> dfs(int u, int par, int mn)
{
	pair<int, int> a = {0, 0};
	if(b[u] != c[u])
	{
		if(b[u])
			a.first++;
		else
			a.second++;
	}
	for(auto &it:g[u])
	{
		if(it == par)
			continue;
		pair<int, int> p = dfs(it, u, min(mn, arr[u]));
		a.first += p.first;
		a.second += p.second;
	}
	if(arr[u] < mn)
	{
		int take = min(a.first, a.second);
		cost += 2 * take * arr[u];
		a.first -= take;
		a.second -= take;
	}
	return a;
}
 
int32_t main()
{
	IOS;
	cin >> n;
	for(int i = 1; i <= n; i++)
		cin >> arr[i] >> b[i] >> c[i];
	for(int i = 1; i <= n - 1; i++)
	{
		int u, v;
		cin >> u >> v;
		g[u].push_back(v);
		g[v].push_back(u);
	}	
	pair<int, int> ans = dfs(1, 0, 2e9);
	if(ans.first || ans.second)
		cout << -1;
	else
		cout << cost;
	return 0;
}

Author of this problem was FastestFinger.

#include <bits/stdc++.h>
using namespace std;
 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define int long long
 
const int N = 2005;
 
int n;
string s, t;
int suf[26][N], suf2[26][N];
int cache[N][N];
 
int dp(int i, int j)
{
	if(j == 0)
		return 0;
	int &ans = cache[i][j];
	if(ans != -1)
		return ans;
	ans = 2e9;
	if(i > 0)
	{
		ans = 1 + dp(i - 1, j);
		if(s[i - 1] == t[j - 1])
			ans = min(ans, dp(i - 1, j - 1));
	}
	int ch = t[j - 1] - 'a';
	if(suf[ch][i + 1] - suf2[ch][j + 1] > 0)
		ans = min(ans, dp(i, j - 1));
	return ans;
}
 
int32_t main()
{
	IOS;
	int tc;
	cin >> tc;
	while(tc--)
	{
		cin >> n >> s >> t;
		for(int i = 0; i <= n; i++)
			for(int j = 0; j <= n; j++)
				cache[i][j] = -1;
		for(int i = 0; i <= 25; i++)
			for(int j = 0; j <= n + 1; j++)
				suf[i][j] = suf2[i][j] = 0;
		for(int i = n; i >= 1; i--)
		{
			for(int j = 0; j < 26; j++)
			{
				suf[j][i] = suf[j][i + 1];
				suf2[j][i] = suf2[j][i + 1];
			}
			suf[s[i - 1] - 'a'][i]++;
			suf2[t[i - 1] - 'a'][i]++;
		}
		int ans = dp(n, n);
		if(ans > 1e9)
			ans = -1;
		cout << ans << endl;
	}
	return 0;
}

Update: Part 2 can be found here!

Many thanks to aryanc403 for helping me with various things for both Part 1 and Part 2. I'd also like to thank _Aaryan_, forgotter, l_returns and Jeel_Vaishnav for their useful comments while test-reading part 2!

x------------------------------------------------------------------------------------------------------------------x

Hello Codeforces community,

I was planning on writing a blog post about our ICPC regionals experience this year for a while now. The reason is that it is fun to know about various team's experiences, how they prepared etc and also maybe how their thought process was at various times of the competition. Also considering that different regionals have different setups usually (I would argue that Indian regionals do not have more of heavier data structures and relatively more adhoc and math questions), I haven't seen enough posts by teams who have done well on these competitions to give us an idea of what it was like participating in the contest.

The first part can be found here.

An example post of what I am talking about is here. I found it extremely fun to read, and it really felt like a proper regionals experience.

Thus, we decided to make a post on our experiences at the Indian regionals this year and we hope you will like it :)

I plan to cover some good problem ideas and how we approached them, our strategy at various times during the contests, and even what we did to relax (this is an informal blog, so there will be somethings off-topic for those just wishing to learn through these. Please feel free to skip through them). While right now I have only written about pre-regionals stages, I will write about the regionals stages soon. Please let me know about any feedback that you have, either in the comments or through PM!

Sometime back, there was a blog on codeforces where people were sharing interesting logic riddles/puzzles/ whatever-you-have-it. I can't find it anymore, either by google search or by Codeforces search. Can anyone provide the link for the same?

P.S I remember there being a problem about getting 2n cards face-down in some order and n guesses, and the solution (which was very cute) was to break the longest permutation into parts smaller than n in size, but I don't remember what it was exactly :(

It seems that there is a bug when you try to change the name of a team. It says "team updated" but the name doesn't change.

Edit: this works now.