glebustim's blog

CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!)
By glebustim, history, 14 months ago, translation, In English

Hello, Codeforces!

SomethingNew and I are glad to invite you to CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!), which will take place on Sep/18/2023 17:35 (Moscow time). You will have 2 hours 15 minutes to solve 8 problems. The round will be rated for everyone.

We would like to thank:

Score distribution:

500 — 750 — 1500 — 1750 — 2750 — 3250 — 3250 — 4000

We hope that our problems will be interesting for you!

Editorial

Congratulations to the winners!

  1. orzdevinwang
  2. cnnfls_csy
  3. jiangly
  4. PubabaOnO
  5. maspy
  6. tourist
  7. AoLiGei
  8. Um_nik
  9. noimi
  10. Geothermal

And here is the information from our title sponsor:

Hello, Codeforces!

We, the TON Foundation team, are pleased to support CodeTON Round 6.

The Open Network (TON) is a fully decentralized layer-1 blockchain designed to onboard billions of users to Web3.

Since July 2022, we have been supporting Codeforces as a title sponsor. This round is another way for us to contribute to the development of the community.

The winners of CodeTON Round 6 will receive valuable prizes.

The first 1,023 participants will receive prizes in TON cryptocurrency:

  • 1st place: 1,024 TON
  • 2–3 places: 512 TON each
  • 4–7 places: 256 TON each
  • 8–15 places: 128 TON each
  • …
  • 512–1,023 places: 2 TON each

We wish you good luck at CodeTON Round 6 and hope you enjoy the contest!

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

Comments Comments (169)
| Write comment?
»
14 months ago, # |
  Vote: I like it +78 Vote: I do not like it

Why it's only 2 Hours for a CodeTON Round? I think we need more than that!

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

    So many things to wonder nowadays... Ratings for many recent contests have not been updated yet :(

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

    you are right.

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

Hope I can reach GM after this.

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

As a tester, problems are really great! I hope you will enjoy the contest as much as I did.

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

As a 74TrAkToR's friend, I am sure the round under his coordination will be excellent!

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

Based on authors, I'm sure there will be no task with bitset lol.

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

SomethingNew round, are you retarded?????????????????????????????

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

    No, no one is retarded, bro

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

    A nice one

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

      yea, too bad people did not get it

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

        what if I don't want this to get normalized

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

          You just should know that sometimes people can be frustrating.

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

            Oh, I see.

            But how did you get that joke but not this one

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

          Then you can honestly forgive some greens who have complete no idea what they're saying.

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

    At least there will be no goddamn bitsets in it

    → Reply
»
14 months ago, # |
  Vote: I like it +75 Vote: I do not like it
you can determine the future of the round.
→ Reply
  • »
    »
    14 months ago, # ^ |
    ← Rev. 2   Vote: I like it +193 Vote: I do not like it

    legends in the author's statements, why????????????????????????????????????????

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

As a tester I recommend you to participate and I hope you will get positive delta!

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

Wish it will be an great contest.

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

as a participant, the 2 hours time combined with that score distribution is scary ._.

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

wishing for a charming contest

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

Finally, great contest (I hope so)

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

Why is the round on a weekday? I won't be able to participate as I have band practice. It's just even more weird given that it is sponsored

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

    Omg Senpai, so true ≧◡≦

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

      I got you! If you are really Ryo and Kita, today is Respect for the Aged Day!

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

As a one gray tester, give me contribution :)

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

74TrAkToR Round? I'll skip this one.

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

Where is my money? I still haven't received my prize from last round. I had to go through the misery of creating a wallet and storing keys.

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

Hope it's the round that I become expert!

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

I am definitely going to have negative points. If the time remains 2hr :(

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

It's gonna be my first contest. I should've started with a div 3 or 4 but I like to challenge myself. Wish me luck

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

Why there's no 1,024-2047 places: 1 TON each?

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

Good Luck!

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

Abcd speedrun

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

I'm nervous about participating after three months of not participating in this competition.

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

Hope I can learn something new from this round, good luck everyone!

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

TON's price seems to fluctuate a lot.

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

Well prepared round. My congratulations to the authors and testers. Definitely one of the best ones I've given these few months.

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

The contest was mexed up

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

Please announce last-minute round duration changes more prominently. I participated this round thinking it was 2 hours, and I couldn't compete for more than 2 hours today. I believe this situation might not be unique to me.

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

Can someone explain why my code isn't TLE for 1870D - Prefix Purchase?

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

    It passed system testing too, but how???

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

      At each step in the while-loop, you are finding the rightmost $$$x$$$ such that $$$\lfloor k/(a[l]-a[x]) \rfloor$$$ is maximal.

      If the value of $$$\lfloor k/(a[l] - a[x])\rfloor$$$ is $$$0$$$, then $$$x=n$$$, and the loop will break.

      Otherwise, assume this value $$$\lfloor k/(a[l] - a[x])\rfloor$$$ is non-zero.

      Then write $$$k = (a[l] - a[x])q + r$$$, where $$$0\le r< (a[l] - a[x])$$$ and $$$q\ge 1$$$.

      Now we have the following inequality:

      $$$r< (a[l] - a[x])q\Rightarrow 2r< (a[l] - a[x])q+r=k\Rightarrow r<\frac{k}{2}$$$

      So every time you assign $$$k:=k\%(a[l]-a[x])$$$, the value of $$$k$$$ becomes less than half of what it was.

      In other words, your algorithm is at worst $$$O(n\log{k})$$$.

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

me spending 10 minutes trying to understand what problem C was trying to say

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

    A grandmaster (at least for now) here. It also takes me some time (~3min) to finally understand it. I initially thought "rectangle in the array $$$b$$$ containing all cells of this color" means "a rectangle which contains only this color". Then the word "smallest" (instead of "largest", which would make it an interesting problem) confused me.

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

      Yup understood the same and thought wouldn't it make this a trivial solution for each k it would be square of length 1 if it exists in array but then figured out later that it meant that the smallest rectangle that would cover all the points with same value

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

Thanks for the fun contest!

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

How to solve E?

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

    SomethingNew alreadly spoiled it a while ago. It's just bitsets :)

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

      UPD. Sorry. I just replaced bitset operations with ordinary cycles with boolean operations, it became two times slower, but still got OK. I guess the solution does benefit from the usage of bitsets, but not drastically.

      So I was wrong during the contest thinking that SomethingNew changed his mind about having bitsets in the jury's solution.

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

How to solve D?

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

    First, we can say, that picking mininal $$$c_i$$$ determines the first element. Amongst all minimal $$$c_i$$$ we only care about one that has max $$$i$$$, so let's create a new array $$$a$$$, where $$$c_i$$$ will be stored in increasing order (we also remember their indices). Then we pick $$$a_0$$$ $$$k / a_0$$$ times. Let's subtract $$$a_0$$$ from $$$a_1$$$. Then, if we decide to pick $$$a_1$$$, that means that we cancel choice of $$$a_0$$$ and replace it with $$$a_1$$$. That's the key idea. When we pick $$$a_i$$$, we need to be able to add number on a segment. It can be done offline using difference arrays.

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

    Suppose the minimum value in array $$$c$$$ is $$$c_i$$$, with ties broken by the largest index. Then the first value can be incremented at most $$$\left\lfloor \frac{k}{c_i} \right\rfloor$$$ times. In fact, if we keep selecting index $$$i$$$, then all values from index 0 to index $$$i$$$ will be equal to $$$\left\lfloor \frac{k}{c_i} \right\rfloor$$$, and it is impossible to increase them further. Note that there may be some surplus $$$k \% c_i$$$ coins left unused.

    However, can we increase some of the later values (which would otherwise remain all 0s in this option)? This requires that we can afford to replace one of the index $$$i$$$ selections with a selection for a later index. Suppose the minimum value from $$$c[i + 1\ldots n - 1]$$$ is $$$c_j$$$, i.e., smallest element located after $$$c_i$$$. Each replacement requires us to spend an additional $$$(c_j - c_i)$$$. Based on our surplus remaining coins, we can then calculate how many of the index $$$i$$$ selections can be replaced with index $$$j$$$ selections, and update our strategy accordingly.

    But what about the values after index $$$j$$$? Once again, we can consider whether we can replace an earlier selection for a later selection. Our earlier selections would be a mix of $$$i$$$ selections and $$$j$$$ selections, but replacing a $$$j$$$ selection will save more money than replacing an $$$i$$$ selection, so we can simply focus on replacing $$$j$$$ selections now. And so on.

    How do we actually implement this? My approach was to first construct a cumulative suffix minimum array, where $$$snm[i] = \min_{i \leq k \leq n - 1}c_k$$$. These are the only values worth considering. For simplicity, I assumed that our initial strategy is to to select cost 0 with frequency $$$k + 1$$$ (effectively $$$\infty$$$). Then we iterate from index 0 to $$$n - 1$$$, each time keeping track of the surplus so far (initially $$$k$$$). For each index, the cumulative suffix minimum array tells us the new cost to consider. We can subtract this new cost minus latest considered cost to determine the cost of replacement, and count how many replacements would be afforded by the surplus, i.e., $$$\left\lfloor \frac{surplus}{newcost - oldcost} \right\rfloor$$$, updating and printing the count accordingly, and also updating our latest cost and surplus as well.

    My submission: 223893795

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

      https://codeforces.net/contest/1870/my

      my approch is also similar but it doesnot work

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

        One error in your implementation is that you allow the number of replacements to exceed the number of selections from the previous cost, even though you can only replace existing selections. Specifically, the output should be non-increasing, but your code allows it to increase.

        Here is a countertest:

        1
2
10 12
19

        The output should be 1 1 (simply pay for the second index), but your code produces 1 4, because the surplus of 9 can be replaced four times by an increment of 2, but you don't actually have four selections to replace (you only have one).

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

          Thanks a lot ! Friend .Urs debug made me to get it accepted. https://codeforces.net/contest/1870/submission/223982510 (Accepted) The another silly error was of indexing (for(int j=0;i<cool[i].size();j++) if(m.find(cool[i][j])!=m.end()) m.erase(cool[i][j]);) giving wrong anwer on test 10 was i<cool[i].size(). wish you grand success.

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

What is pretest 3 on problem D? T_T How do we solve D?

My story today
→ Reply
  • »
    »
    14 months ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    Here's your counter-test: 

    4
4 3 4 5
8

    Your solution gives 2 2 1 1 although it is possible to make 2 2 2 0 (my solution breaks on that test too btw, but I have no idea how to fix those cases)

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

Huge dislike on this contest. Spent half of contest time trying to eliminate TL on correct linear solution for C and correct NlogN solution for D on Kotlin. C successfully, D unsuccessfully. Shame on you.

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

Hopefully no FST today...

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

Nvm

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

I could only think of a bruteforce solution to D.

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

After ~1.5 hours of thinking I still don't get, how can you optimise $$$O(n^3)$$$ into $$$O(n^2)$$$. Can someone give a hint pls?

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

Can we solve E with tries or is it some dp or something else that my small brain couldn't think of?

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

I may have not solved D, but at least I have passed first 4 pretests.

Also this problem is somewhat similar to this problem, we can find largest index with min cost and estimate max amount of possible operations.

Actual solution is probably something like this: keep a vector of candidates with costs higher than min, for each new candidate pop every candidate that is worse, this would work in $$$O(n)$$$ because each element would be added and removed from the vector at most once, then to calculate the final answer use a difference array (I cba implementing this rn).

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

Good problemset

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

I can only think of a crazily long segment tree solution for D,which I have not enough time doing it, and for that I think there has to be some easy-to-write way.

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

    If you came up with idea to add a number on a segment, you can do it offline using difference arrays. Suppose you want to add number $$$x$$$ on a segment $$$[l, r]$$$. To do that, you can create array $$$d$$$ and say $$$d[l] += x, d[r + 1] -= x$$$. If you count prefix sum array on $$$d$$$, you'll get that the segment was increased by $$$x$$$

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

      I planned to use Segment Tree finding the cheapest price with the biggest index during the process of getting better result.Is this unnecessary?

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

        I did this problem without segment tree. It can be used to do addition on segment, but other than that I didn't think about using it

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

          thx. I think I made some mistake with the strategy to ever think of segment tree stuff.

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

        Can't you just sort them or use a priority queue?

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

Did anyone else think that for C with min(Aj, Ai) they meant min(Aj, Aj+1, Aj+2 ... Ai)? That cost me 30 minutes and a headache...

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

A: The maximum possible mex is min(n, x+1), so we need k<=min(n, x+1). Then when k==x we can let a={0, 1, 2, ..., k-1, k-1, ..., k-1}, when k!=x we can let a={0, 1, 2, ..., k-1, x, x, ..., x}.

B: Let bi=(1<<t). If n is even, then the operation will make the t-th bit of x become 0, and if n is odd, it becomes 1. So if n is even, all operations will make x smaller, and if n is odd, all operations will make x greater. Therefore, we can use every operations or no operation to get the maximum and minimum values of x.

C: If t doesn't occur in a[i], the answer of t is 0. Otherwise, for any i,j with a[i]==t, a[j]>=t, we have b[i, j]==b[j, i]==t, so the rectangle need to contain (i, j) and (j, i), then it contains [j, j]. Therefore, If we denote S={i: a[i]>=t}, the answer of t is 2*(max(S)-min(S)).

D: First assume the i0-th operation has the minimum cost, then we need to perfrom at least floor(k/cost[i0]) operations in total. So we can assume that we perform that many i0-th operations, and we can change them into i-th operation later for i>i0 (which costs cost[i]-cost[i0] coins). Then assume cost[i1]=min(cost[j]:j>i0), then we can change as many as possible i0-th operations into i1-th operation to improve the answer. We repeat this process until there are no better operations or we spent all coins.

E: Let time[t] = the minimum i such that we can get answer t in subarray a[1, i]. For each i, we need to update for every t such that time[t]=i. The naive approach is: for every i<j<=k, we let time[t^mex(a[j, k])] <-min- k. But this approach will be O(n^3). To optimize this solution, during the dp process, we need to keep ptr[m]= the minimum k such that there exist some j, i<j<=k and mex(a[j, k])==m (we can do this by pre-calculating mex[j, k] for all 1<=j<=k<=n). The the dp formula will be time[t^r] <-min- ptr[r].

F: Let balance(t) = the change of the rank of t after sorting. Then we can see for t with same number of digits, balance(t) is monotonic. Therefore we can get the answer by binary search, the time complexity is O((log(n))^3).

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

    Love your short and clear explanations.

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

    Why does your solution in E work fast? From the first glance it's not obvious why can't you take all current xors for every i and try to update them with all mexes

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

      Nvm, I saw the editorial

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

        Well, YocyCraft's solution is different to the model one. It works fast because for every t everything is recalculated only once (when time[t] == i)

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

f5 f5 f5 f5 f5

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

    Oof. Your solution is same as mine but with the difference that when i < 1000 I simply iterate through an array. That makes it sqrt(NlogN) instead of sqrt(N)logN (that parameter should be sqrt(NlogN), since in O(sqrt(N/logN)) steps it'll reach that it works in that complexity).

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

How do we solve D ? Only thing I could observe is just take the righmost c[i] , which gives the minimum quotient when K is divided by c[i] and then K-c[i] and repeat the step.

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

    I was not able to solve D as well, But there is one approach I was working upon that is based upon the fact, that we have to do operations at atmost 2 indexes, one with the smallest cost and the other one at appropriate largest index possible.

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

I (might) solved F but I started the contest late and I couldn't finish my code in time. I needed 30 seconds :(

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

Very similar to problem H

And the solution for H is mentioned in its official editorial.

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

H is almost the same as the problem I made before. https://www.luogu.com.cn/problem/P8950

Lucky, only a few people had accepted it before this contest.

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

I am proud to be the absolute loser of this competition

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

my problem, problem H — XXI Open Cup. Grand Prix of Korea , is today's problem G without updates.

By the way, just using binary search + saegment tree to find threshold and calculate block repeatedly guarantees time complexity which is better than $$$O(Q \sqrt N \log N)$$$? It seems to pass pretests.

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

    As I mentioned above you can do it in 2 parts:

    when the position is > sqrt(NlogN) use the segment tree

    when the position is <= sqrt(NlogN) simply use an array an iterate through it.

    that results in O(Qsqrt(N)*logN).

    The editorial claims that simply using an iterative segment tree gets rid of the log completely but it doesn't have a proof atm.

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

What's the problem in my approach 223919097 for problem D? I found all good indices list by this method. 1. Initially,l=0,r=n-1, find minimum ci in this range, and add that i to good list, and make l = i+1. 2. repeat if l<=r

Now maximum value (mxx) we can get in result array a is => k/c[good[0]]. So I iterate from right to left (j) (why ? we need lexicographically largest array a) in good list, now lets say I can do p operations (+1s) on good[j] index. then I need to ensure that p <= k/c[good[j]] and (k - p * v[j]) >= (mxx-p)*c[good[0]].

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

    what if there are more than one js that will be in the final answer?

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

      I am taking all such valid js, I decrease k by p*v[j] and mxx by p

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

        I'm confused about the item k - p*v[j]. It seems that the mxx for ·good[0]· is changeable, but the p for each ·good[j]· is unchangeable？

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

          if I use p operations on index j then, I have to decrease k (total coins) by coins used on j : (p*c[j]). and about p, I am just trying to find best valid p for js.ヾ(￣□￣)ﾂ

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

MEXforces

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

Isn't the $$$O(\log^3 n)$$$ solution of F supposed to get TLE verdict?

Turns out many got accepted with that while I'm struggling to squeeze my code into the time limit. :(

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

bitset passed in problem E, ___ ___ ________?

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

I tried to solve E by precalculating mex of all subarrays and then using dp to find the best subset of subarrays but getting Wrong answer on test 11 , can someone help ?

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

why my code gives wa on test 4

PROBLEM D

https://codeforces.net/contest/1870/submission/223922693

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

    Input:

    1
6
10 100 13 12 13 14
109

    Answer: 10 4 4 4 1 0
    Your output: 10 4 4 4 0 0

    Hope it helps!

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

      Thank You , I realized i couldnt chooose just two positions so I did a rolling ball kind of thing and got AC

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

Finished the first 4 problems in 34 mins, but stuck at E for the rest of the contest :(

I tried to do something with the highest bit of the answer, but it didn't work.

I even considered using bitsets to accelerate the DP, but I didn't know how to do "swap every $$$b[i]$$$ with $$$b[i \oplus c]$$$ in a bitset" in $$$O(\text{fast enough})$$$.

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

    I approached the problem with bitsets and had a similar problem. Actually, I optimized my solution enough that it even works without fast bitset operations (223899736 with bitsets worked in 218 ms; 223934854 without bitsets [actually, with bitsets, but treated as ordinary boolean arrays] worked in 436 ms). However, here you are, xor_convolve is what you need. Asymptotics is $$$\frac{n \log n}{w}$$$ (assuming that $$$w$$$ is the length of RAM word).

    const int B = 13;
const int N = 1 << B;
using Bit = bitset<N>;
 
void xor_shift(Bit& b, const int i) {
	static vector<pair<Bit, Bit>> shifters;
	if (shifters.empty()) {
		shifters.resize(B);
		for (int i = 0; i < B; ++i)
			for (int j = 0; j < N; ++j)
				if (j & 1 << i)
					shifters[i].second[j] = true;
				else
					shifters[i].first[j] = true;
	}
	b = ((b & shifters[i].X) << (1 << i)) | ((b & shifters[i].Y) >> (1 << i));
}
 
Bit xor_convolve(Bit b, const int k) {
	for (int i = 0; i < B; ++i)
		if (k & 1 << i)
			xor_shift(b, i);
	return b;
}
    → Reply
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hints for D Please.

I spent all my time considering that optimal answer will be only from a pair of elements, but my assumption is wrong.

→ Reply
  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    hint 1
    hint 2
    solution
    → Reply
»
14 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Video Editorial For problems A,B,C,D.[Aadhi Hindi + Half Inglish]

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

I will cross 1400 this round. Next target 1600.

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

    this didn’t last very well

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

      Turns out it did :)

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

        congrats! I got specialist too, but idk why i think the ratings are being reevaluated

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

          Yeah, yesterday night they rolled back ratings from the beginning of August and reevaluated them. P.S. — you will get cyan today :)

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

Fun fact: Problem E from today is very different but has the same idea as this F2 from old div2 in which 74TrAkToR was the problemsetter and he is the coordinator from todays round

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

This generator kills not small number of E.

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

    Kill for TLE or WA?

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

      TL / ML. Mainly dp[position] = {the set of possible XOR} with $$$O(n^3)$$$ transition is the target.

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

        I attempted to hack 8 and succeded in 1 of my friends. Big ratio indeed

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

        I only shrinked $$$r$$$ of all segment instead of both of $$$l,r$$$. It got uphacked.

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

Good contest, enjoy it very much. E is brillant(it takes me the longest time to come up with the solution). F is interesting. However I found G much easier(n logn sqrtn with small constant, not standard solution, which got accepted soon after system test) but I was too sleepy to impletement it correctly in the last 15 minutes and successfully missed my LGM.

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

    And then my E got uphacked :) So i should feel lucky instead of regret now!

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

Finally purple.

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

MEXforces

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

Hello, can the question setter or tester provide an incorrect example?223967713

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

Hello, can the question setter or tester provide an incorrect example?223972005

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

    Input:

    1
6
10 100 13 12 13 14
109

    Answer: 10 4 4 4 1 0
    Your output: 10 2 2 2 2 2

    Hope it helps!

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

Is it too late to create a TON wallet in order to get my TON now?

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

its been ages since the last time problem ratings were updated. :feelsoldman:

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

Thanks for the round.

The problems were interesting and nice, but the TLs were too tight, so the pleasure of solving the problems was more or less neglected.

Please rethink the culture of selecting TLs.

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

Hi. How can I get a prize?

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

Hello everybody! What should I do if my attempts are ignored because my code is too similar to someone else's? I received a message from System that my code for task C is very similar to the NoiceFi code, although I wrote it myself. Looking at the NoiceFi code, I noticed that it really is very similar to mine, but I have no idea how it happened. (223885953 and 223878962)

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

So, when are we getting paid?

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

Did anyone get the prize?

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

TON round 7 finished. Yet, round 6 TONS not added..

→ Reply