ace5's blog

By ace5, history, 4 weeks ago, translation, In English

Hello, Codeforces!

I and ooaa are excited to invite you to participate in Codeforces Round 922 (Div. 2), which will take place on Jan/30/2024 17:35 (Moscow time).

This round will be rated for participants, whose rating is below 2100. Participants with higher rating can participate unofficially.

You will be given 7-8 problems and 2 hours to solve them. We recommend you to read all the problems. 1 or more interactive problems may occur in the round, so we suggest to read this post.

We would like to thank:

We wish you good luck and high rating!

UPD. Score distribution: $$$500 - 1000 - 1250 - 2000 - 2500 - 3000 - 3250$$$.

UPD2. Congratulations to the winners!

Div. 2

  1. alice_ssoi

  2. JaredGoff

  3. ppltn

  4. sunc_mgu_govno

  5. 1926_yes

Div. 1+2

  1. arvindf232

  2. SSerxhs

  3. alice_ssoi

  4. natofp

  5. JaredGoff

Congratulations to the first solves as well!

UPD3. Editorial.

  • Vote: I like it
  • +575
  • Vote: I do not like it

»
3 weeks ago, # |
  Vote: I like it +114 Vote: I do not like it

As a tester, it's the first time I tested an actual Codeforces round!

»
3 weeks ago, # |
  Vote: I like it +43 Vote: I do not like it

As a tester,the problemset is incredible!Hope you enjoy it :)

»
3 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

As a tester, it’s my first round that I tested, good luck to everyone!

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

As a tester, it is very good round! Good luck!

»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Lets goooo , its time i become pupil

»
3 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

I loved testing the round, problems are of high quality. Good luck!

»
3 weeks ago, # |
  Vote: I like it -30 Vote: I do not like it

5-6 or 7-8 tasks

»
3 weeks ago, # |
Rev. 3   Vote: I like it +10 Vote: I do not like it

Score Distribution?? Edit : Very Balanced Score Distribution according to toughness..

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

Hoping to stay cyan

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

    Why not aim higher and reach blue? :)

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

      I don’t think a plus 150 is possible at 1456 for me, a -56 is very pills

»
3 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

As a tester, I hope you enjoy the round as much as I did.

»
3 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

As not tester, idk

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

2 hours and 7 tasks :O

»
3 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

How to reach expert ?

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

53 points to master. Hope to be a master tonight!

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

As a tester, good luck to everyone! It's the first time i tested a round.

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Score distribution?

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

Let's go =)

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

Hopefully I move to green this time! Excited for this round! Btw which rating should I be to become a problem setter / tester?

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

    You need to achieve twice your rating to be a problem setter.

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

      So basically 2000? Wow alright. What about a tester?

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

        No, you need to achieve master to purpose a contest/problems . Master's rating is 2100 or up, which is just twice your rating.

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

        You can be a tester at any rating, as long some contest setters know you and tell you test.

»
3 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

What will be the score distribution?

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

Best of luck, guys. It's time for me to become a specialist....

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

hope tonight will lucky night and the line graph will reverse!!

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

waiting for that tree based div 2 D since forever

»
3 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

Knowing Anton, I will be very surprised to see a segment tree in any of his problems

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

Lost 50 pt in previous div2. Hope to recover

»
3 weeks ago, # |
  Vote: I like it +13 Vote: I do not like it

are the round writers siblings?

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

All the best guys! Hoping to reach 1300 today.

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

Good luck and We hope good problems' statement to solve that :D

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

ace5 will the score distribution be announced?

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

hope to become CM in this contest. Now only 72 rating.

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

damn it's going to be speedforces according to the score distribution

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

hope reaches pupil in this contest.

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

As a participant, I hope I can get non negative delta again.

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

I will lose pupil at this round :(

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

Hope not to drop down to pupil, spec is fine

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

GLHF

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

they write to read about interactive problems but dont give any, hope to see one today (ofc i wont be able to solve it)

»
3 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Is D that easy? 1000+ solves and I am not able to figure out from where to begin? :(

»
3 weeks ago, # |
Rev. 6   Vote: I like it +1 Vote: I do not like it

I have no idea how to start thinking about D!

Binary search? NO

Two Pointers? NO

DP? NO

Gready? NO

Graphs? NO

Range queries? NO

Math? NO

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

    What is going through your head??? Why are you discussing problems before the end of the contest???

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

    The funniest thing is that D is actually binary search with dp (not sure about the intended solution, but I've solved it this way)

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

      I also solved it that way.

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

      Binary search on answer?

      If so how to check if If the cost can be less than or equal to x? I was stuck at this point

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

        DP, DP[i] is the minimum sum of blocked elements such that you covered all elements from 1 to i, i used segment tree to query minimums.

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

          You can also just use a set instead of a segment tree. Since you only want the min value of dp in some range $$$[j, i]$$$ where $$$j$$$ is non-decreasing as $$$i$$$ increases, just keep the values in the relevant sliding window in the set and check for the minimum value.

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

            I saw your code and I am not getting why you wrote that additional Prefix_sum[n+1]=Prefix_sum[n]

            can you explain why that steps is crucial

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

        Binary search the max sum of the segments. The best answer happens when the max of all segments is close to the sum of blocked elements.

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

        Let's suppose we want to check, is it possible to make $$$cost \le x$$$.
        We must erase some elements such that all remaining subarrays have $$$sum <= x$$$, and the sum of erased elements must be $$$\le x$$$.
        So, we calculate $$$dp[i]$$$ = minimal sum of erased elements such that there is no range with $$$sum > x$$$ in $$$a[0..i]$$$. Then, $$$cost \le x \leftrightarrow dp[n - 1] \le x$$$.

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

          can you also explain how you are finding the value of dp[i]?

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

            My solution is a bit complicated (i believe there is a simpler one), but here it is:

            First, if $$$x \lt max(a)$$$, there is no solution.

            Let's define $$$dp[i][0]$$$ same as $$$dp[i]$$$ above, but with additional constraint: $$$a[i]$$$ is erased. $$$dp[i][1]$$$ is essentialy the opposite: $$$a[i]$$$ is not erased.

            Base cases are: $$$dp[0][0] = a[0], dp[0][1] = 0$$$.
            We calculate $$$dp[i][0]$$$ just as $$$min(dp[i - 1][0], dp[i - 1][1]) + a[i]$$$, since when we erase $$$a[i]$$$, we don't care about the range which ends before, we just know that it's sum $$$\le x$$$.

            Finding $$$dp[i][1]$$$ is another task. We have the following relation:
            $$$ dp[i][1] = min_{j} dp[j][0]$$$, where $$$j \lt i$$$ and $$$\sum_{k=j+1}^{i} a_i \le x$$$, since if we don't erase $$$a[i]$$$, it must be the end of a certain range (e.g. the entire range $$$[j + 1..i]$$$, because it's sum is less or equal than $$$x$$$).

            The least suitable $$$j$$$ can be maintained during dp calculation with two pointers, and the desired value is just segment minimum of $$$dp[j][0]$$$, which can be found with segment tree (or minimum queue). The complexity of calculating such dp is clearly $$$O(n)$$$ or $$$O(n \log n)$$$, depending on data structure you use.

            Code: 244130581

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

              Got it. THanks for the explanation.

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

                why in transition state of dp[i][1] no contribution of dp[j][1]?

                and i did not understand why a[i] must be end of certain range , plz explain this also

                as if a[i] is end element of some segment , then a[i+1] must be blocked element , how we assume this

                Papercut

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

                  When we calculate $$$dp[i]$$$, we consider only the prefix of $$$a$$$, which ends in $$$a[i]$$$. That's why in $$$dp[i][1]$$$ there's always a range which ends in $$$a[i]$$$ (because it's the last element so far, and it is not erased).

                  Why don't we use $$$dp[j][1]$$$? Consider any $$$j$$$ such that $$$\sum_{k=j+1}^{i} a[i]$$$ <= $$$x$$$. If we make transition from $$$dp[j][1]$$$, we continue a range which ends in $$$j$$$ now. But we actually don't know where this range starts, and we don't know, will it's sum be still less or equal than $$$x$$$ after continuing in up to the $$$i$$$.

                  For better understanding, consider the array $$$d$$$ built on a certain sequence of operations, where $$$d[i] = 0$$$ if we erased $$$i$$$th element, and $$$1$$$ otherwise.
                  For example, $$$d = [0, 1, 1, 0, 0, 1, 1]$$$. In terms of $$$d$$$, when we calculate $$$dp[i][1]$$$, we want to choose the start index of a consequtive segment of ones, end of which will be in $$$i$$$. That is, our current transition looks like "choose a zero $$$j$$$, then fill $$$d[j + 1..i]$$$ with ones — once we've created a range of ones, we don't extend it to the right. Maybe now it is more clear, why it suffices.

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

    The first three are actually YES. (And maybe 6th too, depending on your implementation)

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Thanks a lot for this round! Problems are really interesting, especially E with it's idea of solution(just asking questions as in quicksort?).

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

    Can you explain your solution?

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

      Let's understand comparing an element $$$a[i]$$$ to all others for ~$$$3n$$$ questions. first we will ask about this element $$$a[i]$$$ until $$$X$$$ is equal to a[i]. (this will happen since $$$X$$$ goes sideways each time to the number it is being compared to). Now we have $$$X = a[i]$$$. Now to compare $$$a[i]$$$ and $$$a[j]$$$ we just need to ask the question about $$$a[j]$$$ first. This is how we know the answer.($$$a[i] > a[j]$$$ or vice versa). And now ask about $$$a[i]$$$ again (to make $$$X$$$ equal to $$$a[i]$$$ again). We have learned how to compare this element with all the others. But this is the same as quick sorting!!! We are comparing an element and sorting all the smaller ones and all the bigger ones. the number of queries $$$~O(n log n)$$$ which hopefully will pass.

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

    I had thought of a solution, where LIS + LDS of a permutation has certain minimum lower bound. I had tried to implement with that logic, but timed-out.

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

Is D really this easy? or am I just dumb? 1k+ already solved. It's a recursion problem I know that but somehow not able to form the code ughhhhhhhh :D

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

    D is just binary search + dp, maybe there is an easier solution.

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

      thought of binary search and dp but could not implement dp can u share your approach and code

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

      I wasn't able to even think of it. :)

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

    I wouldn't say it's easy, I'm probably biased towards F, but I personally think that D > E > F.

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

Ternary search in D?

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

Guys why my this code is wrong for codeforces question 3 xor distance one

#include <bits/stdc++.h>
using namespace std;

#define ll long long

void solve()
{
    ll a, b, r;
    cin >> a >> b >> r;
    if (r == 0)
    {
        cout << abs(a - b) << endl;
        return;
    }

    vector<int> a1(64, 0), b1(64, 0);
    int greater = 0;
    for (int i = 0; i <=63; i++)
    {
        if ((a & (1LL << i)))
        {
            a1[i]++;
            greater = i;
        }
        if ((b & (1LL << i)))
        {
            b1[i]++;
            greater = i;
        }
    }

    ll min1 = LLONG_MAX;
    for (int i = 0; i <=greater+1; i++)
    {
        for (int j = 0; j <=greater+1; j++)
        {
            ll k = (1LL << i) + (1LL << j);
            ll o = (1LL << i);
            ll p = (1LL << j);
           

            if (k > r)
                break;
            min1 = min(min1, abs((a ^ k) - (b ^ k)));
            min1 = min(min1, abs((a ^ o) - (b ^ o)));
            min1 = min(min1, abs((a ^ p) - (b ^ p)));
            
        }
    }
    if (min1 == LLONG_MAX)
        min1 = 1;
    cout << min1 << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Do we use divide and conquer on E?

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

    I used divide and conquer in E that reminds of quick sort algorithm.

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

    Yep. I did something like quick sort.

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

    Yes, use a recursive function to solve for a set of indices $$$S$$$ and at each stage you pick a random indice $$$i$$$ from $$$S$$$ and make $$$x$$$ equal to the value $$$p_i$$$.

    Then remove $$$i$$$ from $$$S$$$ and split $$$S$$$ two sets : indices with values $$$< p_i$$$ and values $$$> p_i$$$, solve for both these sets recursively.

    This takes $$$O(n \log{n})$$$ queries.

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

      So we just splitting the set of indecies on two partitions on each step, with "pivot" index value remaining their parent. Then we just restore the answer from a tree. Overall, it shoudn't take more than $$$2nlog(n)$$$ requests. Is this your approach?

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

Oh god, I'm so lucky. I freakin stared at monitor looking for overflow errors in D, but couldn't find anything, since locally everything works ok. Decided to go ooga-booga mode and wrote #define int long long, and it freakin passed. After it passed I realized the error. No -Wconversion moment, shame on me

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

    I write every contest with #define int long long.

    Never got MLE/TLE because of that.

»
3 weeks ago, # |
  Vote: I like it +49 Vote: I do not like it

This is a cool contest with a cool problemset ☝☝☝☝

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

How C?

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

is C brute force?

from topbit(r) to 0, if we can flip current bit then copy it and compute abs(a^r — b^r) to determine bit should be flipped or not.

had 10 WA pretest2 still no clue

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

    If you also tried this approach starting from topbit(r) — 1 you would get AC

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

      why this code is giving WA on 2 . i am using the same approach

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

Man, I was struggling with C :( TLE or MLE was troubling me? Can anyone give the solution?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 8   Vote: I like it +1 Vote: I do not like it

    basic steps to solve C problem
    1 -> find maximum(mx) and minimum(mn) among a and b.
    2 -> ignore common bits because they didn't affect the answer.
    3 -> ignore the first missmatch bit of mx(1) and mn(0)
    4 -> traverse from MSB -> LSB whenever this condition reached that bit of mx is set and bit of mn is unset try to transfer this bit form mx to mn(if possible).

    lets take an example
    7 4 3
    7 -> 1 1 1
    4 -> 1 0 0
    ind-> 2 1 0
    mx = 7,mn = 4
    2nd bit -> ignore because both are same
    1st bit -> first time occur 1 in mx 0 in mn
    0th bit -> try to transfer this bit from mx to mn.

    how to transfer ?
    if (curr bit is set in mx and unset in mn) and we set this bit in x, then after xor with x, curr bit of mx will be unset and curr bit of mn will be set.
    so check whenever this(curr bit is set in mx and unset in mn) condition reach and after setting this bit in x if x <= r then set this bit otherwise ignore this and move on next bit.

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

      Bro can you please help me out with this. I've done the exact same thing as you described but I'm getting WA. Submission

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

        your code is giving WA on testcase 7 4 3. I think you are not applying the third step

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

          what was your intuition behind step 3

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

            Think about the above example:-
            7 4 3
            7 -> 1 1 1
            4 -> 1 0 0
            if we don't ignore the second the bit then we have enoung r to shift second and third bit from mx to mn and after shifting both bit diff will remain 3 which is wrong.

            simply we want like this:-

            mx -> 10000000
            mn -> 01111111
            which minmizes the gap between them.

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

              Thanks a lot for your help! I fixed the mistake

»
3 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

Spent 1h+ on C because wrote 1<<i instead of 1ll<<i =(

The problems are really interesting!

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

    Bruh. Just changed my code and now it's passing pretest 1.

    Thanks for sharing orz. not gonna mess it up in the future again ;-;

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    same

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

    Same

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

    live and learn. this will also overflow

    long long x = 0;
    long long y = (!x) << 40;
    
»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

B is similar to ARC149B, and I think they probably have somthing in common.

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Today i solved 3 problems, and enjoy this contest, Thankyou

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

Can someone please explain, how to solve D?

how to manage the states, within the constraints

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

    didn't solve it but i think this logic can work u make x multiple of twos 2, 4, 8, 16 until r with that u fixed the largest digit in binary representation of x then u pick other digits greadly from second most signficent to least and take the max after each choice of x i think this logic would work but feel free to correct me

  • »
    »
    3 weeks ago, # ^ |
    Rev. 3   Vote: I like it +22 Vote: I do not like it

    use binary search to find the answer. For an answer $$$x$$$, the maximum sum of the segments should below or equal $$$x$$$, and the minimum sum of the blocked elements, too. you can find the sum by an $$$O(n^2)$$$ dp, then optimize it with monotonic queue to $$$O(n)$$$, then you solve this problem in $$$O(n\log V)$$$.

    sry, my english is not very good. if ur chinese, you can look look this solution.

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

      Wow, I used the same idea but with segment tree instead of monotonic queue, this is a good observation, thank you!

»
3 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Oh bad I spent 1:10 and almost 100 lines of code C Why are solutions from my room so short...

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

Was the intended solution for F sth like: sort the sons for each node by greatest depth of node in its subtree, then do dfs in that order and maybe get the profit of jumping from each node on the trampoline when you traverse the tree in dfs order, and take the best profits? I did that without having an actual proof or something and got WA on test 27, but maybe I was missing something.

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

    You can solve it with Aliens trick+DP

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    Input:
    9 2
    1 1 2 3 1 3 3 1
    
    Correct Output:
    11
    
    Your Output:
    12
    
    Picture with solution
»
3 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

Please stop create monkey-problems like B

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

Can someone please tell me what's wrong in this submission for C? Spent over an hour but I couldn't find anything :( Submission

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

Thanks to preparing the contest! I enjoeyed A,B,C, and G That's how I solved G

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

I'm just curious. To solve G, I have worked out the cases when n is even. But when n is odd, I have completely no idea.

I wonder if we randomly choose numbers from {-3,-2,-1,1,2,3}, is is possible to "random" out a possible permutation?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +9 Vote: I do not like it

    For even, yes.

    For odd, I've proved that it is possible as {-4, -3, -2, -1, 1, 2, 3, 4}, but I'm not sure if it is possible as {-3, -2, -1, 1, 2, 3}.

    If you don't mind, please refer to my solution. https://codeforces.com/blog/entry/125215? ad#comment-1111742 and I think this main idea can lead you to solve or dissolve the problem.

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

      My solution 244154502 doesn't choose numbers randomly, but they do end up being in the set $$$\{-3,-2,-1,1,2,3\}$$$ for $$$n$$$ not divisible by 4 (in particular, for odd $$$n$$$). You probably can get all numbers in the said set with a slightly different base case.

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

did 1<<i instead of 1ll << i :(

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

can someone suggest how to approach problems like B. Tried proving many greedy ideas but failed

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

    My approach was sorting them with key sum of ai, bi.

»
3 weeks ago, # |
  Vote: I like it -27 Vote: I do not like it

i hate bitmask problems a little bit

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

why is my solution wrong:

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

problem C made life hard

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

My solution for problem D

We will binary search on the answer. Let's call the currrent value we are dealing with is X Let's call dp[i] : Consider position 1 to i, if we take element i, what will be the sum of blocked elements. So :

dp[i] = min(dp[j] + a[i]) and sum from j + 1 to i — 1 must be <= X. We can find the range of j by binary search and get the minimum value by segment tree simutanously. The function check on binary search return true if there is exist an indice i such that : sum(i + 1, n) <= X && dp[i] <= x Hope it make sense

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

hopefully i will reach Specialist

»
3 weeks ago, # |
  Vote: I like it -46 Vote: I do not like it

C is stolen from codechef just expanded the constraints https://www.codechef.com/problems/XORDIF

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

Did someone prove that in B we are getting the best number of inversions by just sorting one of the permutations? That is not that intuitive for me...

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

    Consider index $$$i, j$$$ If $$$a_i < a_j$$$ and $$$b_i < b_j$$$ or $$$a_i > a_j$$$ and $$$b_i > b_j$$$ , then eliminating inversion in $$$a$$$ eliminates inversion in $$$b$$$.

    If $$$a_i < a_j$$$ and $$$b_i > b_j$$$ then in any configuration you must have 1 inversion due to this pair, thus sorting will eliminate all the inversions pairs of type 1 and 1 inversion is anyway there in type 2 for any configuration

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

    Consider two indices, $$$i$$$ and $$$j$$$ and $$$i < j$$$.

    If the order is different in the arrays:

    • $$$a_i < a_j$$$ and $$$b_i > b_j$$$, or
    • $$$a_i > a_j$$$ and $$$b_i < b_j$$$

    this means if it becomes $$$i > j$$$ in the answer array, the sum of inversions will not change, because if the inversion disappears in a, it reappears in b and vice versa.

    However, if both of the arrays contain inversion with indices $$$i$$$ and $$$j$$$, meaning

    • $$$a_i > a_j$$$ and $$$b_i > b_j$$$

    Then if the indices $$$i$$$ and $$$j$$$ become somehow $$$i > j$$$ in the final array, sum of inversions will decrease by 2.

    If:

    • $$$a_i < a_j$$$ and $$$b_i < b_j$$$

    then their order should be preserved, in other words $$$i < j$$$ should hold after reordering.

    so we want to swap preserve all $$$ai < aj$$$ and remove as much $$$ai > aj$$$ as we can. because the array $$$b$$$ doesn't contribute anything (look at the cases). so the operation that accomplishes this is sorting.

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

    you can use bubble sort to understand. Consider what happens when you swap 2 consecutive numbers

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

    Consider optimal answer by score (number ov inversions in $$$a$$$ + number of inversions in $$$b$$$). If there are more than one optimal answers consider one with lexicographically smallest array $$$a$$$.

    $$$Claim:$$$ array $$$a$$$ will be sorted in such an answer.

    $$$Proof$$$ $$$by$$$ $$$contradiction:$$$ assume it's not. Then there is an index $$$i$$$ such that $$$a_i > a_{i+1}$$$. Let's make operation with $$$i$$$ and $$$i+1$$$, i.e $$$swap(a_i, a_{i+1})$$$ and $$$swap(b_i, b_{i+1})$$$. Number of inversions in array $$$a$$$ decreased by one after a swap, and number of inversions in array $$$b$$$ increased by no more than one, since $$$b_i, b_{i+1}$$$ is the only pair of elements whose relative order was changed in $$$b$$$. Therefore number of inversions in $$$a$$$ + $$$b$$$ $$$\bf{not}$$$ $$$\bf{increased}$$$ after a swap, but array $$$a$$$ became lexicographically smaller. But we chose array $$$a$$$ as lexicographically smallest $$$\to$$$ contradiction, array $$$a$$$ is sorted in optimal answer.

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

      Can you please explain again from 4th line and if possible please explain it with an example

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

Can someone explain the statement of problem B, please?

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

    find the Permutation of both the arrays such that the 'Sum of no of Inversions of a and b' is minimized. When you reorder one array the other array gets reordered the same way.

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

Is there a non-random solution for E?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +32 Vote: I do not like it

    Yes — you can do parallel binary search to find all values in worst case $$$O(n \log n)$$$ queries. My code (244112756) is very messy and might FST; I have a proven, more efficient version that I haven't yet submitted and I'll clean up the code. I'll probably post a comment on the editorial about my solution with a proof of the number of queries.

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

    Firstly you can request X=1 (I think by 2n queries)

    Secondly supporse you have $$$k$$$ indices of consecutive numbers $$$L \ldots R$$$ ($$$R-L+1=k$$$). Find position of $$$m=(L+R)/2$$$ (likely it can be done by $$$O(R-L)$$$ queries). Then split indices to two groups and solve recursively.

    Start call from $$$L=1$$$, $$$R=n$$$, indices = $$$1 \ldots n$$$.

»
3 weeks ago, # |
Rev. 3   Vote: I like it -52 Vote: I do not like it

Whats the issue in this code for C? Working in C++14 compiler on TC1 but not in C++17

`

#include<bits/stdc++.h>
#define ll long long int
#define fr first
#define sd second

define pb push_back

using namespace std;

ll modpow(ll a, ll n)
{
    ll m=1e9+7;
    if(n==0)
        return 1;
    ll y=modpow(a,n/2)%m;
    if(n%2==0)
        return (y*y)%m;
    return (((y*y)%m)*a)%m;
}

ll mod_inv(ll x)
{
    ll m=1e9+7;
    return modpow(x,m-2);
}

ll fact[300005];
ll nCr(ll n, ll r)
{
    ll m=1e9+7;
    return ( fact[n]*mod_inv( (fact[r]*fact[n-r])%m ) )%m;
}

ll pow1(ll a, ll n)
{
    if(n==0)
        return 1;
    ll y=pow1(a,n/2);
    if(n%2==0)
        return (y*y);
    return (y*y*a);
}

ll hcf(ll a, ll b)
{
    if(a==0)
        return b;
    return hcf(b%a, a);
}

bool isPrime(ll x)
{
    for(ll i=2;i*i<=x;i++)
    {
        if(x%i==0)
            return false;
    }
    return true;
}

int digits(int x)
{
    return (int)log10(x)+1;
}

int main()
{
    //ll lmt=1e18;

    ll m=1e9+7;
    /*
    fact[0]=1;
    for(ll i=1;i<300005;i++)
    {
        fact[i]=fact[i-1]*i;
        fact[i]%=m;
    }
    */

    //cout<<"Case #"<<(++cas)<<": "<<()<<endl;
    //std::cout << std::fixed;
    //std::cout << std::setprecision(6);

    int t=1;
    scanf("%d",&t);
    int cas=0;
    while(t--)
    {
        ll a, b, r;
        cin>>a>>b>>r;
        ll xor1=(a^b);
        ll msb=log2(xor1*1L);
        if( (b&(1L<<msb)) != 0L ){
            swap(a, b);
        }
        //cout<<msb<<endl;
        ll ans=0L;
        for(ll i=0;i<msb;i++){
            if( (xor1&(1L<<i)) != 0L){
                if( (b&(1L<<i)) == 0L){
                    ans+=(1L<<i);
                }
            }
        }
        if(ans<=r){
            cout<<abs((a^ans)-(b^ans))<<endl;
        } else {
            int f=0;
            ll ans1=0L;
            for(ll i=msb-1L;i>=0L;i--){
                if(f==1){
                    if( (ans&(1L<<i)) != 0L){
                        ans1=((ans1*1L)|(1L<<i));
                    }
                    continue;
                }
                if( (ans&(1L<<i)) == 0L){
                    if( (r&(1L<<i)) != 0L){
                        f=1;
                    }
                }
                if( (ans&(1L<<i)) != 0L){
                    if( (r&(1L<<i)) != 0L){
                        ans1+=(1L<<i);
                    }
                }
            }
            cout<<abs((a^ans1)-(b^ans1))<<endl;
        }
    }
    return 0;
}

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Where is the Editorial?

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

Is Carrot extension not working?

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

How to solve E?

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

My B solution uses just bubble sort, but I get TLE anyways. Could someone give me some hint?

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

    Bubble sort is O(n^2) which is too slow for the bounds which are 10^5. You need a faster sorting algorithm. If you can use the built-in sort for your language that should be fine.

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

    Just make a pair array where first element is a[i] and second is b[i] and sort this according to first element. the proof of correctness you can do by yourself.

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

I spent a lot of time on B. I think it's too difficult for people without prior knowledge like me. I don’t know how to prove the correctness of my ideas. ;(

»
3 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

My E solution got TLE for java. Had to use chat gpt to convert to c++. Time constraints too tight?

»
3 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Is there a proof for randomised solution for E?

»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

I think E is too tight. I got TLE. However, someone got AC using same idea (maybe just a different select point). too sad~.

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

    Looking at the output for the failed test, it seems that it was actually a WA due to exceeding the query limit, but since the program failed to handle the WA input and exit, it was judged a TLE.

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

Next contest coming in 3 weeks? Why is it taking so long? or am I missing something.

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

Can someone explain me why this is TLE ?Code

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

Intuition for B?

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

    say You have Two arrays as [ a1,a2,a3...,an ] and [ b1,b2,b3..,bn ]. say total number of inversions are N ( N>=0 ). Now say there are two indices in array a i,j such that i<j and a[i] >a[j] . Now what are the corresponding possibilities in array b? There are exactly 3. 1. b[i]<b[j] 2. b[i]==b[j] 3. b[i] >b[j]

    Now say we were to swap i and j in both the arrays. for array a total inversions decrease by 1,because now a[i]<a[j] as we have swapped them. what about array b? if if was case 1. as b[i] was < b[j] now we have swapped them, we gain +1 inversion. so total effect N-1+1 == N 2. as b[i] was equal to b[j] we have swapped we gain none but from a we decrease 1 so now total N-1 3. as b[i] was > b[j] and we have swapped we have decreased one more. so total N-1-1 == N-2.

    in any case by swapping an inversion in any array we either decrease the total by 0,1 or 2. so our best bet is to sort one of them as this never increases the total number, in the worst case remains the same. so just sort any one of them and print the corresponding other as was.

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

Top5 are always smurfs :)

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

Is there no hacking phase?

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

    There is no hacking phase in regular div2 rounds.

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

      Ok. I didn't know. Thanks for letting me know! :)

»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

rating updates ?

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

Thanks, it was a very beautiful contest

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

"Submissions have been scheduled for rejudge on the next testset." This notification came after the system tests were over. What does this mean?

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

Can anyone explain the intuition behind why, for problem C, you need to avoid swapping the bits between a and b until the first time the bits differ?

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

    Because you don't accomplish anything by adding that bit in x. Example: a = 1, b = 1, a⊕0 — b⊕0 = a⊕1 — b⊕1.

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

      @blaze Right, but I'm trying to figure out why this is the case. For the case of 9 and 6, for example, you can notice setting X to 1001 rather than 0001 (or just 1) ends up making it so that, if a > b before this, a < b afterward. I think this is the key insight, but I'm trying to figure out why this is only the case until the first bit differs.

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

        Don't look at the numbers a and b as "numbers", separate them bit by bit and look at them that way. You can assume that a > b because $$$|a \oplus x - b \oplus x| = |b \oplus x - a \oplus x|$$$. You don't want to toggle unnecessary bits in x so that it can be <= r. During subtraction of $$$a \oplus x - b \oplus x$$$ notice that the bits that are the same don't affect the result, xoring them with something won't make those bits different.

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

          Thanks for the reply but I don't think we are talking about the same thing. I understand the bits that are the same between a and b should not have anything xor'd with them. But in correct solution, you skip not only the positions where a and b have the same bit, but also the first position where a and b's bits differ, even if that position has a 1 bit for a and a 0 bit for b. That is the part I am confused on.

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

            we skip first bit because if we swap the MSB, we would have to add that bit to our cost, i.e., r, instead we let it be as it is. best explained with an example:

            suppose these are two numbers in binary:

            110011 001010

            now, in this case we would avoid swapping the first bit because it alone costs 2^5, which would be higher than any cost we would incur to swap subsequent bits however we like. suppose r = 100000 (in binary) in this case.

            then, if had we swapped the first bit, we could not swap any further bit and new numbers would be 010011 and 101010

            notice the third bit from the left would have been better in first number but we don't have any r left but, if we did not swap the first bit, we could do anything later on in this case because r is sufficient.

            if any doubt ask me.

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

              Thanks for your help! I understand if you swap the MSB it comprises the whole cost, but I'm having trouble understanding why this means we shouldn't use it. After all, it makes the biggest change in the numbers, and thus brings them closer together, right?

              However, here the correct X to use is 010001. If instead we used 100000, which is what you get if you don't skip the MSB, you end up subtracting too much from the bigger number and adding too much to the smaller number, which results in not getting an optimal solution.

              What I am trying to understand is, why is this only a problem for the MSB? Why do we always avoid swapping only for the MSB, but we can always do the swaps for any other bit?

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

                Because Suppose n has msb, now the later bits, we are trying to push to m to make n-m as smaller as possible. As m increases and n-m decreases.

                we are greedily avoiding first msb in case a solution existed in which we could switch the first msb then later on we would get the best answer, suppose like this 2 numbers 1111, 0000 and r is 1000 in this case we can switch msb to get best answer but its clearly possible avoid msb and switch rest bits in lesser cost.

                Did i answer your question? If not, i dont think i understand your doubt

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

                  Yes I think this makes sense, thanks for explaining!

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

            approach is like this ->> (without loss of generality, assume n>m) avoid swapping first bit, and later on try to get significant bits to m. since, n>m, first bit will be in n and getting bits to m would make n-m smaller and smaller.

»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

This contest be like:

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

My Solution for problem D https://codeforces.com/contest/1918/submission/244169954

#include <bits/stdc++.h>
using namespace std;

// shortcuts
#define M 1000000007
#define ll long long
#define lld long double
#define vi vector<int>
#define vll vector<ll>
#define mx 1e18
#define mn INT_MIN

// ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
ll find_min(vector<ll> &segment , ll q_left , ll q_right , ll left , ll right , ll segPos)
{
    if(q_left <= left && right <= q_right) return segment[segPos];
    if(q_left > right || left > q_right) return mx;

    ll ans = mx;
    ll mid = (left + right) / 2;
    ans = min(ans , find_min(segment, q_left, q_right , left , mid , 2*segPos+1));
    ans = min(ans , find_min(segment, q_left, q_right , mid+1 ,right , 2*segPos+2));
    return ans;
}

void update(vector<ll> &segment , ll left , ll right , ll segPos , ll idx , ll val)
{
    if(left == right) 
    {
        segment[segPos] = val;
        return;
    }

    ll mid = (left + right) / 2;
    if(idx <= mid) update(segment , left , mid , 2*segPos+1 , idx , val);
    else update(segment , mid+1 , right , 2*segPos+2 , idx , val);
    segment[segPos] = min(segment[2*segPos+1] , segment[2*segPos+2]);
}

ll ok(vector<ll> &vt , vector<ll> &prefix , ll n , ll mid)
{
    vector<ll> dp(n+1 , 0);
    vector<ll> segment(4*n+10 , mx);
    update(segment , 0 , n , 0 , 0 , 0);
    for(ll i = 1;i<=n;i++)
    {
        ll low = 1 , high = i , left = i;
        while(low <= high)
        {
            ll idx = (low + high)/2;
            if(prefix[i]-prefix[idx-1]-vt[i] <= mid)
            {
                left = idx;
                high = idx-1;
            }
            else low = idx+1;
        }

        dp[i] = vt[i]+find_min(segment , left-1 , i , 0 , n , 0);
        update(segment , 0 , n , 0 , i , dp[i]);
    }

    // cout << mid << endl;
    // for(ll i = 0;i<=n;i++) cout << dp[i] << " "; cout << endl;

    for(ll i = 1;i<=n;i++)
    {
        if(dp[i] <= mid && prefix[n]-prefix[i] <= mid) return true;
    }
    return false;
}
void ok()
{
    ll n;
    cin >> n;
    vector<ll> vt(n+1);
    vector<ll> prefix(n+1);
    for(ll i = 1; i <= n; i++) cin >> vt[i];
    for(ll i = 1; i <= n; i++) prefix[i] = prefix[i-1] + vt[i];

    // 1. apply binary search on minimum cost of an array. 
    // 2. use prefix sum to calculate the sum of element in a range.
    // 3. For each iteration of binary search make a dp table, let says currently we are checking for value mid.
    // 4. Now dp[i] = minimum sum of all blocked element from subarray [1...i], when ith element is blocked 
    // 5. Transition dp[i] = min(vt[i] + dp[j]) for all j such that sum(vt[j+1] + ... + vt[i]) <= mid. Use Binary search to find such value of j.
    // 6. Use segment tree to find min(vt[i] + dp[j])

    ll low = 0 , high = prefix[n] , ans = prefix[n];
    while(low <= high)
    {
        ll mid = (low+high) / 2;
        if(ok(vt , prefix , n , mid))
        {
            ans = mid;
            high = mid-1;
        }
        else low = mid+1;
    }
    cout << ans << endl;
}

int main()
{
    // Shubham Kumar Jha
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

#ifndef ONLINE_JUDGE
    freopen("zinput.txt", "r", stdin);
    freopen("zoutput.txt", "w", stdout);
#endif

    ll t = 1;
    cin >> t;
    for(ll i = 1;i<=t;i++)
    {
        ok();
    }
    return 0;
}
»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Thank you for fast Editorial

»
3 weeks ago, # |
  Vote: I like it +72 Vote: I do not like it

great problemset, definitely one of the best div2's of last months!

»
3 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

D problem (Blocking Elements) Video Editorial : https://youtu.be/ZfqWLxBG-Ow?si=WxQOHwg_hdelqH4C

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

everything went as planned, I will farm next div 4

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

i had solved 1 problem and it is accepted but why my rating get minused?

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

    Based on your current rating, you are expected to have a better rank now to get a positive delta. i.e. Solve B to climb up in the rank-list.

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

I like this round, especially the strong input/output examples. Good round.

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

I was using ideone for my few last contests, I did not knew that someone else can see my code from there, I am really sorry for this mistake. I will take care of this from next,

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

Hey! This was indeed a very educational type of round, thanks to the contest problem-setters. I just managed to curate some well-elaborated problem discussion sessions covering problems A to D https://youtube.com/playlist?list=PLxHsiA8Ewxn24IVOuNjADlvah8d_eIXuW&si=IbM9faXnzHYP7uSH They should be helpful for beginners and many Div2 participants, especially problem D. Excited to see the community grow together!

PS: Didn't get time till now to work on the problems E to G, but would be glad to have discussions on them on any forum!

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

W round