amnchouhn's blog

Short & Easier Solution to C. Even Positions from last contest.
By amnchouhn, history, 5 hours ago, In English

I have found a very short solution of 1997C - Even Positions compared to what's available everywhere. Please upvote if found helpful.

Shayan, adedalic, BledDest, Neon, awoo Is there any edge case for this solution?

#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define FAST_IO ios::sync_with_stdio(false); cin.tie(nullptr);

void solve() {
	int n; cin >> n;
	string s; cin >> s;
	int ans = 0;
	for (int i = 0; i < n; i += 2) {
		if (s[i + 1] == ')') {
			ans += 1;
		}
		else {
			ans += 3;
		}
	}
	cout << ans << nl;
}

int main() {
	FAST_IO
	int tc; cin >> tc;
	while (tc--) {solve();}
}
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 hours ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

This is pretty clever! Starting from the end of the string helped me understand this approach -- the last character must be a ')', and from there you can have either -)-) or -(-). In the first case, you can do -)(), and ignore the last block () of size 2, adding 1 to the answer. Otherwise, for -(-) the next best thing to do is (()), adding 3 to the answer and ignoring the this last block of size 4. I think this solution works great!

→ Reply
»
112 minutes ago, # |
  Vote: I like it 0 Vote: I do not like it

shorter one

i still don't get how it works lol

→ Reply
  • »
    »
    89 minutes ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Realized a flaw in my previous reasoning that aligns with the solution you mentioned -- starting from the back, we can only block off when you hit another ')'. Until then, we have something like )-(-(...-(-). Now, a ')' can be greedily put in every space except the first one from the left. That needs to be a '(' to block it off. So we can think of each '(' as adding 3 to the answer: 1 for the '()' that's formed, and 2 for the cost of the last ')', which is paired with the first '(' in the block. The fixed ')' at the end also adds 1 to its cost.

    The solution you mentioned works similarly -- it adds 1 for each '()' at the start with pairs/2. Then it counts the extra +2s for each '('. Hope that helps =D

    → Reply
    • »
      »
      »
      75 minutes ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for explaining, it really helped.

      → Reply