Please read the new rule regarding the restriction on the use of AI tools. ×

ikrpprppp's blog

By ikrpprppp, 2 months ago, In English

1995A - Diagonals

Hint
Answer to Hint
Solution

1995B1 - Bouquet (Easy Version)

Hint
Solution

1995B2 - Bouquet (Hard Version)

Hint
Solution

1995C - Squaring

Hint
Answer to Hint
Solution Integer
Solution Float
Code Integer
Code Float

1995D - Cases

Hint 1
Hint 2
Answer to Hint 2
Hint 3
Hint 4
Hint 5
Solution

1995E1 - Let Me Teach You a Lesson (Easy Version)

Hint 1
Answer to Hint 1
Hint 2
Hint 3
Answer to Hint 3
Hint 4
Solution

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

Hint 0
Hint 1
Answer to Hint 1
Hint 2
Solution
  • Vote: I like it
  • +100
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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

»
2 months ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

was the 3 ^ C complexity for D intended here ? the constraints are way too low that it passes

272198648

»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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.

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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://mirror.codeforces.com/contest/1995/submission/272222265

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 months ago, # |
  Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

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

»
2 months ago, # |
  Vote: I like it +28 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
    Rev. 4   Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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:

      void solve(){
          ll n, m;
          cin >> n >> m;
          vector<ll> arr(n);
          map<ll, ll> k;
          for (int i = 0; i < n; i++) {
              cin >> arr[i];
          }
          vector<ll> 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

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

     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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it +16 Vote: I do not like it

lovely problems, especially E

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Is $$$O(n\cdot2^c)$$$ intended to pass on D? 272115564

Either this should be hackable or provably lower complexity through optimization.

»
2 months ago, # |
  Vote: I like it -17 Vote: I do not like it

Fast Editorial!

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Can someone explain the solution to C, why are we squaring the previous element value if its already less the current element value

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No it is not the case ,the previous value has also got updated before and may have passed current number in terms of value

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Has anyone tried simulated annealing in E? I tried many times but failed.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
2 months ago, # |
  Vote: I like it +40 Vote: I do not like it

B2 is a very bad problem...

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain why 2 pointer approach fails on test case 4 in problem B1 (https://mirror.codeforces.com/contest/1995/submission/272115613)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

this submission is giving me TLE , though approach is same as in editorial , what is wrong with this , can someone help ?? 272174109

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

B2 was really cool! Loved the problem, Couldnt solve it but really cool <3

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Kindly give access for the B1 solution code

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Great sharing, appreciated.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This was a hard contest overall,why didn't you have atleast equal points for B2 and C?

»
2 months ago, # |
  Vote: I like it -11 Vote: I do not like it

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
    }
}
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why cant we see the editorial's solution? Its showing You are not allowed to view the requested page

»
2 months ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Can't you just use two pointers to get rid of binary search?

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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)

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Yes that (obviously) works! It is also slightly faster and I modified my comment. Thanks!

          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
            Rev. 6   Vote: I like it 0 Vote: I do not like it

            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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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")

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks, I am now also using two pointers and your solution seems to be similar to mine.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

My Code
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Probably because of precision issue due to ceil function. For ceil(a/b) , try using (a+b-1)/b

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 Code
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I am having the same issue

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Curious about how did you get the 178th input? Usually it only prints a few lines.

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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 ; 
      }
»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Submission for B2=> https://mirror.codeforces.com/contest/1995/submission/272253389 Submission for B1=> https://mirror.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...

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Having the same issue but I did not use binary search or priority queue here is my submission 272143091

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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;
}
»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Any solution for B2 with Binary search?

»
2 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

anyone solved B2 using binary search?

im getting WA. my solution

»
2 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      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.


»
2 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 5   Vote: I like it 0 Vote: I do not like it

      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

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    thanks bro i was struggling with the other method

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      It works both ways for my solution. 273113918

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        https://mirror.codeforces.com/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

        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for such a neat solution, was stuck in it for so long!

»
2 months ago, # |
  Vote: I like it +25 Vote: I do not like it

Why having B2? I think remove B2 will be better.

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Guys, can someone please explain to me, why do we need to calculate the prefix sums for op(array in solution)? UPD: I inderstood))

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

hello can some one explain why my code is getting TLE for question B1? 272156166

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    try to use int64_t

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That solved the issue, thanks a lot! Will definitely keep the constraints in my mind next time.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why wrong answer a test 6 ? 272300984

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain the C integer solution please

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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:

    1. ( 4 * 4 = 16 )
    2. ( 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:

    1. ( 2 * 2 = 4 )
    2. ( 4 * 4 = 16 )
    3. ( 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

»
2 months ago, # |
Rev. 3   Vote: I like it +12 Vote: I do not like it

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 Case

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

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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)
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Nvm. Yes, computing & storing led to TLE. Accepted when only dealing with powers

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How binary search can used in problem B2?

»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I fail to understand why submission 272216064 doesn't work for C and also 272336177

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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!

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This is the change I did:

      ll q = ceil(log2(log2(a[i — 1])/log2(a[i])) + (double)r[i — 1]);

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 ?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      just noticed that your solution with WA11 has wrong parenthesis for q, I corrected it and got AC

      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ohh got it. Nice to know that it works there as well. Awesome, mate!!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

IN B1 we can simply do by sliding window

»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

272257924

Can anyone explain why my solution for B1 gives TLE in TC 5?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like 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?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
2 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

does anyone know why we do (need - eps) instead of just (need) in the Float solution to C?

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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
  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      what is "this case" referring to? b1 <= k1?

    • »
      »
      »
      2 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    why k2 + r + b1 — k1, not k2 + k2 — b1?

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      guess you are right about k2+k1-b1 as k2+r-(undo steps) is k2+r — (r+b1-k1) is k2+k1-b1

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it
  • 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;
}
»
2 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

After taking the log of the array, question C Sqauring can be solved similarly to 1883E - Look Back. My submission : 242466697

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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://mirror.codeforces.com/contest/1995/submission/273987698

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Binary search(+dp) solution for E2: https://mirror.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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

1995D - Cases the task is to find a bitmask $$$p$$$, s.t. $$$\forall $$$stored bitmask $$$q$$$, $$$ p \And q\ne 0$$$.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

»
7 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Main idea of Problem C and this problem 1883E - Look Back is same