By Vladosiya, history, 18 months ago, translation,

1759A - Yes-Yes?

Idea: MikeMirzayanov

Tutorial
Solution

1759B - Lost Permutation

Idea: MikeMirzayanov

Tutorial
Solution

1759C - Thermostat

Tutorial
Solution

1759D - Make It Round

Idea: MikeMirzayanov

Tutorial
Solution

1759E - The Humanoid

Idea: Gornak40

Tutorial
Solution

1759F - All Possible Digits

Idea: senjougaharin

Tutorial
Solution

1759G - Restore the Permutation

Idea: MikeMirzayanov

Tutorial
Solution
• +26

| Write comment?
 » 18 months ago, # | ← Rev. 2 →   0 I solved A by checking if there is a letter that is not in the word "Yes", and checking that each Y has s before it, each e has Y before it, and each s has e before it. Also I solved D using lcm, for each i such that 1<=i<=18 check if lcm(n,10^i)/n<=m. If it is, multiply the answer by m/answer
 » 18 months ago, # | ← Rev. 8 →   -10 Great round! Hope to see another Div.3 soon. Div.3 almost always meant +ve delta for me, so I am always hyped for them.To point out, F didn't need a very complex data structure. A single set (a sorted set would be preferrableI just checked, an unordered set worked equally as fast) was enough. If you look at the constraints, you will notice that $n \leq 100$. Therefore, if you save digits that did exist in the original number and the number after a carry, the size of the set is guaranteed to be less than 200. Now if we follow the process I explained in that another comment, we know we can manage $\mathbf{pp}$ and $\mathbf{pk}$ linearly starting from $p$ and the number of the last digit, and the loop won't take over 200 iterations. This is more than enough to fit in the TL. (I have not tested using an array here though, but the process will be the same anyways.) One great thing to note is that this solution's time complexity only relies on $n$. Maybe for this reason (and due to some additional constants), my solution turns out to be 5x faster than the jury solution. Good to know!Here is a submission based on this approach — 181506873.upd: The TeX for problem D's tutorial seems to be broken. Maybe you forgot come curly braces?
•  » » 17 months ago, # ^ |   0 yeah true, I also did a similar approachSubmission: 187409654 Codevoid solve(){ lli n , p; cin >> n >> p; vl a(n); lli ans = 0; map frq; for(int i = 0 ; i < n ; i ++) { cin >> a[i]; frq[a[i]]++; } lli last_not_seen = -1; for(lli x = p-1 ; x >= 0 ; x--) { if(frq[x] == 0) { last_not_seen = x; break; } } if(last_not_seen == -1) { cout << 0 << endl; } else { //cout << last_not_seen << endl; if(last_not_seen > a[n-1]) { ans += last_not_seen - a[n-1]; last_not_seen = -1; for(lli x = a[n-1]-1 ; x >= 0 ; x --) { if(frq[x] == 0) { last_not_seen = x; break; } } } if (last_not_seen == -1) { cout << ans << endl; } else { lli range_low = 1 , range_high = a[n-1] - 1; ans = p - a[n-1]; a[n-1] = p; for(int i = n-1; i >= 0 ; i --) { if(a[i] >= p){ a[i] -= p; if(i == 0) { frq[1]++; } else { a[i-1]++; } } } for(int i = n-1 ; i >= 0 ; i --) { frq[a[i]]++; } last_not_seen = -1; for(lli x = range_high ; x >= 0 ; x --) { if(frq[x] == 0) { last_not_seen = x; break; } } if(last_not_seen == -1) { cout << ans << endl; } else { ans += last_not_seen; cout << ans << endl; } } } } 
 » 18 months ago, # |   0 1759D - Make It RoundHere's my clear and concise code for D #include #define int long long int signed main() { std::ios::sync_with_stdio(false); std::cin.tie(0); int t = 1; std::cin >> t; while(t--){ int n, m; std::cin >> n >> m; int x = 10, ans = n*m; while(1){ int g = std::__gcd(x, n); int k = x/g; if(k <= m){ ans = k*(m/k)*n; } else break; x *= 10; } std::cout << ans << "\n"; } } Greedy approach : We will try to append as many 0's at the end within given constraint How to find it ?Let's take input examples : 6 11 We can have 30 60 90 120 ... But only 30 and 60 falls within constraint 6*5 = 30, k = 5 6*10 = 60, k = 10 6*15 = 90, k = 15 not possible Now we will build our answer by checking if I append zeros can I get some k such that it falls under constraint, once we can't append 0's we will break loopHow to do it? How to find possible values of k? Well it's easy, we can use some mathematics We will check if I can have some possible number as z*10 z*100 z*1000 and so on... z [1, 9] z should be minimum possible as we are using greedy  we have our n as 6 so to append 0 at the end I can have z*10 n = 2*3 ans = z*10 so we have ans = n*k, 1 <= k <= m n = 6 k = 5 z = 3 ans = 30 n = 6 k = 10 z = 6 ans = 60  How to find k ? Let g = gcd(x, n) = (10, 6) = 2 then k = x/g = 10/2 = 5, k can take minimum value as 5 within given constraints But as we have to find max answer if we append some zeros so we will find k as k = (11/5)*k k = 10 Thanks :), You can ask doubt
 » 18 months ago, # |   0 I solved D with binary search for answer. I think it would be better to add binary search tag to D.
 » 18 months ago, # | ← Rev. 2 →   0 I almost copy-pasted solution for problem E from the editorial and it's giving WA on test 1?!Submission: 181810855 Code#include using namespace std; int g, b; int solve(vector &a, int n, int i, long long h, int green, int blue) { if(i==n) return 0; if(h>a[i]) return solve(a, n, i+1, h+a[i]/2, green, blue)+1; g=(green?solve(a, n, i, h*2, green-1, blue):0); b=(blue?solve(a, n, i, h*3, green, blue-1):0); return max(g, b); } int main() { ios::sync_with_stdio(0); cin.tie(0); int T; cin >> T; while(T--) { int n; long long h; cin >> n >> h; vector a(n); for(int i=0; i> a[i]; sort(a.begin(), a.end()); cout << solve(a, n, 0, h, 2, 1) << '\n'; } } 
•  » » 18 months ago, # ^ |   0 Those global variables are the issue. Try declaring them inside the function.
•  » » » 18 months ago, # ^ |   0 Thank you, it worked, but why?
•  » » » » 18 months ago, # ^ |   0 Not quite sure aswell
•  » » » » 13 months ago, # ^ |   0 Think about how solve() works. First, you compute g. No problems here. Second, you compute b. This uses a recursive call to solve(), so the global variable g may get overwritten during this subcall.Finally, you compute max(b, g). This can give WA if g is no longer the correct value.
•  » » » » » 13 months ago, # ^ |   0 I figured it out on my own already, but thank you for the comment anyways.
•  » » 16 months ago, # ^ |   0 g=(green?solve(a, n, i, h*2, green-1, blue):0); b=(blue?solve(a, n, i, h*3, green, blue-1):0);how this work i don't understand
•  » » » 16 months ago, # ^ |   0 I hope these few lines will make it clearer.$\text{green}$ is the number of green serums left and $\text{blue}$ is the number of blue serums left.$\text{g}$ is the answer if we use green serum at the $\text{i}$ -th step and $\text{b}$ is the answer if we use blue serum at the $\text{i}$ -th step.When writing boolean valus, x is same as writing x!=0 where x is a number.
 » 18 months ago, # |   0 For E, shouldn't it be $O(NlogN)$ instead of $O(N)$ since you need to sort the astronauts?
•  » » 18 months ago, # ^ |   0 Good remark, thank you
•  » » 18 months ago, # ^ | ← Rev. 8 →   0 Gornak40 harryzhengipsum Gornak40 can you help me calculate the TC of E? how I Calculate (No. states * transition) So, According to me, TC comes out to be n*h*s1*s2*2. Which is too high. What I am doing Wrong? I thought if I memories it will give MLE with 4 states.
 » 18 months ago, # |   0 Can somebody explain why the solution to D works, or what is the idea about it?Obviously it is somehow about the number of divisiors 2 and 5 in n, but how? And how/why does the sol find "If there are several possible variants, output the one in which the new price (value n⋅k) is maximal."?
•  » » 18 months ago, # ^ |   0 The input number $n$ number can be factored as $x 2^a5^b$, $a, b \geq 0$The number of zeroes at the end of this number is equal to $min(a,b)$, so our goal is to maximize $min(a,b)$We start with $k=1$.while $k \leq m$, do:if $a < b$, multiply $k$ by $2$ and increment $a$.if $a > b$, multiply $k$ by $5$ and increment $b$.if $a=b$, multiply it by $10$. and increment $a$ and $b$. This guarantees that $k \cdot n$ has the largest amount of zeroes at the end, this does not guarantee that $k$ is the biggest possible number, to do this, we try to make $k$ as close to $m$ as possible.$k \cdot q \leq m$$q \leq \frac{m}{k}$$q = \frac{m}{k}$So the answer is $q \cdot k \cdot n$
•  » » 5 hours ago, # ^ |   0 .ComplaintFrame { display: inline-block; position: absolute; top: 0; right: -1.4em; } .ComplaintFrame a { text-decoration: none; color: #ff8c00; opacity: 0.5; } .ComplaintFrame a:hover { opacity: 1; } ._ComplaintFrame_popup p, ._ComplaintFrame_popup button { margin-top: 1rem; } ._ComplaintFrame_popup input[type=submit] { padding: 0.25rem 2rem; } ._ComplaintFrame_popup ul { margin-top: 1em !important; margin-bottom: 1em !important; } The greedy approach can be derived through the fact that we know that multiplying 2*5 always would add a 0 at the end, so greedy we say that instead of multiply k with 10, why not multiply it with an even smaller number -> 2 or 5, Thus i can say, we would try to equalize the count of 2 and 5.
 » 18 months ago, # |   0 Problem E: Please someone explain to me why we use solve(0, h, 2, 1) in the initial call, I don't understand why we use 2,1.? what's the logic behind it.?
•  » » 18 months ago, # ^ |   0 oh, my bad, I missed that part — "the humanoid took with him two green serums and one blue serum".
•  » » » 18 months ago, # ^ |   0 I am getting no idea what we are doing in que E. why are we recursively calling that function and what that function is doing?
•  » » » » 18 months ago, # ^ |   0 @hemantpatil10125 it's just an observation. Try to figure out how it works, recursion is always hard, but very easy if you can catch the basic and base cases, sometimes tricky logic. Keep trying at least 20 easy recursion problems, understand how they work, then it will be much easier. I am also a newbie, so It may sound inappropriate to make a statement about that. Hope you will expert one day if you solve problems daily.
•  » » » » » 18 months ago, # ^ |   0 thank u @survo_datta. What resources did you follow to learn recursion? How's striver's playlist?
•  » » » » » » 18 months ago, # ^ |   0 @hemantpatil10125 you can follow tutorial from Luv(@iamluv) in youtube. Follow his DP series. I tried different tutorials and find his tutorial more accurate and beginner friendly though he covers many advanced problems too. Firstly you should solve problems from this: https://mirror.codeforces.com/group/MWSDmqGsZm/contest/223339 after solving all of the problems from this, follow his tutorials on youtube. you will be an expert in it.
•  » » » » » » » 18 months ago, # ^ |   0 thank you...
 » 18 months ago, # |   0 Can someone explain the segment tree solution for problem G?
•  » » 17 months ago, # ^ | ← Rev. 2 →   0 Did you got any segment Tree approach for this problem?
•  » » » 16 months ago, # ^ |   +8 I hope it's not too late, please see my comment below.
•  » » 17 months ago, # ^ |   0 hey have you got the approach for segment tree, i could not come up with the solution of G i was trying using segment tree but i got stuck somewhere, if you got it please could you share the code.
•  » » » 16 months ago, # ^ |   +8 I think I finally got it. Imagine there's a bracket sequence $s$ of length n, for each $i$, we set $s_{b_i}$ to a right bracket and set the rest to left brackets (e.g. the first example input is (())()). So our target would became for each right bracket we want to match it to a left bracket to its left, so the solution exists only if it's a valid bracket sequence, i.e. all prefix sums are greater than or equal to 0.Because we want the lexicographically minimal permutation, so for each $b_i$ we want to find the smallest $j < b_i$ such that if we remove $s_j$ and $s_{b_i}$, the remaining bracket sequence is still valid. We claim that we should choose the largest $j$ such that $pref_{j - 1} = 0$ (I'm too lazy to explain it so try to come up with it by yourself). In order to find such $j$, we use a segment tree by maintaining the sum, min prefix, and the position of the min prefix. See jiangly's code or my code 188831632 for implementation.
•  » » » » 11 months ago, # ^ |   0 You can also use a Range Max-Query Segment tree and then binary search for each value in the unused array so that you find the right most element in the input array ($a_i$) such that $a_i$ > $unused_j$Here is the code for this approach: Code#include typedef long long ll; typedef long double ld; typedef unsigned long long ull; #define PI 3.14159265358979323846 #define sbits(x) __builtin_popcount(x) #define tbits(total_size , num) total_size - __builtin_clz(num) #define pb push_back #define trav(name , ds) for(auto&name : ds) #define f first #define s second #define clr(ds) ds.clear() #define all(ds) ds.begin() , ds.end() #define pi pair #define vi vector #define vll vector #define vpi vector #define sz(i) (int)i.size() #define rsz(ds ,size , val) ds.assign(size , val); int xP[] = {0,0,1,-1,1,1,-1,-1} , yP[] = {1,-1,0,0,1,-1,-1,1}; using namespace std; uint64_t time() { using namespace std::chrono; return duration_cast(system_clock::now().time_since_epoch()).count(); } size_t hF(pair a){ return (a.first + a.second)*(a.first + a.second + 1)/2 + a.second; } void setIO(string name = "") { cin.tie(0)->sync_with_stdio(0); if (name.size()) { freopen((name + ".in").c_str(), "r", stdin); freopen((name + ".out").c_str(), "w", stdout); } } struct seg{ vi tree; int n; seg(){} seg(vi& arr){ n = sz(arr); while(sbits(n)!=1){ n++; arr.pb(INT_MIN); } rsz(tree , 2*n , 0); for(int i = n;i<2*n;i++) tree[i] = arr[i-n]; for(int i =n-1;i>=1;--i) tree[i] = max(tree[i*2] , tree[i*2+1]); } void update(int ind , int val){ ind+=n; tree[ind] = val; while(ind!=1){ ind/=2; tree[ind] = max(tree[ind*2] , tree[ind*2+1]); } } int query(int nL , int nR , int qL , int qR , int node){ if(nL>qR || nR=qL && nR<=qR) return tree[node]; return max(query(nL , nL+(nR-nL)/2 , qL , qR , node*2) , query(nL+(nR-nL)/2+1 , nR , qL , qR , node*2+1)); } void print(){ int size = 1; int curr = 1; while(size<=n){ for(int i = curr;ib[ind]){ answer = middle; left = middle+1; } else right = middle -1; } return answer; } void solve(){ cin >> n; clr(a); clr(b); rsz(a , n/2 , 0); vi exists(n); for(int i = 0;i> a[i]; exists[a[i]-1] = 1; } for(int i = 1 ; i<=n;i++) if(!exists[i-1]) b.pb(i); if(sz(a)!=sz(b)){ cout << -1 << "\n"; return; } reverse(all(b)); tree = seg(a); vi answer(n/2); for(int i =0;i> t; while(t--){ solve(); } } And the corresponding submission: 210703511
 » 18 months ago, # |   0 For the problem G, can we binary search on the value we put before each element of the input array? For each element, the search space will be the elements in the unused set which are smaller than this element. And to check if a value is feasible, we will check that we still have sufficient options left for rest of the elements if we put this value before the current element in the final array. This can be done using ordered set (refer my solution). We will choose the least among all feasible values, to maintain the lexicographic condition. Also note that the search space will follow monotonicity.I used the above approach, but got WA on TC3. Solution: LINK
•  » » 18 months ago, # ^ |   0 Take a look at Ticket 16479 from CF Stress for a counter example.
•  » » » 18 months ago, # ^ |   0 Thanks man
 » 13 months ago, # |   0 can someone tell me the mistake in my code of problem G. I have done pretty much the same as editorial's approach,but I am getting WA on test case 14. (basically,my code is also including 0 in one of the outputs which I am unable to think of why) https://mirror.codeforces.com/contest/1759/submission/202043617
•  » » 13 months ago, # ^ |   +8 You are dereferencing a pointer after you've deleted the corresponding element, hence you get a garbage value of zero as seen in the checker logs.
•  » » » 13 months ago, # ^ |   0 thanks a lot sir...!!!
»
10 months ago, # |
0

# include

using namespace std;

void p(int n){ cout<<n<<endl; }

int main() { int t; cin >> t;

while (t--) {
int l, r, x;
cin >> l >> r >> x;

int a, b;
cin >> a >> b;
if(a>b) swap(l,r);
if(a == b) p(0);
else if(abs(a-b)>=x) p(1);
else if(abs(r-b)>=x) p(2);
else if(abs(a-l)>=x) p(2);
else if(abs(r-a)>=x && abs(b-l)>=x) p(3);
else p(-1);
}
return 0;

}

 » 9 months ago, # |   0 1759F - All Possible DigitsI implemented the algorithm below, which is O(n) time-complexity and O(n) space-complexity. But still, I am getting TLE for the 7th test case.Could anyone tell me the error in my code and how I can optimize the algorithm's run-time?The code can be found here: 218600714
•  » » 3 weeks ago, # ^ |   0 There are so many places, where it is not O(n), vector allocation, loopsO(p), maybe, but p = 10^9, that's why TLE,Here is the solution that works in O(nlogn):259545032
 » 4 months ago, # |   0 In problem E, I kept failing using non recursive approach, didn't think about the case where you'd use green twice
 » 6 weeks ago, # |   0 what a incredible problem EI was only thinking the recursive DP approaches which were too slow because to it depended on the health tooo, but reading editorial solution made me think I have lot to learn bring more problems like these.