1995A - Diagonals
How many described diagonals are there in total? How many cells do they contain?
In total we have $$$2 n - 1$$$ diagonals. There is only one diagonal that contains $$$n$$$ cells, two containing $$$n - 1$$$ cells, ..., and two containing only one cell each (namely passing through $$$(1, n)$$$ and $$$(n, 1)$$$).
Obviously, in this case, it is worth filling the largest diagonal with chips, then two that are smaller in size, and so on. The asymptotics turns out to be $$$O(n)$$$.
1995B1 - Bouquet (Easy Version)
For each number of petals, we can bruteforce the answer for $$$x, x + 1$$$
First, we can aggregate number of flowers with $$$x$$$ petals into $$$c_{x}$$$ (for example, sort the array and then create array of pairs $$$(x, c_{x})$$$, where $$$c_{x}$$$ is the length of segment with elements equal to $$$x$$$).
Note that $$$\sum_{x} c_{x} = n$$$. Also note that for every $$$x$$$ we won't need more than $$$\left\lfloor\frac{m}{x}\right\rfloor$$$ flowers (otherwise total number of petals will exceed $$$m$$$).
Then we iterate through all $$$x$$$. Suppose that we want to assemble a bouquet with $$$x, x + 1$$$ petals. We can bruteforce the amount of flowers with $$$x$$$ petals in $$$O(c_{x})$$$. If we have $$$0 \le k_1 \le min(c_{x}, \left\lfloor\frac{m}{x}\right\rfloor)$$$ flowers with $$$x$$$ petals, we already have $$$k_1 * x$$$ petals. There are still $$$m - k_1 * x$$$ coins which we can spend for flowers with $$$x + 1$$$ petals. There are at most $$$k_2 = min(c_{x + 1}, \left\lfloor\frac{m - k_1 * x}{x + 1}\right\rfloor)$$$ flowers with $$$x + 1$$$ petal we can buy. So we need to find maximum over all such $$$k_1 * x + k_2 * (x + 1)$$$.
Total complexity is $$$O(\sum_{x} c_{x}) = O(n)$$$ for finding the maximum and $$$O(n \log n)$$$ for sorting.
1995B2 - Bouquet (Hard Version)
Maybe there is a way to change bruteforce into checking optimal values for counts of $$$x, x + 1$$$? Maybe there are only few types of optimal bouquets for $$$x, x + 1$$$?
We already have a list of $$$c_x$$$. We can use hash map to be able to check for any $$$c_x$$$ by $$$x$$$.
We again will try to assemble the bouquet only with flowers with $$$x, x + 1$$$ petals. We set $$$k1 = min(c_{x}, \left\lfloor\frac{m}{x}\right\rfloor)$$$. Then we have $$$coins = m - k1 * x$$$. Let's set $$$k2 = min(c_{x + 1}, \left\lfloor\frac{coins}{x + 1}\right\rfloor)$$$. Then we have $$$coins = m - (k1 * x + k2 * (x + 1))$$$. Let's substitute flower with $$$x$$$ petals with flower with $$$x + 1$$$ petals as many times as we can. This can be done $$$r = min(k1, c_{x + 1} - k2, coins)$$$ times, as each operation will require us 1 coin, 1 flower in the bouquet with $$$x$$$ petals and one 1 flower with $$$x + 1$$$ petals not in the bouquet. In total we can get $$$(k1 - r) * x + (k2 + r) * (x + 1)$$$ petals.
This assembling is optimal. Here is why. Suppose that we have $$$0 \le b1 \le c_{x}$$$ flowers with $$$x$$$ petals and $$$0 \le b2 \le c_{x + 1}$$$ flowers with $$$x + 1$$$ petals and greater total value of $$$b1 * x + b2 * (x + 1)$$$. We already know that $$$b1 \le k1$$$ by choosing of $$$k1$$$. If $$$k1 - r < b1$$$, then we can ''undo'' our operation $$$r + b1 - k1$$$ times, sum is still not greater than $$$m$$$, 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$$$. If $$$k2 + r < b2$$$, then $$$r \ne c_{x + 1} - k2$$$, if $$$r = k1$$$ then it is just the case when we have only flowers with $$$x + 1$$$ petals which will be considered in case $$$x + 1, x + 2$$$, if $$$r = coins$$$ then $$$m = (k1 - r) * x + (k2 + r) * (x + 1)$$$ and we already found the maximum. So $$$b2 \le k2 + r$$$ and $$$b1 \le k1 - r$$$ and $$$b1 * x + b2 * (x + 1)$$$ is not better than optimal.
Total time complexity is $$$O(n)$$$.
1995C - Squaring
How many times we need to apply the operation to index $$$i$$$, so that $$$a[i - 1] \leq a[i]$$$? Let's call it $$$op[i]$$$
It's easy to calculate these values in no time.
Can we just accumulate them?
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] \le 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$$$?
Let's set $$$op[i]$$$ to the number of operation we need to apply to index $$$i$$$ so that $$$a[i - 1] \leq a[i]$$$.
But, if $$$a[i - 1] \ll a[i]$$$, let's set it to the negative number of times that we can apply the operation to $$$a[i - 1]$$$ so that $$$a[i - 1] \leq a[i]$$$ still holds.
Now let's just calculate the prefix sum $$$\texttt{prefix_op}$$$, don't forget to do $$$\max(0, \texttt{prefix_op}[i])$$$. The sum of values in $$$\texttt{prefix_op}$$$ is the answer.
Let's try to go to the logarithmic space to get rid of too big numbers.
$$$\log(x * x) = 2\log(x)$$$
So, if we replace each value with its logarithm, the operation of squaring becomes multiplying by 2.
But this is not good enough, since we may need to do the operation thousands of times, $$$2^{1000}$$$ is too big, it doesn't fit into any floating point.
So, let's just repeat our trick and go to the log-log space
$$$\log(2 * y) = \log(y) + \log(2)$$$
Now we see that the operation turns into just adding $$$\log(2)$$$. We can afford doing that thousands and millions of times.
Let's deine $$$b[i] = \log{\log{a[i]}}$$$
So now, we can just go with a for-loop and do $$$\displaystyle{\left\lceil\frac{b[i] - b[i - 1]}{\log(2)}\right\rceil}$$$ opeartions with $$$i$$$-th element, updating $$$b[i]$$$ accordingly.
Since initially $$$b[i] \leq \log(10^6) \leq 20 \log(2)$$$, we can maintain the invariant that $$$b[i] \leq (20 + i)\log(2)$$$ since after applying an operation to $$$b[i]$$$ we can't exceed $$$b[i - 1]$$$ by more than $$$\log(2)$$$. It means that the final numbers in the log-log space won't exceed $$$(n + 20)\log(2)$$$. We can maintain $$$O(n)$$$ arithmetics using double without any problems.
1995D - Cases
If letter is chosen as an ending to some case, each occurrence of this letter may in the text can be considered an ending?
The length of the word is something too complex. How can you simplify the restriction?
The final letter must be an ending of some case and among any $$$k$$$ consecutive letters there must be at least one ending.
Now you don't need the text because you can store bitmasks instead of substrings of length $$$k$$$. To calculate the bitmasks you can use prefix sums for each of the characters (it will take $$$O(cn)$$$ overall).
Now you need to find a bitmask with a minimal number of ones which intersects all the stored bitmasks.
Identify "bad" bitmask instead of "good" ones.
(Read the hints.) $$$b$$$ is bad if there exists stored $$$a$$$ such that $$$a \text{&} b = 0$$$ which is equivalent to $$$b$$$ being a submask of $$$\text{~}a$$$. All such b can be found using simple dp on bitmasks. The rest $$$b$$$ are good.
Time complexity: $$$O(c n + c 2^c)$$$
1995E1 - Let Me Teach You a Lesson (Easy Version)
Consider cases of odd and even $$$n$$$. Which one is simpler?
Even. In this case you can solve the problem for the opposite desks independently. From now on $$$n$$$ is odd.
Let a desk have knights with intelligence $$$a$$$, $$$b$$$ and the opposite one with $$$c$$$, $$$d$$$. Since $$$(a + b) + (c + d) = (a + c) + (b + d)$$$, the minimal total intelligence on these desks is greater iff the maximal total intelligence is less.
If you reorder desks/knights in a way that you swap neighbors (i.e. $$$2$$$ with $$$3$$$, $$$4$$$ with $$$5$$$, ..., $$$2 n$$$ with $$$1$$$) instead of opposite knights, it'll probably become easier to think about this problem. We will use this notation from now on.
You're allowed to run in $$$O(n^2)$$$. Wouldn't it have sense to fix some entity and solve in linear time for fixed entity?
Fix the minimal (maximal) desk and the knights who are sitting at it (if the original knights were swapped or not). You'll need to find the minimal maximum on a desk for $$$4 n$$$ such cases.
DP.
(Read the hints.) Let the fixed desk have index $$$k$$$. Let $$$dp_{i, b}$$$ (where $$$i$$$ is the index of the desk and $$$b$$$ is $$$0$$$ / $$$1$$$ which indicates whether the knight $$$2 i$$$ was swapped) be the minimal maximum that can be achieved on a segment from $$$k$$$ to $$$i$$$ (satisfying bit $$$b$$$ and the fact that the desk $$$k$$$ is actually minimal). Then you can easily make transitions $$$dp_{i, 0}, dp_{i, 1} \to dp_{i + 1, 0}, dp_{i + 1, 1}$$$. In the end you'll just need to check $$$dp_{k - 1, b'}$$$ where $$$b'$$$ indicates whether the knight $$$2 * k - 1$$$ was swapped in our choice.
(All the indices for the desks are taken modulo $$$n$$$ and all the indices for the knights are taken modulo $$$2 n$$$.)
Time complexity: $$$O(n^2)$$$, but the constant is large and $$$O(n^2\log n)$$$ solutions with binary search are unlikely to pass.
1995E2 - Let Me Teach You a Lesson (Hard Version)
Read the first two hints to E1.
There are $$$4 n$$$ possible desks in total. One of them will be the minimal desk and another one will be the maximal. What is the common-used technique for such problems?
Sort them and then use two pointers.
The data structure you need is very famous.
(Read the hints.) Assign a boolean matrix $$$2 \times 2$$$ to each of the desks. Rows correspond to the first knight at the desk (two rows for each of the events "the knight was swapped" / "the knight was not swapped"), columns correspond to the second one. The value in the intersection is true if under current restrictions (minimum and maximum) both events can happen, i.e. the result on the desk is between minimum and maximum.
What is a (boolean) multiplication of matrices from $$$d_l$$$ to $$$d_r$$$?
The matrix where the rows correspond to the knight $$$2 d_l - 1$$$ and the columns correspond to the knight $$$2 d_r$$$.
To determine whether it's possible to swap the knights under current restrictions you can just multiply all the matrices and check if there are ones on the main diagonal. Now using two pointers and a segment tree on these matrices you can solve the problem (basically, when you leave some option for a desk in the sorted array of options, you change one of the values of this matrix from $$$1$$$ to $$$0$$$, and vice versa).
Auto comment: topic has been updated by ikrpprppp (previous revision, new revision, compare).
Access denied 2024-7-24 09:10:13
was the 3 ^ C complexity for D intended here ? the constraints are way too low that it passes
272198648
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.
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).
Watch Um_nik solving this: https://youtu.be/yQx0XNXhf5A?si=I26GD-0SNRXTTBrl&t=3581
I created video editorial for D: Cases
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.net/contest/1995/submission/272222265
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
2 13
3 4
6 3
i found one
Man, I probably could have done better if I didn't try throwing FFT at C as soon as I saw it lol
// 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)); }
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
in B2 what is the intuition behind greedily taking flowers with X petals and then greedily taking flowers with X + 1 petals?
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.
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.
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 day
any hints would be greatly appreciated
code:
Thanks
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.
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)$$$.
lovely problems, especially E
Is $$$O(n\cdot2^c)$$$ intended to pass on D? 272115564
Either this should be hackable or provably lower complexity through optimization.
Fast Editorial!
Can someone explain the solution to C, why are we squaring the previous element value if its already less the current element value
No it is not the case ,the previous value has also got updated before and may have passed current number in terms of value
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.
Has anyone tried simulated annealing in E? I tried many times but failed.
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.
B2 is a very bad problem...
Can someone please explain why 2 pointer approach fails on test case 4 in problem B1 (https://codeforces.net/contest/1995/submission/272115613)
this submission is giving me TLE , though approach is same as in editorial , what is wrong with this , can someone help ?? 272174109
B2 was really cool! Loved the problem, Couldnt solve it but really cool <3
Kindly give access for the B1 solution code
Great sharing, appreciated.
This was a hard contest overall,why didn't you have atleast equal points for B2 and C?
I solved Problem C using DP
I 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<n; i++){ if(arr[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 } }why cant we see the editorial's solution? Its showing You are not allowed to view the requested page
$$$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: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 :( ))Proof by AC: old version with binary search; new version with two pointers
Can't you just use two pointers to get rid of binary search?
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
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.
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:
where "is possible" means that there is a way to do the swaps such that all intelligences are in the given interval)
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.
Yes that (obviously) works! It is also slightly faster and I modified my comment. Thanks!
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.
"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.
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")
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.
Thanks, I am now also using two pointers and your solution seems to be similar to mine.
My Code for C failed for test 4, can anyone suggest what's going wrong here.
Probably because of precision issue due to ceil function. For ceil(a/b) , try using (a+b-1)/b
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:
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?
I am having the same issue
Curious about how did you get the 178th input? Usually it only prints a few lines.
I stored the input array elements in a string and printed that string for 178th test case. You can refer to this submission. 272239875
this 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<<endl ; cout<<s<<endl ; }Submission for B2=> https://codeforces.net/contest/1995/submission/272253389 Submission for B1=> https://codeforces.net/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...
Having the same issue but I did not use binary search or priority queue here is my submission 272143091
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
similar approach,
Submission why does this solution give tle on tc5?
how do i fix it?
nvm got it
Any solution for B2 with Binary search?
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
anyone solved B2 using binary search?
im getting WA. my solution
https://codeforces.net/contest/1995/status/B2/page/4?order=BY_PROGRAM_LENGTH_ASC
You can get the idea from here...
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)
How does above two for loops achieve point no 2, which you have mentioned in editorial?
ikrpprppp
The first loop marks all the inverted submasks of bms as bad (they are immediately bad because they do not intersect with at least one of the submasks in bms). The second loop iterates over all submasks in decreasing order. It checks whether there exists a bad submask which differs from the current in one bit (1 instead of 0). It works because all such submasks are clearly greater than current (meaning their badness is already finalised).
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
ksize 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.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
Code : 272281705
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.
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::floorand 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
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
Another property of log :
We take log again
As n should be greater than k we have to take ceil of the log portion.
Now, I got that. Thanks a lot Roronoa_Zoro, you couldn't have made it any clearer.
Welcome
thanks bro i was struggling with the other method
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??
It works both ways for my solution. 273113918
https://codeforces.net/contest/1995/submission/273111814
yeah I saw, I still don't find any difference ...Above is my code ...if possible could u pls figure out where it goes wrong
$$$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
Thanks for such a neat solution, was stuck in it for so long!
Why having B2? I think remove B2 will be better.
Guys, can someone please explain to me, why do we need to calculate the prefix sums for op(array in solution)? UPD: I inderstood))
hello can some one explain why my code is getting TLE for question B1? 272156166
Can someone help me out with B1? submission
I 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.
try to use int64_t
That solved the issue, thanks a lot! Will definitely keep the constraints in my mind next time.
why wrong answer a test 6 ? 272300984
can someone explain the C integer solution please
Let's assume there were no time constraints. The simplest approach would be to traverse the entire array
asuch that for everya[i] < a[i-1], we keep squaringa[i]untila[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: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: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
awas[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
thanks a lot sir
An alternate and direct solution for C(1995C - Квадратирование) :
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.
Also note that $$$y>=0$$$ so make sure the remember this
PS : 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 :(
272307612
Feel free to ask any queries if anything is not clear :)
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.
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
opsmoves which initially is0and we can maintain aprevas 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
Why am I getting TLE here(prob C)? Is it because of calculating & storing the values?
Pls help someone:
Nvm. Yes, computing & storing led to TLE. Accepted when only dealing with powers
How binary search can used in problem B2?
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
I fail to understand why submission 272216064 doesn't work for C and also 272336177
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.272340317
I 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!
This is the change I did:
ll q = ceil(log2(log2(a[i — 1])/log2(a[i])) + (double)r[i — 1]);
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 ?
It's just try around & find out.
just noticed that your solution with WA11 has wrong parenthesis for q, I corrected it and got AC
Ohh got it. Nice to know that it works there as well. Awesome, mate!!
IN B1 we can simply do by sliding window
272257924
Can anyone explain why my solution for B1 gives TLE in TC 5?
Problem C, integer solution:
Why it does work? For
op[2]we have1, and forop[3]-1. Total sum:0. It's not clear enough for me, can someone tell more on it.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?
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_maskshould 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.
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?
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]
lasttimes & we've to square a[i]btimes such that a[i-1]**(2**last) <= a[i]**(2**b). Then take log both sides twice & get the eqn forb.This was very simple & straight forward. I had expected the editorial soln to be something like this.
https://codeforces.net/blog/entry/131851?#comment-1174958
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.
does anyone know why we do
(need - eps)instead of just(need)in the Float solution to C?For someone confused with proof of optimality in B2 solution:
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?
what is "this case" referring to? b1 <= k1?
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
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?
why k2 + r + b1 — k1, not k2 + k2 — b1?
guess you are right about k2+k1-b1 as k2+r-(undo steps) is k2+r — (r+b1-k1) is k2+k1-b1
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)
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: 272606027
My 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.
After taking the log of the array, question C Sqauring can be solved similarly to 1883E - Look Back. My submission : 242466697
ikrpprppp, can you please explain me points below in problem C [
float]:1 + (need - EPS) / log(2)instead ofceil?1e-15gives wrong answer, why we should use1e-9?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?
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.net/contest/1995/submission/273987698
Binary search(+dp) solution for E2: https://codeforces.net/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.
Hello
There actually is a solution for D that involves simple iteration over subsets of letters (with some optimization).
Let's iterate (recursively) over subsets to find the max amount of letters we can throw away.
To check if we can throw away current letter let's create the linked list of all letters to remember which of letters we currently have. Thus it's easy to remove all letters 'X' from the linked list (just by remembering the indexes of the letters 'X') and actually is easy to put them back (in the recursion).
Now let's cut off the recursion if we can't get the better answer in this branch.
275112198
This is just on the edge of TL.
Now to push it further I needed some random shuffle before the start of the recursion and it solved the task :/
May be it's not perfect, but I think it's not so close from getting OK without random shuffling.
E (hard and easy) can be solved with divide and conquer in O(nlogn), the constant factor is pretty huge though. See 275144093 The main idea is to consider a range of seats [start, end], and consider all of the max's and min's that can be achieved by swapping only inside this range, ignoring all other seats. dp[start, end] stores 4 arrays of max's and min's that can be achieved with all 4 combinations of whether start/end are swapped or not. Then you can use divide and conquer by utilizing the answers to dp[start, mid] and dp[mid+1, end] (where mid = (start + end)/2) and combining these answers using 2 pointers/merging of merge sort. As with all the other sols to E, easier said than done. Its really annoying to code up due to the constant factor and also the merging has some intricacies to it, and in addition, you have to do at least 2*4^2 = 32 merges per function call.
1995D - Падежи the task is to find a bitmask $$$p$$$, s.t. $$$\forall $$$stored bitmask $$$q$$$, $$$ p \And q\ne 0$$$.
Hey, my solution for C fails on testcase 13. I have checked the code multiple times, but the logic seems exactly the same as used in the solution. Can someone please help me here? Thanks!
Main idea of Problem C and this problem 1883E - Look Back is same