### ikrpprppp's blog

By ikrpprppp, 12 days ago,

Hint
Solution

Hint
Solution

Hint
Solution

Hint
Solution Integer
Solution Float
Code Integer
Code Float

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution

Hint 1
Hint 2
Hint 3
Hint 4
Solution

## 1995E2 - Let Me Teach You a Lesson (Hard Version)

Hint 0
Hint 1
Hint 2
Solution
• +101

 » 12 days ago, # |   +1 Auto comment: topic has been updated by ikrpprppp (previous revision, new revision, compare).
•  » » 11 days ago, # ^ |   -14 Access denied 2024-7-24 09:10:13
 » 11 days ago, # | ← Rev. 2 →   +8 was the 3 ^ C complexity for D intended here ? the constraints are way too low that it passes272198648
 » 11 days ago, # |   +5 Sorry for still having questions about D. I understand till masking. All masked numbers are bad. For example like ABCDACDBBCDADA when k=4, consider D as the last digit, masked numbers are 1111, 1011, 0111, 1001, 1000. After that, we need to find a number a=xxxx, where a & all masked numbers>0. How do you figure out this step? I can not fully understand. Thank you for answering.
•  » » 11 days ago, # ^ |   +2 All the bad masks are the submasks of the inverted masks of k consecutive characters (in your case, inverted masks are 0000, 0100, 1000, 0110, 0111).
•  » » 10 days ago, # ^ |   0 Watch Um_nik solving this: https://youtu.be/yQx0XNXhf5A?si=I26GD-0SNRXTTBrl&t=3581
•  » » 10 days ago, # ^ |   +3 I created video editorial for D: Cases
 » 11 days ago, # | ← Rev. 2 →   0 for B2 can someone help me find a counter testcase for this submission my appraoch : for each 2 consective X and Y , Y = X+ 1 we take as much X and Y as possible if we can reduce one Y and Add 2*x ( when the money left + Y >= 2 * X ) we make this operation https://codeforces.com/contest/1995/submission/272222265
•  » » 11 days ago, # ^ |   0 for exp : m = 13 4 5 4 2 we take 2 * 5 first our curr ans= 10 & money left = 3 moneyleft + 5 >= 4*2 so we take 4*2 and reduce 5 final ans = 4 + 4 + 5
•  » » » 11 days ago, # ^ | ← Rev. 2 →   +3 2 133 46 3 i found one
 » 11 days ago, # |   +2 Man, I probably could have done better if I didn't try throwing FFT at C as soon as I saw it lol
• »
»
15 hours ago, # ^ |
0

// can u tell how can i make it right,its giving sigterm,know the growth is rapid,but ....

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

# include<bits/stdc++.h>

using namespace std;

# define ll long long

ll calc(ll small,ll big){ ll ans=0; ll to_sq=small; while(big>small){ ans++; to_sq=pow(small,2); small=to_sq; } return ans; }

int main(){ ll t; cin>>t; while(t>0){ ll n; cin>>n; vectorv; for(ll i=0;i<=n;i++){ ll x; cin>>x; v.push_back(x); } ll maxi=v[0]; ll cnt=0; for(int i=0;i<n;i++){ // maxi=max(maxi,v[i]); if(v[i]<maxi){ cnt+=calc(v[i],maxi); maxi=max(maxi,v[i]); } } cout<<cnt; t--; cout<<endl; } // cout<<(calc(2,100000)); }

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 » 11 days ago, # |   +28 in B2 what is the intuition behind greedily taking flowers with X petals and then greedily taking flowers with X + 1 petals?
•  » » 11 days ago, # ^ | ← Rev. 4 →   0 Let the number of flowers with X petals in an optimal solution be A and the number of flowers with X+1 petals be B. Let the maximum number of possible flowers with X petals be C. It is clear that C >= A+B. I claim that in an optimal solution A+B = C. Why? Suppose C > A + B and the solution is optimal. The maximum number of petals you can have is (C-1)(X+1) petals. That is CX-1 petals which is smaller than CX so it isn't optimal. So C = A+B. By greedily replacing as many 'A's with 'B's as we can, we add 1 to the maximum number of petals. Not very intuitive, but in my opinion it somewhat explains why this greedy algorithm is true. Can someone also confirm if my logic is correct.
•  » » 11 days ago, # ^ |   +3 You need to spend M coins. You have unlimited flowers of X and X + 1 petals.If you take flowers with X petals until you can't take any more of such flowers (ie if you take one more flower with X petals the sum exceeds M).The remaining money is M % X. Now you can remove a flower with X petals and add a flower with X + 1 petals. The net increase in the number of petals is 1 and that is how you can cover the M % X amount that is left.
•  » » » 11 days ago, # ^ |   0 Hi i am doing somewhat like this you described above but getting wa on 2879 initially i thought that there may be case when my petals become less than 0 so i added that but not working i am stuck on it for a dayany hints would be greatly appreciatedcode: void solve(){ ll n, m; cin >> n >> m; vector arr(n); map k; for (int i = 0; i < n; i++) { cin >> arr[i]; } vector cost(n); for (int i = 0; i < n; i++) { cin >> cost[i]; k[arr[i]] = cost[i]; } ll ans = 0; for (int i = 0; i < n; i++) { ll freq = k[arr[i]]; ll freqnext = k[arr[i] + 1]; ll val = m - arr[i]; if(val<0){continue;} freq--; ll divnext = val / (arr[i] + 1) + 1; if (freqnext >= divnext) { ll val2 = arr[i] + (arr[i] + 1) * divnext; ll diff = val2 - m; if (freq >= diff) { ans = max(ans, m); } else { ans = max(ans, val2 - diff); } } else { ll val2 = arr[i] + (arr[i] + 1) * freqnext; ll diff = m - val2; ll div = diff / arr[i]; if (freq >= div) { val2 += arr[i] * div; ans = max(ans, val2); } else { val2 += arr[i] * freq; ans = max(ans, val2); } } } cout << ans << endl; } Thanks
•  » » 11 days ago, # ^ | ← Rev. 2 →   0 When we pick the $x'es$ first with all we have, and then pick the $x + 1'es$, it is very obvious that this option makes us pick the most "number" of flowers (not petals). Then we shift some $x'es$ to $x + 1$ as long as we are $\leq m$. Intuitively, if we are limited to buying exactly this number of total flowers, the sum of petals after shifting certain $x'es$ to $x + 1'es$ is the best we can do. Want to increase $x$? We are already at max $x$, want to increase $x + 1$? Then we are decreasing the sum. Want to increase both? Not possible since we would be going beyond the maximum flower count. Let's say our configuration has a, b flowers, and there exists another configuration with greater sum, having p, q flowers and p + q < a + b. Then we get $x \cdot (p + q) + q > x \cdot (a + b) + b$. Implies $q - b > x$. Meaning our count of $x + 1$ in configuration 2 is exceeding the count of $x + 1$ in configuration 1 by at least x + 1. Now we are obviously left with a lot of $x'es$ to be picked in the second configuration, due to $p + q < a + b$ and $q - b > x$. Which implies $x < q - b < a - p$, meaning we are left with at least x + 1 more unused $x'es$ from c1. If the count of $x + 1$ in c2 is exceeding that of c1 by at least x + 1, then consider x $x + 1'es$. All of those extra ones can be collected together to form an $x$ and all those $x + 1$s turn into $x'es$, together forming x + 1 $x'es$, (increasing the flower count by one). Which we indeed have to spare. We can keep doing this as long as total count of the configuration is less than our original one. Every other configuration will be reduced to our total flower count, for which we already have the maximum sum!The intuitive path on how to think about it is to first realise that the max petals sum comes from a configuration with maximum flowers picked, just as a guess, since this is not true in general for example m = 14, and petals are 3 and 7 respectively instead of consecutive. Overall it is one of this luck based problems, where you win if it clicks or you lose typa problem.
•  » » 11 days ago, # ^ |   +10 This is a visualization of the solution. x is the number of flowers with 4 petals, and y is the number of flowers with 5 petals. (1) Buy as many flowers with 4 petals as possible. (2) Buy as many flowers with 5 petals as possible. (3) Replace the flowers with 4 petals with flowers with 5 petals.
•  » » 11 days ago, # ^ |   0 I found the intuition from Bezout's identity. Basically, given we are $an+b(n+1) \leq m$. By maximizing greedily the value of $a$ and thus obtaining $a'n+b'(n+1) = m'$ (where $m - m' > 0$), we know that it doesn't give an optimal solution. Now, we need to find a linear combination of (negative amount of) $n$ and (positive amount of) $n+1$ that is the closest to $d = m - m' > 0$ but not exceeding it.By Benzout's identity, $an+b(n+1)=c$ have a solution for any integer $c$ (though we only need to consider all such c so that $0 < c \leq d$). One trivial solution (satisfying $a < 0$ and $b>0$) is $(-c, c)$. Note that this is the most optimal pair, since all solutions to $an+b(n+1)=c$ are of the form $(-c+(n+1)k, c-nk)$.
 » 11 days ago, # |   +16 lovely problems, especially E
 » 11 days ago, # | ← Rev. 2 →   0 Is $O(n\cdot2^c)$ intended to pass on D? 272115564Either this should be hackable or provably lower complexity through optimization.
 » 11 days ago, # |   -17 Fast Editorial!
 » 11 days ago, # | ← Rev. 2 →   0 Can someone explain the solution to C, why are we squaring the previous element value if its already less the current element value
•  » » 11 days ago, # ^ |   0 No it is not the case ,the previous value has also got updated before and may have passed current number in terms of value
 » 11 days ago, # |   0 can anyone poing out whats going wrong with my B1 submission . I am sorting the vector and trying to go over the vector while keeping a sum and resetting it whenever we find an element with difference of >1.
 » 11 days ago, # |   0 Has anyone tried simulated annealing in E? I tried many times but failed.
 » 11 days ago, # |   0 My submission 272141985 to E2 may have a quadratic complexity. Can anyone hack it?Outline: Basically do the same DP as in E1 editorial, but maintain only the Pareto front of current (min, max).I couldn't come up with a counterexample where the number of points on the Pareto front becomes linear, nor could I find a proof that the number of points is bounded.
 » 11 days ago, # |   +40 B2 is a very bad problem...
 » 11 days ago, # |   0 Can someone please explain why 2 pointer approach fails on test case 4 in problem B1 (https://codeforces.com/contest/1995/submission/272115613)
 » 11 days ago, # |   0 this submission is giving me TLE , though approach is same as in editorial , what is wrong with this , can someone help ?? 272174109
 » 11 days ago, # |   0 B2 was really cool! Loved the problem, Couldnt solve it but really cool <3
 » 11 days ago, # |   0 Kindly give access for the B1 solution code
 » 11 days ago, # |   0 Great sharing, appreciated.
 » 11 days ago, # |   0 This was a hard contest overall,why didn't you have atleast equal points for B2 and C?
 » 11 days ago, # |   -11 I solved Problem C using DPI am provinding the code and you can understand what we trying tot do.static PrintWriter out = new PrintWriter(System.out); static FastReader s = new FastReader(); public static void main(String[] args) { int T = 1; T = s.nextInt(); outer:while (T > 0) { T--; int n = s.nextInt(); long arr[] =s.readArrayLong(n); long count = 0; for(int i = 0 ; i < n; i++){ if(arr[i] > 1)count++; if(arr[i]==1 && count > 0){ System.out.println(-1); continue outer; } } long ans = 0; long dp[] = new long[n]; for(int i =1; i=arr[i-1] && arr[i-1] !=1 ){ long a = arr[i-1]; long sum = 0; while(a < arr[i]){ a = a*a; sum = sum+1; } long b = 0; if(a > arr[i])b++; if(sum <= dp[i-1]){ dp[i] = Math.abs(sum -dp[i-1])+b; ans = ans+dp[i]; } }else if(arr[i] < arr[i-1]){ long a = arr[i]; long sum = 0; while(a < arr[i-1]){ a = a*a; sum++; } dp[i] = sum + dp[i-1]; ans = ans+dp[i]; } } System.out.println(ans); // end of while loop } }
 » 11 days ago, # |   0 why cant we see the editorial's solution? Its showing You are not allowed to view the requested page
 » 11 days ago, # | ← Rev. 2 →   +14 $E1$ (and maybe $E2$ according to the tags) can be solved with 2-sat + binary search.(For $n \equiv_2 0$ it is easy to solve with the greedy algorithm, see Hint 1)For each desk there are 4 possible ways to for the total intelligence (swap position 1 and/or swap position 2), and on of them must be the minimum total intelligence of all desks. We can then binary search the maximal total intelligence (or actually the difference between the minimal and maximal total intelligence) and take the "best" one. Instead of a "slow" binary search, we can save all possible values for the total intelligence on a desk in some array and sort/dedup it. Every solution will have all total intelligences between some lowest total intelligence and some highest, so we can use two pointers to find the "best" pair. To check whether a pair of (minimum total intelligence, difference) is possible, we remember for each desk which of the 4 possible ways would lead to an intelligence in $[\text{min}; \text{min} + \text{diff}]$. This means we have one of the four possible outcomes: all $4$ ways are possible, i.e. we don't have any (additional) constraints for the two positions only $3$ ways are possible $\implies$ $1$ isn't possible; $\lnot (a \land b) \equiv \lnot a \lor \lnot b$ which can be added to the two-sat solver $2$ ways are possible, i.e. $(a \land b) \lor (c \land d) \equiv (a \lor c) \land (a \lor d) \land (b \lor c) \land (b \lor d)$, which can also be added to the two-sat solver $1$ way is possible, this means that we have to "force" both swaps (constraints, and this can also be easily added to the solver) all $4$ ways are impossible, this means that for that specific pair of $(\text{min intelligence}, \text{difference})$ it is not possible Then, after adding all constraints (there are $n$ variables, one for each of the first $n$ positions), if the two-sat solver finds an assignment, there is some combination of swaps that would result in that $(\text{min intelligence}, \text{difference})$. So after trying out all possible mininum total intelligences, we simply take the best result and output it.The time complexity is O(n * log A * n) = O(n^2 log A) where A = 2e9.As mentioned in the comments (and described above), using (a simple) two-pointer method leads to a complexity $\mathcal O(n^2)$.(Unfortunately, as mentioned in the editorial, the constants are large so I had to optimize a lot of things to make it (barely, 1800ms/2000ms) pass (and it can probably be hacked :( ))
•  » » 11 days ago, # ^ |   +3 Can't you just use two pointers to get rid of binary search?
•  » » » 11 days ago, # ^ | ← Rev. 2 →   0 what exactly should I use two pointers on? My (modified) approach would be sort (and dedup) all possible total intelligences for the desks and do two-pointers on that array. But unfortunately that does not work, mostly because I'm not sure when to move the "left"/"right" pointers. My current approach is to do $l \gets l + 1$ if it is possible to do some swaps such that all total intelligences are in $[\text{desk}[l + 1]; \text{desk}[r]]$, but unfortunately that won't work because that (check) is not really monotonous. Is that what you mean by two pointers or do you mean something else?Edit: only binary searching on the values in "desks" should improve constant factors a lot though
•  » » » » 11 days ago, # ^ |   0 Why is it not monotonic? There can't be a situation where you can't have all the intelligences in $[l, r]$, but can in $[l + 1, r - 1]$, therefore the value of the minimum $r$ is non-decreasing with $l$, so you can find them all in $O(n^2)$ total.
•  » » » » » 11 days ago, # ^ |   0 Maybe that's just a skill issue/misunderstanding on my side, but the way I know two pointers, you basically increase $l$ "as long as possible" and decrease $r$ "as long as possible". The problem is that both $[l + 1; r]$ and $[l; r - 1]$ might be valid intervals but the optimal solution might be $[l; r - 1]$, so I need to somehow decrease $r$ first. On the other hand, the optimal solution might be $[l + 1; r]$, so I would have to increase $l$ first. (I think the main problem is that the step size, i.e. $\text{desk}[i + 1] - \text{desk}[i] \ne c$, is not constant.)(Just to clarify, my algorithm would be: while $l < r$ and $[\text{desk}[l + 1]; \text{desk}[r]]$ is possible, increase $l$ by $1$ while $l < r$ and $[\text{desk}[l]; \text{desk}[r - 1]]$ is possible, decrease $r$ by $1$ where "is possible" means that there is a way to do the swaps such that all intelligences are in the given interval)
•  » » » » » » 11 days ago, # ^ |   0 You want to calculate for all $0 \le l \le 4n$ the value of $l \le r_l \le 4n$, where $r_l$ is the minimum $r$ such that $[desk[l], desk[r]]$ is possible. Then obviously $r_{l - 1} \le r_l$. So we can calculate $r_0$, then $r_1$, then $r_2$, etc. When we go from $r_l$ to $r_{l + 1}$, we set $r_{l + 1} = r_l$ and increase it by $1$ while $[desk[l + 1], desk[r_{l + 1}]]$ is not possible. $r$ will be increased no more than $4n$ times.
•  » » » » » » » 10 days ago, # ^ |   0 Yes that (obviously) works! It is also slightly faster and I modified my comment. Thanks!
•  » » » » » » 7 days ago, # ^ | ← Rev. 6 →   0 One thing that I realized from this problem is that there are two main ways of using two pointers.The first approach is to position the pointers at opposite ends of the array and iterate them towards each other uintil they meet, in which case the distance between the pointers is monotonically decreasing, such that $n$ iterations are performed in total (in an array of length $n$).A variant of the first approach is to keep iterating the pointers past each other until they reach their opposite ends, respectively, performing $2n$ iterations. (Whether this is needed or not, depends on the problem.)The second approach is to position the pointers at the same end of the array and iterate them towards the other end, in which case the distance between the pointers keeps changing (for more or for less), but the distance from each pointer to the other end of the array is monotonically decreasing, such that $2n$ iterations are performed.The right approach depends on the problem, of course. In this problem, if you positioned the pointers at opposite ends, it would not be clear which one to move at each iteration, so the second approach is best.
•  » » 11 days ago, # ^ |   0 "there are $n$ variables, one for each of the first $n$ positions"Aren't there only $O(n)$ constraints? For $i$-th position only $i-1$-th and $i+1$-th positions matter.
•  » » » 11 days ago, # ^ |   0 Yes, there are exactly $n$ constraints. I didn't use Hint 2, so I assume that I can only swap knight $i$ and $i + n$ (which means that every possible "swap" is "responsible" for 2 positions; one in the first $n$ and one in the last $n$, i.e. there are (exactly) $n$ "swap-variables/constraints")
•  » » 11 days ago, # ^ |   0 Check 272115438 for a 2-sat + 2-pointers $O(n^2)$ solution. The minimal maximum is monotonic w.r.t. the lower bound of a given minimum.
•  » » » 10 days ago, # ^ |   0 Thanks, I am now also using two pointers and your solution seems to be similar to mine.
 » 11 days ago, # |   0 My Code for C failed for test 4, can anyone suggest what's going wrong here. My Code#include "bits/stdc++.h" using namespace std; #define ll long long int #define pb push_back #define vi vector void iv(vi &v, int n) { ll temp; for (int i = 0; i < n; i++) { cin >> temp; v.pb(temp); } } void ov(vector &v) { for (auto i : v) { cout << i << " "; } cout << endl; } long long int fun(long long int n) { ll n1 = 1; while (n > n1) { n1 = (n1 * 2); } return n1; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while (t--) { int n; cin >> n; vi v; iv(v, n); long long unsigned int ans = 0; int flag = 0; vector op(n, 1); for (int i = 1; i < n; i++) { if (v[i] < v[i - 1] && v[i] == 1) { flag = 1; break; } op[i] = ceil( ((op[i - 1]) * log(v[i - 1])) / log(v[i])); op[i] = max((ll)1, op[i]); op[i] = fun(op[i]); ans += (ll)ceil((log(op[i])) / (log(2ll))); } if (flag) { cout << -1 << endl; continue; } cout << ans << endl; } return 0; } 
•  » » 11 days ago, # ^ |   0 Probably because of precision issue due to ceil function. For ceil(a/b) , try using (a+b-1)/b
•  » » » 11 days ago, # ^ |   0 Thanks for your concern, but the problem was in calculating the op array in my code , in which I was storing powers of 2 (obviously in increasing manner) for adding that in my answer( but while adding to answer I was taking log2 of op[i] ), but for some large N, the elements of op array were getting out of Integer limit.I have written new code: New Codec++ #include "bits/stdc++.h" using namespace std; #define ll long long int #define pb push_back #define vi vector void iv(vi &v, int n) { ll temp; for (int i = 0; i < n; i++) { cin >> temp; v.pb(temp); } } void ov(vector &v) { for (auto i : v) { cout << i << " "; } cout << endl; } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int t; cin >> t; while (t--) { int n; cin >> n; vector v; iv(v, n); vector op(n, 0); vector pref(n, 0); int i1 = 0; while (i1 < n && v[i1] == 1) { i1++; } if (i1 == n) { cout << 0 << endl; continue; } int flag = 0; long long int temp; for (int i = max(i1, 1); i < n; i++) { if (v[i] == 1) { flag = 1; break; } if (v[i] == v[i - 1]) { pref[i] = pref[i - 1]; continue; } if (v[i] < v[i - 1]) { temp = ceil(log(v[i - 1]) / log(v[i])); temp = ceill(log(temp) / log(2ll)); pref[i] = pref[i - 1] + temp; } else { swap(v[i], v[i - 1]); temp = floor(log(v[i - 1]) / log(v[i])); temp = floor(log(temp) / log(2ll)); pref[i] = max(0ll, (pref[i - 1] + (-1) * temp)); swap(v[i], v[i - 1]); } } // cout << "==============\n"; // ov(pref); if (flag) { cout << -1 << endl; continue; } cout << accumulate(pref.begin(), pref.end(), 0ll) << endl; } return 0; } 
 » 11 days ago, # |   0 I noticed an issue with my submission for question C (Squaring) during Codeforces Round 961 (Div. 2). My solution ID 272155531 was marked wrong on test case 2. After the contest, I found that the problem was with the 178th case of the testcase2 that is 5 8 7 7 7 4(5 is the size of array) .On my local machine (VS Code), it gives the correct output of '5', but the system showed my code is giving output '10'. ikrpprppp can you please check this?
•  » » 11 days ago, # ^ |   0 I am having the same issue
•  » » 11 days ago, # ^ |   0 Curious about how did you get the 178th input? Usually it only prints a few lines.
•  » » » 11 days ago, # ^ | ← Rev. 3 →   0 I stored the input array elements in a string and printed that string for 178th test case. You can refer to this submission. 272239875this part :if(g==178){ string s ="" ; s=to_string(n) ; s.push_back(',') ; fo(0,n,1){ s =s+to_string(a[i]) ; s.push_back(',') ; } // cout<<1<
 » 11 days ago, # | ← Rev. 2 →   0 Submission for B2=> https://codeforces.com/contest/1995/submission/272253389 Submission for B1=> https://codeforces.com/contest/1995/submission/272164317 Guys...these are the submissions for B1 and B2. I used a map to store the frequency of each no.of petals in B1, but in B2 this is already given as array C(quantity of flowers).That's the only trivial change I made . Rest of the code comprising of implementation of binary search and priority_queue remains same. please help me figure why is it getting accepted in B1 but gives wrong ans in B2 in Test case 3 whereas I don't find any difference in the logic ...Thank you...
•  » » 11 days ago, # ^ |   0 Having the same issue but I did not use binary search or priority queue here is my submission 272143091
 » 11 days ago, # | ← Rev. 2 →   0 Can't we just use log2 for C though, it just removes the log(2) in the tutorial and makes implementation a lot easier, however I got WA on testcase 13. Believe this is a precision thing... Don't know tho.upd: I found the mistake lol, just a couple of overflowing. Here's the code if anyone's interested double a[MX]; int cnt[MX]; void solve() { int n; cin >> n; rep(i, 1, n) cin >> a[i], a[i] = log2(a[i]), cnt[i] = 0; int ans = 0; rep(i, 1, n) { if (cnt[i-1] + log2(a[i-1]) <= cnt[i] + log2(a[i])) continue; if (a[i]==0) return void(cout << -1 << nl); cnt[i] = cnt[i-1] + ceil(log2(a[i-1]/a[i])); } cout << accumulate(cnt+1, cnt+n+1, 0ll) << nl; } 
•  » » 11 days ago, # ^ | ← Rev. 2 →   0 similar approach,Submission why does this solution give tle on tc5?how do i fix it?
•  » » » 11 days ago, # ^ |   0 nvm got it
 » 11 days ago, # | ← Rev. 2 →   0 Any solution for B2 with Binary search?
 » 11 days ago, # | ← Rev. 2 →   +1 Hello Codeforces, I have a question in the author solution for problem C(code) , why is he taking the value of epsilon to be 1e-9. Is it chosen arbitrarily or is there some maths behind it. If anybody could explain me it would be really helpful . ikrpprppp please help, thank you in advance
 » 11 days ago, # |   0 anyone solved B2 using binary search?im getting WA. my solution
•  » » 10 days ago, # ^ |   0 https://codeforces.com/contest/1995/status/B2/page/4?order=BY_PROGRAM_LENGTH_ASCYou can get the idea from here...
 » 11 days ago, # | ← Rev. 4 →   0 Point no 1 : (Read the hints.) b is bad if there exists stored a such that a&b=0 which is equivalent to b being a submask of . (Understood this statement.) **** Point no 2 : All such b can be found using simple dp on bitmasks. The rest b are good. (Can't understand) vector bad(1 << c); for (int i = 0; i < (1 << c); ++i) bad[i] = bms[((1 << c) - 1) ^ i]; for (int bm = (1 << c) - 1; bm >= 0; --bm) for (int b = 0; b < c; ++b) bad[bm] = bad[bm | (1 << b)] | bad[bm]; How does above two for loops achieve point no 2, which you have mentioned in editorial?ikrpprppp
•  » » » 11 days ago, # ^ | ← Rev. 4 →   0 hmm, trying with pen-paper for better understanding. thanks. Update : understood it, thanks a lot, it was really good problem, sadly couldn't solve it in contest. Problem D:Once we have understood the logic of k size sliding window, we can transform the D problem into below statement. Given an array of 'n' elements, where each element is less than $2^{18}$. We want to find a mask(some integer), such that a[i] & mask > 0 , 0 <= i < n, and mask should have minimum number of set bits.
 » 11 days ago, # | ← Rev. 2 →   +1 I have a very simple solution for problem C. Lets say we are at index $i$, so what we need to check is whether $a_i >= a_{i-1}$ (remember the value $a_i$ here is the updated value). Let's say we used K times the given operation for index $i-1$. First, lets see what that means . If $K = 1$, it means the number is $a_{i-1}^2$; if $K = 2$, then the number is $a_{i-1}^4$, and so on . Therefore, the number at index $i-1$ has now become $a_{i-1}^{2^K}$ . Now we need to make $a_i$ greater than this number . Say we used the operation for it $n$ times (n is any variable). The number will become $a_i^{2^n}$. The equation will now become $a_i^{2^n} \ge a_{i-1}^{2^K}$. Taking $\log_{2}$ two times on both sides and reforming the equation, we will get $n = k + \lceil{\log_{2}\frac{\log_{2}a_{i-1}}{\log_{2}a_i}}\rceil$Code : 272281705
•  » » 11 days ago, # ^ |   0 Thanks a lot for such an awesome explanation but for my own dumbness, I am not abling to come from a2ni≥a2Ki−1 to n=k+⌈log2log2ailog2ai−1⌉.Could u please help me how to reach here by adding one or two lines in between the math.
•  » » » 11 days ago, # ^ | ← Rev. 5 →   0 I maybe use slightly different approach, but formula is kind of similar. So you found some $i$ for which is true that: $a_i > a_{i+1}$. Now you want to find some $k$, that after $k$ squaring you reverse this inequality, so you want to raise $a_{i+1}$ to power $2^k$.Now lets apply $log_{a_{i}}$ to inequality $a_{i + 1}^{2^k} \ge a_{i}$. We got: $2^k \cdot log_{a_{i}} a_{i+1} \ge log_{a_i} a_i = 1$Now lets apply another $log_{2}$ to reduce $2^k$ because k might be around 1e5. We will got another reduced form: $log_2 (2^k \cdot log_{a_{i}} a_{i+1}) = log_2 2^k + log_2 (log_{a_i} a_{i+1}) = k + log_{2} (log_{a_i} a_{i + 1}) \ge log_{2} 1 = 0$And now we can easily find $k$ using std::floor and some eps precision guessings. Note that its all correct because we applying monotonic functions on both sides of inequality(logarithms are, check desmos) and we also always have basement of log that more that 1, so it doesnt change sign of our inequality.Hope it's more clear now. My approach
•  » » » 11 days ago, # ^ | ← Rev. 2 →   0 Property of log: $\log_{a}b^{c} = c\log_{a}b$RHS: $\log_{2}a_{i-1}^{2^{k}} = 2^{k}\log_{2}a_{i-1}$Similarly for LHS, we will get: $2^{n}\log_{2}a_i$Divide by $\log_{2}a_i$ on b/s and we will get $2^{n} \ge 2^{k} \frac{\log_2{a_{i-1}} }{\log_2{a_i}}$Another property of log : $\log_{2}a\cdot b= \log_{2}a + \log_{2}b$We take log again $n \ge k+ \log_{2}\frac{\log_2{a_{i-1}} }{\log_2{a_i}}$As n should be greater than k we have to take ceil of the log portion.
•  » » » » 11 days ago, # ^ |   +1 Now, I got that. Thanks a lot Roronoa_Zoro, you couldn't have made it any clearer.
•  » » » » » 11 days ago, # ^ |   0 Welcome
•  » » 10 days ago, # ^ | ← Rev. 2 →   +1 thanks bro i was struggling with the other method
•  » » 7 days ago, # ^ |   0 Heyy...I also solved it this way ...It gets accepted when written as log2(log2b/log2a) but getting WA when written as log2(log2(b))-log2(log2(a)) ...Any idea why is it??
•  » » » 7 days ago, # ^ | ← Rev. 2 →   0 It works both ways for my solution. 273113918
•  » » » » 7 days ago, # ^ |   0 https://codeforces.com/contest/1995/submission/273111814yeah I saw, I still don't find any difference ...Above is my code ...if possible could u pls figure out where it goes wrong
•  » » » » » 5 days ago, # ^ |   0 $OP[p] = ceil( OP[p - 1] + (log2(log2(A[p - 1])) - log2(log2(A[p]))));$ Your code is right, the only problem here is that after $OP[p-1]$, you have added $log$ and then subtracted $log$ this may lead to error if the number of decimal digits varies between the two double numbers. So either take the constant term out of log or put a bracket between these $log$ functions
 » 11 days ago, # |   +25 Why having B2? I think remove B2 will be better.
 » 11 days ago, # | ← Rev. 2 →   0 Guys, can someone please explain to me, why do we need to calculate the prefix sums for op(array in solution)? UPD: I inderstood))
 » 11 days ago, # |   0 hello can some one explain why my code is getting TLE for question B1? 272156166
 » 11 days ago, # |   0 Can someone help me out with B1? submissionI have stored the petals in a vector and then converted it into a map, with (petals, number of flowers with those petals) format. I then check for each key if there is a (petals+1) entry, and use brute force as the editorial suggests.However I am not sure why it fails on test #7. Thanks.
•  » » 11 days ago, # ^ |   0 try to use int64_t
•  » » » 11 days ago, # ^ |   0 That solved the issue, thanks a lot! Will definitely keep the constraints in my mind next time.
 » 11 days ago, # |   0 why wrong answer a test 6 ? 272300984
 » 11 days ago, # |   0 can someone explain the C integer solution please
•  » » 11 days ago, # ^ |   +4 Let's assume there were no time constraints. The simplest approach would be to traverse the entire array a such that for every a[i] < a[i-1], we keep squaring a[i] until a[i] >= a[i-1]. However, given the constraints, this would result in a TLE error. Instead, we keep a reference with respect to the previous element. I think it would be easier to explain with an example.Let's consider a = [128, 4, 2].Since 4 < 128, we initiate our count at 0 and keep squaring 4 until it becomes greater than or equal to 128: ( 4 * 4 = 16 ) ( 16 * 16 = 256 ) Since 256 > 128, we update our count to 2, as it took us 2 steps.If we continue with our naive approach, the array would be a = [128, 256, 2]. Next, we need to keep squaring 2 until it becomes greater than or equal to 256: ( 2 * 2 = 4 ) ( 4 * 4 = 16 ) ( 16 * 16 = 256 ) So it took us (2 + 3 = 5) steps in total.Now, if we use a different approach, we don't update 4 to 256 in our main array and just keep track of the count. Hence, after the first operation, a = [128, 4, 2]. We know it took us 2 steps to make 4 greater than or equal to 128, so we compare 2 with its previous element (4). It takes just 1 step to make 2 greater than or equal to 4, as ( 2 * 2 = 4 ). Finally, with reference to the previous element, we can say it takes us (2) (steps to convert 4 to 256) + (1) (step to convert 2 to 4) + (2) (steps to convert 4 to 256) = 5 steps.Similarly, if the array a was [128, 4, 16], we compare 4 with 16 and realize it takes 1 step (4 * 4 = 16) for 4 to become greater than or equal to 16. Therefore, to convert 16 to the previous element of 4, it would take us (2) (steps to convert 4 to 256) + (2 — 1) (steps to convert 16 to the previous element of 4, as 4 requires at least 1 step to be greater than or equal to 16).My submission for reference
•  » » » 10 days ago, # ^ |   +1 thanks a lot sir
 » 11 days ago, # | ← Rev. 3 →   +12 An alternate and direct solution for C(1995C - Squaring) : We will store the number of times we are squaring the $a_i$ as $cnt_i$. Initially $cnt[0] = 0$Let the value of $cnt[i] = x$ and for the sake of convenience let $a[i] = p, a[i+1] = q$, we need to find the value of $cnt[i+1]$ Let $cnt[i+1] = y$.So, in other words, we need to find the minimum $y$ such that $p^{2^x}<=q^{2^y}$ Taking log on both sides, we get $2^xlogp <= 2^ylogq \implies x + log2(log(p)) <= y + log2(log(q)) \implies x + log2(log(p)/log(q))<=y$Hence, we directly get the value of $y$, and can keep doing this on and on, and find all the $y$ and simply sum them up. Edge CaseAlso note that $y>=0$ so make sure the remember thisPS : For some reason $log2(log(p))$ — $log2(log(q))$ is giving WA, like I found the cases too, it is generally when $q$ is a power of $p$, but I could not get this flaw in the contest and missed this problem due by this :( Code272307612Feel free to ask any queries if anything is not clear :)
•  » » 11 days ago, # ^ |   0 Ohh nice, this is clean. The most intuitive sol to C I've come across.Btw, can you help me with figuring out why my code gave TLE. It's this.
•  » » 10 days ago, # ^ |   0 I found a very similar approach say:If $( x > y )$ and we need to make $( y \geq x ),$ we must square $( y )$ as follows: $( y^t \rightarrow y^{2t} \rightarrow y^{4t} )$ and so on. Given that one operation takes ops moves which initially is 0 and we can maintain a prev as what it took with the previous operation, then for each $( ar[i - 1] > ar[i] ),$ the operations can be generalized as:$[\text{currOps} = \text{prev} + \log_2 \left( \frac{\log(ar[i - 1])}{\log(ar[i])} \right)]$where $(\text{currOps} = \lceil \text{currOps} \rceil),$ and then add $(\max(\text{currOps}, 0))$ to $(\text{totalOps}).$Code
 » 11 days ago, # |   0 Why am I getting TLE here(prob C)? Is it because of calculating & storing the values?Pls help someone: def read_num(): return int(input()) def read_nums(): return map(int, input().split()) def read_list(): return list(map(int, input().split())) def get_yn(o): return 'YES' if o else 'NO' t = read_num() outs = [] from math import log, floor, ceil for _ in range(t): n = read_num() a = read_list() tot = 0 for i in range(1, n): if a[i]==1 and a[i-1]!=1: tot = -1 break if a[i]
•  » » 11 days ago, # ^ |   0 Nvm. Yes, computing & storing led to TLE. Accepted when only dealing with powers
 » 11 days ago, # |   0 How binary search can used in problem B2?
 » 11 days ago, # | ← Rev. 3 →   0 Can anyone explain me please, how do 2 pointers work in E2? The idea with $2\times 2$ matrix multiplication is clear to me (multiplication of such matrices with indexes from $l$ to $r$ have meaning "can the whole $[l,r]$ segment satisfy current restrictions if knight $2l - 1$ is/isn't swapped and knight $2r$ is/isn't swapped")However, if 2 pointers mean "for every lower bound $low[i]$ find the minimal possible upper bound" (or something similar), it's not clear what $\forall i, j$ "$j < i \Rightarrow low[j] \leqslant low[i]$" (or something similar)Upd: not relevant anymore
 » 11 days ago, # | ← Rev. 2 →   0 I fail to understand why submission 272216064 doesn't work for C and also 272336177
•  » » 11 days ago, # ^ |   +1 I was able to fix the 1st one by replacing log(log(a)) — log(log(b)) with log(log(a)/log(b)).Due to issues with handling floating points, you were getting WA. I copied your code, did this change and it was AC. Pls find it here.272340317I tried the same with 2nd code but it gave WA at test 11. Again issues with handling FPs. Wasn't able to fix it as the computation there was a bit complicated. However, you can try diagnosing it as well. Hope that helps mate!
•  » » » 11 days ago, # ^ |   0 This is the change I did:ll q = ceil(log2(log2(a[i — 1])/log2(a[i])) + (double)r[i — 1]);
•  » » » » 11 days ago, # ^ |   0 thanks, but I don't know why mine doesn't work and yours does, is there any theory or article which I can read to get a better understanding or is it just try around and find out ?
•  » » » » » 10 days ago, # ^ |   0 It's just try around & find out.
•  » » » 11 days ago, # ^ |   0 just noticed that your solution with WA11 has wrong parenthesis for q, I corrected it and got AC
•  » » » » 10 days ago, # ^ |   0 Ohh got it. Nice to know that it works there as well. Awesome, mate!!
 » 11 days ago, # |   0 IN B1 we can simply do by sliding window
 » 11 days ago, # | ← Rev. 3 →   0 272257924Can anyone explain why my solution for B1 gives TLE in TC 5?
 » 11 days ago, # |   0 Problem C, integer solution: We almost can. But, let's take [4,2,4] as an example. op[2] = 1, but we don't want to do anything with a[3]. So, sometimes a[i−1]≤a[i] and we may not want touch a[i] at all, even if something was applied before it. So, should we consider making op[i]<0 for some i ? Why it does work? For op[2] we have 1, and for op[3] -1. Total sum: 0. It's not clear enough for me, can someone tell more on it.
 » 11 days ago, # |   0 I find the editorial of D very hard to understand -- there's no explanation of what is $a$ or $b$, or how "good" or "bad" bitmasks are used to produce the final answer. Can anyone give a more detailed explanation?
•  » » 11 days ago, # ^ |   +1 Every sliding window of size $k$ must contain at least one character that is part of the answer. Either the first character can be part of the window, or the second character, or the third character and so on. This is a lot of words in english, so instead turn on all the bits corresponding to ALL the elements in the window and just say that a non empty subset of the set bits should be present in the answer. That is still a lot of english words. To convert it to maths, notice the ans & window_mask should be non zero (Because at least one set bit from window_mask needs to be preserved). There will be $n - k$ window masks, and this condition should be satisfied for every window.Hence, we have a list of window masks, and we are looking for a mask that satisfies the given condition for each window. Let's find the bad masks. They are the ones where mask & window_mask = 0. In other words, they are the submasks of ~window_mask. Hence, you need to mark all submasks as bad. From here on, everything is standard, depending upon your skill level.You can implement a $4^c$ bruteforce approach by iterating over all bitmasks and checking if one is submask of the other, then you can optimize it to $3^c$ by iterating over submasks directly. Then, you can optimize it by noticing that "subsets of a subset are a subset of the original set", so you don't need to iterate over all submasks, if you process them in decreasing order of set bit count (in their BFS order in the tree created by toggling off one bit at a time), you can just mark the nodes at the next level (with one less set bit count as bad, and offload the remaining responsibility to its children). The time complexity for this seems to be $O(c^2 \cdot 2^c)$ but it is actually $O(c \cdot 2^c)$. Finally, if you want a fancy solution, you can iterate over the masks in decreasing order, and do the same thing as before. This works, because, by the time you reach a mask, all the supermasks would have been processed.
 » 10 days ago, # |   0 I really don't understand the explanation of problem C, at all! What does $a[i-1] « a[i]$ mean? Is $[4,2,4]$ the best example for your point?
•  » » 10 days ago, # ^ | ← Rev. 2 →   +3 Yes, I too felt the same. It's really confusing & didn't need to be like that. I went thru the comments & using the insights wrote this 272336232 & it was AC.So, if we had to square a[i-1] last times & we've to square a[i] b times such that a[i-1]**(2**last) <= a[i]**(2**b). Then take log both sides twice & get the eqn for b. This was very simple & straight forward. I had expected the editorial soln to be something like this.
•  » » 10 days ago, # ^ |   0
 » 10 days ago, # | ← Rev. 3 →   0 Random fact: problem E is essencially an easier version of Day 1 D in Belorussian Olympiad. In that problem you were given a tree, each vertex had a weight, and you have to split tree into connected components of size $\le 2$ such that value {component with max total weight — component with min total weight} was minimised. Unsuprisingly no one solved that one.
 » 10 days ago, # |   0 does anyone know why we do (need - eps) instead of just (need) in the Float solution to C?
 » 10 days ago, # | ← Rev. 2 →   0 For someone confused with proof of optimality in B2 solution: proof of optimality: suppose not (proof by contradiction) then there is another linear combination (b1,b2) which is better than (k1-r,k2+r) if b1>k1-r (obs) b1<=k1, if b1>k1-r then we encountered this case while reaching k1-r , therefore by definition of r it cannot be optimal if b2>k2+r (obs) r cannot be freq[nextIdx]-k2 so r was k1 or coins no need to consider r = k1 case as this would be handled when we reach x+1 if r is coins then (k1-r,k2+r) is m so optimal if neither of above then of course (b1,b2) cannot be optimal
•  » » 10 days ago, # ^ | ← Rev. 2 →   0 what does "if b1>k1-r then we encountered this case while reaching k1-r , therefore by definition of r it cannot be optimal" mean?
•  » » » 10 days ago, # ^ |   0 what is "this case" referring to? b1 <= k1?
•  » » » 9 days ago, # ^ | ← Rev. 2 →   0 we chose r by taking continuously replacing one x by x+1, each time we got a larger answer(cuz one more petal)... since b1>k1-r and b1<=k1 we must have encountered this(b1) number of x flowers somewhere while coming down to k1-r hence b1 cannot be optimal... this refers to the case when number of x flowers is b1
 » 10 days ago, # | ← Rev. 2 →   0 In B2, what does "and we know that now there can't be more than k2+r+b1−k1 flowers with x+1 petals, as otherwise we didn't chose optimal k2" mean?
•  » » 10 days ago, # ^ |   0 why k2 + r + b1 — k1, not k2 + k2 — b1?
•  » » » 9 days ago, # ^ |   0 guess you are right about k2+k1-b1 as k2+r-(undo steps) is k2+r — (r+b1-k1) is k2+k1-b1
•  » » 9 days ago, # ^ |   0 we chose k2 so be the max number of x+1 flowers we could accomodate... and each time we replaced one x flower with x+1 we maintained this property(that number of x+1 flowers is max possible for the number of x flowers)
 » 10 days ago, # |   0 Hi, I was really fascinated by the float method illustrated in editorial for problem C. However I tried to solve it in the log2 (base 2 logarithm) space but somehow I am unable to solve it.here is my submission: 272606027My logic is: In the log2 space, the operation is equivalent to adding 1 to the element. So its basically just checking how any 1s should be added to a[i] for making it larger than a[i-1].Can anyone help me with finding what's wrong in my implementation, or is there some issue in my logic itself, either in my assumption that it would work in log2 space or some other point i've missed.Thanks.
 » 9 days ago, # |   0 Easy Understandable solution of Problem — D Cases With comments to understand /* * Author: Arjit Khare * Created: Friday, 26.07.2024 12:09 PM (GMT+5:30) * linkedin: https://www.linkedin.com/in/arjitkhare/ */ #include using namespace std; #define ll long long #define mod 1000000007 int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #ifndef ONLINE_JUDGE // freopen("input.txt", "r", stdin); // freopen("output.txt", "w", stdout); #endif int t; cin>>t; while(t--){ //inspired solution by tourist int n, c, k; cin>>n>>c>>k; string s; cin>>s; vector letter(n); for(int i = 0; i < n; i++) { letter[i] = s[i] - 'A'; } vector ct(c); for(int i = 0; i < k; i++) { ct[letter[i]]++; } int totalBits = (1< bad(totalBits, false); //there has to be a word ending in a window of k size //so the bitmask not corresponding to that is a bad bitmask for(int i = k; i < n; i++) { int bitmask = 0; for(int j = 0; j < c; j++) { if(ct[j]) bitmask |= 1<
 » 9 days ago, # | ← Rev. 2 →   0 After taking the log of the array, question C Sqauring can be solved similarly to 1883E - Look Back. My submission : 242466697
 » 9 days ago, # |   0 ikrpprppp, can you please explain me points below in problem C [float]: In the solution why we should use 1 + (need - EPS) / log(2) instead of ceil? When I set EPS to 1e-15 gives wrong answer, why we should use 1e-9`?
 » 8 days ago, # |   0 I came up with the solution for C. Squaring by myself(mathematically at least) and realized it was failing due to the missing epsilon(eps) in the code. Why is this value required?
 » 2 days ago, # |   0 Binary search solution for B2: 1) We first try to use only one value of $a_i$ to construct the bouquet. 2) Try to construct a bouquet using $a_i$ and $a_{i-1}$ : Assume that we use $x$ elements of $a_{i - 1}$ and $y$ elements of $a_i$ we will get: $total = x \cdot a_{i-1} + y \cdot a_i \implies total = x \cdot (a_i - 1) + y \cdot a_i$ : $total = -x + a_i \cdot (x + y)$ , let $c = (x + y), \ c \ \leq \ b_{i-1} + b_i$ we get $total = -x + a_i \cdot c$ Notice that if we use some $c$ value and can't make $total \leq m$ by replacing some values of $a_i$ with $a_{i-1}$, then for all values greater then $c$ we cannot make $totatl \leq m$ code: https://codeforces.com/contest/1995/submission/273987698
 » 42 hours ago, # |   0 Binary search(+dp) solution for E2: https://codeforces.com/contest/1995/submission/274040099 Basically we run dp for maximum value among pairs. For even n calculating minimum value is easy, for odd we use dp for i, did we swap the first element, did we swap the i-th element. Then we get WA and understand that binary search sometimes doesn't work Yet it is kinda obvious that the right answer is close to bs result so we also check 20(maybe even less. 10 didn't work) numbers to the right and it gets AC.