ace5's blog

By ace5, history, 9 months 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

»
9 months 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!

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

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

»
9 months 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!

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

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

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

Lets goooo , its time i become pupil

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

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

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

5-6 or 7-8 tasks

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

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

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

Hoping to stay cyan

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

    Why not aim higher and reach blue? :)

    • »
      »
      »
      9 months 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

»
9 months 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.

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

As not tester, idk

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

2 hours and 7 tasks :O

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

How to reach expert ?

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

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

»
9 months 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.

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

Score distribution?

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

Let's go =)

»
9 months 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?

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

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

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

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

      • »
        »
        »
        »
        9 months 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.

      • »
        »
        »
        »
        9 months 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.

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

What will be the score distribution?

»
9 months 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....

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

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

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

waiting for that tree based div 2 D since forever

»
9 months 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

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

Lost 50 pt in previous div2. Hope to recover

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

are the round writers siblings?

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

All the best guys! Hoping to reach 1300 today.

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

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

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

ace5 will the score distribution be announced?

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

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

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

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

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

hope reaches pupil in this contest.

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

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

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

I will lose pupil at this round :(

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

Hope not to drop down to pupil, spec is fine

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

GLHF

»
9 months 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)

»
9 months 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? :(

»
9 months 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

  • »
    »
    9 months 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???

  • »
    »
    9 months 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)

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

      I also solved it that way.

    • »
      »
      »
      9 months 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

      • »
        »
        »
        »
        9 months 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.

        • »
          »
          »
          »
          »
          9 months 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.

          • »
            »
            »
            »
            »
            »
            9 months 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

      • »
        »
        »
        »
        9 months 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.

      • »
        »
        »
        »
        9 months 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$$$.

        • »
          »
          »
          »
          »
          9 months 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]?

          • »
            »
            »
            »
            »
            »
            9 months 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

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

              Got it. THanks for the explanation.

              • »
                »
                »
                »
                »
                »
                »
                »
                9 months 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

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  9 months 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.

  • »
    »
    9 months 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)

»
9 months 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?).

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

    Can you explain your solution?

    • »
      »
      »
      9 months 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.

  • »
    »
    9 months 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.

»
9 months 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

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

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

    • »
      »
      »
      9 months 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

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

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

  • »
    »
    9 months 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.

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

Ternary search in D?

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

Do we use divide and conquer on E?

  • »
    »
    9 months 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.

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

    Yep. I did something like quick sort.

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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?

»
9 months 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

  • »
    »
    9 months 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.

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

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

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

How C?

»
9 months 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

  • »
    »
    9 months 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

    • »
      »
      »
      9 months 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

»
9 months 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?

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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

      • »
        »
        »
        »
        9 months 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

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

          what was your intuition behind step 3

          • »
            »
            »
            »
            »
            »
            9 months 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.

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

              Thanks a lot for your help! I fixed the mistake

»
9 months 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!

  • »
    »
    9 months 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 ;-;

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

    same

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

    Same

  • »
    »
    9 months 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;
    
»
9 months 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.

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

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

»
9 months 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

  • »
    »
    9 months 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

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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!

»
9 months 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...

»
9 months 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.

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

    You can solve it with Aliens trick+DP

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

Please stop create monkey-problems like B

»
9 months 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

»
9 months 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
»
9 months 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?

  • »
    »
    9 months 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.net/blog/entry/125215? ad#comment-1111742 and I think this main idea can lead you to solve or dissolve the problem.

    • »
      »
      »
      9 months 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.

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

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

»
9 months 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

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

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

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

i hate bitmask problems a little bit

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

why is my solution wrong:

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

problem C made life hard

»
9 months 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

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

hopefully i will reach Specialist

»
9 months 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

»
9 months 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...

  • »
    »
    9 months 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

  • »
    »
    9 months 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.

  • »
    »
    9 months 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

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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

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

Can someone explain the statement of problem B, please?

  • »
    »
    9 months 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.

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

Is there a non-random solution for E?

  • »
    »
    9 months 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.

  • »
    »
    9 months 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$$$.

»
9 months 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;
}

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

Where is the Editorial?

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

Is Carrot extension not working?

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

How to solve E?

»
9 months 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?

  • »
    »
    9 months 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.

  • »
    »
    9 months 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.

»
9 months 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. ;(

»
9 months 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?

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

Is there a proof for randomised solution for E?

»
9 months 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~.

  • »
    »
    9 months 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.

»
9 months 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.

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

Can someone explain me why this is TLE ?Code

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

Intuition for B?

  • »
    »
    9 months 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.

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

Top5 are always smurfs :)

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

Is there no hacking phase?

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

    There is no hacking phase in regular div2 rounds.

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

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

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

rating updates ?

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

Thanks, it was a very beautiful contest

»
9 months 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?

»
9 months 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?

  • »
    »
    9 months 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.

    • »
      »
      »
      9 months 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.

      • »
        »
        »
        »
        9 months 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.

        • »
          »
          »
          »
          »
          9 months 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.

          • »
            »
            »
            »
            »
            »
            9 months 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.

            • »
              »
              »
              »
              »
              »
              »
              9 months 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?

              • »
                »
                »
                »
                »
                »
                »
                »
                9 months 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

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

                  Yes I think this makes sense, thanks for explaining!

          • »
            »
            »
            »
            »
            »
            9 months 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.

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

This contest be like:

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

My Solution for problem D https://codeforces.net/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;
}
»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Thank you for fast Editorial

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

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

»
9 months 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

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

    Why the downvotes? Did I write something wrong?

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

      You didn't write anything wrong, but you shouldn't to editorials to problems you didn't solve during the contest.

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

everything went as planned, I will farm next div 4

»
9 months 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?

  • »
    »
    9 months 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.

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

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

»
9 months 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,

»
9 months 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!

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

W round