By Vladosiya, history, 2 years ago,

1714A - Everyone Loves to Sleep

Tutorial
Solution

1714B - Remove Prefix

Idea: MikeMirzayanov

Tutorial
Solution

1714C - Minimum Varied Number

Idea: MikeMirzayanov

Tutorial
Solution

1714D - Color with Occurrences

Idea: MikeMirzayanov

Tutorial
Solution

Idea: senjougaharin

Tutorial
Solution

1714F - Build a Tree and That Is It

Idea: MikeMirzayanov

Tutorial
Solution

1714G - Path Prefixes

Idea: MikeMirzayanov

Tutorial
Solution
• +22

| Write comment?
 » 2 years ago, # |   +23 Code for D is messed up a bit.
•  » » 2 years ago, # ^ |   0 I implemented it in an easier way. My Submissionvoid solve() { string s; int n, len = size(s); cin >> s >> n; vector v(n); cin >> v; vii ans; int last = 0; while (last != size(s)) { int id = -1, cur = last; rep(i, 0, n) { int j = last, k = size(v[i]); while (j >= 0 and last - j < k) { if (size(s) - j >= k and s.substr(j, k) == v[i] and cur < j + k) cur = j + k, id = i; j--; } } if (id == -1) { cout << -1 << endl; return; } ans.pb({id, cur - size(v[id])}); last = cur; } cout << size(ans) << endl; for (auto &e : ans) cout << e.ff + 1 << " " << e.ss + 1 << endl; } 
 » 2 years ago, # |   0 Mike Mirzayanov thanks for awesome editorial
•  » » 2 years ago, # ^ |   0 Idk, awesome editorial in my understanding contains much more detailed and intuitive solutions with hints, this one is just ok.
 » 2 years ago, # |   +15 Question D is a great problem,but why is the code for D so messy？
 » 2 years ago, # |   0 How to solve question D with DP? Can you tell me about it and share your code? If you can help me, I will thank you very much.
•  » » 2 years ago, # ^ |   0 Here is my solution: 166798483
•  » » » 2 years ago, # ^ |   0 What does your dp[i] mean？
•  » » » » 2 years ago, # ^ |   0 dp[i] is the minimum number of steps needed to color prefix(length is i) of text t in red.use[i]: If an operation was done at a certain location, I recorded the selected subscript.from[i]: Otherwise I recorded which operation the location was affected by.
•  » » » » 2 years ago, # ^ |   -9 dp is an array and i is the element position in the array
•  » » » » » 2 years ago, # ^ |   0 wth is this shit man. Stop it
•  » » » » » 2 years ago, # ^ |   0 This comment does not have enough downvotes for destroying almost the entire comment section of the editorial.
 » 2 years ago, # |   +10 Indented solution of problem D from editorial: Solution#include #define len(s) (int)s.size() #define forn(i, n) for (int i = 0; i < int(n); i++) using namespace std; int ans = 0; bool ok = true; void Find(int a, int b, string &t, vector&str, vector>&match){ int Max = 0, id = -1, pos = -1; for(int i = a; i <= b; i++){ for(int j = 0; j < len(str); j++){ string s = str[j]; if(i + len(s) > len(t) || i + len(s) <= b)continue; if(t.substr(i, len(s)) == s) { if(i + len(s) > Max){ Max = i + len(s); id = j; pos = i; } } } } if(id == -1) { ok = false; return; } else { match.emplace_back(id, pos); ans++; if(Max == len(t)) return; else Find(max(pos + 1, b +1), Max, t, str, match); } } void solve(){ ans = 0; ok = true; string t; cin >> t; int n; cin >> n; vectors(n); vector>match; forn(i, n) { cin >> s[i]; } Find(0, 0, t, s, match); if(!ok) cout << "-1\n"; else{ cout << ans << endl; for(auto &p : match) cout << p.first + 1 << ' ' << p.second + 1 << endl; } } int main(){ int q; cin >> q; while(q--){ solve(); } return 0; } 
 » 2 years ago, # |   0 "When you color a letter in red again, it stays red."Missed this line during contest does this make the question similar to Jump game? ->where we can jump from index to any index in range (i,i+a[i])
•  » » 23 months ago, # ^ |   +1 Yes essentially the same problem. Here's my implementation using this idea.https://codeforces.com/contest/1714/submission/169954163
 » 2 years ago, # |   +3 The code for F: Build a Tree and That is it does not really clarify things mentioned in tutorial rather it has checks and implementations that makes it seem like the code to be working on a different idea. Can anyone either explain the tutorial or the code ? Thanks.
•  » » 2 years ago, # ^ |   0 Can you help me with G.I checked ur code, but can't understand, Can u explain ur idea ? Thanks.
•  » » » 2 years ago, # ^ |   +3 So, let's first make a DFS call and make array Asum[N], where Asum[u] stores the sum of all the A-values along the edges from root to node u.Now notice that B values of all edges are positive. Let's pick any node u. And let's say, Path[u] = [B1, B2, B3, B4, B5,.....Bx] where the Bi indicates the B-values of all edges from root to node u.Since Bi s are positive the prefix sum on Path[u] will only increase. Let's call the prefix sum on Path[u] as PrefixPath[u].Since we want to know maximum prefix path that doesnt go beyond all A values sum in the path from root to u, the final answer for node u will beAnswer[u] = Largest index k in PrefixPath[u] such that PrefixPath[k] > Asum[u].
•  » » 2 years ago, # ^ |   +6 I can explain my idea of solution if it can help you.Let's place $1,2$ and $3$ nodes. There is $4$ possible ways to do it: link to image The first case: $d_{23} = d_{31} + d_{12}$. Let's check it, if it is right, then let's build our tree like in image. The second case: $d_{31} = d_{23} + d_{12}$. Let's check it, if it is right, then let's build our tree like in image. The third case: $d_{12} = d_{23} + d_{31}$. Let's check it, if it is right, then let's build our tree like in image. The last case: let's see that $d_{12} + d_{23} + d_{31} \le n$, let's get loop for $d_{14} = [1..n]$ (sum of $n$ for all cases is $\le 10^5$ so we can do it), now we know $d_{34} = d_{31} - d_{14}$ etc. If all this right, then let's build our tree like in image. If all cases are wrong, answer is NO.
•  » » » 2 years ago, # ^ |   +3 Woah...Thank you so much. The image actually made your idea very clear. upvote_plus_plus
 » 2 years ago, # |   0 It was a very good contest D was interesting but i think you should reorder the problem like this B C A E D G F
•  » » 2 years ago, # ^ |   0 B C A E G D F
•  » » » 2 years ago, # ^ |   0 B C A D E G F
 » 2 years ago, # |   0 I read the solution "Thus, we will apply the operation to each element of the array until its remainder modulo 10 becomes, for example, 2, and then check that the array does not contain both remainders 2 and 12 modulo 20." I don't know why do we need to check that "the aray does not contain both remainders 2 and 12 modulo 20". Why do we have to do that. Can you explain for me. Thanks
•  » » 2 years ago, # ^ |   0 There are only 2 possible cycles when considered modulo 20 (2 -> 4 -> 8 -> 16 -> 2) and (12 -> 14 -> 18 -> 6 -> 12). If members of both cycles are present, you can never make all the numbers the same.
 » 2 years ago, # |   0 Code for $Problem D$ should be posted like this : Solution #include #define len(s) (int)s.size() #define forn(i, n) for (int i = 0; i < int(n); i++) using namespace std; int ans = 0; bool ok = true; void Find(int a, int b, string &t, vector&str, vector>&match) { int Max = 0, id = -1, pos = -1; for(int i = a; i <= b; i++) { for(int j = 0; j < len(str); j++) { string s = str[j]; if (i + len(s) > len(t) || i + len(s) <= b) continue; if (t.substr(i, len(s)) == s) { if (i + len(s) > Max){ Max = i + len(s); id = j; pos = i; } } } if(id == -1) { ok = false; return; } else { match.emplace_back(id, pos); ans++; if (Max == len(t)) return; else Find(max(pos + 1, b +1), Max, t, str, match); } } void solve() { ans = 0; ok = true; string t; cin >> t; int n; cin >> n; vectors(n); vector>match; forn(i, n) { cin >> s[i]; } Find(0, 0, t, s, match); if(!ok) cout << "-1\n"; else{ cout << ans << endl; for(auto &p : match) cout << p.first + 1 << ' ' << p.second + 1 << endl; } } int main(){ int q; cin >> q; while(q--){ solve(); } return 0; } I think Vladosiya has forgotten to write  at the end.
•  » » 2 years ago, # ^ |   +1 Thanks for tagging, Fixed
 » 2 years ago, # |   0 In problem E, why flag12 and flag2 should not be true for the answer to be YES?
•  » » 2 years ago, # ^ |   0 Remainders 2, 4, 6, 8 cycles and in that cycle number increases by 20. So difference between every two elements must divide by 20 (and these elements must have the same remainder modulo 20).
 » 2 years ago, # |   0 Why I got TLE ? What's wrong with my code[submission:166546367]
 » 2 years ago, # |   0 Is there a way to solve G using binary lifting
•  » » 2 years ago, # ^ |   0 Yes 167804403
 » 23 months ago, # |   0 Could someone explain why this submission for G of mine get TLE ? I know it's inefficient but I still don't get why it doesn't workFirst I do a dfs to precompute all prefix sums for a and b. Then for each leaf I find the path from it to the root, reverse the path, and use binary search for each vertices on the path to get the answer.
 » 23 months ago, # | ← Rev. 3 →   0 Hi can anyone help me figure out why my code for D is wrong? Thanks a lot! Basically I have tried to iteratively find the places with maximum coverage. However, it gives WA on a later TC. Code#pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma") #pragma GCC optimize("unroll-loops") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef long double ld; typedef pair p32; typedef pair p64; typedef pair pdd; typedef vector v64; typedef vector v32; typedef vector > vv32; typedef vector > vv64; typedef vector > vvp64; typedef vector vp64; typedef vector vp32; double eps = 1e-12; #define forn(i,e) for(ll i = 0; i < e; i++) #define forsn(i,s,e) for(ll i = s; i < e; i++) #define rforn(i,s) for(ll i = s; i >= 0; i--) #define rforsn(i,s,e) for(ll i = s; i >= e; i--) #define ln "\n" #define dbg(x) cout<<#x<<" = "< void swp(T&a,T&b) { T temp=a; a=b; b=temp; } // Useful Funcs // smallest prime divisor // int smp[100001]={0}; // void calcPrimes(){ // forn(i,100001){ // smp[i]=i; // } // ll ct=2; // while(ct*ct<100001){ // if(smp[ct]==ct){ // for(ll j=ct*ct;j<100001;j+=ct){smp[j]=ct;}} // ct+=1; // } // } ll ceil_div(ll a, ll b) {return a % b == 0 ? a / b : a / b + 1;} // Recursive function to calculate gcd long long gcd(long long a, long long b){ if(b==0) return a; return gcd(b,a%b); } /* Iterative Function to calculate (x^y)%p in O(log y) */ long long modex(long long x, unsigned int y, long long p) { long long res = 1; // Initialize result x = x % p; // Update x if it is more than or // equal to p if (x == 0) return 0; // In case x is divisible by p; while (y > 0) { // If y is odd, multiply x with result if (y & 1) res = (res*x) % p; // y must be even now y = y>>1; // y = y/2 x = (x*x) % p; } return res; } int binarySearch(int arr[], int l, int r, int x) { if (r >= l) { int mid = l + (r - l) / 2; // If the element is present at the middle // itself if (arr[mid] == x) return mid; // If element is smaller than mid, then // it can only be present in left subarray if (arr[mid] > x) return binarySearch(arr, l, mid - 1, x); // Else the element can only be present // in right subarray return binarySearch(arr, mid + 1, r, x); } // We reach here when element is not // present in array return -1; } // STL binary search functions // binary_search(start_ptr, end_ptr, num) // returns true if element present, // otherwise returns false. // upper_bound(start_ptr, end_ptr, num) // returns the first index having value // greater than num. // If there is no such index, then returns // length of array. // lower_bound(start_ptr, end_ptr, num) // returns the fiirst index having value // not less than num // Subtract v.begin() or a(in case of array) to get index. // Pointers // for array-> a, a+x // for vector-> v.begin(), v.begin()+x, v.end() const ll MOD = 998244353; const ll mod = 1e9+7; void solve(){ string t; cin>>t; ll n; cin>>n; vector s(n); forn(i,n) cin>>s[i]; ll m = sz(t); v64 c(m); ll ans = 0; vp64 ansl; for(ll cv=10;cv>=1;--cv){ forn(i,m){ forn(j,n){ if(sz(s[j])>=cv && m-i>=sz(s[j])){ ll cov = 0; bool b=true; forn(k,sz(s[j])){ if(s[j][k]!=t[i+k]){ b=false; break; } else{ if(!c[i+k]) cov++; } } if(b && cov==cv){ ans++; ansl.pb({j+1,i+1}); forn(k,sz(s[j])){ c[i+k]=1; } } } } } } bool b=true; forn(i,sz(t)){ if(!c[i]){ b=false; break; } } if(b){ cout<> t; for(int it=1;it<=t;it++) { solve(); } return 0; } 
•  » » 23 months ago, # ^ |   0 Take a look at Ticket 16127 from CF Stress for a counter example.
•  » » » 23 months ago, # ^ |   0 Thanks! However, I am also interested to know why the editorial solution won't face the same problem as my solution.
 » 10 months ago, # |   0 Can D be solved using Shortest Paths I am not able to calculate number of nodes created in worst case can someone help? Sorry about Necroposting I just can't seem to figure it out
 » 6 months ago, # |   0 Why in Problem D ,why does the algorithm in which selecting the word from which maximum red letters occurs in string s in a given step doesn't work.. According to my understanding .. If we don't pickup the substring of s in which maximum occurence of red happens in a step , then we can always pick it up later if the substrings of current picking doesn't intersect with the substring in which the maximum red occurence happens in a particular step. And if the substring intersect , then still we can swap the positions of picking of a substring in which maximum red characters appear in a step , the number of reds will decrease by the same. But , if one string is a substring in the strings in which we have to make it red. then picking the string with maximum red happens in a step is still optimal .. So , at each step just applying the operation with the string k[i] (1 <= i <= k) , in which the maximum new red characters which happen in a operation in string s is wrong.Implementation of the Algorithm :- In the submission Link.Wrong Submission Link :- 242502092Question Id :- 1714D - Color with Occurrences