Auto comment: topic has been updated by ikrpprppp (previous revision, new revision, compare).

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.

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

Man, I probably could have done better if I didn't try throwing FFT at C as soon as I saw it lol

in B2 what is the intuition behind greedily taking flowers with X petals and then greedily taking flowers with X + 1 petals?

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

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:

• 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 :( ))

Proof by AC: old version with binary search; new version with two pointers

My Code for C failed for test 4, can anyone suggest what's going wrong here.

#include "bits/stdc++.h"
using namespace std;
 
#define ll long long int
#define pb push_back
#define vi vector<long long int>
 
void iv(vi &v, int n)
{
	ll temp;
	for (int i = 0; i < n; i++)
	{
		cin >> temp;
		v.pb(temp);
	}
}
 
void ov(vector<long long int> &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<long long int> 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;
}

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?

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...

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;
}

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

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<bool> 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

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

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.

why wrong answer a test 6 ? 272300984

can someone explain the C integer solution please

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.

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 :(

Feel free to ask any queries if anything is not clear :)

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]<a[i-1]:
            
            b = ceil(log(a[i-1], a[i]))
            trg = a[i]**(b)
                
            b += b%2
                
            x = ceil(log(b, 2))
            a[i] = a[i]**(2**x)
                
            tot += x
            
            
    outs.append(tot)

for out in outs:
    print(out)

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

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:

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.

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?

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?

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:

• 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

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?

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.

• 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 <bits/stdc++.h>
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<int> letter(n);
        for(int i = 0; i < n; i++)
        {
            letter[i] = s[i] - 'A';
        }
        vector<int> ct(c);
        for(int i = 0; i < k; i++)
        {
            ct[letter[i]]++;
        }
        int totalBits = (1<<c);
        vector<bool> 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<<j;
            }
            int badmask = totalBits - 1 - bitmask;
            bad[badmask] = true;
            ct[letter[i]]++;
            ct[letter[i - k]] --;
        }
        //we dont need to find bad mask for last window as any bitmask not having last letter is bad
        int badmask = totalBits - 1 - (1<<letter[n-1]);
        bad[badmask] = true;
        //removing every subset of bad bitmasks
        //if you reverse the order of loops then some bits will be set after they have been traversed
        for(int i = 0; i < c; i++)
        {
            for(int j = 0; j < totalBits; j++)
            {
                if((bad[j] == false) || ((j & (1<<i)) == 0)) continue;
                bad[j-(1<<i)] = true;
            }
        }
        //finding bitmask with least set bits
        int ans = c + 1;
        for(int i = 0; i < totalBits; i++)
        {
            if(bad[i] == true) continue;
            ans = min(ans, __builtin_popcount(i));
        }
        cout<<ans<<endl;
    }
    return 0;
}

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]:

• 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?

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 - Cases 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

Binary search solution for problem B2?