Serval's blog

By Serval, history, 16 months ago, In English

UPD: The start time has been changed. Note that the start time is unusual.

Hi Codeforces!

Bazoka13, Toxel, and I Serval are glad to invite everyone to participate in Codeforces Round 853 (Div. 2), which will be held on Feb/25/2023 17:20 (Moscow time).

This round will be rated for participants with rating lower than 2100. We will be glad to see the participants with a higher rating to take part in our round unofficially as well!

You will be given 6 problems to solve in 2 hours. Scoring distribution will be announced later.

We would like to thank everyone that makes this round possible:

Good luck & Have fun! :P

UPD2: Scoring distribution: 500 — 1000 — 1250 — 1750 — 2000 — 2750.

UPD3: Editorial is out. Thanks for your participation!

Congratulations to the winners!

Overall:

  1. daubi
  2. BurnedChicken
  3. maspy
  4. tute7627
  5. Um_nik

Div. 2:

  1. MakaPakka
  2. inhabitant
  3. b8LI
  4. Reisael
  5. stkwill
  • Vote: I like it
  • +394
  • Vote: I do not like it

| Write comment?
»
16 months ago, # |
  Vote: I like it +120 Vote: I do not like it

As an author, the problems are very interesting. I wish everyone could enjoy this round and have good luck!

»
16 months ago, # |
Rev. 3   Vote: I like it -49 Vote: I do not like it

--DELETED--

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

    You should know that codeforces contest >>>>>>>>>>>>>>>> any class. And you are already writing decent english i think you can easily skip one class. xD.

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

As an author, I hope you enjoy this round!

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

Hope to get positive delta this time. ALL the best guys!

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

This will be my "birthday-contest"✔️

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

As a tester, I hope you will enjoy the round! The problems are very interesting and educational. Good luck for everyone!

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

As a tester, I witness the great effort made by authors to make this round better. The problemset in fact changed a lot compared to the very beginning version and I believe the current version is worth participating.

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

As a tester, I encourage everyone to participate!

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

good luck QwQ

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

I hope this contest will help us to learn new things. wish everybody a good contest :)

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

Wish I could participate but I don't have time. I hope I can enjoy upsolving the problems!

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

As a chinese university student,I wish the constest be successful.

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

Hope this is my CM promotion contest !

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

    Hope this is my E promotion contest!

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

      You became an expert before me reaching CM! :(

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

I hope you will enjoy these interesting problems. Good luck to you!

»
16 months ago, # |
  Vote: I like it -62 Vote: I do not like it

Hey could i get some likes to remove negative contribution.

»
16 months ago, # |
Rev. 2   Vote: I like it -24 Vote: I do not like it

Well, just completed with implementation and basic questions of trie data structure, and I have already completed bst. Now that I have another tool in my toolkit, hoping to solve more questions this time.

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

    I don't know if you're talking seriously but if you are trie won't get you to pupil

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

      I never aimed for the pupil rank, at least not until I finished the basics of DSA. Earlier, I learned about stack, queue, and linked list, but they weren't useful for contests. So unknowingly, I got the assumption that maybe trees and graphs are more useful for contests. Anyhow, learning a new data structure opens up more ways to approach a problem, and even if I can't solve more questions, it is still valuable.

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

    We will be glad to see you making your tries to solve our Bazoka13 & Serval & Toxel problems. :P

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

As a tester, I hope that all the participants could enjoy the contest! Good luck & have fun! I'm more than excited to say that it's the first time I took part in the management of a CodeForces contest. Thanks Serval for inviting me! QwQ

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

    Do you mean that there will be some problems related to Arcaea in this contest? :)

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

      You'll see :P

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

      What do the cases of problem E mean?

      1: 1 2 4 -> ok that's simple

      2: 1279 -> notes of Fracture Ray FTR

      3: 344208 591000 4779956 5403429 -> scores which can be reached during Tempestissimo Beyond 11

      4: 1633 1661 1741 2134 2221 -> notes of the 5 hidden songs in Arcaea 4.0, in Beyond difficulty.

      Also, the calculation formula of problem E was adapted from Arcaea's MAX-Pure system.

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

Another Chinese Round :) Will it be hard?

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

Hope I can get back to expert :)

Edit: I appreciated the Paldea reference in C, but problem D is just way too hard.

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

I hope after this round I will stop being a prisoner of the blue

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

    If you dont become a specialist, you will deserve a lot of dislikes.

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

    Great perfomance in this round from you!

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

Does anyone know the reason for the contest time change?

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

I want to enjoy this contest together!

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

I hope I'll be able to solve problem C, Glad to learn new tips & trick apart from Practice & consistency

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

Hoping for a quality contest!

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

which is better starting with B to A or vice versa ?

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

Why the unusual time?

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

Thanks for 3 problems contest.

Please correct the blog.

You will be given 3 problems to solve in 2 hours.

»
16 months ago, # |
  Vote: I like it -58 Vote: I do not like it

Why is an O(m+n) solution giving TLE for problem C??

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

    Read rules of participation and don't post anything about contest when contest is going on

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

    you make a loop from 1 to 4e5 also number of testcaces is 2000. so u make 8e8 operations which is too large (8 seconds i guess)

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

Wonderful. But I think you meant Div 1 not 2.

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

Honestly, I dont think testers tested this round.

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

I know how to do D with $$$n + 1$$$ operators but with $$$n$$$ operators I can't. :DD

»
16 months ago, # |
  Vote: I like it -15 Vote: I do not like it

Easyforces, but tasks are still cool!

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

DEF are hard

How to solve E?

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

How solve D?

  • »
    »
    16 months ago, # ^ |
    Rev. 4   Vote: I like it +6 Vote: I do not like it
    One possible solution to D
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Excuse me I'm a bit confused, what is complexity of this? I think i read once it was O(n) but my and offical solution is O(n^2).

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

        There are at most $$$n$$$ operation(s), and in each operation, you need to simulate the XOR process, which takes $$$O(n)$$$ operations either, so the complexity is $$$O(n^2)$$$.

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

This contest gives me some Chinese amazing!

Translate: We will give them some little Chinese amazing

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

This round is 6 stages of grief

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

Can Anyone help how to solve C problem?

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

    HINT-> Just think of how much a number from range 1->n+m would contribe to the answer.

    It was a really cool question just try to solve it using this HINT if you still can't solve see the editorial as it would be available soon I guess.

    Hope you solve the question by seeing the hint yourself :)

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

    Just think in terms of contribution of each value when u form pairs. we need to know in how many arrays out of m+1 total , does a particular value occur. Then apply simple PnC for the arrays it appears in and for the arrays it doesn't appear in

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

WHY is TL on E so tight???

Edit: It turns out that my solution could be greatly optimized. It got AC in 1.7sec.

Edit2: My slow solution without optimizations works in under 3s. If the authors set TL to 4s, it would pass...

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

    maybe O(S)

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

      Maybe. But I think I saw some other $$$O(s_n*ln(s_n))$$$ solutions which passed.

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

    Try to avoid multiple long arrays. Due to the memory system, the pointer transferring would be slow if so.

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

      Yeah. I have already optimized my code(by avoiding useless calculations). Anyways it's a little bit sad:(

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

    https://codeforces.com/contest/1789/submission/194977514

    Here's my solution when testing the round, which runs below 1.5 seconds per test. Actually, as I use Z (modulo class), it should be slower than usual.

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

D is too hard,why

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

How to solve E? I've thought long and hard about how to optimize the complexity of my approach,which was $$$O(n \sqrt{s_n})$$$

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

    Mine $$$O(s_n*ln(s_n))$$$ solution got TLE 5....

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

ABC were good problems overall.

I just feel a bit dumb for missunderstanding C and solving it when you concatenate Ai, A(i+1)...Aj...

It is a pretty interesting problem though

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

    please explain your approach

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

      For which problem ? The missunderstood version or the C?

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

        not the misunderstood

        also please explain this part of the problem the number of distinct elements of the concatenation of Ai _ and Aj_

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

          OK so basically, let's consider the contribution each integer gives to the answer.

          Let's consider a pair (i,j) and an integer x. For x to contribute +1 to the value of (i,j), x must be in Ai or Aj. So you will first need to find, for each integer, the number of array it is in (you can do this by simply simulating the process and remembering at what point in time you last added the integer in the array).

          Then for each integer, either you chose (i,j) such that x is in Ai and Aj, either you chose (i,j) such that x is in Ai and not in Aj (or in Aj and not in Ai).

          Code: 194973423

          Let me know if something is unclear

          Edit: so for what you've asked, it means that you consider an array B(i,j) consisting of the integers of Ai and Aj and you then consider the number of distinct integers in this array B(i,j)

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

    wait, wasn’t it the point of the C problem? Or am I misunderstanding it too

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

      Nop. In C you consider the concatenation of Ai and Aj only, not of Ai, A(i+1)...till Aj.

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

Worst contest I have ever seen. I could not see the update in the start time :( (But problems were good.)

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

Div2 problems: A-B-C- E -E-F

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

read "not need to minimize the number of operations"

did not read "no more than n operations"

sadge :(

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

cp is hard

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

people from rank 200 to 2000 (in official standings) solved only three problems. problem set in unbalanced.

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

    Indeed. I would've risen by at least 100 rankings if I had solved C a half hour earlier (I solved it towards the very end)

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

A very hard contest..

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

My solution to E was very cancerous and prone to random errors (no idea). My solution works in $$$\mathcal O(s_n \log s_n + n)$$$ per test case with somewhat large constant factors (there are a couple of linear passes). Is there a faster solution? I didn't find a way to reduce to $$$s_n \log n$$$. You could always precompute sieve earlier instead of doing it implicitly in the computation from $$$x = 1$$$ to $$$s_n$$$ but I for some reason thought it would to be too slow and wouldn't work. In particular, I feel like $$$s_n$$$ plays a very big role in deciding the complexity, $$$n$$$ doesn't even matter. Is it possible to get $$$s_n \log \log s_n$$$?

[EDIT: OKAY, it passed at 1200ms, so I guess $$$s_n \log s_n$$$ implemented with a somewhat not large constant factor does pass.]

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

Again I'm Unable to solve problem C ಠ╭╮ಠ feeling sad,but I'll not give up Let's see how long it will take.

By the way problem C is very good.

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

How to solve D

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

worst D ever

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

If I've consumed 10 minutes less on problem D, I could have solved E. So unfortunate!

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

    What you do in years, I do in a day. We are not the same.

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

Can anyone please explain what is pi and qi in problem E?

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

    It doesn't matter at all, this is a hint:

    Separate the question into two parts:

    1. s[n]%x==0
    2. s[n]%x!=0
    • »
      »
      »
      16 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      I finally understood the problem statement. It could have been formulated in a much better way (f(x) is defined as the number of i (1 <= i <= n) for which there exists at least one pair of non-negative integers x and y that satisfy si = x * .. + y * ..).

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

i think you should find more candidate master, expert, specialist, pupil and newbie to test the round, instead of most of the testers' rating are > 2100.

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

    Agree

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

    how testers are found is : they make a announcement in the cf testing discord server

    And since, there is a direct correspondence with interest and strength, the testers are more likely to be higher rated.

    If a lower rated guy asked to test, he would be allowed to. Coordinators cant really go around Dming random people.

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

:C

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

Am I correct to think that D is in fact just super easy construction?

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

    When I look at the problem D today(I didn't participate yesterday), I think it's no harder than before, or even easier than common D.

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

    The solution is the same as the writer's one. Congratulations!

    But I noticed that there are some solutions with <100ms time limit, and I'm curious about it.

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

      194988517 this one runs in 171ms.

      last critical observation (mentioned in the editorial)
      • »
        »
        »
        »
        16 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        ok I know why. During the calculation of LCS3, a small trick is used: when the last digits of the first 2 parts of the string are not the same, then the case is not optimized and we can pass it. By carefully arranging the condition order, it could be fast.

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

    that's a cool solution and quite easy to understand, thanks for sharing

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

For D, is't there an O(n) solution?

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

How to solve E, when sn % x != 0.

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

    I think I got the problem down to counting numbers from the array that are in ranges of the form $$$\left[ k \cdot \lfloor \frac{s_n}{x} \rfloor, k \cdot \lfloor \frac{s_n}{x} \rfloor + k \right]$$$ for any $$$k$$$. I believe this should be $$$O(s_n \cdot \log{s_n})$$$ if done correctly, but I got TLE.

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

      Your solution is correct. Maybe you need to speed up your implementation.

  • »
    »
    16 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    One possible solution to E
»
16 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I stucked at A for an hour just because I thought that O(T*N^2) will result TLE...turns out that it don't

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

    A good heuristic is that you can do about 1e9 operations per second, so O(T * N * N), which would result in max 500 * 100 * 100 = 5e6, will easily pass. This can often be helpful when thinking about time complexities :)

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

      So we can actually run a for loop from 1 to 10^9 in a contest with TLE?? Something new learned. Thanks

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

        10% situations that u can do it with pragma

        90% is usually 1e8

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

        What Tima9 said and also depends on what and how many O(1) operations you do inside the for-loop.

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

      You should also keep in mind that finding gcd takes O(log n) operations, so, in the worst case, it is 500*100*100*20 = 1e8, which, as for me, is a bit too much for the first problem

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

screencast with commentary

Also nice problem F. But gifting arrays is cancer.

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

Any hints for D apart from the "obvious" observation below?

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

Explanation for D:

If a and b are both all-zero, we don't need any operation. If a is all-zero, we can't change a by operation, so if b is not all-zero, there's no solution. Also if b is all-zero but a is not, there's no solution because shift(a, k) must be different from a since k!=0, so a^shift(a, k) can't be zero. Therefore, we can assume there are some 1 in a and b.

Let min_a = the minimum position that a[pos]=1, min_b = the mininum position that b[pos]=1. We solve the problem by different situations:

--min_a<min_b. If we right-shift by k, we will flip a[min_a+k] and leave a[1...min_a+k-1] unchanged, so we can use right-shift (n-min_a) times to make a and b same on range [min_a+1, n]. Then let max_a = the maximum position that a[pos]=1. because min_a<min_b, we have max_a>min_a, so we can use left-shift min_a times to make a and b same on range [1, min_a].

--min_a==min_b. We still can let a[min_a+1...n]==b[min_a+1...n] first. Because min_a==min_b, we have a[min_a]==b[min_a]==1, so we can use left-shift (min_a-1) times to let a[1...min_a-1]==b[1...min_a-1].

--min_a>min_b. Now we need to left-shift a[max_a] to make a[1...max_a-1]==b[1...max_a-1], and then right-shift a[min_a] to make a[max_a...n]==b[max_a...n].

Explanation for E:

First, we find maximal blocks [l, r] such that floor(s[n]/x) is same for x in range [l, r]. Let a=floor(s[n]/l), then for x in [l, r-1], we have ceil(s[n]/x)=a+1. Let's check how many s[i] can be represented as sum of several a and (a+1). In fact, only numbers in these ranges satisfy the condition: [a, a+1], [2*a, 2*a+2], [3*a, 3*a+3], ..., [(a-1)*a, (a-1)*a+(a-1)], [a*a, s[n]]. We can use prefix-sum to count them, and multiply it by sum[l, r-1]=(l+r-1)*(r-l)/2. Then for x==r, if ceil(s[n]/r)=a+1, we just change sum[l, r-1] to sum[l, r]. If ceil(s[n]/r)=a, we need to check how many s[i] can be represented as sum of a: we just need to check all multiples of a. (My upsolve submission for E: 194975227)

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

When can we expect rating changes to occur?

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

great F

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

Why can you come up with problem E during playing music games? Is there any story-like problem statement?

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

yaa , problems are really good

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

It seems that the difficulties of some constructive problems like D are often underestimated.

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

What is the edge case in problem D that gives this many fst??

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

The data of question C is weak. Someone memset in every test case and he got accepted.

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

    memset for the array with a length of 400000. It's wrong at all.

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

      It's normal, even though memset is $$$\mathcal{O}(n)$$$ in theory, it's very fast in practice. Doing $$$t = 10^4$$$ memset over array of length $$$n = 2 \cdot 10^5$$$ is fast enough.

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

        I know. I used to be able to hack such code, so I usually thought the data was not strong enough. If the data is very strong and can't hack it, then I'm sorry for my excited remarks.

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

Started the contest late because you thought it will start at 20:05(IST) gang:(

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

You can find the editorial video for the problem C on my channel.

Problem C: https://www.youtube.com/watch?v=7nYE42FZzN4

wishing positive deltas to everyone :)

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

What is the expected rating for C?

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

Вопрос по задаче А. Что я не так делаю? Отсортировал массив, нашел для всех префиксов ноды. Потом иду по массиву нодов и смотрю если нод больше длины, то ответ нет. Если для всего массива условие выполняется то ответ да. Конкретно на примере: есть массив 1 4 2 6 сортирую его получается массив 1 2 4 6 для его строю массив нодов 1 1 1 1. Каждый текущий нод меньше текущей длины значит массив хороший. Может кто подскажет контрпример. Вылетает на 231 тесте, а его невидно.

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

    Непонятно, зачем тут нужно сортировка? Ты же понимаешь, что у тебя для 7 14 15 будет ответ "no", а если переставить как 7 15 14 то будет "yes"

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

      7 14 15 нод 7 и 14 равен 7 и это больше двух значит массив плохой. Я ещё проверяю и для реверсированого массива 15 14 7 здесь ноды 1 1 1. И это ответ yes

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

        Ладно, я привел плохой пример, но понятно что нет причины сортировать числа.

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

        7 14 15 20

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

How are you supposed to find the solution of problems such as C in a reasonable amount of time? I participated in a lot of contests (this is a new account), and my weakest point has always been spotting these small "tricks" and "observations" that these problems require in order to be solved.

Before saying the "duuh, just practice!", I want to say that I tried practicing a lot, trying to understand the solution of the problems and the whole process of finding it, but for me it's still so hard to see the solutions of problems like these.

I couldn't find it during contest, it took me like 2 hours after that to see the solution is that you must know at the end how many times does each element appear throughout the whole transformations over all arrays, and from that you can calculate the solution. But the thing is, I just stumbled upon this randomly, because I tried different ideas that didn't work, it wasn't because there was some heavy thought to it. I find it frustrating that after years of trying (again, this is a new account, I used to be 'expert' rating) sometimes I can't even solve C problems, while other participants who are newer to this just finish it in like 20-30 mins (or even less).

Am I too stupid for this?

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

    As a CM, I even couldn't solve some problems between B-D for several times (and that's why I've dropped from master). I think everyone will perform badly at some times, so cheer up please.

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

    Man I feel this so much, and honestly, I don't know any better advice than to practice more and don't look at tutorials :/

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

    The trick is to break down the problem, first into any solution then optimize it. Here, I will perform it on problem C.

    We need to transform into a palindrome, right? We need to change a segment so that our thing becomes a palindrome. Obviously, we could just check every possible change in O(n^3) complexity but that's too slow. Here, we can make use of something that we know — the symmetry. A palindrome is, by definition, symmetrical so we can notice that changing the same segment in the first half or its mirrored counterpart in the other is virtually the same for the purpose of the solution. That also means that we will only ever change something on one of the halves (because if we were to start our segment in the first half and end somewhere in the second one, we might just as well not change the middle parts and reduce the operation to changing only in one half. So here we are, we reduced it only to a half. What does that mean? That means that we need to change every single bit that isn't equal to the mirrored counterpart in the other half. Now, when is that possible? When all of those form a single segment and checking that is really easy.

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

      That's B, not C

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

        oh, ye, my bad

        Anyways, for C then. Obviously, we can just try and merge every 2 arrays and count the distinct numbers but the complexity would be O(n^2 * m) which we cannot afford. Even if we had a magical box that would merge arrays in O(1), we would still have an O(nm) solution. That means that we need a much different approach than testing all combinations. We can see that the arrays change by one number at a time and for every number that appears during the whole thing we can denote when it appears and disappears (we can do that as numbers are pairwise distinct). Using that information, we can see in how many arrays the number appears. That allows us to count the score for each number (there are max n + m distinct numbers) and then conunting in how many combinations the number appears (that's just combinatronics, you can do it many ways)

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

      the general idea is that you try and find every single, even useless consistency you can and note them down until you find something that is useful

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

    Well, you just move from one idea to another until it works

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

Had 6 WA's because I missed one return statement :(

Anyways, got AC on D 2 min before the contest ends :)

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

It's good to be cyan :)

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

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

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

became cyan today!!

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

O-oooooooooo AAAAE-A-A-I-A-U- JO-oooooooooooo AAE-O-A-A-U-U-A- E-eee-ee-eee AAAAE-A-E-I-E-A- JO-ooo-oo-oo-oo EEEEO-A-AAA-AAAA

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

Can someone please explain why these 2 solution differ only in one operation that is theoretically the same in both cases but one gives wrong answer ?

correct one: https://codeforces.com/contest/1789/submission/194991180

wrong one: https://codeforces.com/contest/1789/submission/194991257

ps: the difference is where I initialized ans

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

    Your wrong one has parenthesis around ((m + 1) * m), which evaluates the inside first using 32-bit integer, and hence it overflowed. Your correct one evaluates from left to right and using 64-bit integers, which will not overflow.

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

      Thank you very very much!!! So if I understand correctly if I will always write like that : 1ll * (int variable from expresion) it should always work ?

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

        Yes, or you can just use long long for all your variables, because usually you would have enough memory to do so.

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

For problem D, I use boost/dynamic bitset to allocate dynamic size. But it's not accepting on cf compiler. What can I do? Here is my code https://codeforces.com/contest/1789/submission/197297649