Идея: pashka
Разбор
Tutorial is loading...
Решение
for _ in range(int(input())):
s = input()
for c in "abcdefgh":
if c != s[0]:
print(c + s[1], end=' ')
for c in "12345678":
if c != s[1]:
print(s[0] + c, end=' ')
print()
Идея: pashka, MikeMirzayanov
Разбор
Tutorial is loading...
Решение
for _ in range(int(input())):
s = list(input())
n = len(s)
upper = []
lower = []
for i in range(n):
if s[i] == 'b':
s[i] = ''
if lower:
s[lower.pop()] = ''
continue
if s[i] == 'B':
s[i] = ''
if upper:
s[upper.pop()] = ''
continue
if 'a' <= s[i] <= 'z':
lower += [i]
else:
upper += [i]
print(''.join(s))
1907C - Удаление некрасивых пар
Идея: Vladosiya
Разбор
Tutorial is loading...
Решение
orda = ord('a')
def solve():
n = int(input())
cnt = [0] * 26
for c in input():
cnt[ord(c) - orda] += 1
mx = max(cnt)
print(max(n % 2, 2 * mx - n))
for _ in range(int(input())):
solve()
Идея: MikeMirzayanov, Vladosiya
Разбор
Tutorial is loading...
Решение
def solve():
n = int(input())
seg = [list(map(int, input().split())) for x in range(n)]
def check(k):
ll, rr = 0, 0
for e in seg:
ll = max(ll - k, e[0])
rr = min(rr + k, e[1])
if ll > rr:
return False
return True
l, r = -1, 10 ** 9
while r - l > 1:
mid = (r + l) // 2
if check(mid):
r = mid
else:
l = mid
print(r)
for _ in range(int(input())):
solve()
Идея: pashka
Разбор
Tutorial is loading...
Решение
t = int(input())
for _ in range(t):
n = int(input())
cnt = 1
while n > 0:
d = n % 10
n //= 10
mul = 0
for i in range(d + 1):
for j in range(d + 1):
if d - i - j >= 0:
mul += 1
cnt *= mul
print(cnt)
Идея: pashka
Разбор
Tutorial is loading...
Решение
t = int(input())
for _ in range(t):
n = int(input())
a = list(map(int, input().split()))
a = list(reversed(a))*2
p = [0]
q = [0]
for i in range(n*2-1):
p.append(p[-1]+1 if a[i]>=a[i+1] else 0)
q.append(q[-1]+1 if a[i]<=a[i+1] else 0)
minn = 1000000
for i in range(n-1,len(p)):
if p[i] == n-1:
minn = min(minn, i-n+1, len(p)-i+1)
if q[i] == n-1:
minn = min(minn, len(p)-i, i-n+2)
print(-1 if minn == 1000000 else minn)
Идея: pashka
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
#define long long long int
#define DEBUG
using namespace std;
// @author: pashka
void solve(){
int n;
cin >> n;
vector<bool> s(n);
{
string ss;
cin >> ss;
for (int i = 0; i < n; i++) {
s[i] = ss[i] == '1';
}
}
vector<int> a(n);
for (int i = 0; i < n; i++) {
cin >> a[i];
a[i]--;
}
vector<int> res;
vector<int> d(n);
for (int i = 0; i < n; i++) {
d[a[i]]++;
}
vector<int> z;
for (int i = 0; i < n; i++) {
if (d[i] == 0) z.push_back(i);
}
for (int i = 0; i < (int)z.size(); i++) {
int x = z[i];
int y = a[x];
if (s[x]) {
res.push_back(x);
s[x] = !s[x];
s[y] = !s[y];
}
d[y]--;
if (d[y] == 0) {
z.push_back(y);
}
}
vector<bool> u(n);
for (int i = 0; i < n; i++) {
if (s[i] && !u[i]) {
int x = i;
vector<int> p;
vector<bool> ps;
int c = 0;
while (!u[x]) {
p.push_back(x);
ps.push_back(s[x]);
c += s[x];
u[x] = true;
x = a[x];
}
int k = p.size();
p.push_back(x);
ps.push_back(s[x]);
if (c % 2 == 1) {
cout << -1;
return;
}
vector<int> v1;
vector<bool> ps1 = ps;
for (int j = 0; j < k; j++) {
if (j == 0 || ps1[j]) {
v1.push_back(p[j]);
ps1[j] = !ps1[j];
ps1[j + 1] = !ps1[j + 1];
}
}
vector<int> v2;
vector<bool> ps2 = ps;
for (int j = 0; j < k; j++) {
if (j != 0 && ps2[j]) {
v2.push_back(p[j]);
ps2[j] = !ps2[j];
ps2[j + 1] = !ps2[j + 1];
}
}
if (v1.size() < v2.size()) {
for (auto x : v1) {
res.push_back(x);
}
} else {
for (auto x : v2) {
res.push_back(x);
}
}
}
}
cout << res.size() << "\n";
for (auto x : res) cout << x + 1 << " ";
}
int main() {
int t;
cin >> t;
for(int _ = 0; _ < t; ++_){
solve();
cout << "\n";
}
return 0;
}
It would be better if you added formatting for the solution to Problem F.
UPD: Thanks
In E, we can also notice that the answer to each digit x(0-9) is simply ((x+1)*(x+2))/2.
Explanation 1: Let, x be split as x=a+b+c. If a=x, b+c=0; this will generate one combination->(x,0,0). If a=x-1, b+c=1; this will generate two combinations->(x-1,0,1) and (x-1,1,0).Similarly you can notice that the total combinations for digit x= 1+2+3+..+x+x+1= ((x+1)*(x+2))/2. So, no need to use the loops to calculate this.
Explanation 2(Suggested by my brother): The combinatorics formula to distribute x as a sum of k non-negative numbers is C(n+k-1,k-1) which here transforms to C(x+3-1,3-1)=C(x+2,2)=((x+1)*(x+2))/2.
Or, you could have just figured this out by looking at the test cases.
How did you get this equation? ((x+1)*(x+2))/2
Summation of numbers from 1 to n = (n*(n+1))/2
Why do I calculate numbers from 1 to x+1 ?
I think you might be confused in this line : "Similarly you can notice that the total combinations for digit x= 1+2+3+..+x+x+1= ((x+1)*(x+2))/2. So, no need to use the loops to calculate this." that's why you need to calculate the sum from 1 to x+1. Please correct me if I am wrong.
It is not clear to me why we will stop at x+1 "
Maybe this will help:
When a=x, there is 1 combination: (x,0,0)
When a=x-1, 2 combinations: (x-1,1,0),(x-1,0,1)
When a=x-2, 3 combinations: (x-2,2,0),(x-2,1,1),(x-2,0,2)
.
.
.
When a=1, x combinations: (1,x-1,0),(1,x-2,1),(1,x-3,2)----(1,1,x-2),(1,0,x-1)
When a=0, x+1 combinations: (0,x,0),(0,x-1,1),(0,x-2,2)----(0,1,x-1),(0,0,x)
Total combinations =1+2+....+x+(x+1)
This is called stars and bars. U can read more about in this article in TOPCODER https://www.topcoder.com/thrive/articles/Basics%20of%20Combinatorics
Thank You Very Much for sharing this
Was solving this, did the exact thing and then saw the editorial. Why is this solution not in the main editorial?
I guess the problem setters always have their own solution in mind at the time they are designing the problem. This ensures the problem can actually be solved. This is a good approach but it may sometimes happen that the first thought solution is not the the most optimal one. Then during a later reading the setter or a contestant finds a more optimal one. Well, that's the crux of research, understanding the optimizing over known results. Just like how my brother gave an even better understanding over my original solution.
Video Editorial For Problems A,B,C,D,E,F,G._
After this video, can you speak English or have subtitles in English for your video so that all coders around the world can understand it?
Greeting sir/bhiya
I am trying this question from tomorrow smjh nahi aarha kaha galti kr raha hu , if you could point it would be great help .
Link of submission .
Thankyou
The way you are moving from one node to another while applying topological sort is wrong and also you are code is bit messy while solving around cycle of the graph. You can look at my code to understand it better. My code
wasn't able to participate in this contest, but the problems were very good, I think. although G does feel like it reduces down to just applying a standard graph algorithm, no?
Yes, topological sort with some greedy approach.
Video solution for Chinese:
BiliBili
gratitudes!
Can you explain the transition states in this DP.
Wow! It so a beautiful DP
Can someone please explain why this code for G is giving TLE at test case 25. I am following a bit different approach to encounter bulbs in cycle but it is O(N) only. This is my submission link -> https://mirror.codeforces.com/contest/1907/submission/236036536
Can someone explain F,i don't understand tutorial at all.
You can think that:
So, we can conclude that:
The final structure must have a long string of S's in the middle, and an optional R at the beginning and end.
Thank you very much!
how does writing the array twice and then looking at the increasing and decreasing segments help ?
Such array contains all shifts of initial one, if there is an increasing or decreasing segment of length $$$n$$$ it is one of the shifts we are searching for.
How can someone reach SRS===R condition?(How to think of this condition,intuition wise)
Consider RSR, you move the first element of array to the last place, and shift all other elements to the left, it's a reversed operation to S, so S(RSR) will not change the array, therefore SRS === R:)
In C, how do you prove that if no character appears more than floor(n/2) times, we can always achieve n%2 length of the final string? Please help.
Does anyone have a formal proof for this?
Yes, https://mirror.codeforces.com/blog/entry/122931?#comment-1090827
коротко и ясно
Nearly 24 hours have passed, and the rating still doesn't change?
Is the reason why editorial's check function for Binary Search works trivial? Because after x steps, if the intersection with the segment is non empty => I have one sequence of steps that lands me after x steps inside that interval. It does not ensure that those steps are consistent with the last x-1 regions right? (It should since the editorial is right, but I don't see how we can prove it.)
Consider the segment after x steps, if you can find one with intersection. For all points inside this segment there is a point in the last segment you could have reached it from. In other words you can pick any point in the current valid segment, and there is a point in the last segment from where you could reach this. You can continue this reasoning to the first segment. I agree, this is not that trivial to see.
Thank you for such a wonderful round pashka, Vladosiya, MikeMirzayanov. I will be looking forward to a new and interesting round from you.
G is very similar to https://mirror.codeforces.com/problemset/problem/1872/F. Just a little addition that the nodes now have states attached to them.
Hi, can anyone tell me why this is TLE in Python but AC in C++?
Python: 236125120 it is TLE without the fastIO line as well.
C++: 236125273
I am having an identity crisis.
*accidentally posted the comment in Russian, my apologies for the spam
Because string concatenation via + is very expensive operation in Python. Here is you code but string and s += are replaced with array and s.append(). It passes. 236138895
Is this Tutorial written for those who don't need it?
No proof, No explanation, Only conclusion. Oh, yes, I completely understood
236178810 Can Anyone tell me what is wrong in the mentioned code.
The problems are great, but I feel that the editorial is written rather poorly.
Here is a (hopefully) more intuitive editorial of problem F -
Let us consider the inverse of the operations given in the original problem, for the sake of better understanding.
Given a sorted array in non-decreasing order $$$s$$$, you can perform two operations:
- Shift Inverse: move the first element of the array to the last place, and shift all other elements to the left, so you get the array $$$s_2,s_3,...,s_n,s_1$$$.
- Reverse: reverse the whole array, so you get the array $$$s_n,s_{n-1},...,s_1$$$.
By observation, we realize, that there are three types of arrays that arise when we perform the above operations on some sorted array $$$s$$$:
i) The most basic of it is the reverse of $$$s$$$ — the array $$$s_n,s_{n-1},...,s_1$$$.
ii) An array of the form $$$s_k,s_{k+1},...,s_n,s_1,s_2,...,s_{k-1}$$$, $$$1 \lt k \le n$$$.
iii) An array of the form $$$s_k,s_{k-1},...,s_1,s_n,s_{n-1},...,s_{k+1}$$$, $$$1 \le k \lt n$$$.
Thus, we can break down the original problem into the following cases:
If $$$a$$$ is sorted — No moves required, answer is $$$0$$$.
If $$$a$$$ is sorted in reverse order — reversing the array solves it, answer is $$$1$$$.
If $$$a$$$ is of the form presented in case ii) above —
Let us break the array into two parts: the first part being the part of $$$a$$$ corresponding to $$$s_k,s_{k+1},...,s_n$$$ (let us call this part $$$F$$$) and the second part being the part of $$$a$$$ corresponding to $$$s_1,s_2,...,s_{k-1}$$$ (let us call this part $$$S$$$). We can solve this in two ways —
(a) perform the 'Shift' operation on all elements of $$$S$$$. So total number of moves = $$$|S|$$$.
(b) perform the 'Reverse' operation on $$$a$$$, perform 'Shift' operation on all elements of $$$F$$$, and then perform the 'Reverse' operation again. So total number of moves = $$$|F|+2$$$.
We take the minimum of (a) and (b), and that is our answer.
If $$$a$$$ is of the form presented in case iii) above —
Let us break the array into two parts: the first part being the part of $$$a$$$ corresponding to $$$s_k,s_{k-1},...,s_1$$$ (let us call this part $$$F$$$) and the second part being the part of $$$a$$$ corresponding to $$$s_n,s_{n-1},...,s_{k+1}$$$ (let us call this part $$$S$$$). We can solve this in two ways —
(a) perform the 'Shift' operation on all elements of $$$S$$$, and then perform the 'Reverse' operation. So total number of moves = $$$|S|+1$$$.
(b) perform the 'Reverse' operation on $$$a$$$ and then perform 'Shift' operation on all elements of $$$F$$$. So total number of moves = $$$|F|+1$$$.
We take the minimum of (a) and (b), and that is our answer.
If $$$a$$$ is neither of the cases presented above, then the answer is $$$-1$$$.
C++ code for reference.
So much better than the editorial, thank you very much!
236178810 I did same approach ? Why is it wrong then?
[DOUBT][PROBLEM G] — > can someone explain how to find minimum number of operations to turn off all turned on lights in the cycle? firstly, we will remove/turn off all nodes with in-degree=0 and will keep on removing till we find the cycle. I am struck after this point.
Find any light that is on in the cycle. There are only two ways for it too be turned off — either you directly flip it's switch or you flip the switch of the previous node in the cycle. Once you've chosen the starting node to start flipping you can move through the greedily flipping any lights that are on. Calculate the number of flips for both starting nodes and choose the smaller.
The editorials are very hard to understand, specially for E, F and G. :)
:D
In Problem E. 1907E — Good Triples Can someone please tell the proof for:
"A triplet is considered good only if each digit of the number n was obtained without carrying over during addition."
This is a good observation, but how can I prove such information or approach it at least?
There exists a hashing solution to problem F.
You can save two hash values , one for the sorted non-decreasing array and the other for the sorted non-increasing array.
Then, you can try doing the operations on the original array or on the reverse of it ( with additional cost of one operation). Doing the operation on an element which is the last in array is simply subtracting the element from the current hash, dividing by base and adding this value * base ^ (n-1).
Then, the first moment where the hashes are equal , we have found an answer to minimize over it and stop doing operations.
Link to submission: https://mirror.codeforces.com/contest/1907/submission/236598692.
P.S I found this solution more understandable than what is written in the tutorial.
But hashing ( although the probability is very small) may lead you to collisions in the worst case..
Probability of collision with double hashing is very very small : )
If anyone want solution for question F , i have explained in comments in simple words 273078914