PoPularPlusPlus's blog

Codeforces Round #882 (Div 2)
By PoPularPlusPlus, history, 16 months ago, In English

Hi Codeforces!

I welcome everyone to participate in Codeforces Round 882 (Div. 2) which will start on Jul/06/2023 17:35 (Moscow time).

The round will be rated for participants of Division 2 with a rating lower than 2100. I would encourage Division 1 participants to participate in the round unofficially.

You will be given 6 problems and 2 hours to solve them. One of the problem is interactive, so please read guide for interactive problems if you are not familiar with it.

the theme of the contest is

All the problems are prepared by me and StArChAn.

We would like to thank:

Also, the editorial video for all the problems will be available on my channel right after the contest ends

All the best everyone!! Eager to see you going All Around The World and being Unstoppable in climbing the ranklist.

UPD: Scoring distribution — $$$500 - 1000 - 1500 - 2000 - 2750 - 3000.$$$

UPD: For video editorial of the problems, you can find it here

UPD: Editorial is out.

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

Comments Comments (250)
| Write comment?
»
16 months ago, # |
  Vote: I like it +51 Vote: I do not like it

Finally a contest after almost a week!

→ Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it -63 Vote: I do not like it

    Worst contest I have ever seen!..

    The queue at the beginning and the statement of the problem D was awful.

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it -16 Vote: I do not like it

      What happened with me was when I submitted a solution it showed Runtime error on pretest 1 where as my IDE was not showing any errors. After that when I randomly commented a line which was not useful it started showing TLE. Also for another problem it was showing wrong length of output where as my output was a single int.

      → Reply
    • »
      »
      »
      16 months ago, # ^ |
      ← Rev. 2   Vote: I like it +53 Vote: I do not like it

      -Deleted-
      Just wanted to deliver the idea that authors try their bests ,so we shouldn't comment "Worst contest ever" every single contest

      → Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it -100 Vote: I do not like it

    Solution to C

    All that matters is how fast you can google. HATE SUCH CONTESTS,

    Message for Authors — At least make some new problems instead of useless & BULLSHIT stories. Codeforces pays you for a reason.

    → Reply
    • »
      »
      »
      16 months ago, # ^ |
      ← Rev. 3   Vote: I like it +5 Vote: I do not like it

      If you used your head you would realize that due to the small constraints that you can brute force instead of googling an algorithm. Not only did you reveal you are not very good, but also that you were cheating

      → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
        ← Rev. 2   Vote: I like it +29 Vote: I do not like it

        Googling isn't cheating; it's allowed in the CF rules

        → Reply
      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it -7 Vote: I do not like it

        yeah and that brute force TLE's for some people because of the trash constraints , exact same sol as my friends and im the only one TLEeing

        → Reply
        • »
          »
          »
          »
          »
          16 months ago, # ^ |
          ← Rev. 2   Vote: I like it +13 Vote: I do not like it

          you got TLE because your implementation is sucK man (O(T * MAXN)). Don't blame.

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

            nah i meant the very first submission its clearly implemented the same way with my friends and they got ac there is the sum of n thing wdym T

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

        Dear friend I got to know after contest that the solutions are available as it is on internet. I'm not like you who starts googling, after trying for 5 minutes. Also, No offence to setters, The questions were good but The language framing was a piece of shit rather shittiest piece of shit, That's why I was so frustrated. Also doesn't matter if you downvote it 100 or 1000, THAT'S WHAT IT WAS

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

          I do not know what I did to suggest to you I was googling. The statements were good and I read them without trouble. In fact they were fairly typical statements. Maybe you can improve reading.

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

      I guess it's hard to create an easy problem that wasn't already on CF or anywhere else just because every contest has a lot of easy tasks. I think you might be able to google A, B is just another "go through array while maintaining some values"

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

        Creating d2B harder than creating d1F.

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

    All these submissions have a same function for problem C 212411474 212408231 212415822 212444362 212445049 some of them have removed comments otherwise the functions and structs are same.

    → Reply
»
16 months ago, # |
  Vote: I like it +41 Vote: I do not like it

I went nowhere and did based testing.

→ Reply
»
16 months ago, # |
  Vote: I like it +22 Vote: I do not like it

I went to Antarctica and did kinesthetic testing.

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

    Wishing for the ratings in Antarctica to stay afloat and not sink.

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

I went to Narnia and did soulful testing.

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it -6 Vote: I do not like it

--Deleted--

→ Reply
»
16 months ago, # |
  Vote: I like it +18 Vote: I do not like it

Is one of the problem named Treelike?

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

since this is being set by indians my guess is there would be problems on graph and bits.

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is one of the anime Vinland saga?

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

As a fan of [user:darrkcyan], I recommend you to participate this contest:))

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Finally I'm going to be rated!!

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

Let me guess, is the anime Horimiya?

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

    No, it's obviously going to be "Do You Love Your Mom and Her Two-Hit Muti-target Attacks?"

    → Reply
»
16 months ago, # |
  Vote: I like it +1 Vote: I do not like it

first time seeing a grey tester! hope the contest is good.

→ Reply
»
16 months ago, # |
  Vote: I like it +4 Vote: I do not like it

I hope one of the problems is related to One Peice .

→ Reply
»
16 months ago, # |
  Vote: I like it +43 Vote: I do not like it

I went to Alaska and did master level testing.

→ Reply
»
16 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Atekichan Finally your time to shine!!

→ Reply
»
16 months ago, # |
  Vote: I like it -37 Vote: I do not like it

i have a bad feeling about this round...

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

    Nothing's too hard if you are prepared and god willing.

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

      plus, what are you so worried about. Non-rated people like me will always have their rating increase, cause your rating can't go down if it's your first rated competition. :thinkies:

      → Reply
»
16 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Enjoy every competition

→ Reply
»
16 months ago, # |
← Rev. 4   Vote: I like it +11 Vote: I do not like it

Anime Prediction List :

0) DeathNote, (Involves mental games )

1) Code Geass ( Considering the theme is Coding, this one fits ),

2) PsychoPass

3) Naruto ( So many fans )

4) Black Clover ( So Many fans )

5) Demon Slayer,

6) One Piece,

Keep the list going :D .

→ Reply
»
16 months ago, # |
  Vote: I like it +23 Vote: I do not like it

I went to Antartica and did gawky testing.

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is anyone left for taking part in the contest?

→ Reply
»
16 months ago, # |
  Vote: I like it +60 Vote: I do not like it

As a tester,tasks are nice and wish everyone good luck (〃•ω‹〃)♡

→ Reply
»
16 months ago, # |
  Vote: I like it +6 Vote: I do not like it

score distribution when?

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I wonder why MikeMirzayanov has more contribution than anyone but doesn't show up on the leaderboard for Top contributors...

→ Reply
»
16 months ago, # |
  Vote: I like it +23 Vote: I do not like it

Indian setters and testers means contest with bits questions :)

→ Reply
»
16 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Its time to purple again :)

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope to get to CM!

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

Balanced score distribution

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I will become specialist :)

→ Reply
»
16 months ago, # |
  Vote: I like it -6 Vote: I do not like it

My unmatched perspicacity coupled with my sheer indefatigability makes me a feared opponent in any realm of human endeavor.

→ Reply
»
16 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Huge gap from D to E. Interesting!

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

    I'm not sure, but he mentioned scoring distribution instead of rating, so it's difficult to determine the gap between D and E, right?

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

      Yeah I guess that, anyway, enjoy the problems ^^

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

        I'm sorry, you are right. It seems that a high contribution can indeed indicate some issues.

        → Reply
»
16 months ago, # |
  Vote: I like it +24 Vote: I do not like it

Please remember to add a space after +!? in interactive questions.

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

excited to participate!

→ Reply
»
16 months ago, # |
  Vote: I like it +12 Vote: I do not like it

There seems to be some issue with the queue. Solutions submitted later have been judged, but the ones earlier in queue are pending.

→ Reply
»
16 months ago, # |
  Vote: I like it +24 Vote: I do not like it

You thought it was a programming contest but It was I, Dio

→ Reply
»
16 months ago, # |
  Vote: I like it +10 Vote: I do not like it

W Contest

Spoiler
→ Reply
»
16 months ago, # |
  Vote: I like it +6 Vote: I do not like it

there are few bitwise operations today thx

→ Reply
»
16 months ago, # |
  Vote: I like it +32 Vote: I do not like it

Bitwiseforces

→ Reply
»
16 months ago, # |
  Vote: I like it -8 Vote: I do not like it

this contest very very very hard

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

just keep in mind we don't have time to keep searching for your ANIME things :(

→ Reply
»
16 months ago, # |
  Vote: I like it +18 Vote: I do not like it

GFGforces

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

    As the contest ends

    here is the link : https://www.geeksforgeeks.org/find-the-maximum-subarray-xor-in-a-given-array/

    Should all setters try so that answer should not pop up if you search "MAXIMUM XOR SUBARRAY".

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

      Don't know if other problems had the similarity. But for problem C, this isn't a fair criticism.

      Because for this problem C, figuring out we need to find the maximum XOR subarray is the main part. After that, One doesn't need to use any Trie or anything. Constraints on values are so small, one can check for each position for all possible previous prefix sums till now.

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

    stop using your alt-account whining about false things

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

how to come up with the idea for the problem c for the first time if you have not used(implementation) trie before and is there any other solution?

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

    I dont know, in my room there are like 5 solutions with same structure "Trie". I begin with C, and send it in 5 minutes after. Just use that numbers are small:) You can see my easy submission

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

    You don't need trie

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

    using the two properties of xor :

    a^0 = a

    a^a = 0

    hence we can choose any subarray we want by choosing first r to m then l to m , hence the problem becomes finding the subarray with maximum xor

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

      yep but didnt know how to calculate it in O(N) without trie

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

        It can be easily solved in O(2 ^ 8 * n) which passed tests

        Just support all possible xor of segments ending in i'th element. Because a[i] < 2^8 then xor also < 2^8.

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

    Any value which you will append is going to be xor of any subarray. And you can append any xor subrray in 2 operation. So you just need to find maximum xor of all subarrays

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

    If you can find the pigeonhole principle in the prefix XOR values, then you will have to look forward to only 256 indices for an index i. So, it can be solved in O(256n)

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

    I think , the best way to deal with such questions is to , to do the operations specified in the questions by yourself. Like if you randomly do some operations you start getting hints about the problem and patterns emerge . That's atleast the way I do for such problems . Hope it helps

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

    You may notice that due to constraints number of different prefix-xores is small (not greater than 257), so if you sort them and apply the 'unique' operation, you can use brute-force to find a maximum xor of all pairs.

    → Reply
»
16 months ago, # |
  Vote: I like it +10 Vote: I do not like it

LtoR forces bitwiseForces SpeedForces jojoforces

→ Reply
»
16 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Can we solve F like that -: We have to find the smallest subarray with or greater than v. Now if we fix the start index say l, then there can be at most 32 index r, such that or of subarray a[l..r]changes. So we store all these 32 indexes for all l from 1 to n and use prefix minimum for the query?

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

In problem D, second sample, query 2, why is the answer 3? After flipping a3, a5, the only ones which are in t(s) are a3 and a7, ans <= 2. What am I missing?

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

    I think the answer is 3 because:

    • Swap pos1 (1) with pos2 (0)

    • Swap pos4 (1) with pos5 (0)

    • Swap pos6 (0) with pos7 (1)

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

    Dude I swear I wasted 30-50 mins because of this similar doubt and was unable to solve D fast enough. But the thing is that there are some 1s which are not in t(s) and we can use them

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

      Even I didn't realise that we can use the 1s that are not in t(s), I realised it after contest :(

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

I bricked C hard. I could not for the life of me figure it out until like the end of the contest. :/

→ Reply
»
16 months ago, # |
  Vote: I like it +67 Vote: I do not like it

Anyone else misread D's statement, thinking we swap elements in T(s) instead? :( wasted an hour

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the idea for the solution to Problem F? I have gotten a bunch of insights but haven't been able to formulate the complete solution.

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I liked the ideas of the problems, but my request to you, since there are many religious people that love to participate in CF contests, is to not use phrases like "The Man who became a God" in the problem title or description. Thank you.

→ Reply
»
16 months ago, # |
  Vote: I like it +30 Vote: I do not like it

What is this obsession with Bitwise operators and GFG ? Make some original problems.

→ Reply
»
16 months ago, # |
  Vote: I like it +3 Vote: I do not like it

As I understand it, in problem C, you need to find a segment with the maximum XOR. Is there any well-known way to do this? Two pointers don't work here.

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

    212397289

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

    It uses Tries.

    GFG Article for the solution

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

      I see, that too many ppl just copy all code there. Seems all of them can get "cheat plag".

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

        Nope. You can copy code published before the contest has started

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

          Of course you can. But the plag system is now a human, if like 1000 solutions are really the same(with the same comments:)), they can be plag. I am pretty sure, that anyone will not unplag such 1000 ppl:)

          → Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 3   Vote: I like it +15 Vote: I do not like it

    A solution without tries- First find the prefix xor array. for the given constraints on ai, you could just iterate the prefix xor array from left to right and maintain a 256 sized boolean array which stores whether a certain number has been seen before in the iteration or not. Hence at every iteration just iterate over this boolean array, if a number has been seen then just xor that number and the current value of prefix sum and take max of it with the current best answer!

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

      This works with ai<=2^63. This is maximum xor pair but it can easily be extended to maximum xor subarray.

      Code
      → Reply
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Yup I did this. I used a set to store all the visited prefix XOR's tho

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

        Oh, I was a bit paranoid about this approach cuz this can in the worst case add a factor of log(2^8) to the time complexity

        → Reply
»
16 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Runtime error on test 13 at problem D. Really sad, I was getting close to purple.

→ Reply
»
16 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Nice round! I enjoyed how Problem C masked the well known problem of maximum subarray XOR, but I think it might be unfair for people who tried to come up with the solution on their own rather than Googling, since the most common solution uses a Trie which would suit Problem D more.

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Cool contest! though i had troubles since i haven't written contests in a while

I saw my friend solve D in 25 mins, and rushed to solve D before C, came up with the solution quickly but implemented it too slowly, ac-ed, got a low score for it 30 mins before the end, and solved C 3 mins before the end. Happily the contest was prolonged for 15 mins:)

→ Reply
»
16 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Was the last submission considered over the first? I thought that it is so, only if first submission failed FST :(

→ Reply
»
16 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Any hints for D? I'd like to try solving it on my own

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

    I thought about assigning priority to each index, ig this might serve as a hint if this is in the correct direction, can anyone confirm this?

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

    Give priority to each character, according to their first appearance in $$$t$$$. Then if you have a lower priority character as $$$'1'$$$ and a higher priority character as $$$'0'$$$, swapping them will be better.

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

    $$$t(s)$$$ can be annoying, can you solve it when the goal is to make the following string as large as possible?

    (Goal 1)
    (Goal 2)
    (Goal 3)

    Once you have that, you have solved half of the problem, can you solve the full problem?

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any good hints to solve F?

→ Reply
»
16 months ago, # |
← Rev. 4   Vote: I like it +28 Vote: I do not like it

Don't like C at all. It's just duplicate of https://cses.fi/problemset/task/1655. Furthermore, I was suprised by the quantitiy of people could solve it in the contest after 1 hour passed, since Trie is not something most people could know and implement.

Yeah, honestly I just want to imply that the majority copied and pasted the solutions. But i think the main point here is about problem setters. It's okay to use some of small problems , but not to use the whole of them adding to a single C.

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

    You can solve it just by brute force because ai <= 256

    → Reply
»
16 months ago, # |
  Vote: I like it +7 Vote: I do not like it

I wonder where they got the idea for Problem-C:

Spoiler
→ Reply
»
16 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Try to make beautiful problems not a beautiful blog.

→ Reply
»
16 months ago, # |
  Vote: I like it +10 Vote: I do not like it

HAHAHAHA, FUCK ME, TL ON D CUZ OF THIS SHIT:

j = *upper_bound(st.begin(), st.end(), j);

INSTEAD OF:

j = *st.upper_bound(j)

HAHAHAH, ADORE PROGRAMMING))))))))))))

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

    yep, got it accepted, after this and 1 more edit)

    tilt...

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I read the title of problem A, well that made me thought the contest's theme was DeathNote =))

→ Reply
»
16 months ago, # |
  Vote: I like it +3 Vote: I do not like it

A pretty bad contest, its difficulty is more difficult than the number in the problem.

→ Reply
»
16 months ago, # |
← Rev. 3   Vote: I like it +38 Vote: I do not like it

A: Sort the array of {a[i]-a[i-1]} and choose n-k minimum elements.

B: Let A=a[1]&a[2]&...&a[n]. If A>0, then for all 1<=i<=n we have a[i]>=A, so if there are more then one groups, the bitand of each group will be at least A, and the sum will be at least 2*A > A, so there can be only one group. If A==0, we can build groups greedily from left to right (by choosing the minimal prefix of remaining elements with bitand==0).

C: By trying for some small cases we can find that all possible values of strength are the xor-sum of some ranges [L, R], we can find them in O(max(n^2, n+(2^8)^2)) = O(2^8*n).

D: For numbers in [L1, R1] we let a[L1]=1, a[L1+1]=2, ..., a[R1]=R1-L1+1, because s[L1] is the first element appears in t, s[L1+2] is the second element appears in t, and so on. For numbers in [L2, R2] and not in [L1, R1] we assign values to a[i] by the order s[i] appears in t. Using an ordered set we can process all m ranges in O(m+n*log(n)). Assume there are k numbers in any range [L, R]. For answering queries, let's assume there are x occurences of 1, then for all i such that a[i]<=min(x, k), we need do operations to make s[i]=1. Then we can answer the queries by fenwick tree.

E: untested problem.

F: If we let b[i]={a[1], a[2], ..., a[n], a[1], a[2], ..., a[n]}, then we can see all values appear in {a[n+1], a[n+2], ...} are some range-bitor of b[i], and for ranges with same right bound and same value of bitor, we only need to keep the smallest range. For each right end, there are most log(max(a[i])) different values of range-bitor, and we can find them by sparse table and binary search, so we can solve the problem in O(n*log(n)*log(max(a[i]))).

pattern of F
→ Reply
»
16 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Anyone else overkilled problem A with dp?

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

    I was literally thinking that how can problem A be dp and read the problem's constraints too many times before submitting

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

    Wasted like 10 minutes implementing the DP solution, got annoyed, stopped to think, facepalmed, submitted the greedy — AC.

    Lesson: Don't take breaks from CP.

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

      For me implementing DP was easier than coming up with the greedy solution.

      → Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    For the long time(about 25 minutes) I was thinking smth like: "Nah, it's the first problem, there should be easier solution". The result was just wasting these 25 minutes, 'cause I've written dp solution finally.

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

No written editorial?

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

hmm

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

    bruh, its not same, there are more simple a[i]<256 u can just do N*256, there are no even need to think (if u know prefix arrays)

    Also it fair

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

    It's kind of hard to reduce the problem down to max subarray xor, so I think it's fair

    → Reply
»
16 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Just not my day I guess. .

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

    Someone please help me with B, didn't we just needed to find the maximum segments that had the same "&" as that of the entire array, such that all segments have that same "&".

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

      that's right when the and is 0 but when it is anthing else the answer is always one group as adding more groups will always give higher sum

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

      We need to find the minimum sum of bitwise and. Suppose the full array has bitwise and $$$3$$$. If you find two subsegments, both with bitwise and $$$3$$$, the sum of those is $$$3 + 3 = 6$$$, which is more than $$$3$$$ and not optimal.

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

      Let biwise AND of all the elements equal to k,

      Case 1: k == 0 : Try to create maximum number of partitions such that AND of all partitions = 0.

      Case 2: if k > 0 , it's always optimal to create only one group, i.e. the whole array. Reason :--> It's easy to prove Bitwise AND of any partition is >= k , hence more the partitions, more will they contribute to sum, so make just 1 partiotion with AND = k

      → Reply
»
16 months ago, # |
← Rev. 4   Vote: I like it -81 Vote: I do not like it

problem c is a copy of these problems: https://www.geeksforgeeks.org/find-the-maximum-subarray-xor-in-a-given-array/ https://www.spoj.com/problems/QN01/ https://sairampenjarla.medium.com/maximum-xor-subarray-3b9e27bc302d https://codeforces.me/gym/103091/problem/A https://cses.fi/problemset/task/1655

should this round be rated?

→ Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 2   Vote: I like it +101 Vote: I do not like it

    If every round that had problem that after thinking is reduced to standard problem as most major component is unrated, almost every round would be unrated.

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

    in problem C you need to make some observations before that, so no

    → Reply
  • »
    »
    16 months ago, # ^ |
      Vote: I like it -34 Vote: I do not like it

    easily you can see that the task is finding the max xor range it's obvious, everyone knows that a^a = 0 this is the only reduction you need and its also a well-known property of xor, if you just copy standard problems and rephrase them almost every round will be googlable! and worthless. it's okay to use standard ideas in a multitasking problem or make from them a new variation but anyone can just copy the code from gfg with no understanding of it at all and it will pass! , this is my opinion i respect all your points but it is just not fair.

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

      easily you can see that the task is finding the max xor range it's obvious

      You say it's obvious but in a 101 word comment you were unable to explain why it is obvious.

      The fact that one can guess the task without proving it is the correct solution is not ideal and the most interesting problems make it hard to guess the idea, I agree.

      anyone can just copy the code from gfg with no understanding of it at all and it will pass!

      Thankfully everyone has access to the internet, so it's an equal playing field when it comes to fetching code to solve standard problems. You can carry on and have fun with the remaining 5 problems in the contest instead of complaining.

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

        Actually its rather obvious since operation on a index is performed only once(two operations will just introduce a zero) its simple to just jot some equations down and see the result that it always leaves a subarray xor

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

          If you have to "jot some equations down" to convince yourself it is true, that's not what I call "obvious". But maybe we have different definitions of the word.

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

        everyone knows that a^a = 0 this is the only reduction you need and its also a well-known property of xor

        That's why it's obvious. you can take any suffix you want and delete from it(a^a=0) any other suffix and it gives you any subarray you want.

        Thankfully everyone has access to the internet, so it's an equal playing field when it comes to fetching code to solve standard problems..

        yes, but you don't participate in rounds to copy solutions, it's okay to copy some block of code that will help you in solving the problem but not the solution itself! , so when I participate in a round i trust in cf that it will give me original problems so i depend on myself, others maybe will go to copy the answer so you will have 5k+ solutions so its not fair to those who trust cf.

        You can carry on and have fun with the remaining 5 problems in the contest instead of complaining

        for sorry not everyone can solve the whole problem set, if someone can only solve till c it will affect him if c was a googlable so i has the right to complain .

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

          Can you explain why can't we get any subsequence of the array? Or, at least, prefix + suffix? Why only subarrays?

          → Reply
        • »
          »
          »
          »
          »
          16 months ago, # ^ |
          ← Rev. 3   Vote: I like it +16 Vote: I do not like it

          As nifeshe implies, to me it is obvious you can get any subarray, but not so obvious you can't get any subsequence. Maybe for you it is, great, but it was not for many including me.

          It is sad that many can just happen to guess, but that is true of arguably most lower level problems.

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

          All of this frustration may be valid, but may I ask... Why are you complaining about a problem in a contest you didn't participate in?

          In fact, according to your profile you haven't made a submission in a contest in almost 6 months. I wonder what the fuss is all about.

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

            I mean if a problem is heavily disliked or liked one can have the curiosity to look at it

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              16 months ago, # ^ |
              ← Rev. 16   Vote: I like it 0 Vote: I do not like it

              Heavily disliked by whom? Steven-_-AbuAlkhair was one of the first to comment about the problem, right after the contest ended.

              Do you also go to the comments section to complain about how frustrated you are about the quality of specific problems, immediately after contests end? For contests you did not participate in? Really?

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

                Yeah since I didn't participated in contest I cant dislike a problem that's true :), leaving all that nothing was wrong about problem C, it was just a another easy div2 C, most frustration from people is due to others using online code while they didn't(either for being absent minded or they didn't want to)

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  16 months ago, # ^ |
                  ← Rev. 7   Vote: I like it 0 Vote: I do not like it

                  most frustration from people is due to others using online code while they didn't

                  Again: how could they (the person who started this thread) be frustrated about others using online code to solve a problem in a contest that they did not participate in?

                  I'm done engaging here. Enjoy life.

                  → Reply
»
16 months ago, # |
  Vote: I like it +15 Vote: I do not like it

DEF -> FDE

→ Reply
»
16 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Codechef Forces.. gave me the vibes of their contest

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

My approach for C was to calculate all suffix xor. Then answer will be maximum xor of any 2 suffix in an array. I don't understand how it is equal to maximum xor in a subarray. This is my solution btw — https://codeforces.me/contest/1847/submission/212410188

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

    Notice that the xor of 2 suffixes is equivalent to the xor of a subarray, example:

    Suffix xor 1 = a^b^c^d^e^f Suffix xor 2 = d^e^f

    Now if we xor these 2 we get a^b^c^d^e^f^d^e^f = a^b^c, notice how the intersection of the suffix xors get cancelled out. So when you calculate the xor for any 2 suffixes, you're actually just calculating the xor of every single subarray. Same with prefix xors.

    → Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Problem C likely had so many submissions because once you recognize that ans is max xor subarray you just have to google the solution. The max xor subarray problem is a great classical problem but I dont think such classical problems should be put in cf. How many people who submitted the solution knew how the solution works using tries I wonder. Not a good problem

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

    I did the trie part after thinking for like 15 minutes.

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

    I didn't solve the problem with max-xor-subarray.

    I didn't reach the this observation until you mentioned it. But still I managed to solve the problem.

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Which anime was it?

→ Reply
»
16 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Huge Jojo fan, but pretty bad contest

→ Reply
»
16 months ago, # |
  Vote: I like it +1 Vote: I do not like it

As a tester, I can say that the quality of the problems was very high. (especially C in my opinion)

→ Reply
»
16 months ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve D ?

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

    Lets do 2 key obsertvations. 1) If we have 2 segments that overlap, we can subtract the overlapping part with the segment with less "priority" in the calculation of t(s). Where the less the position is in t(s), the higher priority. So now lets recalculate the segments this way, and now each index belongs only to one "segment", even though they could now be not segments. 2) Now lets do a trick: lets calculate t(s) and instead do all of the operations on t(s). Now, because of observation 1 each element from s can be found exactly 1 time in t(s). Now lets do a segment tree for finding the sum on t(s) and to recalcing the answer is obvious: the numbers of 0s in the segment [0; x] where x is min(number_of_1_in_t(s), unified_length_of_all_segments)

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

      I did the priority distribution right, but couldn't come up with this idea that minimum operations is just number of zeroes that should've been 1. Thanks for your solution btw :)

      → Reply
»
16 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Fun fact: C can be solved with O(nlog(max a[i])) complexity by using trie of prefix xor-sums.

→ Reply
»
16 months ago, # |
  Vote: I like it -21 Vote: I do not like it

trash round did the same thing as some of my friends in 1st 15 minutes and it TLE'd for me only so had to use a trie , just regretting i woke up for this cringey contest

→ Reply
»
16 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Za Warudo toki wo tomare !!!

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it -11 Vote: I do not like it

d

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

clown round, testers not doing their job properly, not even clown level this contest is the whole circus

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

    But what didnt you like particularly

    → Reply
»
16 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

A fun contest. But getting TLE 46 on D...... why me. But he solution was O(nlogn) so it should have gotten AC

EDIT WHAT I GOT AC NOW THEY CHANGED THE TL

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

    I don't think using a mass segment tree is a good idea when you can use scanline

    → Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

Thanks for the 15 mins extension. I solved F in the last 3 mins (going back to master yeah). F is a really cool problem and I love it!

→ Reply
»
16 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Finally, the cheaters were exposed this round. Thanks Youtube for wrong solution in problem C :D.

→ Reply
»
16 months ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

Me when FST on E

Edit: TLE on 68 because I forgor to remove a cerr that printed 2^16 arrays -_-

→ Reply
»
16 months ago, # |
  Vote: I like it -10 Vote: I do not like it

Literally the worst contest ever

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

    why?

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

      never saw these many bitwise questions in a single contest and apparently solution to C is available on the internet

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

        that doesnt mean round is bad plus u dont even need internet solution u can just do naive and check, no even need to think

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

          can u check my didnt my naive sol pass? also i mean the first submissiong BEFORE A

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

            delete long long, add fast i/o, idk about pragmas, i often dont trust them

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

        Fact is that if you have little variety of problems the contest is a little boring in my opinion

        → Reply
»
16 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Maybe a little bit less bits problem next time XD

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

proof for problem C please, why we can't do better than max subarray?

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

    In XOR operation XORing the same number twice (or even number of times) negates it 1 ^ 1 ^ 2 = 2 so when Dio summons a stand user at index i, when he summons another stand user, stand users from i till the end will be negated so he can use this to negate numbers that lowers total XOR in the end of the array to negate the ones in the front he can just choose i to be equal to the element after them when summoning the last stand user for example if we have this array: 3 7 2 5 8 1 6 4 1 the maximum subarray xor answer is 15 which is 8 ^ 1 ^ 6 so he needs to git rid of 3 7 2 5 from the start and 4 1 from the end to get rid of the 4 1 he summons a new stand user with strength = 4 ^ 1 = 5 so now we have 3 7 2 5 8 1 6 4 1 5 to now summon the stronger stand user he can he need to negate 3 7 2 5, so he chooses i to be the index of 8 when summoning it so its strength is 8 ^ 1 ^ 6 ^ 4 ^ 1 ^ 5 and 4 ^ 1 ^ 5 = 0 so the strength is 8 ^ 1 ^ 6 = 15 which is the maximum XOR subarray

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

      thank you, but I already solved it by finding "maximum XOR subarray" in contest time, I mean why "maximum XOR subarray" will be the max answer which we can get, why answer can't be greater than "maximum XOR subarray" ?

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

        For each summon you only negate (or return already negated) numbers from the array, you don't add new number , so there is no way you can get an array with XOR larger than the maximum (It may be possible if you can add numbers from outside the array, but you can't) When you summon a user you its strength is equal to the XOR of the subarray which starts with i and ends with the end of the array to summon the strongest user you need to choose i that makes the XOR of subarray = to the maximum (i.e. the maximum has to be in the end of the array) if it's not in the end you summon a user that negates the users after the last user in the maximum subarray

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

C can also be solved with dp https://codeforces.me/contest/1847/submission/212455218

→ Reply
  • »
    »
    16 months ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    What can't be done with dp :D Nice solution btw

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

    Sad you had to copy from geeksforgeeks instead of dp

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

      During contest when I figured out the approach. I was pretty much sure there must be some implementation so I googled it and pasted that solution.

      And after the contest while having my dinner I also figured out that it can also be solved with dp

      BTW I solved problem A also with dp

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

        Interesting to see that your initials are also "DP":XD

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

    Nice solution using dp. I was unable to understand why maximum xor subarray works here, that thing is not intuitive to me. But seeing your dp solution, it helped me get that intuition!

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

    Could u please explain your dp solution. I am not able to understand ur dp states and transitions

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

      2^8=256 which is not large so we can find all the possibility using our array elements.

      Also our aim is to find maximum xorsum so we will update the maximum at each step.

      and also when we are visiting any index with some xorsum then we can surely say that we can find all the coming subsequences using xorsum from that index. So we will not visit that xorsum and index again as it will give the same output.

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

In c everyone just copies tries code form online, please check plagiarism.

→ Reply
»
16 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

sorry, who can tell me why wa? I generate permutation, where p[i] is priority of symbol in string. Next i compare sum on prefix and all '1'. this

→ Reply
»
16 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Ratings updated preliminary, it will be recalculated after removing the cheaters.

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I solved C by BFS. There are only 256 possible states to look for.

→ Reply
»
16 months ago, # |
  Vote: I like it +32 Vote: I do not like it

I found E quite interesting! (although the implementation is tough)

→ Reply
»
16 months ago, # |
  Vote: I like it +5 Vote: I do not like it

edogawa_something orz

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why C was giving pretest 2 wrong when solved with Kadane's Algorithm

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

    Maybe because xor != sum... Interesting that you ask questions like this and you got AC with trie solution

    → Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we approach B by doing binary search on answer,if yes how ? Thanks in advance

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I've waited for 4 — No, 5000 years for this

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I was trying F by offlining the queries and divide and conquer during contest but couldn't finish implementation. I made the following observations:

  1. If there exists some x in the infinite sequence then it must be the bitwise or of some subarray of the given array (consider the given array to be circular in mind).

  2. Or value of smaller subsegments appear first.

  3. So for each query we can binary search the length l of smallest interval s.t. there exists a subarray of length l (if its start point lies on or before n — l + 1, otherwise length l + 1 i.e. OR[start][n] | OR[1][l + 1 — (n — start + 1)]) whose bitwise OR value is > given query but unfortunately, this is too slow (O(nlog(n))

  4. So instead of answering them online we can offline them so that we do the binary search thing for multiple queries at the same time.

  5. Thus we use divide and conquer where we essentially do binary search on min length of such an interval. If among all the subarray of length mid, the max possible or value is x then all queries with value < x must recurse left (< x) and rest on right (> x)

  6. Since for all elements recursing to the left, x is also an option, we update their ans.

However, I am getting WA on test 3 with this approach. And I cannot figure out where I am wrong. Any suggestions would be helpful. Thanks in advance. My submission

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

CHEATFORCES!

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, i misunderstand the statement and ended up trying to solve a different version of it.

Here it is :
In this version we do operation on t instead of s and try to make t as lexicographically as large as possible. i don't know if it is solvable with dependent queries or not.

But it can be solved if queries were independent.

we can calculate number of ones after each update and sort it in non decreasing order and go from left to right. Let's say length is $$$len$$$ than we need to compute some prefix of segments such that it's total size if equal to our $$$len$$$ and we update these segments in segment tree as $$$seg[l]$$$++ and $$$seg[r + 1]$$$-- and now for our query we can easily calculate number of ones in our $$$len$$$ range and can get result for current query. We than go right and again push our pointer ahead in our ranges as mentioned above and do same thing again. Here we don't need to start again from 0 as we have sorted length (number of ones after update) of each query and we can continue after we stopped last time and do same.

But if queries were dependent as in problem d it is, than how to solve it ?
note that in this version we are updating t instead of s.

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

for problem f:

i am thinking that we will first find an array say maxs(n), where

maxs(i) = maximum bitwise or of i consecutive elements then we can do binary search and get suitable minimum i where maxs(i) > v, and then for that particular i we can again do some binary search or something to find exact position.

but here i am not able to find maxs(n) in less than o(n^2), could some one please give some hints regarding that.

→ Reply
»
16 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Absolutely, F is greatly easier than E.

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

why my dp for C doesnt work ?

https://codeforces.me/contest/1847/submission/212438627

→ Reply
»
16 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Please Bring Editorial :/

→ Reply
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Interesting round,but with too mamy bitwise operation problem XD

→ Reply
»
16 months ago, # |
  Vote: I like it +3 Vote: I do not like it

problem C :Easy solution without dp https://codeforces.me/contest/1847/submission/212554250

→ Reply
»
15 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I can not understand the third output in problem C. Can someone help me pls :(

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