Идея: senjougaharin, разработка: senjougaharin
Разбор
Tutorial is loading...
Решение
#include <iostream>
using namespace std;
void solve() {
int n, d;
cin >> n >> d;
string s;
cin >> s;
for (int i = 0; i < n; ++i) {
if (s[i] - '0' >= d) {
cout << s[i];
} else {
cout << d;
for (int j = i; j < n; ++j) {
cout << s[j];
}
cout << '\n';
return;
}
}
cout << d << '\n';
}
int main() {
int t;
cin >> t;
for (int _ = 0; _ < t; ++_) {
solve();
}
return 0;
}
Идея: Vladosiya, разработка: senjougaharin
Разбор
Tutorial is loading...
Решение
def layer(n, x, y):
return min([x, y, n + 1 - x, n + 1 - y])
def solve():
n, x1, y1, x2, y2 = map(int, input().split())
print(abs(layer(n, x1, y1) - layer(n, x2, y2)))
t = int(input())
for _ in range(t):
solve()
Идея: MikeMirzayanov, разработка: myav
Разбор
Tutorial is loading...
Решение
#include "bits/stdc++.h"
using namespace std;
void solve(){
int n;
cin >> n;
vector<int>b(n-1), a;
for(int i = 0; i < n - 1; i++) cin >> b[i];
a.emplace_back(b[0]);
for(int i = 0; i < n - 2; i++){
a.emplace_back(min(b[i], b[i + 1]));
}
a.emplace_back(b[n - 2]);
for(auto &i : a) cout << i << ' ';
cout << "\n";
}
int main(){
int t;
cin >> t;
while(t--){
solve();
}
return 0;
}
Идея: Gornak40, разработка: Gornak40
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 50;
int fib[MAXN];
void build() {
fib[0] = fib[1] = 1;
for (int i = 2; i < MAXN; ++i)
fib[i] = fib[i - 2] + fib[i - 1];
}
bool solve(int n, int x, int y) {
if (n == 1) return true;
if (fib[n - 1] <= y && y < fib[n])
return false;
if (fib[n] <= y)
y -= fib[n];
return solve(n - 1, y, x);
}
int main() {
int t; cin >> t;
build();
while (t--) {
int n, x, y; cin >> n >> x >> y;
cout << (solve(n, --x, --y) ? "YES" : "NO") << '\n';
}
}
1811E - Живая последовательность
Разбор
Tutorial is loading...
Решение
#include <iostream>
#include <cmath>
#include <cctype>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <deque>
#include <stack>
#include <unordered_set>
#include <sstream>
#include <cstring>
#include <iomanip>
#include <queue>
#include <unordered_map>
#include <random>
#include <cfloat>
#include <chrono>
#include <bitset>
#include <complex>
#include <immintrin.h>
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
int32_t num_tests;
std::cin >> num_tests;
for(int32_t t = 0; t < num_tests; t++) {
int64_t k;
std::cin >> k;
std::vector<int32_t> digits;
while(k > 0) {
digits.push_back(k % 9);
k /= 9;
}
std::reverse(digits.begin(), digits.end());
for(int32_t i = 0; i < digits.size(); i++)
std::cout << (char)(digits[i] < 4 ? (digits[i] + '0') : (digits[i] + '1'));
std::cout << "\n";
}
return 0;
}
Идея: Vladosiya, разработка: Vladosiya
Разбор
Tutorial is loading...
Решение
#include <bits/stdc++.h>
using namespace std;
int sz(int v, vector<vector<int>> &g, vector<bool> &used){
used[v] = true;
int s = 1;
for(int u: g[v]){
if(!used[u]) s += sz(u, g, used);
}
return s;
}
void remove(vector<int> &from, int x){
for(int &e: from){
if(e == x){
swap(e, from.back());
from.pop_back();
return;
}
}
}
void solve(int tc) {
int n, m;
cin >> n >> m;
vector<vector<int>> sl(n);
for(int i = 0; i < m; ++i){
int u, v;
cin >> u >> v;
sl[--u].emplace_back(--v);
sl[v].emplace_back(u);
}
int k = sqrt(n);
if(n != k * k || m != n + k){
cout << "NO";
return;
}
for(int i = 0; i < n; ++i){
if(sl[i].size() != 2 && sl[i].size() != 4){
cout << "NO";
return;
}
}
vector<bool> used(n);
if(sz(0, sl, used) != n){
cout << "NO";
return;
}
for(int i = 0; i < n; ++i){
if(sl[i].size() == 2) continue;
for(int j = 0; j < sl[i].size();){
int u = sl[i][j];
if(sl[u].size() > 2){
remove(sl[i], u);
remove(sl[u], i);
}
else{
j++;
}
}
}
used = vector<bool>(n);
for(int i = 0; i < n; ++i){
if(!used[i] && sz(i, sl, used) != k){
cout << "NO";
return;
}
}
cout << "YES";
}
bool multi = true;
signed main() {
cout.tie(nullptr);
int t = 1;
if (multi)cin >> t;
for (int i = 1; i <= t; ++i) {
solve(i);
cout << "\n";
}
return 0;
}
1811G1 - Влад и правильные пути (простая версия)
Идея: Vladosiya, разработка: Vladosiya
Разбор
Tutorial is loading...
Решение
M = 10 ** 9 + 7
def pw(a, n):
if n == 0:
return 1
b = pw(a, n // 2)
return b * b % M * (a if n % 2 == 1 else 1) % M
def obr(x):
return pw(x, M - 2)
def cnk(n, k):
return fact[n] * obr(fact[k]) % M * obr(fact[n - k]) % M
def solve():
n, k = map(int, input().split())
c = [-1] + [int(x) for x in input().split()]
if k == 1:
print(1)
return
dp = [[0] * (n // k + 1) for i in range(n + 1)] # dp[i][j] = number for i prefix with j blocks
dp[0][0] = 1
for i in range(1, n + 1):
for j in range(0, n // k + 1):
if j > 0:
sz = 1
for s in range(i - 1, - 1, -1):
if c[s] == c[i]:
sz += 1
if sz >= k:
dp[i][j] += dp[s - 1][j - 1] * cnk(sz - 2, k - 2) % M
dp[i][j] %= M
dp[i][j] += dp[i - 1][j]
dp[i][j] %= M
for j in range(n // k, -1, -1):
if dp[n][j] > 0:
print(dp[n][j])
return
t = int(input())
fact = [1] * 101
for i in range(1, 101):
fact[i] = fact[i - 1] * i % M
for _ in range(t):
solve()
1811G2 - Влад и правильные пути (сложная версия)
Идея: Vladosiya, разработка: Vladosiya
Разбор
Tutorial is loading...
Решение
from sys import stdin
input = lambda: stdin.readline().strip()
M = 10 ** 9 + 7
cnk = [[0] * (5000 + 1) for i in range(5000 + 1)]
def solve():
n, k = map(int, input().split())
c = [-1] + [int(x) for x in input().split()]
if k == 1:
print(1)
return
dp = [[0, 0] for i in range(n + 1)] # dp[i] = [number, max] for i prefix
dp[0][0] = 1
for i in range(1, n + 1):
sz = 1
for s in range(i - 1, - 1, -1):
if c[s] == c[i]:
sz += 1
if sz == k:
dp[i][1] = dp[s - 1][1] + 1
if sz >= k:
if dp[s - 1][1] < dp[i][1] - 1:
break
dp[i][0] += dp[s - 1][0] * cnk[sz - 2][k - 2] % M
dp[i][0] %= M
if dp[i][1] < dp[i - 1][1]:
dp[i] = [0, dp[i - 1][1]]
if dp[i][1] == dp[i - 1][1]:
dp[i][0] += dp[i - 1][0]
dp[i][0] %= M
print(dp[n][0])
for i in range(5000 + 1):
cnk[i][0] = 1
for i in range(1, 5000 + 1):
for j in range(1, i + 1):
cnk[i][j] = (cnk[i - 1][j] + cnk[i - 1][j - 1]) % M
t = int(input())
for _ in range(t):
solve()
Auto comment: topic has been translated by Vladosiya (original revision, translated revision, compare)
Great problems! had so much fun during the contest. One of the most interesting Div 3 contest for sure. Happy coding :)
The contest was good. I wish div 3 and div 4 will be arranged atleast 2 — 3 times a month for beginner like me
Still i can't visualize problem D.
You can draw some cases for Fn=5 and Fn+1=8, you will realise that there is a dark spot for columns 4 & 5, where the answer is always false, in other case you can just now cut away the 5*5 rectangle because you had to incorporate one 5*5 rectangle, and continue so on in the recursion
Sure will try tommorrow morning. Thanks, i guess i have to make a lot of diagrams and dry run each one of them.
Yeah I mean atleast you'll need a whole page ;)
But there's not more than lets say 3-4 cases
Here is a hint: break up the Fn by Fn+1 rectangle into a Fn by Fn square and a Fn by Fn-1 rectangle. Keep breaking the rectangle until you break up the larger rectangle entirely into squares.
Can somebody give a recursive and easily understandable solution for g1/g2?
check out My solution
solveMax is a function to find the maximum number of segments of length k, starting from index i.
solve is a function to count the number of ways to make a path with the maximum answer.
Can someone explain editorial of G1?
TBH it's a brute force with some memorization. if you find it hard you can train more on dp problems :)
But I'm gonna try to explain anyway. (I Hope it helps beginners)
for G1 :
first, find the longest path :
each segment must contain k elements of the same color. so to define a state for dp, you should indicate the current index, how many elements there are in the current segment, and what is the current segment's color.
for each element, you try to put in the current segment if you can (if the elements in the current segment are less than k, and the color of the current index is the same as the current segment color).
or you start a new segment from this index (if the size of the current segment is 0).
or do nothing with the current index.
Now you have the longest path value for each index, now make another dp to count the ways to construct a path with the optimal answer.
Same with me XD .
This was the contest i became pupil luckily. I could solve 4. This contest was kind of lucky for me. I wish I can do better in the future.
Can someone explain this line "and these cycles do not intersect at the vertices" in problem F, when the simple cycle intersect at the vertices?
Problems are seems harder than usual div3...though they are fantastic..
For problem C, a[i]=min(b[i],b[i+1]) at 2≤i≤n−1 is right?
that is what i want to know as well.
how to understand this example
{1 7 0 1}, result given by code is{1 1 0 0 1},7 = max(1, 0)?i think they made a mistake
this array b is not possible.It will not be a part of testcases They've mentioned it in solution as well.Read carefullly
Interesting problem E
G2 can be solved by finding the number of paths of length m for each possible m ending at each i and updating the max m divisible by k and the respective number of ways to reach max respectively. Submission: 200833766
in D point number 4, don't you mean $$$F_{n-1} \le y_n < F_n$$$ ?
No, the current inequality $$$F_{n-1} < y_n \le F_n$$$ is correct. The rows and columns are 1-indexed in the editorial.
Ah, i see. Thanks!
myav In the editorial for problem C, $$$a_i = min(b_i, b_{i-1})$$$ for $$$2 \le i \le n-1$$$. Please correct it.
Yes, it's a bug is the tutorial. Later in the proof the formula $$$a_i = \min(b_{i-1},b_i)$$$ is used. Please fix it, Vladosiya, myav and MikeMirzayanov.
Vladosiya why my solution-200898470 got TLE its same as mentioned in editorial .. the same it getting accepted in PyPy-3-200940055.During contest it got accepted in PyPy-2 but after testing i got tle and my rank reduced from 4k to 10k. It's not fair. Please look into it.
I was so close to get pupil but lost it.
BY the Way u must know PyPy-2 is faster than PyPy-3
It is fair. You used the wrong language
I can't understand the Tutorial of E ...
In the $$$9$$$ base you do not have digit $$$9$$$. In the problem you do not have digit $$$4$$$, but it is the same situation. In $$$9$$$ base: $$$1,2,3,4,5,6,7,8,10,11,12,...$$$ In problem: $$$1,2,3,5,6,7,8,9,10,11,12,...$$$
is this work for any number?
if i dont want have digit 5 so i will take base 9 and every digit more than or equal to 5 i increase it ?
can Someone explain D, i really can't wrap my head around bunch of inequalities given in the tutorial!
For A, why does the O(n) solution run out?200968450
It is guaranteed that the sum of n for all test cases does not exceed $$$2⋅10^5$$$ . My English is so poor that I can't understand the meaning of this sentence.
You wrote "const int N = 100010; ", but N can be 200000. If you increase, you will solve the problem.
Another approach to solve E 1)Let our initial answer be k itself. 2)Now count the no of numbers which contain 4 until k. 3)Add this count to k(our new ans). 4)Now count the no of numbers which contain 4 until our new answer and subtract this count by previous count(as prev count was taken into consideration at step 3). 5)update our value of ans by adding the count. 6)Repeat until our ans is not updating to a new value.
Basically a Gauss-Seidal Approach.
200812209
is this called digit dp or digit dp is something else?
Not sure what they used but i solved with digit dp.
let $$$f(x) = $$$ how many numbers before $$$x$$$ with digit 4
use digit dp to solve $$$f(x)$$$.
Then answer for the problem is $$$x$$$ where, $$$x-f(x)=k$$$.
Binary search to find $$$x$$$
https://codeforces.net/contest/1811/submission/202927151
what is k here?
I tried this approach, but this gives TLE Code
same approach
Can someone explain editorial of G2 in detail?
Can anyone help me figure out why this submission has a run-time error? 201201145
I have been stuck on this problem for a long time and I'm not quite sure why it has a run time error. :/
Hey in problem C mike's solution doesn't stand out if the array b is 1 4 5 3 2 1 In other words if my array has a peak middle element is greater than it's adjacent elements 5 7 3 or 0 4 0 anything. Can anyone help me with it.
That input doesnt have an answer. The input is made from the array not the other way around.
how did you decide that only fib0^2 + fib1^2 + .... fib^n = fibn*fib(n+1) is the only way to split the product into n+1 numbers?
Do you have some proof regarding this?
For the solution to G1, how can we show that the number of paths is never a multiple of the mod? If the number of paths is a multiple of the mod, we would skip over the current length and go to the last longest length.
For Problem E, can we also DP on number of removed numbers? That is, number of removed numbers from 1 to 10^k, denoted as r(k), is r(k) = 10^(k-1) + 9 * r(k-1).
Problem B: It's a shame xth row and yth column is ambiguous. You should indicate xth row (starting the count from 1).
Problem E can be solved using Base conversion
since our ask is basically same as in find the number in 9 base where ( 0 — 9 are allowed except 4 )
so first we can convert the number to 9 base then after that if a digit >= 4 we can modify it by adding +1,
but doing this we also need to maintain the carry overs when we will increase 9 -> 10
my AC code using this: AC CODE
yey brooo... it's very easy...
my codeee...
/* यदा यदा हि धर्मस्य ग्लानिर्भवति भारत। अभ्युत्थानमधर्मस्य तदात्मानं सृजाम्यहम् परित्राणाय साधूनां विनाशाय च दुष्कृताम् । धर्मसंस्थापनार्थाय सम्भवायुगे युगे */ #include<bits/stdc++.h> using namespace std; /********************** Template Start *************************/ #define endl "\n" // #define int long long #define vi vector<int> #define vb vector<bool> #define vvi vector<vector<int>> #define vvb vector<vector<bool>> #define pb push_back #define pob pop_back #define rep(x, i, y) for(int i = x; i < y; i++) #define all(a) a.begin(), a.end() #define mapi map<int,int> #define seti set<int> #define umapi unordered_map<int,int> #define useti unordered_set<int> #define mapc map<int,char> #define setc set<char> #define umapc unordered_map<int,char> #define usetc unordered_set<char> #define pq priority_queue<int> #define pqG priority_queue<int, vector<int>, greater<int>> #define ff first #define ss second #define all(a) a.begin(), a.end() #define srt(a) sort(a.begin(), a.end()) #define srtrev(a) sort(a.rbegin(), a.rend()) #define prdouble(x) cout << fixed << setprecision(10) << x #define c(x) {cout << x << endl;} /**************************/ #define int long long int #define llu unsigned long long // #define endl '\n' /**************************/ // const int aaa[100000+1]; const int NN = 2*1e5; vi aaa(NN, 0); #define f(i,n) for(int i=0;i<n;i++) #define revf(i,n) for(int i=n-1;i>=0;i--) #define f1(i,n) for(int i=1;i<=n;i++) #define rf1(i,n) for(int i=n;i>=1;i--) /**************************/ void revstr(string& str){ int n = str.length(); for (int i = 0; i < n / 2; i++) swap(str[i], str[n - i - 1]); } /**************************/ #define con continue #define S second #define F first #define pb push_back #define pob pop_back #define el endl #define yes cout << "YES" << endl #define no cout << "NO" << endl #define mkn int n;cin >> n; #define mkx int x;cin >> x; #define mks string s;cin>>s; #define mkab int a,b;cin>>a>>b; #define mkabc int a,b,c;cin>>a>>b>>c; #define mkabcd int a,b,c,d;cin>>a>>b>>c>>d; // /-----------------------------------------/ string dc(int n) { string v=to_string(n); return v; } // /-----------------------------------------/ const int M = 1000000000+7; const int mod = 998244353; const int prime_N = 1e6; vb isPrime(prime_N, false); vi lp(prime_N, 0); vi hp(prime_N, 0); const int fact_N = 1e6; vi fact(fact_N); void __print(int x) { cerr << x; } void __print(double x) { cerr << x; } void __print(long double x) { cerr << x; } void __print(char x) { cerr << '\'' << x << '\''; } void __print(const char *x) { cerr << '\"' << x << '\"'; } void __print(const string &x) { cerr << '\"' << x << '\"'; } void __print(bool x) { cerr << (x ? "True" : "False"); } void __print(vector<int> a) { for (auto x : a) cerr << x << " "; cerr << endl; } void __print(set<int> s) { for (auto x : s) cerr << x << " "; cerr << endl; } void __print(map<int, int> mp) { for (auto x : mp) cerr << x.ff << " " << x.ss << endl; cerr << endl; } vi vp; const int prime_NN = 1e6; void prime(){ vector<bool>prm(prime_NN+1,true); prm[0]=prm[1]=0; for(int i=2;i*i<=prime_NN;i++){ if(prm[i]==true){ for(int j= i*i;j<=prime_NN;j+=i){ prm[j] = false; } } } for(int i =2;i<=prime_NN;i++){ if(prm[i]) vp.pb(i); } } int _ceil(int a,int b){ if(a%b==0){ return a/b; }else{ return a/b + 1; } } int cnt_bit(int n){ int c=0; while(n){ n&=n-1; c++; } return c; } void pridp(vvi &dp){ f(i, dp.size()) { f(j, dp[0].size()) { cout << dp[i][j] << " "; } cout << endl; } } void pri(vi v) { rep(0, i, v.size()) { cout << v[i] << " "; } cout << endl;} vector<int> in(int n) { vector<int> a(n); rep(0, i, n) cin >> a[i]; return a; } set<int> input_set(int n) { set<int> s; rep(0, i, n) { int x; cin >> x; s.insert(x); } return s; } multiset<int> input_multiset(int n) { multiset<int> ms; rep(0, i, n) { int x; cin >> x; ms.insert(x); } return ms; } vi prime_factors(int n) { vi prime; for(int i = 2; i*i <= n; i++) { while(n % i == 0) { prime.pb(i); n /= i; } } if(n > 1) { prime.pb(n); } return prime; } vi divisors(int n) { vi v; for(int i = 1; i*i <= n; i++) { if(n % i == 0) { v.pb(i); if(i != n / i) { v.pb(n / i); } } } return v; } int gcd(int a, int b) { if(b == 0) { return a; } return gcd(b, a%b); } long long binMultiply(long long a, long long b, long long mod) { long long ans = 0; a = (a % mod); while(b > 0) { if(b & 1) { ans = (ans + a) % mod; } a = (a + a) % mod; b = b >> 1; } return ans; } int lcm(int a, int b) { return (a*b) / gcd(a, b); } int binExp(int a, int b, int mod) { int ans = 1; while(b > 0) { if(b & 1) { ans = (ans * 1LL * a) % mod; } a = (a * 1LL * a) % mod; b = b >> 1; } return ans; } int ncr(int n, int r) { int ans = fact[n]; int den = (fact[n - r] * 1LL * fact[r]) % M; return (ans * binExp(den, M - 2, M)) % M; } int power(int a, int b, int mod) { if(b == 0) { return 1; } int res = power(a, b/2, mod); if(b & 1) { return (a * res * res) % mod; } else { return (res * res) % mod; }} bool prime_factors_one(int n) { bool f=0; for(int i = 3; i<= n; i+=2) { if(n % i == 0){f=1;break;} } return f; } bool divisors_check(int n) { bool f=false; for(int i = 3; i*i <= n; i+=i) { if(n % i == 0) { f=true;break;} } return f; } bool ts(int k,vi &v){ int l = 0; int r = v.size()-1; while(l<r){ int m1 = l + ((r-l)/3); int m2 = r - ((r-l)/3); if(v[m1]==k || v[m2]==k) return 1; if(v[m1]<k) l = m1+1; else if(v[m2]>k) r = m2-1; else { l = m1+1; r = m2-1;}} return 0;} int hd(string s , string s2){ int c=0; f(i,s.size()){ if(s[i]!=s2[i]) c++; } return c; } void solve(){ mkab mks // c(b) char t = char(b+'0'); // c(v"T "<<t) bool f=0; string tmp; // tmp+=s[0]; f(i,s.size()){ if(s[i]<t){ tmp+=t; for(int j=i;j<s.size();j++){ tmp+=s[j]; } f=1; break; }else tmp+=s[i]; } if(f==0){ c(s+t) // cout<<t; }else{ c(tmp) } // cout<<endl; // c(s) } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while(t--) { solve(); } return 0; }Problem F can be easily solved by enumerating all the cycles and then checking. Submission: 284842801