_LeMur_'s blog

By _LeMur_, 11 months ago, In English

1917A - Least Product

Author: zidder
Preparation: _LeMur_
Editorial: zidder
Official solution: 238752794

Hint 1
Hint 2
Hint 3
Solution

1917B - Erase First or Second Letter

Author: _LeMur_
Preparation: _LeMur_
Editorial: zidder
Official solution: 238752759

Hint 1
Hint 2
Hint 3
Hint 4
Solution

1917C - Watering an Array

Author: IgorI
Preparation: IgorI
Editorial: IgorI
Official solution: 238743155

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution
Bonus 1
Bonus 2

1917D - Yet Another Inversions Problem

Author: IgorI
Preparation: IgorI
Editorial: IgorI
Official solution: 238743552

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Hint 7
Hint 8
Hint 9
Solution
Bonus 1
Bonus 2

1917E - Construct Matrix

Author: _LeMur_
Preparation: _LeMur_
Editorial: _LeMur_
Official solution: 238752669

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Solution
Bonus

1917F - Construct Tree

Author: _LeMur_
Preparation: _LeMur_
Editorial: _LeMur_
Official solution: 238752543

Hint 1
Hint 2
Hint 3
Hint 4
Hint 5
Hint 6
Solution
  • Vote: I like it
  • +192
  • Vote: I do not like it

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

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

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

Just Missed C by implementation,and i thought i can solve problems that are implementation based easily...C proved i was wrong.

»
11 months ago, # |
  Vote: I like it +41 Vote: I do not like it

Thank you for the fast editorial! Also between this and Pinely round I have a huge Christmas backlog to upsolve.

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

Thanks for the fast editorial

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

problem E is wangba.

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

why bitsets

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

Oh it was bitsets. I was thinking how to get the two sets in better that $$$n d^2$$$ complexity.

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

Respect for the fast editorial.

Disrespect for a wrong number in contest's title

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

C was really frustraing. Anyways, nice idea and observation.

»
11 months ago, # |
  Vote: I like it +19 Vote: I do not like it

bitset in the author's solution,

  • »
    »
    11 months ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    I really don’t understand why after EVERY ROUND with a bitset in author’s solution, someone has to complain. Bitset is a very good optimization by at least a factor of 32, which is huge both in competitive programming and real life job programming: imagine google pages or apps loading 32 times slower! Bitset is also something quite easy to learn, a lot less advanced than (for instance) a segtree, so it appearing in a div2F or E should really not represent a problem. So why not use it when it is available and force contestants to know it as well?

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

      Non c++ users are at disadvantage in these problems

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

i dont know but somehow a is more tougher than b

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

    actually a just have few logical cases thats it and we miss that. in B one the idea was great to just traverse the array add chraacter to set and increment count variable by set size everytime

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

    no :)

»
11 months ago, # |
  Vote: I like it +18 Vote: I do not like it

C's pretests are really weak, I did same thing with k instead of 2 * n +1; how this case couldn't create? Respect to authors but these are really unnecessary things for FST :(

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

fst round lets gooo

»
11 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Overkilled and missed D by a few minutes.

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

any countertest for C 238728699 please?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it
    1
    8 10 10
    8 1 2 3 4 5 6 7
    1 1 1 1 1 1 1 1 8 1
    

    you can do 1st type of opearation on 1st 9 days, then 2nd type operation on 10th day. ans will be 7 in this case.

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

who solve B with dp or something different from guide?

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

      can you explain the intuition behind this solution?

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

        simple observation of first and last test cases: in first — aaaaa all chr are same and ans is 5; in last -abcd.... all chr are unique and ans is 210;

        so we can assume that initial ans should be sum of 1,2,3..n, and we need to subtract some value when we have same characters: so first test case ans is 5 (15 — x) x is 10 here right, and for last is 210 — 0. and if you continue you could find this x calculating from similar chr in s

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

    https://codeforces.net/contest/1917/submission/238697447

    Intuition:

    A string with all unique characters will have n(n+1)/2 distinct strings.

    If any of the character pair repeats then they will produce duplicate set of strings. A 5 length string can produce 2 4 length strings if the character pairs are unique, but if they are same then they will produce only, 1 4 length string.

    Try making a tree and you will see that on each level you are doing + 1 to the strings formed in previous level. But in case of repeating character you do + 0 to the strings formed in previous level.

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

A more intuitive solution for B is to iterate over string and find number of distinct characters from 2nd position onwards. At every index, number of distinct strings of length (n-i+1) that can be made is number of distinct characters. Time complexity will be O(N) as set will have constant time complexity(max size is 26).

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

    your solution is far better than editorial

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

Thank you for the fast editorial and Merry Christmas to everyone celebrating!

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

E is nice.

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

    It's nice to see that someone evaluates authors' work :)

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

Let see if Specialist is in sight!!!

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

Can anyone explain why this works for B?

    set<char> c;
    int ans = 0;
    for (int i = 0; i < n; i++) {
      c.insert(s[i]);
      ans += (int) c.size();
    }
    cout << ans << '\n';
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Read the editorial, because the problem reduces to for each $$$j$$$ count all possible $$$s_i s_j s_{j+1} \ldots s_n$$$ where $$$i<j$$$

    and choices for $$$s_i$$$ are exactly the number of distinct characters in the prefix $$$s_1 \ldots s_{j-1}$$$

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

    For a string of remaning suffix length l, you can take remove any (n-l-1) elements from (n-l) elements, so only one character is left , thus (l+1) length string with number of distinct character at starting

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

    The idea is based on the fact that every new character encountered introduces new possibilities for generating distinct strings.

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

    First let us suppose all characters are distinct eg. abc then possible strings will be abc, bc, ac, c, b, a. See we have 1 occurrence of length 3, 2 occurrence of length 2 and 3 occurrence of length 3. So what we are doing is we are selecting the Substring from [0,i) and deleting it except one character which gives one occurrence. There are total i ways to select one character between [0,i) substring. Therefore, we need the count of distinct characters at every position of i and add it to our answer.

»
11 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Rare rare contest where system test cases are tricky. I can't remember the last time so many people got their submissions rejected. Unfortunately Problem $$$C$$$ test case $$$26$$$.

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

https://codeforces.net/contest/1917/submission/238696258 Can anyone tell why my sol gives wrong answer

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

    Look at the constraints !! It says $$$a_{i} \leq 10^9$$$. Suppose all $$$a_{i}$$$ have that upper bound value. Their multiplication will be $$$10^{900}$$$ which can't be represented as $$$long$$$. There will be overflow leading to unexpected behavior.

»
11 months ago, # |
  Vote: I like it +18 Vote: I do not like it

I guess C was the toughest problem.

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

"You are not allowed to view the requested page."

I got this message when I click on Official solutions: A, B, E, F

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

The only reason I managed to solve B was pattern recognition. I coded a slow solution, and saw that the amount of possibilities that got added on with each new character of s were equal to the amount of unique characters encountered so far.

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

solved D for the transpose matrix instead, it was a cool problem too :D

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

    Can you give intuition behind it? i was thinking same in contest.

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

      consider two rows, if the difference between the q values of both of them is more than 20, the one with the higher q value will have all of it's element greater than the other. now for each difference from 1 to 20, you pre-calculate the number of inversions the cases when the lower q is ahead of the higher one and vice versa. rest can be handled using segment/fenwick trees

»
11 months ago, # |
  Vote: I like it +32 Vote: I do not like it

The submissions of problems A,B,E and F aren't puplic, Only C and D are (I guess it could have been submitted in the manager mode or something). _LeMur_

Nice contest, sadly I was busy so I managed only to attend the last hour :", (that is why I though of doing it in reverse).

I liked the problems F,E,D (in order)

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

Div.2 E

Why for n, k:
6 6
solution:
1 1 1 1 1 1
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

wrong?

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

    It is not wrong, but there can be multiple solutions, you can print any

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

      l printed. Verdict: wrong.

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

        You got wrong answer, because you print “YES” instead of “Yes”.

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

Great tutorial! Especially I loved the hints.

I have a question regarding my solution for problem C: Why it was enough for me to check for min(2 * n, d)?

Spoiler

full code

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

    You don't need 2*n (you don't even need n actually), the only thing you're interested in is if your first reset could be made more optimal by adding a bunch of stuff so you have a better alignment. Let's say at time 0 you have 5 index that have the same value (so you're score is 5), you only need to check for 2*(n-5) (potentially), because past that, you can make up the point difference by spamming rule 1->2 which will give you 1 point every 2 steps.

»
11 months ago, # |
  Vote: I like it +8 Vote: I do not like it

For B, all final strings will be of the form of a single character and a suffix to the right, or just a suffix by itself. For the suffix case, just add n to your answer since there are n suffixes. For the other case, iterate over the suffix and count the #of characters to its left that aren't the same as the one immediately to its left and update the answer by that much to make sure we only consider unique strings.

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

    My approach is a little bit different.

    Assuming the answer will always have at least two letters. Then it will be one character and a suffix to the right.

    So the answer would be for each suffix, add the number of distinct characters to its left.

    Lastly, we add the number of distinct letters for answer that only has one letter.

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

Not being able to understand why 2*n works in Problem C.


What would happen in this case? when do we perform the first operation of type 2?: 4 10 10 1 1 2 3 1 1 1 1 1 1 1 1 1 4
»
11 months ago, # |
  Vote: I like it +4 Vote: I do not like it

actually crying about C, I had the entire solution up until the 2n+1 part which should be so obvious :(

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

    can you please explain why 2n+1?

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      2*n because max count of ai==i is n and if you take days more than 2*n ratio of score to days will be less than considering alternating operations which will give 1/2 as score to day ratio

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

    Exactly the same situation here !!

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

Can someone please explain why checking till the $$$(2*n + 1)$$$ th day is sufficient in Problem C?

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

    first reset and use op1 and op2 operations for (2*n+1) days, max possible score of n can be achieved. We are trying to get maximum score from initial array of size n by applying op1 in (say x days) and get score y by using (x+1) days. So maximum score from initial array can be n, and this score can be achieved by simply using first op1 and then op2 for (2*n+1) days, so checking beyond (2*n+1) days to get maximum score from initial array by applying op1 is not helpful!

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

Can somebody explain me, why we are performing first type2 operation in min(d , 2 * n) days?? why 2*n?

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

    Doing the first type2 operation can get at most n points. By doing opration(1,2) n times(2n times operations), you can get n points, too. So if you doing the first type2 operation on (2n+1)th day, why not doing 1+n*(1,2) instead?

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

FST on C ..... [sad]

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

could someone help to find why my code have TEL?https://codeforces.net/contest/1917/submission/238891629

I use a set instead of log(k) pointers to find numbers, it should have a complexity of O(A*n*log(k)+k*log(k)).

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

in C problem if we take t=10^3 and n=2^103 then the total time complexity will be tc->10^3 * 2*10^3 * 2*10^3 ie O(t*n*(min(d,2*n))) ie finally tc->4*10^9 so how it is not giving tle as according to me 2sec->2*1e8 operations

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

    "It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2000$$$"

    You can't have $$$1000$$$ test cases each with $$$n = 2000$$$ as the sum of $$$n$$$ over all test cases would be greater than $$$2000$$$.

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

For the bonus part of problem E (n is odd). We can solve the problem as follows := First we note that if we have found a construction for k , then by inverting every bit we get another valid construction for k'= n ^ 2 — k.Let us handle odd k , for k >= n and k <= 2n — 1 . we can easily find solution for k = n , for k = n + 2 , we can place 1s at (1,1) ; (1,2) ; (1,3) ; (2,1) ; (3,1) and place rest of them on the diagonal i.e. a[i][i] = 1 for i >= 4. Now by filling 2 × 2 squares , we can get the solution for all odd k in [n, 2n — 1]. For even k <= (n-1)^2 , the problem reduces to the original problem E. Also note we can't have even k > n * (n — 1). For k in [(n-1)^2 + 1 , n * (n — 1)] we can reduce the problem to odd k' = n^2 — k. and we have already solved that. Similarly odds > 2n , can be solved by interting bits for k' = n^2 — k.

»
11 months ago, # |
  Vote: I like it +18 Vote: I do not like it

My screencast & editorial. Only problems A, B, C, but it's more than nothing.

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it
void solve()
{
    int n,k,d;
    cin>>n>>k>>d;
    vector<int>a(n),v(k);
    int score=0;
    for(int &i:a)cin>>i;
    for(int &i:v)cin>>i;
    for(int i=0;i<min(2*n,d);i++)
    {int cnt=0;
        for(int j=0;j<n;j++)
        {
            if(a[j]==j+1)cnt++;
        }
        score=max(score,cnt+(d-(i+1))/2);
        for(int l=0;l<v[i%k];l++) // ik as well 
        {
            a[l]++;
        }

    }
    cout<<score<<endl;

} 

here why we did a[l]++ we have to set it zero na then increment it ? pls help

  • »
    »
    11 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    it's type one operation
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In the editorial of C it was said we need to wait for atmax 2n days if 2n < d.Can someone explain this because i think atmax n days would be sufficient. Is there anything which i am missing ? 238724490

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

Problem C
For all who are confused regarding why we are iterating 2*n times instead n times, you can try this test case.

5 6 7
0 1 2 3 4
1 1 1 1 1 5

if you will iterate only n times, then you will get maxscore=3. But correct answer is 4.
In order to get correct answer you have to iterate more than n times

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

D is hard to write code

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

Can someone help with C. 238738762

I know that can be solved by $$$ O(n^2) $$$, but can be there other solutions than authors?

I used $$$ dp[i] $$$ like when $$$ a[i]==i $$$ and $$$ dp2[i] $$$ when $$$ (a[i]==i+1) $$$.

My solution is $$$ O(n*log2(k)+k*log2(k)+n^2) $$$

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

Can anyone give an example where min(d,n+2) fails and min(d,2*n+2) will pass and proof for 2*n

238785353

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

    here you go
    8 11 12
    2 1 2 3 4 5 6 7
    1 1 1 1 1 1 1 1 1 1 8

    correct answer should be 7 but if you will iterate only till n+2, then you will get 5 as result which is wrong.

»
11 months ago, # |
  Vote: I like it +4 Vote: I do not like it

My solution for problem D is exactly $$$\mathcal O(n \log n \log V)$$$, which is the same as the tutorial. But it gets TLE on test 6, can anyone tell me why? thanks!

238788200

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

Can anyone explain in C why it is required to iterate up to 2*n???

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

    Because after 2*n , We can't gain more than value of 'n' from type one operation . But we can gain more than 'n' from type two and one alternatively . So its optimal to not choose operation 1 after 2*n onwards . So we stop when it reaches 2*n .

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

    see we know that after doing our first op2(if it is optimal),we need to repeat op1 and op2 for the rest of the days. But our score can be atmost n for the first op2.This is because we have n integers,so n positions can have ai=i atmost. So, n can be the max score from out first op2.Now,we know after doing our first op2 we will add (d-i)/2 to our score.if 2*n days have occured,this means if we directly start from repeating op1 and op2 we will get our score as 2*n/2=n and dont need to check for first op2 anymore.As after 2*n days we will always get an answer greater than n which cant be acheived anyhow by the most optimal score of first op2.so after 2*n days our most optimal approach will be to repeat 1st and 2nd operation .

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

      the best reply for this question,finally solved my puzzle

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

      helped me alot. Tks 4 this

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

      I read many comments till now and yours was the one that finally made me understand why 2*n. Thank you for the wonderful explanation.

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

for C , why cant we stop the loop for checking it by brute force just when the count (arr[i]==i) is more than possible(arr[i]<i)?

238793450

giving an WA

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

Can someone share how to solve B using DP?

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

For bonus part of C, you can refer to my solution. Time Complexity: $$$O(n\;log(d)\;log(k) + n\;log(n))$$$.

https://codeforces.net/contest/1917/submission/238793642

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

    hi , for C, if we want to add to score on the first day , isnt it the best option if we have elements with arr[i]==i more than elements with arr[i]<i?, 238793450 if i remove line 38 it will pass , can you help me? thanks

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

C got you

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

I was getting (WA) on test case 26 for Problem C

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

I solved C with going till $$$max(min(n,d),k)$$$ and it passed. You can try to hack, submission id: 238742923

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

https://codeforces.net/contest/1917/submission/238804436 can someone help with reducing the time complexity of this code for the E problem since the time limit exceeds in 2nd test case

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

Problem B. Erase First or Second Letter ***** in second pretest ababa i am getting 10 strings please correct if i am wrong-->

ababa,baba,aaba,bba,aba,ba,aa,ab,b,a

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

    It's not possible to get "b" and "ab" from your list

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

"This array is non-increasing and adding 1 to any of its suffixes keeps it non-increasing ". Isn't performing the first operation will increase its prefixes rather than its suffixes?

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

For Problem C.

How come the answer for this test case is 1 and not 3 ?

  • 3 2 2
  • 0 1 2
  • 1 1

on the first day you will perform operation 1 and increase to make the array as 1 2 3 and on the second day, since all 3 numbers are equal to it's index, we will get answer as 3 and knock everything down to 0.

The answer should be 3 right ? please someone help me out here, I am attaching the link to my code as well : My code

Because in my opinion the answer must be mp[x]-(days-x-1)/2 where mp will store the number of terms with difference i+1-arr[i] if positive.

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

A Silly mistake in C ruined my contest

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

For C, if the waiting days >= 2n + 2, we can get n scores at most by way 1, but we must get n + 1 at least by way 2, so waiting days <= 2n + 1.

»
11 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Great contest, in problem C when I try n times and get WA on test 3, I have a lucky guess 2*n and get AC :)

»
11 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I have a 2n proof for C.

The min ans if we do reset at the begin is floor((d-1)/2).

The max ans if we wait after 2n op is n+floor((d-2n-1)/2)<=n+floor((d-1)/2)-n=floor((d-1)/2).

So we only try waiting at most 2n op.

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

great see by the way !!!

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

Can some explain why number of inversion in $$$[x, 2x, 4x, ..., 2^mx, y, 2y, 4y, ..., 2^my]$$$ depends on $$$\log_{2}\frac{y}{x}$$$?

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

    Is it something like $$$x > y$$$ -> $$$x <= 2^m * y$$$ -> $$$m >= \log_{2}\frac{y}{x}$$$ but how does it affect the entire array ?

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

FOR THOSE WHO ARE CONFUSED WHY AUTHOR CHOOSED 2*N RATHER THAN N SUPPOSE WE ARE GIVEN A TEST CASE

9 12 12

9 1 2 3 4 5 6 7 8

1 1 1 1 1 1 1 1 1 1 1 9

SO FOR FIRST 11 DAYS WE WOULD APPLY OPERATION 1 AND THEN ON LAST DAY WE APPLY OPERATION 2 SO WE GET SCORE OF 8. BUT BY CHANGING ARRAY INTIALLY TO 0 AND APPLYING OPERATION 1 AND AGAIN OPERATION 2 WE GET ANSWER 6.

Now consider if case was for 18 days. We would get 9 by using second technique and 8 using first technique.

I hope it clears.

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

I did D as given in the tutorial, but I counted inversions using merge sort logic and it gave me TLE. Whereas it passed when I counted using fenwick tree logic. Both methods are O(nlogn) right?

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

_LeMur_

In the Solution of "1917D — Yet Another Inversions Problem", there are some mistakes:

  • Incorrect : "By multiplying this number by k" (line 3)
  • Correct : "By multiplying this number by n"

  • Incorrect : if 2x<y<4x, ... = m(m+1)/2 − (m−1) inversions
  • Correct : if 2x<y<4x, ... = m(m+1)/2 − (m) inversions

Similarly, correction needed in "if 4x<y<8x"

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

I love writing complexity O as follows

$$$\displaystyle\mathcal{O}(n)$$$

like flamestorm and mesanu (Writers of Div.4) Did 😄

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

hello everyone, is there a site that tells you how many greedy problems and how many DFS problems have you solved?

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

Could someone provide a comprehensive breakdown of the DP formulation used to address 1917F - Construct Tree?

While I managed to reach a similar conclusion as outlined in the editorial, focusing on finding subsets whose sums and their complements sum to specific values, particularly ignoring the largest element, the critical aspect of formulating the DP remains elusive to me. In my opinion, the editorial lacks sufficient detail in explaining it.

Upon examining tourist's solution 238702895, $$$dp[i][j]$$$ seems to represent whether there exists a subset of sum $$$i$$$ such that ignoring it allows obtaining a sum of $$$j$$$ (the maximum element obviously is never being considered). However, the intuition and the exact process behind filling the DP table are unclear to me.

  • »
    »
    11 months ago, # ^ |
    Rev. 4   Vote: I like it +5 Vote: I do not like it

    Let consider diameter consisting of the vertices $$$v_1$$$, $$$v_2$$$, $$$\ldots$$$, $$$v_k$$$ (let's consider that $$$v_i$$$ and $$$v_{i + 1}$$$ are connected for each $$$1 \leq i \leq k - 1$$$) and some vertex in the diameter (let's denote it $$$v'$$$). Now the state of dp will be the following two lengths: $$$dist(v_1, v')$$$ and $$$dist(v_k, v')$$$, we want to find all possible pairs $$$(x, y)$$$ such that we can construct diameter which will have some vertex $$$v'$$$ on it, such that $$$dist(v_1, v') = x$$$ and $$$dist(v_k, v') = y$$$.

    In tourist's solution, the same thing is done. So he tries to find all pairs $$$(x, y)$$$ without using the length of the largest one. And then just checking if there exists one pair $$$(x', y')$$$ such that both $$$x' + l_n \leq d$$$ and $$$y' + l_n \leq d$$$ (because only in this case we can construct tree, we will create edges for all remaining lengths incident to the same vertex $$$v'$$$ in our case).

    I hope, it's already more clear for you :)

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

      Got it! Your clarification was indeed helpful. The phrase "taking a diameter of length $$$k$$$ and listing its nodes" in the editorial momentarily made me question the solution's direction.

      Framing the DP thinking about any partition of size two for any diameter could potentially simplify comprehension.

      Specifically, identifying the node in between those two partitioned subsets as the one where we connect all non-used edges could add clarity to the explanation. To elaborate further, your example of length $$$k$$$.

      Hence, in understanding the solution, $$$dp(x, y)$$$ represents the possibility of forming two disjoint subsets with specific sums $$$x$$$ and $$$y$$$, utilizing the given set elements (excluding the greatest one).

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

min(2*n+1,d), because the maximum score can only be n. so, floor(d/2)=score ; floor(d/2)=n ; d=2*n+1 ; this means to achieve the max. score we should only check up till min(2*n+1,d) as above this value, the max. score (n) is already explored in the previous days which means exploring above this value is redundant.

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

I ended up writing a solution to C that runs in O(nlogk + klogk) if anyone is curious (Bonus 2). Could also be modified to solve Bonus 1 as well.

Solution: https://codeforces.net/contest/1917/submission/238896629

»
11 months ago, # |
  Vote: I like it +8 Vote: I do not like it

The problem C is so great, love from fst :)

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

Somehow during the contest I thought I must do better than O(n^2) in C, and so I missed it despite figuring out the solution a long time ago. But can someone help me with solving it in better than O(n^2)?

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

_LeMur_

F solution without bitset

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

C is illusion, B is truth, though both are nice problems!

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

problem D is very cool and educational

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

Problem D is terrible. I just modified the inversion counting algorithm and passed. I can't see any reason to use a segment tree.

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

In problem C , Can anyone explain how only in 2*n times we get the break point. I am unable to thnink.

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

Can anyone explain how to solve Problem B? Tutorial isn't helpful.

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

thanks for including a buncha hints so that people who are stuck don't have to get the entire prob revealed.

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

Can anyone please give me the DP solution of Problem B

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

    if you do get the solution please tell i tried creating some approach of dp state but it failed

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

D can be solved without segment trees by first calculating the amount of inversions in between elements of P, then adding num_inversions(Q) * n.

def arith(k, shift):
    k -= abs(shift)
    
    ans = k*(k+1)//2
    if shift < 0:
        shift = -shift
        ans += (k+shift)*(shift)
        ans += shift*k
    
    return ans

def num_inversions(A):
    before = SortedList()
    ans = 0
    for x in A:
        ans += len(before) - before.bisect_left(x)
        before.add(x)
    return ans

def solve():
    n, k = R()
    P = R()
    Q = R()
    
    rem = SortedList(P)
    
    ans = 0
    for x in P:
        rem.remove(x)
        if not rem:
            break
        
        pos = []
        cur = x
        while cur > rem[0]:
            pos.append(rem.bisect_left(cur))
            cur /= 2
        pos.append(0)
        
        for shift, (a, b) in enumerate(itertools.pairwise(pos)):
            ans += arith(k, -shift) * (a-b)    
        
        cur = x
        pos = [rem.bisect_left(cur)]
        while cur < rem[-1]:
            cur *= 2
            pos.append(rem.bisect_left(cur))
            
        for shift, (a, b) in enumerate(itertools.pairwise(pos)):
            ans += arith(k, shift+1) * (b-a)    
          
    ans += num_inversions(Q) * n
    return ans
            
    
    
for _ in range(int(input())):  
    print(solve())