Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

vovuh's blog

Codeforces Round #555 (Div. 3) Editorial
By vovuh, history, 22 months ago, In English

1157A - Reachable Numbers

Idea: BledDest

Tutorial
Tutorial is loading...
Solution
def f(x):
	x += 1
	while(x % 10 == 0):
		x //= 10
	return x

a = set()
n = int(input())

while(not(n in a)):
	a.add(n)
	n = f(n)

print(len(a))

1157B - Long Number

Idea: BledDest

Tutorial
Tutorial is loading...
Solution
#include<bits/stdc++.h>

using namespace std;

int f[10];
string s;

int main()
{
	int n;
	cin >> n;
	cin >> s;
	for(int i = 1; i <= 9; i++)
		cin >> f[i];
	vector<int> diff;
	for(int i = 0; i < n; i++)
		diff.push_back(f[s[i] - '0'] - (s[i] - '0'));
	for(int i = 0; i < n; i++)
		if(diff[i] > 0)
		{
			while(i < n && diff[i] >= 0)
			{
				s[i] = char(f[s[i] - '0'] + '0');
				i++;
			}
			break;
		}
	cout << s << endl;
}

1157C1 - Increasing Subsequence (easy version)

Idea: MikeMirzayanov

Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	
	string res;
	int l = 0, r = n - 1;
	int lst = 0;
	while (l <= r) {
		vector<pair<int, char>> cur;
		if (lst < a[l]) cur.push_back(make_pair(a[l], 'L'));
		if (lst < a[r]) cur.push_back(make_pair(a[r], 'R'));
		sort(cur.begin(), cur.end());
		if (int(cur.size()) == 2) {
			cur.pop_back();
		}
		if (int(cur.size()) == 1) {
			if (cur[0].second == 'L') {
				res += 'L';
				lst = a[l];
				++l;
			} else {
				res += 'R';
				lst = a[r];
				--r;
			}
		} else {
			break;
		}
	}
	
	cout << res.size() << endl << res << endl;
	
	return 0;
}

1157C2 - Increasing Subsequence (hard version)

Idea: MikeMirzayanov

Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	
	string res;
	int l = 0, r = n - 1;
	int lst = 0;
	while (l <= r) {
		vector<pair<int, char>> cur;
		if (lst < a[l]) cur.push_back(make_pair(a[l], 'L'));
		if (lst < a[r]) cur.push_back(make_pair(a[r], 'R'));
		sort(cur.begin(), cur.end());
		if (int(cur.size()) == 2 && cur[0].first != cur[1].first) {
			cur.pop_back();
		}
		if (int(cur.size()) == 1) {
			if (cur[0].second == 'L') {
				res += 'L';
				lst = a[l];
				++l;
			} else {
				res += 'R';
				lst = a[r];
				--r;
			}
		} else if (int(cur.size()) == 2) {
			int cl = 1, cr = 1;
			while (l + cl <= r && a[l + cl] > a[l + cl - 1]) ++cl;
			while (r - cr >= l && a[r - cr] > a[r - cr + 1]) ++cr;
			if (cl > cr) {
				res += string(cl, 'L');
			} else {
				res += string(cr, 'R');
			}
			break;
		} else {
			break;
		}
	}
	
	cout << res.size() << endl << res << endl;
	
	return 0;
}

1157D - N Problems During K Days

Idea: MikeMirzayanov

Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n, k;
	cin >> n >> k;
	if (n < k * 1ll * (k + 1) / 2) {
		cout << "NO" << endl;
		return 0;
	}
	
	int nn = n - k * (k + 1) / 2;
	vector<int> a(k);
	for (int i = 0; i < k; ++i) {
		a[i] = i + 1 + (nn / k) + (i >= k - nn % k);
	}
	
	if (nn != k - 1) {
		cout << "YES" << endl;
		for (int i = 0; i < k; ++i) cout << a[i] << " ";
		cout << endl;
	} else {
		if (k > 3) {
			--a[1];
			++a[k - 1];
		}
		if (k == 2 || k == 3) {
			cout << "NO" << endl;
		} else {
			cout << "YES" << endl;
			for (int i = 0; i < k; ++i) cout << a[i] << " ";
			cout << endl;
		}
	}
	
	return 0;
}

1157E - Minimum Array

Idea: vovuh

Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<int> a(n);
	multiset<int> b;
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	for (int i = 0; i < n; ++i) {
		int x;
		cin >> x;
		b.insert(x);
	}
	
	for (int i = 0; i < n; ++i) {
		auto it = b.lower_bound(n - a[i]);
		if (it == b.end()) it = b.begin();
		cout << (a[i] + *it) % n << " ";
		b.erase(it);
	}
	cout << endl;
	
	return 0;
}

1157F - Maximum Balanced Circle

Idea: MikeMirzayanov

Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>

using namespace std;

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	int n;
	cin >> n;
	vector<int> a(n);
	vector<int> cnt(200 * 1000 + 1);
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
		++cnt[a[i]];
	}
	
	sort(a.begin(), a.end());
	a.resize(unique(a.begin(), a.end()) - a.begin());
	
	int l = 0, r = 0;
	int ans = cnt[a[0]];
	for (int i = 0; i < int(a.size()); ++i) {
		int j = i + 1;
		int sum = cnt[a[i]];
		while (a[j] - a[j - 1] == 1 && cnt[a[j]] > 1) {
			sum += cnt[a[j]];
			++j;
		}
		int cr = j - 1;
		if (j < n && a[j] - a[j - 1] == 1) {
			sum += cnt[a[j]];
			cr = j;
		}
		if (ans < sum) {
			ans = sum;
			l = i;
			r = cr;
		}
		i = j - 1;
	}
	
	cout << ans << endl;
	for (int c = 0; c < cnt[a[l]]; ++c) cout << a[l] << " ";
	for (int i = l + 1; i < r; ++i) {
		for (int c = 0; c < cnt[a[i]] - 1; ++c) cout << a[i] << " ";
	}
	for (int c = 0; l != r && c < cnt[a[r]]; ++c) cout << a[r] << " ";
	for (int i = r - 1; i > l; --i) cout << a[i] << " ";
	cout << endl;
	
	return 0;
}

1157G - Inverse of Rows and Columns

Idea: vovuh

This is the comment about the quadratic solution. Thank you so much for mentioning this fact, STommydx!

Tutorial
Tutorial is loading...
Solution
#include <bits/stdc++.h>

using namespace std;

int n, m;

void invRow(vector<vector<int>> &a, int idx) {
	for (int pos = 0; pos < m; ++pos) {
		a[idx][pos] ^= 1;
	}
}

void invCol(vector<vector<int>> &a, int idx) {
	for (int pos = 0; pos < n; ++pos) {
		a[pos][idx] ^= 1;
	}
}

int main() {
#ifdef _DEBUG
	freopen("input.txt", "r", stdin);
//	freopen("output.txt", "w", stdout);
#endif
	
	cin >> n >> m;
	vector<vector<int>> a(n, vector<int>(m));
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < m; ++j) {
			cin >> a[i][j];
		}
	}
	
	for (int cnt0 = 0; cnt0 <= m; ++cnt0) {
		string r(n, '0');
		string c(m, '0');
		vector<vector<int>> b = a;
		for (int j = 0; j < m; ++j) {
			if ((j < cnt0 && b[0][j] == 1) || (j >= cnt0 && b[0][j] == 0)) {
				invCol(b, j);
				c[j] = '1';
			}
		}
		bool ok = true;
		if (cnt0 < m) {
			for (int i = 1; i < n; ++i) {
				int sum = accumulate(b[i].begin(), b[i].end(), 0);
				if (sum != 0 && sum != m) {
					ok = false;
				} else if (sum == 0) {
					invRow(b, i);
					r[i] = '1';
				}
			}
		} else {
			int idx = -1;
			for (int i = 1; i < n; ++i) {
				int sum = accumulate(b[i].begin(), b[i].end(), 0);
				if (sum != 0 && sum != m) {
					if (idx != -1) ok = false;
					else idx = i;
				}
			}
			if (idx == -1) {
				for (int i = 1; i < n; ++i) {
					int sum = accumulate(b[i].begin(), b[i].end(), 0);
					if (sum == 0) {
						invRow(b, i);
						r[i] = '1';
					}
				}
			} else {
				for (int i = 1; i < idx; ++i) {
					int sum = accumulate(b[i].begin(), b[i].end(), 0);
					if (sum == m) {
						invRow(b, i);
						r[i] = '1';
					}
				}
				if (b[idx][0] == 1) {
					invRow(b, idx);
					r[idx] = '1';
				}
				for (int j = 1; j < m; ++j) {
					if (b[idx][j] < b[idx][j - 1]) {
						ok = false;
					}
				}
				for (int i = idx + 1; i < n; ++i) {
					int sum = accumulate(b[i].begin(), b[i].end(), 0);
					if (sum == 0) {
						invRow(b, i);
						r[i] = '1';
					}
				}
			}
		}
		if (ok) {
			cout << "YES" << endl << r << endl << c << endl;
			return 0;
		}
	}
	
	cout << "NO" << endl;
	
	return 0;
}
 
 
 
 
  • Vote: I like it
  • +34
  • Vote: I do not like it

Comments Comments (42)
»
22 months ago, # |
  Vote: I like it +4 Vote: I do not like it

The editorial for Problem G looks like a little the editorial of Problem F

→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Thank you for mentioning, I just forgot to fix this place :)

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

it was a greedy contest :D Good round by the way

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My solution problem D after contest(sad): 1)Find minimum first element with binary search 2) let's get maximum suffix, when we can add 1 for all numbers on segment, do it, while exist this is segment 3) end O(nLogn), and write easy

https://codeforces.com/contest/1157/submission/53393728

→ Reply
»
22 months ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

In problem "A" we don't need to store reachable numbers ,As soon as we hit a number less than 10 we add 9 to our counter and stop

Nice problems btw
→ Reply
»
22 months ago, # |
  Vote: I like it +8 Vote: I do not like it

1157D — N Problems During K Days can be solved simply by putting $$$1,2,\dots,k$$$ initially and then trying to put $$$(n-(k*(k+1)/2))/k$$$ elements in each, and then from reverse order adding as many elements in each position as possible, without considering special cases separately.

You can go through my submission for clear understanding.

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem number B, why we are not checking the digits which comes after the first digit which become less after replacing.

for example 
if a = 13373
and f[] = {1, 2, 5, 4, 6, 6, 3, 1, 9};
then the correct answer is 15573 but why not 15575;
→ Reply
  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The problem mentions a contiguous subsegment and the operation can be performed at most once.

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone help me in finding the cause of TLE in Problem D in my solution.

→ Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 2   Vote: I like it +2 Vote: I do not like it

    "erase" for vector works in linear time of size of the whole vector

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

      And what about erase in multiset?

      Is there any way that I can still use vector and solve the problem. I know that using multiset will make it very easy but still as a matter of knowing.

      BTW, Thanks for the reply buddy !!

      → Reply
      • »
        »
        »
        »
        22 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        You can’t use vector.erase for this problem. unless you want to code yourself a multiset libary for vectors, multiset is the only way to solve the problem in AC time, which erases elements from the container at log(n) time.

        → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This problem also has a solution like D:

https://www.codechef.com/SNCK1B19/problems/MAXPRODU

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

please help me...y its showing error in test case 15 always!!!

https://codeforces.com/contest/1157/submission/53440011

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

    make it a habit to write long codes, your is too short to get accepted

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone have a solution for problem E which does not involve STL structures, specifically without using multiset,set,map or multimap ?

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Help me out in finding TLE in my Solution for Problem C

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E, why "lower_bound(m.begin(), m.end(), val)" gives TLE 53488500 and "m.lower_bound(val)" got Accepted 53488794 ?

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Problem D: "Then if nn != k — 1 or k = 1 then this answer is correct."

Any explanation for this ?

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem 1157c1, what if the input is

7 7 4 5 6 3 2 1

The solution code out puts 5 RRRRL But if I discard 7 and take the subsequence [4 5 6 3 2 1],it's possible to get a strictly increasing subsequence of size 6, right?

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When is the next div3?

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's wrong with my solution for problem B? https://codeforces.com/contest/1157/submission/53566680 I am getting wrong answer on test case 7

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I solved D in a different way. Mine

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I'm kind of late, but problem D can be easily (more or less) solved by binary searching the first element, and then binary searching every other element as well, from left to right, so that the minimum possible sum is <= n and the maximum possible sum is >= n. My submission

→ Reply
»
22 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Nice Problem Set.

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For the D problem, I just initialized array to 1,2,...,K then added (S — (K * (K + 1)) / 2) / N to every element in the array, and then just distributed (S — (K * (K + 1)) / 2) % N from the behind appropriately. Just wondering why there were so less submissions for this problem?

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem Minimum Array using segment trees??

→ Reply
  • »
    »
    22 months ago, # ^ |
    ← Rev. 5   Vote: I like it 0 Vote: I do not like it

    I solved with segment tree, so I will try to explain my solution:

    First we need to sort B array, to be able to find some index j for each $$$A_i$$$ such that $$$A_i + B_l \lt n$$$ for all $$$l \lt j$$$, and $$$A_i + B_r \ge n$$$ for all $$$r \ge j$$$. We'll have only one index j for each $$$A_i$$$, because $$$max(A) + max(B) < 2n$$$.

    After that we can divide B array in two parts and find the best among these greedly, using segment tree here to get minimum, and then updating the used element to not be taken more than once.

    Submission

    → Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone please tell why my recursive solution for c2 gives tle ? I think my solution too has the same time complexity as the editorial's .

→ Reply
»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Guys can someone help me understand why http://codeforces.com/contest/1157/submission/53985650 gives wrong results on test case 9

→ Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it 
Your code here...

//why it doesn't work for problem B

include<bits/stdc++.h>

using namespace std; int main() { char x[10]; int n,i,f=0,t1,t2; string p; cin >> n; cin >> p; for(i=1;i<=9;i++) cin >> x[i]; for(i=0;i<p.size();i++) { t1=p[i]-'0'; t2=x[t1]-'0'; // cout << t1 << " " << t2 << endl; if(t2>t1) { p[i]=x[t1]; f=1; } else if(f==1) { break; }

} cout << p << endl;

}

→ Reply
»
17 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

/*what's going on the problem C2 it give the right answer for test case 1 in online compiler but in the cf compiler shows wrong answer.I submitted this code in gnu c++17 */ https://codeforces.com/contest/1157/submission/61860615

→ Reply
»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone tell me mathematical proof of E i just wanted to know why finding greater element is optimal than finding lesser value element if n-a[i] is not found

→ Reply
  • »
    »
    5 weeks ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    It is because for any $$$k\geq n-a[i]$$$ and any $$$0\leq b < n-a[i]$$$, you will have $$$(a[i]+k) \mod n \leq a[i] + (n-1) \mod n < a[i] \leq a[i]+b < n$$$.

    → Reply