Блог пользователя glebustim

Автор glebustim, история, 14 месяцев назад, По-русски

Привет, Codeforces!

Мы с SomethingNew рады пригласить вас на CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!), который пройдёт в 18.09.2023 17:35 (Московское время). У вас будет 2 часа 15 минут на решение 8 задач. Раунд будет рейтинговым для всех.

Мы хотим выразить благодарность:

Разбалловка:

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

Мы надеемся, что наши задачи будут интересными для вас!

Разбор

Поздравляем победителей!

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

Информация от спонсора этого раунда:

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!

  • Проголосовать: нравится
  • +394
  • Проголосовать: не нравится

»
14 месяцев назад, # |
  Проголосовать: нравится +76 Проголосовать: не нравится

я не понял, а где мемы в анонсе?

»
14 месяцев назад, # |
  Проголосовать: нравится +78 Проголосовать: не нравится

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

»
14 месяцев назад, # |
  Проголосовать: нравится +75 Проголосовать: не нравится

Hope I can reach GM after this.

»
14 месяцев назад, # |
  Проголосовать: нравится +88 Проголосовать: не нравится

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

»
14 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Yeahh ! CodeTON finally ;D

»
14 месяцев назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

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

»
14 месяцев назад, # |
  Проголосовать: нравится +80 Проголосовать: не нравится

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

»
14 месяцев назад, # |
  Проголосовать: нравится +54 Проголосовать: не нравится

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

»
14 месяцев назад, # |
  Проголосовать: нравится +75 Проголосовать: не нравится
you can determine the future of the round.
»
14 месяцев назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

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

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Wish it will be an great contest.

»
14 месяцев назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
14 месяцев назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

wishing for a charming contest

»
14 месяцев назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

wishing for a charming contest

»
14 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Finally, great contest (I hope so)

»
14 месяцев назад, # |
  Проголосовать: нравится +116 Проголосовать: не нравится

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

»
14 месяцев назад, # |
  Проголосовать: нравится -31 Проголосовать: не нравится

As a one gray tester, give me contribution :)

»
14 месяцев назад, # |
  Проголосовать: нравится +186 Проголосовать: не нравится

74TrAkToR Round? I'll skip this one.

»
14 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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.

»
14 месяцев назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

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.

»
14 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Hope it's the round that I become expert!

»
14 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
14 месяцев назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

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

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good Luck!

»
14 месяцев назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Abcd speedrun

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
14 месяцев назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

TON's price seems to fluctuate a lot.

»
14 месяцев назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

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

»
14 месяцев назад, # |
  Проголосовать: нравится +90 Проголосовать: не нравится

The contest was mexed up

»
14 месяцев назад, # |
  Проголосовать: нравится +122 Проголосовать: не нравится

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.

»
14 месяцев назад, # |
Rev. 2   Проголосовать: нравится -7 Проголосовать: не нравится

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

  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It passed system testing too, but how???

    • »
      »
      »
      14 месяцев назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      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})$$$.

»
14 месяцев назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится +32 Проголосовать: не нравится

    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.

    • »
      »
      »
      14 месяцев назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thanks for the fun contest!

»
14 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

How to solve E?

  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

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

    • »
      »
      »
      14 месяцев назад, # ^ |
      Rev. 3   Проголосовать: нравится +13 Проголосовать: не нравится

      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.

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve D?

  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится +17 Проголосовать: не нравится

    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.

  • »
    »
    14 месяцев назад, # ^ |
    Rev. 4   Проголосовать: нравится +5 Проголосовать: не нравится

    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

    • »
      »
      »
      14 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      my approch is also similar but it doesnot work

      • »
        »
        »
        »
        14 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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).

        • »
          »
          »
          »
          »
          14 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Thanks a lot ! Friend .Urs debug made me to get it accepted. https://codeforces.me/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.

»
14 месяцев назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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

My story today
  • »
    »
    14 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

    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)

»
14 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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.

»
14 месяцев назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Hopefully no FST today...

»
14 месяцев назад, # |
Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

Nvm

»
14 месяцев назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

I could only think of a bruteforce solution to D.

»
14 месяцев назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

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?

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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).

»
14 месяцев назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Good problemset

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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$$$

    • »
      »
      »
      14 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        14 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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

        • »
          »
          »
          »
          »
          14 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        14 месяцев назад, # ^ |
          Проголосовать: нравится +11 Проголосовать: не нравится

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

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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...

»
14 месяцев назад, # |
Rev. 4   Проголосовать: нравится +78 Проголосовать: не нравится

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).

  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    Love your short and clear explanations.

  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      14 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Nvm, I saw the editorial

      • »
        »
        »
        »
        14 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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)

»
14 месяцев назад, # |
  Проголосовать: нравится +57 Проголосовать: не нравится

f5 f5 f5 f5 f5

  • »
    »
    14 месяцев назад, # ^ |
    Rev. 3   Проголосовать: нравится +11 Проголосовать: не нравится

    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).

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    14 месяцев назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
14 месяцев назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

Very similar to problem H

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

»
14 месяцев назад, # |
Rev. 4   Проголосовать: нравится +19 Проголосовать: не нравится

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.

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

too lazy to code problem E lol

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I am proud to be the absolute loser of this competition

»
14 месяцев назад, # |
  Проголосовать: нравится +31 Проголосовать: не нравится

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.

  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
»
14 месяцев назад, # |
Rev. 4   Проголосовать: нравится -8 Проголосовать: не нравится

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]].

  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      14 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        14 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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?

        • »
          »
          »
          »
          »
          14 месяцев назад, # ^ |
          Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          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.ヾ( ̄□ ̄)ツ

»
14 месяцев назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

MEXforces

»
14 месяцев назад, # |
Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

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. :(

»
14 месяцев назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

bitset passed in problem E, ___ ___ ________?

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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
»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

why my code gives wa on test 4

PROBLEM D

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

  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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!

    • »
      »
      »
      14 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
14 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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})$$$.

  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится +29 Проголосовать: не нравится

    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;
    }
    
»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    hint 1
    hint 2
    solution
»
14 месяцев назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

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

»
14 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

I will cross 1400 this round. Next target 1600.

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Anyone knows why in the problem E, solution $$$O(n \cdot t)$$$ where $$$t$$$ stands for the number of segments $$$[l, r]$$$ so that $$$mex[l][r]$$$ is equal to neither $$$mex[l + 1][r]$$$ nor $$$mex[l][r - 1]$$$ passes all the tests? In other words how to bound $$$t$$$ to less than $$$O(n^2)$$$?

»
14 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
14 месяцев назад, # |
  Проголосовать: нравится +34 Проголосовать: не нравится

This generator kills not small number of E.

  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Kill for TLE or WA?

    • »
      »
      »
      14 месяцев назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

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

      • »
        »
        »
        »
        14 месяцев назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        14 месяцев назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

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

»
14 месяцев назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

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.

  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

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

»
14 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Finally purple.

»
14 месяцев назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

MEXforces

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
14 месяцев назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

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

»
14 месяцев назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
14 месяцев назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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.

»
14 месяцев назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Hi. How can I get a prize?

»
13 месяцев назад, # |
  Проголосовать: нравится -12 Проголосовать: не нравится

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)

»
13 месяцев назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

So, when are we getting paid?

»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Did anyone get the prize?

»
12 месяцев назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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