Day 25 | Codeforces Div3 Round 820 (A|B|C) | C++

Let's solve Codeforces round 820 A, B, and C today. I will also post how to solve interactive E tomorrow once, I understand why it is failing at test case 27.

I am sharing my contest implementations as well and will add my simple implementation to them soon. My contest implementation uses my template, it might be a little hard to comprehend it, but try it this way - My solution for each test case is implemented in solve()

Two Elevators | Contest Implementation

It is quite obvious what we have to do here.

time-taken by elevator a to reach floor 1, t1 = a - 1;

time-taken by elevator b to reach floor 1, t2 = abs(b-c) + c - 1;

Hence, as the question suggests we will

• choose 1 if t1 < t2

• choose 2 if t1 > t2

• choose none if equal

You can implement it like this

void solve(int test_case){
    int a,b,c;
    cin >> a >> b >> c;
    int e1 = abs(a-1);
    int e2 = abs(c-b) + abs(c-1);
    if(e1 < e2){
        cout << 1 << '\n';
    }
    else if(e1 > e2){
        cout << 2 << '\n';
    }else{
        cout << 3 << '\n';
    }
}

Decode String | Contest Implementation

This is a fun question, I liked it. The point to notice is that for every 2-digit number there is 0, thus making it a 3-digit number.

So if we reverse the string, then the next two characters after every unprocessed 0 are the numbers (in reverse 17 will be read at 71 because the string is reversed)

So we can solve it like this

• Reverse the input

• if you encounter anything other than 0, then place its character in the answer

• if you encounter 0, then compute the number and place it in the answer

You can do it like this

    reverse(s.begin(),s.end());
	string ans = "";
	for(int i = 0; i < s.size(); i++){
		int num = 0;
		if(s[i] == '0'){
			num = s[i+2] - '0';
			num*=10;
			num += s[i+1] - '0';
			i+=2;
		}else{
			num = s[i] - '0';
		}
		ans += char(num + 'a' - 1);
	}
	reverse(ans.begin(),ans.end());
	cout << ans << '\n';

Jumping on Tiles | Contest Implemenation

This is a good question.

Notice that we need minimum cost,

Your lowest possible cost is obviously |s[0] - s[n-1]|

But let's say you are going from a-f

then if you go directly a-f (+5) or go like a-b-c-d-e-f (it will still be the same as +1 in each)

But if we go like this

a - c - b - f, then it is not minimum cost as it will be +2 +2 + 4 = 8

So, basically we will go in either non-decreasing order (if s[0] < s[n-1]) like in above example

or in non-increasing order like going from f to a

There is no barrier on which cell we can go to next, we actually just print all cells in sorted order of character (ASC or DSC depending on s[0] and s[1])

	string s;
	cin >> s;
	int n = s.size();
	vector<pair<char,int>> a;
	for(int i = 0; i < s.size(); i++)
		a.push_back(mp(s[i],i+1));
	vector<int> ans;
	sort(a.begin(), a.end());
	bool special_case = s[0] > s.back() ;
	if(special_case)
		ans.push_back(s.size());
	for(int i = 0; i < s.size(); i++){
		if(a[i].S == s.size() && special_case)continue;
		if(a[i].S == 1 && special_case)continue;
		if(a[i].F < min(s[0],s.back()))continue;
		if(a[i].F > max(s[0],s.back()))break;
		ans.push_back(a[i].S);
	}
	if(special_case){
		ans.push_back(1);
		reverse(ans.begin(),ans.end());
	}
	cout << abs(s[0] - s.back()) << " " <<ans.size() << "\n";
	for(int i : ans) cout << i << " ";
	cout << "\n";

Please like and share my posts if they are helpful.