FBI's blog

Codeforces Round 981 (Div. 3)
By FBI, history, 3 days ago, In English

Hello Codeforces!

I am pleased to invite you all to participate in Codeforces Round 981 (Div. 3), which will start on Oct/24/2024 17:35 (Moscow time).

The format of the event will be like any Div. 3 rounds:

  • 6-8 tasks;

  • ICPC rules with a penalty of 10 minutes for an incorrect submission;

  • 12-hour phase of open hacks after the end of the round (hacks do not give additional points)

  • after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated

  • by default, only "trusted" participants are shown in the results table.

I encourage participants with a rating of 1600+ not to create new accounts but to participate unofficially.

Only trusted participants of the third division will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as a trusted participant of the third division, you must:

  • take part in at least five rated rounds (and solve at least one problem in each of them),
  • do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600 (or you are a newcomer/unrated), then the round will be rated for you.

Also, it will be a round with unrated register. If you already registered as rated participant you can change registration type here.

I would like to thank

Good luck!

Upd: Editorial is out.

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

»
3 days ago, # |
  Vote: I like it +6 Vote: I do not like it

Auto comment: topic has been updated by FBI (previous revision, new revision, compare).

→ Reply
»
3 days ago, # |
  Vote: I like it -43 Vote: I do not like it

As a participant, I hope everyone reach newbie after the contest.

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

cat

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

finally a div 3 after a month, lets go!!!

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

FBI!Open your mind!

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I. WILL. REACH. PUPIL. AFTER. THIS. CONTEST ( else I'll quit cp touch grass and get a life )

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

How to get +200 in this round?

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

What the heck?By FBI?

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Ciallo～(∠・▽< )⌒☆

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

FBI Contest!

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

As a participant... oh wait? I cant be? rip I have class at the time

Ill be sure to virtual tho

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

hope to reach pupil after this

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

Finally a contest with usual time.

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

As a tester, I would like to say the Chefir is a very interesting cat.

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

for what div3 ? to make it unrated how previous div4? #mike_fix_cdf

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

As a tester, I would like to say that all the tasks are interesting, and Chefir in the photo is very cute.

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

dog

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

Hello! I was a bit late with testing the round, I have sent a message with the feedback, but I am worried that my feedback won't be seen, so I decided to also leave a message here

→ Reply
»
3 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Waga bakuretsu mahou wo kurau ga ii! EXPLOSION!

→ Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

my max rating is 1190, hoping that i can achieve 1200+ after this contest

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

I think I can cross $$$1400$$$ before next Div. 4 round. Since, I opened the account, there's not a single Div. 4 Contest. However, attending straight into Div. 2 helped me to improve my skill quickly.

Anyway, What's the score distribution?

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

    There are no score distributions for ICPC styled contests, where each problem is weighted equally (no individual score per problem). Div 3 and Div 4 contests are ICPC styled contests.

    → Reply
»
2 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can I go back to being a Pupil?

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

cat will help to increase rating

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

What a nice name--"FBI"...

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

As a tester, I hope no one will use AI

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

    Just a thought. Can't AI's just partner up with codeforces and not answer the questions during the contest?

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

      I think it is not that easy. If it was, it would be already ig. But it would be fine

      → Reply
»
2 days ago, # |
← Rev. 4   Vote: I like it +15 Vote: I do not like it

Knock Knock !!!

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

To qualify as a trusted participant of the third division, you must: do not have a point of 1900 or higher in the rating.

did you mean 1600?

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

as a tester, this round has problems

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

My greatest dream has become a Div3 not at 17:35. I'm very busy at this time every day , All div3 at this time, why ?

→ Reply
»
44 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Bro only sets Div 3!!!

→ Reply
»
43 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

LETS GET IT GANG!!!

→ Reply
»
42 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

eyuuuuuuuuuuuuuuuuuu

→ Reply
»
41 hour(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Can I pet the cat :)

→ Reply
»
39 hours ago, # |
  Vote: I like it +27 Vote: I do not like it

As a tester, good luck have fun

→ Reply
»
39 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

cant wait to get Pupil rank!

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

Greetings Chefir!

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

As a tester, I respect Chefir orz

→ Reply
»
35 hours ago, # |
  Vote: I like it -19 Vote: I do not like it

Can you provide problems Rating Range?

→ Reply
»
34 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I would love to see more photos of chefir

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

Is there a way I can submit during contest if I forgot to register before the contest started?

→ Reply
»
32 hours ago, # |
  Vote: I like it -7 Vote: I do not like it

Thanks for problem B! In all seriousness how is it even possible to screw the problem statement that bad??

→ Reply
  • »
    »
    31 hour(s) ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    I will be personally reading all your problems when (if) you will be hosting a competition someday. Have a great day.

    → Reply
    • »
      »
      »
      30 hours ago, # ^ |
      ← Rev. 3   Vote: I like it -6 Vote: I do not like it

      It seems like I was the only one that had trouble understanding the problem. But still I believe the statement before the change was bad and why you get offended(I know it is lot of effort to organize/make contest and I respect that)."It is known that at every point in the valley, the heights are less than 0","height of each spike","she can select a square area of mountains and increase the height of each mountain"...

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

      Why do you have to be pricky about it, bad is bad. You went from mountains to spikes in no time.

      → Reply
»
32 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I was able to solve 3 problems for the first time in a CF contest :)

→ Reply
»
31 hour(s) ago, # |
  Vote: I like it +12 Vote: I do not like it

Nice F,G. No clue where to even start.

→ Reply
»
31 hour(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

problem C is just wow.

i have no word

→ Reply
  • »
    »
    31 hour(s) ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    authors can really surprise you every time with how bad they are at determining the level of the problem

    → Reply
  • »
    »
    31 hour(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You just had to solve it from the middle of the array, not from the start!

    → Reply
    • »
      »
      »
      31 hour(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      wdym

      → Reply
    • »
      »
      »
      31 hour(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      could you tell me why my logic isn't working for problem C 287809023

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

        Although you are starting from the middle of the array, your approach is still wrong.

        The correct approach is to start filling a new empty array b of size n from the middle using array a. And calculate the disturbance in that array b.

        → Reply
»
31 hour(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

How to do C??

→ Reply
  • »
    »
    31 hour(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what i did. get all pairs. distribute numbers again greedily considering swapping a[i] with a[n-i+1] or leave them at their original positions.

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

      why does this work

      → Reply
      • »
        »
        »
        »
        27 hours ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        It’s based on a simple exchange argument proof. Basically, at each step you have 2 choices: swap a[i] and a[n-i+1] or not (dp works here too).

        Assume a=[3,3,7,5,3,9,1,7,4], and we are considering swapping a[1] and a[7], in this case, swapping or not leads to the same optimal answer we can get for a[0…2] and a[n-2…n] but this answer is independent of the optimal answers we can get for a[3..n-3].

        Therefore, we calculate the local optima we can get at each step hoping it leads to the global optima. Hope this helps ;)

        → Reply
  • »
    »
    31 hour(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ll i(1) , j(n-2) ;

    while ( i < j) {

    if ( v[i]!=v[j] && (v[i-1]==v[i] || v[j+1]==v[j] )) {swap(v[i] , v[j]) ; }

    i++ ; j-- ;

}
    → Reply
  • »
    »
    29 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If n is odd, ignore the middle element. Now take 2 middle elements,let their value be 'a' and 'b'. Let the element to the left of 'a' be 'c' and element to the right of 'b' be 'd'. Note that if a!=c and b!=d, this is best you can get(zero disturbances), so do not do anything, otherwise just swap positions of c and d, because this will not worsen the answer, the number of disturbances will either remain same or it will decrease, in this way move to the end points of the array. At last, you have the modified array with you, just count the number of indices where a[i] = a[i+1]

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

    what i did, fix the first pair of numbers, and then greedily order the rest, and then fix the first pair of numbers in the opposite way, and then again greedily order the rest. and then just take whichever of these 2 is better

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

    I did the following: swap $$$a_i$$$ and $$$a_{n - 1 - i}$$$ if either of these elements are same as their outer elements. By outer elements I mean the element just left of $$$i$$$ and just right of $$${n - 1 - i}$$$ respectively. The final array by iterating till the centre of the array is the optimal arrangement.

    Proof: Consider an optimal arrangement. we will show that any optimal arrangement can be transformed to our preferred arrangement without worsening the answer at any part of the transformation. Starting from the outermost pairs of elements ($$$0$$$ and corresponding $$$n - 1$$$), let's say the first relative order of elements we encounter which is not arranged according to our preference is between $$$x - 1$$$ and $$$x$$$. Now if we swap all the elements from $$$x$$$ to $$$n - 1 - x$$$, they will preserve their relative order, and thus the disturbance for all the elements in the segment. In fact the only thing that changes is the relative order between indexes $$$x$$$ and $$$x - 1$$$ and the corresponding pair on the other side of the centre. So the overall answer will only change due to the change in this part, which we can easily show, will not worsen if we swap it. We can continue to find such out of order indexes and swap them to our preference and none of these flips will worsen the answer.

    Thus, irrespective of the optimal arrangement, we can transform it into our exact arrangement, and the disturbance never got worse. Hence our arrangement algorithm in fact provides optimal arrangements itself.

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

      what is the difference between optimal and preferred arrangement ?

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

        By preferred I mean the arrangement that you propose to be solution, and the optimal is a hypothetical arrangement which has the optimal answer, but not necessarily same as your proposed arrangement. By the end of the argument the goal is show that the preferred solution is optimal itself. Note thatseveral different solutions nay all be optimal, you just need to show yours is one of them.

        → Reply
»
31 hour(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

Was F really that easy (~1500 submissions)? I've been staring at the question for the last 1.5 hours and can't think of anything.

→ Reply
  • »
    »
    31 hour(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ig there was pattern through which we had to only find first no divisible by k...but after % operation idk how to check if original no was divisible by k

    → Reply
  • »
    »
    31 hour(s) ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    F is oeisforces. Basically you need to find G(1, k). G(1, k) <= 2 * k. G(n, k) = G(1, k) * n.

    → Reply
  • »
    »
    31 hour(s) ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Fibonacci mod k always has a cycle. You just find the cycle length and then answer is simply a multiplication of the cycle length times n modulo 1e9+7.

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

    no wondering, F was ChatGPT solvable with single attempt

    → Reply
»
31 hour(s) ago, # |
  Vote: I like it +6 Vote: I do not like it

Born to make problems for div2. forced to make problems for div3.

→ Reply
»
31 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest. Got to learn about fast doubling method in finding Fibonacci numbers in logn time complexity. Wonder if it could be used in F ? :/

→ Reply
»
31 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Good job, guys. Very nice contest!

→ Reply
»
31 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

what's wrong in my F .

We just need to multiply Pisano period of k with n in mod ? Right .

I am Getting this 998488007 instead .

→ Reply
  • »
    »
    31 hour(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You will

    → Reply
  • »
    »
    31 hour(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    There can be more than one Fibonacci number having $$$0$$$ mod $$$k$$$ in one Pisano cycle. Your answer will only work when there is exactly one $$$0$$$.

    → Reply
»
31 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Even though I will be losing rating again, but great contest!!

→ Reply
»
31 hour(s) ago, # |
  Vote: I like it +3 Vote: I do not like it

Great contest, but sadly D is literally on leetcode

→ Reply
»
31 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Implementation Forces

→ Reply
»
31 hour(s) ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

I solved F assuming that the period of "0" could be different, depending on the first term of the sequence ((0, 1, 1) is different of (0, 2, 2) for k = 4, for example), and this led tosome more unnecessary thinking and code, instead of just finding the first "0" and multiplying the answer by n. Now I see by bruteforcing all k's the period is always equal.

→ Reply
  • »
    »
    31 hour(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can u plz share how did u find first 0?

    → Reply
    • »
      »
      »
      31 hour(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      bruteforce. I tried for all k's and found the first 0 in less than 2*k operations.

      → Reply
      • »
        »
        »
        »
        31 hour(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        maybe a dumb doubt but fibo no would have been %. How to check if its divisble by k?

        → Reply
        • »
          »
          »
          »
          »
          31 hour(s) ago, # ^ |
            Vote: I like it +2 Vote: I do not like it

          You can do like this for all k

          code
          → Reply
    • »
      »
      »
      31 hour(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ig there's a method called Pisano Period wiki link

      → Reply
  • »
    »
    31 hour(s) ago, # ^ |
      Vote: I like it +35 Vote: I do not like it

    Sequence $$$(0, x, x, ...)$$$ is $$$(0, 1, 1, ...)$$$ multiplied by $$$x$$$, so period is the same ($$$gcd(x, k)$$$ is always $$$1$$$).

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

      This is making more sense now, if $$$gcd(x, k) \neq 1$$$ the sequence wouldn't be periodic (would never be "1" in $$$(mod\ k)$$$ again).

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

      You can also use $$$F_{s+t}= F_{s-1}F_t + F_sF_{t+1}$$$ to show that zeros are evenly spaced.

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

      Didn't understand how we're able to conclude that $$$gcd(x,k)$$$ is always 1

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

        Both $$$fib[n]$$$ and $$$fib[n + 1]$$$ are divisible by $$$d$$$, where $$$d = \mathbb{gcd}(x, k)$$$ and $$$n$$$ is position of first $$$0$$$. Using the Euclidean algorithm we can deduce $$$fib[n - 1] \mod d = 0 \implies fib[n - 2] \mod d = 0 \implies ... \implies 1 = fib[0] \mod d = 0$$$, so $$$d = 1$$$.

        → Reply
»
31 hour(s) ago, # |
  Vote: I like it +39 Vote: I do not like it

Am I the only one who swapped operations in G and ended up solving that for no reason xD

→ Reply
  • »
    »
    31 hour(s) ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I wasted 30 mins doing the same and then realised I have been solving the wrong problem.

    Result: Left the contest XD

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

    What is meant by that?

    → Reply
»
31 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the follow up for F, i understood it will have a modular cycle, upon some search and reduction i can deduce the : nth fibonacci number as f(n) = (((1 1) (1 0)) ^ n - 1) * (1 0), but how to make progress with this. Any help will be appreciated.

→ Reply
  • »
    »
    31 hour(s) ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    for all k, we can find the first "0" element by linear number of calculations. I bruteforced all k's from 2 to 100000 to find out the maximum number of operations, and that's always lower than 2*k (Didn't prove the general case). For some reason this period is always equal for all k <= 100000 too.

    Here is proved by AC 287807845

    → Reply
»
31 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the order of swapping in 3rd question or simply what was the logic behind this question, I tried a lot but didn't got the answer.

→ Reply
»
31 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Great contest, mainly E, still figuring out how to optimise E..

→ Reply
»
31 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

When does the Editorial will publish?

→ Reply
»
31 hour(s) ago, # |
  Vote: I like it +8 Vote: I do not like it

The problem statements were so poorly worded and sample I/O was not explained. For example, in problem B, you talk about mountain and then suddenly ask at the end about spikes. Mountain is defined to have positive height, but a square of mountain can have lakes (that have negative height). Why even write a legend if you cannot be consistent about it in the very problem statement? sigh

→ Reply
  • »
    »
    31 hour(s) ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    I have the same thoughts, the spikes confused me a lot, and I wasted 15 minutes trying to understand it.

    → Reply
»
31 hour(s) ago, # |
  Vote: I like it +4 Vote: I do not like it

F was a sadistic problem

→ Reply
»
31 hour(s) ago, # |
  Vote: I like it +23 Vote: I do not like it

What the hell is problem C

→ Reply
»
31 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

For E. I got TLE on TC 5, how can I further optimize this?

Submission: Link

→ Reply
»
31 hour(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

Please add a note or explain at least one of the test cases. I am not asking for an explanation on every test case of the question, but as a beginner, some questions can be challenging for me to understand. I often look through the test cases and notes to get an idea about the question. Again, I’m not suggesting you add explanations for Problem A; I suggest starting with at least Problem B.

→ Reply
»
31 hour(s) ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

Any hints on C and D? My brain is deep-fried and cannot think clearly anymore

→ Reply
  • »
    »
    31 hour(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    C : Think of a swap as penalty increase, no effect on penalty or penalty decrease. Penalty increases after a swap if the ai != ai+1 and we swapped in a penalty value. So we only swap when ai = ai+1 as it will either decrease penalty or will keep it same. I don't know how to explain better than this.

    D : Prefix sum map int -> int. store the last index where the sum appears. Iterate from beginning and if you find some sum again update its last appearance and increment ans.

    → Reply
    • »
      »
      »
      31 hour(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      damn I miss the map part... I was completely stuck at D and have no mood for C. Actually thought the same idea but have no time (about C)

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

      I can't solve C, can you explain or hint more?

      → Reply
»
31 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

NEED MORE DIV3s PLEASE CF-SAMA

→ Reply
»
31 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Greedy Forces

→ Reply
»
31 hour(s) ago, # |
← Rev. 3   Vote: I like it +46 Vote: I do not like it

who else when $$$k=1$$$ printed $$$n$$$ instead of $$$n$$$ $$$mod$$$ $$$10^9 + 7$$$ ?

→ Reply
»
31 hour(s) ago, # |
  Vote: I like it +2 Vote: I do not like it

f is easy to find in google, d < c, excellent round, thanks fbi, now i prefer the KGB

→ Reply
»
31 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

G : Try to solve offline....... For a pair ( v , k ) , find node k distance up from v , now if I go up to a node x , ans of query can be level[v] + ( "distance of deepest leaf node from x found so far" — level[x] ) . we can create a array on the basis of inTime of nodes , and use it to find maximum in a range from l to r using a max segmentTree . l : inTime[u] : u nodes after k jumps up from v ( use binary lifting to make it fast ) r = inTime[v] .As soon as a node is done , update its value with — inf in segmentTree

Just want to know is it somewhat related to Heavy Light Decomposition.

Sorry for my weak English

Refer to code

→ Reply
  • »
    »
    31 hour(s) ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    why are you thinking about hld being gray?

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

    i also want to know "Just want to know is it somewhat related to Heavy Light Decomposition?"

    → Reply
»
31 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the solution to F?

→ Reply
  • »
    »
    31 hour(s) ago, # ^ |
    ← Rev. 3   Vote: I like it +8 Vote: I do not like it

    Just find first index of fib for which $$$fib[ind]\%k = 0$$$ and then $$$ans = n*ind$$$. That's it

    → Reply
    • »
      »
      »
      31 hour(s) ago, # ^ |
      ← Rev. 2   Vote: I like it +6 Vote: I do not like it

      I see, thanks. So do the zeros always repeat after a set amount? And is there a proof for that?

      → Reply
      • »
        »
        »
        »
        31 hour(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yeah they always repeat like for 4 after every 6 it will repeat

        → Reply
      • »
        »
        »
        »
        31 hour(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes. After the first index where rem=0, the reminders tend to again follow the fib sequence from the beginning

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

          It seems like some of them aren't the Fibonacci sequence exactly, but eventually it goes back to a Fibonacci sequence after a few zeros. Like this is how it is for $$$5$$$:

          5

          After $$$4$$$ sub-turns, it eventually went back to $$$1, 1, 2, 3, 0$$$ and just continues looping through the $$$4$$$ sub-turns.

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

            Yeah, it's not exactly fib sequence, but multiple of fib sequence and the multiple is not a multiple of k so it doesn't actually affect the period of 0

            After first 0, its $$$3*(1)\%5, 3*(1)\%5, 3*(2)\%5, 3*(3)\%5, ...$$$

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

        The period of multiples of k will not exceed 6*k wikipedia

        → Reply
»
31 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

for E, if you also have to print the swaps, then it's similar to https://cses.fi/problemset/task/1698

→ Reply
»
31 hour(s) ago, # |
  Vote: I like it +5 Vote: I do not like it

C is incredibly hard as a 3C

→ Reply
»
31 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Fidelity Bravery Integrity

→ Reply
»
31 hour(s) ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

greedyforces. guessforces. readforces.

pA: The problem statement is so long that I need a lot of time to read the statement. Also, no explain testcases makes me more confused. I can't understand who wins on problem A, and I need a lot of time to read the statement again and again. I also don't like the output of A, why not just output yes/no instead of the LONG name?

pB: "If aij<0, then THERE is a lake THERE". Why 2 THERE in the same santence? "With her magic, she can select a square area of mountains and increase the height of each mountain on the main diagonal of that area by exactly one." The sentence is too long, u should split the sentence by "," and ".".

pC, pD, pE, pF are all GREEDY. Why put so many greedy in a contest? To make people guess the ans again and again? pF is the most painful problem among them.

To do pF, we first need to guess that there is a cycle of the remainder of k. Then, guess the upper bound cycle length is bounded by a multiple of k. We just guess everything in pF, that's stupid. Also no need for a ll n in the input, which makes me lose my AC for k=1. Honestly, What do we learn from this problem? Guess? Take care for output of k=1 bcz n is too big?

I learn nothing from this contest. I just guess and guess all the ans from all the problems. Problem statements on pA and pB are fxxking long and really weird, which made me suffer. We DO need the contest to test our CP ability, instead of reading problem statements/guess the ans/avoid the unnecessary traps.

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

    If you think greedy is guessing, then maybe you can try learning how to prove your greedy solutions ;)

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

      no, proofs are too hard, i think he’s better off improving at guessing

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

        thats true for increasing your rating, but he mentioned he learnt nothing from the contest, and trying to prove any greedy solution is of course an enlightening activity.

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

          Yeah, try to prove the greedy of F. That may need a lot of papers. Nobody cares about the proof of greedy during the contest, and also nobody will prove the greedy after the contest. I am just telling the truth.

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

            F is not even greedy lmao

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

              Not greedy, sorry for the wrong word. I mean to guess everything in F. No proof can be provided during the contest, and that remainder property of Fib is not useful in CP.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                15 hours ago, # ^ |
                  Vote: I like it +12 Vote: I do not like it

                Yea well I do agree that thinking about proofs is bad during contest. But thinking about it post-contest can actually help improve your intuition so that you can guess better next time. As such, no problem is useless you have seen it before :)

                → Reply
  • »
    »
    30 hours ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it

    Generally agree your perspective on the extremely boring A, B, D and F with awful statements or ideas. But it seems that C can be solved by linear DP and E can be abstracted into a relatively interesting graph problem(about how to optimally cut the long loops). However despite the multiple solutions, this round is still too relied on key observation and guessing as you just said, and F is the most weird amongst all the unreasonable ones. It's just like a guessing game rather than a true algorithmic problem combined with number theory.

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

    I read the problem A half way, saw the test cases and assumed (idk why i risked it) that its just odd/even and AC.

    B was stupid too, I was baffled by the lengthy and confusing statement. C was also not clear in the first instance. went straight for D. really a guessforces.

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

      even i guessed it but still wanted to verify it, there is often bias about these A,B problems.

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

    I feel better after using DP on C instead of greedy. The problem has a single observation to pair the disturbance of i with the disturbance of n-i, instead of n-i+1 as one initially does. The problem also leaves behind one of the repeating pairs count in the description to allow this. You need this "creativity" to solve the problem, regardless of what everyone else says about "proving greedy" or whatever. Fundamentally, it's about math creativity. This means that for the front half of the elements we pair with the element in front and for the back half we pair with the element behind. In doing this the problem of [2,n-1] becomes a subproblem of [1,n]. Then DP follows.

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

      Both DP and greedy have optimal substructure. If u find some optimal substructure, and say that "This problem is DP", then u are totally wrong. "creativity" is indeed greedy choice property.

      → Reply
»
31 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

loved it I got the idea of F but couldn't implement it out as I didn't focused that we just can brute forced it out man but was a great contest for me

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

hmm

→ Reply
»
30 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I was able to solve problem 2033F - Kosuke's Sloth by making an observation that numbers divisible by k occur at regular intervals in fib sequence (I don't know why)

https://r-knott.surrey.ac.uk/fibonacci/fibtable.html

Then you have to find first index i where fib[i]%k is 0 and another observation I made is that this index i is always less than or equal to 2*k. You simply multiply this index by n to get index of nth element divisible by k.

if you see the table in mentioned link, you will observe indexes —

divisible by 2 — 3,6,9....

divisible by 3 — 4,8,12....

divisible by 4 — 6,12,18.... (huh?)

divisible by 5 — 5,10,15.... (why?)

divisible by 6 — 12,24,36... (what?)

Is there a way we can find the first index using k itself?

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

    there is a fact about fibonacci numbers which says that if n divides m => fib(n) divides fib(m), so using this you can see why that property is true

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

      Thanks. I was not aware of this.

      → Reply
  • »
    »
    30 hours ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Brute force, since k <= 1e5

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

      That's what I did but there must exist some formula that directly gives us the first index divisible by k using k only. That is, f(1)=1, f(2)=3, f(3)=4, f(4)=6, f(5)=5, f(6)=12 and so on.

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

        I missed the constraint on k and was trying to calculate it based on $$$m=p_1^{e1}* p_2^{e2} * ... * p_n^{en}$$$ then $$$a(m) = lcm(a(p_1^{e1}), a(p_2^{e2}), ..., a(p_n^{en}))$$$ and $$$a(p^e) = p^{e-1}*a(p)$$$, found those on OEIS

        → Reply
»
30 hours ago, # |
← Rev. 4   Vote: I like it -13 Vote: I do not like it

B's Statement is too long for 3B

C is hard for 3C

D is somewhat classic

I think F was in hand , if we just had better set and statements

→ Reply
»
30 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the idea of E?

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

    You can visualize this as a directed graph where every node i is connected to node P[i]. The given conditions will be satisfied only when all cycles in this graph have a length of 1 (that is i = P[i]) or 2 (that is P[i] = j and P[j] = i).

    → Reply
  • »
    »
    23 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Hint 1
    Hint 2
    Solution
    → Reply
»
29 hours ago, # |
  Vote: I like it +10 Vote: I do not like it

Is it just me, or did anyone else implement G , such that if you move from child to parent, your stamina doesn't decrease, but when you move from parent to child, your stamina decreases.

( basically, direction of travel was reversed :| ) .

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

    but even after that how to solve it?

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

      when we do it in reverse, I guess question becomes even more difficult than the question that is already asked.

      The question that is asked, for that I guess DFS + Segment tree is enough.

      The question that I was solving, we need to maintain monotonically increasing set of nodes, which always improve the answer.

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

        Can you guide me to the solution? How do I start with this one?

        Can we use dfs tree flattening? we can go upto k parents up, then we just want to figure out the farthest node from i within that subtree.

        Is this approach useful? too complicated? any help would be appreciated.

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

          Lets define few terms,

          1) Level of 'node' is equal to distance of current node from node-1.

          2) Maximum depth of the node — in the subtree of given 'node', what is the maximum length of any chain.

          Now do 2 parse DFS .

          First DFS

          In the first DFS, you can keep track of level of node, and maxDepthOfTheNode ( You just need to keep track of two maximums ) .

          Second DFS

          When we travel from 'parent' to 'child' node, we have to find, what is the maximum length chain, that is starting from the 'parent' node, and doesn't pass through 'child' node ( basically passes through sibling of the current child we are exploring ). You need to insert this value in the segment tree. ( Point update in max-segment tree).

          Then it is simple range query for last 'k' elements of the Segment Tree.

          Hope this helps.

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

    i thought that at first when i read it, but thats fairly trivial. edit: its not that trivial actually nvm

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

      IMO, the implementation is little tricky when we do it reverse. The implementation is very straight-forward, if you have max-sementTree template.

      The reverse of the question, was little edge-case involving.

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

        yea i just started thinking about it, and i just realized its not actually trivial at all. i believe segment tree is needed for both of the versions, and sadly i have no idea how to implement it or use it so i can only wonder :(

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

          I was unable to figure out, how the segment tree would help in reverse direction. Please elaborate idea. What values would you store in segment tree ?

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

            It is solvable and i solved it during contest before realizing I alongside 100s of others made the same misreading

            Solution : as in the other solution, we assume we have d_i a depth array calculated where d_i represents deepest node in subtree of i'th parent of v (which is not present in subteee of (i — 1)th parent of v)

            Now, we want to find the maximum of expression

            $$$i + min(d_i, k)$$$

            Find the last index $x$ where d_i >= k using Walk on segment tree. Then, either optimal index is $$$x$$$ or one of the indices $$$x + 1....$$$

            Calculating value for $$$x$$$ is easy, and for $$$x + 1...$$$, you can note thar the function becomes $$$i + d_i$$$ because $$$d_i < k$$$, and the segment tree we are already using for this version of the problem suffices

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

              exactly what I did bhai... But instead of using the segment tree, I had used monotonic set of nodes, which will always improve the answer. and then applied lower_bound search on those. couldn't think of SegTree based solution.

              Code for reverse direction

              While running sample test cases, I realised, I am screwed. Although it was good problem to solve.

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

can anybody tell why the code for G problem of this contest is giving tle its complexity is (n+q)logn https://mirror.codeforces.com/contest/2033/submission/287818878

→ Reply
»
29 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

I am sad

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

For the problem f, The proof of the solution is

Let F(i) be the first term when F(i)%k == 0, then the series from the ith term modulo k for every term (F%k) onward will be like F(i-1),0,F(i-1)*(1), F(i-1)*(1),F(i — 1)*(2), F(i — 1)*(3),... F(i-1)*F(i)

Now, we can can say that F(i — 1)%k != 0 since F(i)%k == 0 as we assumed, therefore the 2*ith term which is F(2*i)%k = F(i — 1)*F(i),.. Now carrying on forward, we can say that i,2*i, 3*i, 4*i,... will be the term when F(i)%k == 0.

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

    This is nice, but how do we know that there is no zero in between $$$F(i)$$$ and $$$F(2i)$$$. I was wondering what if $$$F(i-1)*F(j)$$$ is a multiple of $$$k$$$, where $$$j < i-1$$$

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

      The Fibonacci sequence modulo k is known to be periodic, with the period length called the Pisano period. This means that Fibonacci numbers modulo k will eventually repeat after a fixed number of terms. Once the sequence reaches F(i) (the first number divisible by k ), the subsequent terms follow a predictable pattern.

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

    Its a little unclear still. Can you explain a little more?

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

      Pisano period

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

        I read pisano period. But pisano period just says that there is a cycle. Not necessarily that the 0s also cycle.

        What if there are two zeros but unevenly occurring in the cycle, then the 0s don't cycle.

        For ex: Let's say the cycle length if 5 and the first, 4th and 5th number is a 0. Then the 0s don't form a cycle.

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

For the problem F ,

what is the proof for the following fact : I brute forced for all prime's up to 1e6 (p) to find index of the smallest fibonacci number that is == 0 (mod p)

here are the values up to 100

as you can see the value is at most n+1 , that allows for submissions like rainboy's to pass as they just naively find the first fibonacci number which is == 0 (mod k) and multiply it by n.

Does anyone has a proof for this , why does this work ?

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

    i do the same thing, and my function that does this was promptly named PROOFBYAC :D.

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

C was too hard for a div3C, totally made for guessing the solution. In D, you could have explained what you meant by non-overlapping, do you consider (a,b) and (b,c) to be non-overlapping? or do you consider (a,b) (b+1,c) to be non-overlapping? Its the former,which i got to know after a WA.

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

    totally made for guessing the solution

    Disagree with this. If you start solving the problem from the middle, the problem becomes quite simple I believe. If we consider the even case, we can fix the middle two elements in any order, because no matter how the middle two are arranged, we can always adjust the rest of the elements relative to them. Now once we fix the middle two elements, we start moving outward. Suppose we are at $$$l,r$$$ currently, now we just need to compare with elements $$$l+1,r-1$$$. If swapping $$$l$$$ and $$$r$$$ results in a better answer than not swapping, then we should definitely swap them. Instead of just swapping $$$l$$$ and $$$r$$$, think of each step as swapping the entire prefix till $$$l$$$ and the entire suffix from $$$r$$$ onwards. If we think of it this way, one can see that only the relationship between $$$l,r$$$ and $$$l+1,r-1$$$ is changing, everything else stays the same. Hence, it is always enough to look at the immediate inner neighbors, and swap if it improves the answer.

    I'm a little surprised that this problem has barely more solves as E. I was a tester and when I was giving virtual contest, this was actually problem B. While I did feel that this might be a little hard for a B, didn't think it's as hard as E.

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

      instead of just swapping land r, think of each step as swapping the entire prefix till l and the entire suffix from r onwards

      Could you explain this more?

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

        did you get it ?

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

        Assuming we have an array of 6 elements:

        a1, a2, a3, a4, a5, a6

        We can actually fix the middle two elements in any order because the two middle elements are a3 and a4. We can place a3 on either the left or the right. Wherever we decide to place it, it won’t affect our future choices because we can choose a2 and a5 however we want in the future. So, if a3 in the optimal arrangement should be before a5, we can leave a3 in its place and then swap a2 and a5, which will have the same effect as swapping a3 and a4.

        That’s what he means by prefix and suffix. If you decide to swap L and R, then whatever needs to be a neighbor to L after it’s swapped can still be its neighbor, and the same applies for R. disclaimer : I wrote this comment to better understand the problem myself so I might be Hallucinating

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

      I started from the beginning. The order of the first and last elements do not matter, so put them in any order. Then, while filling the positions (l, r), I compared them to the elements right outside (l-1, r+1), the position I filled in the previous step. This works, but I do not know why.

      Previous to this, I tried swapping each position and comparing whether disturbances decrease. I compared l with both neighbors (l+1, l-1) and r with (r+1, r-1). I got a score out of 4. If swapping decreases this score, then swapping is optimal. Else it's not. This did not even pass the sample test cases. Any idea why?

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

        because you are comparing and determining the current greedy optimal with something that might be changed in the future (l+1,r-1)

        → Reply
»
28 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please hack this solution?

https://mirror.codeforces.com/contest/2033/submission/287788123

Thanks!

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

    i doubt that anyone can, youre essentially just breaking down a big cycle into 2-cycles or 1-cycle, which is optimal.

    → Reply
    • »
      »
      »
      21 hour(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, but I thought that since I am using map, so maybe there might be some testcase that can cause a TLE? 1983ms runtime on a qn with 2s limit seems hackable no?

      → Reply
      • »
        »
        »
        »
        21 hour(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        yea it seems so, but im not really sure what makes it so slow in the last test. it seems that no matter the input, you will always do (n-1)/2 operations which means you will be accessing the map that many times, and i tried to hack like that, but that passes in 500ms. maybe when you have multiple test cases and make a new map and initialize it all over again or something like that

        → Reply
»
28 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Guys what would you suggest to learn or what do you think should be the mane focus on people like my that make it till problem B in div 2 and div 3. Like I know what DP is or Recursion. I've learnt about this topics and can I know on what field to use them but when I get a problem I have a great visualization on what to do but as soon as I get on to typing the code I get lost in stupid shit. What is your suggestion on solving this

→ Reply
»
26 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

why so many D's are getting Hacked ??

→ Reply
  • »
    »
    26 hours ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Because of unordered map I think.

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

    Overflow/underflow problems, I assume. You need to use a 64 bit integer map/set key as n = 10^5 and ai can be in range -(10^5) to 10^5, so total sum of a can be -(10^10) or 10^10, which are respectively less than INT_MIN and greater than INT_MAX. As such, I believe solutions that use a 32 bit integer map/set key will be prone to hacks.

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

      Below is a generator for hacking people storing their prefix sum in map/set with 32 bit integer key. It causes an overflow which results in the integer value '32704' to be stored in the map, then carefully adds negative integers until a final value is added to be equal to '32704'. This causes the bugged code to falsely find a prefix sum which doesn't exist in reality.

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

    Yeah, mine too got hacked.

    → Reply
»
25 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please hack my solution for C?

287837237

I just did mindless greedy.

→ Reply
»
23 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

div 3 more like div 2 lol

→ Reply
»
23 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

guys my solution got hacked, and i dont really understand how, and what is wrong with it, i'm new to codeforces, can anyone check and tell me why did it got hacked?

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

    change unordered_map to map.

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

      How does that actually work tho , like could you please give me an example of the difference or a test case for instance

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

        For unordered_map worst case time complexity for searching can be O(n) while using map it is O(logn).

        See test case 12 of problem D.Unordered_map will give you TLE.

        → Reply
»
23 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Does anyone know how to approach problem F intuitively without any googling or guessing the idea. Like ok maybe I can guess the first occurrence of zero must be periodic for all zeros, but how to prove this simply?

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

    This is how i solved: First observe/guess that when you find the first number divisible by k, its just periodic and every x-th number is divisible by k. Then I try and calculate the first k fibonaci numbers and assume that its enough to find the first divisble number. That fails on test cases, but k+1 passes, so i submit. Get WA on test2. Ok so lets just assume that we can calculate it in some y*k time where y isnt too big, and if i just calculate until i find it, it should pass time limits. Submit and get AC.

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

      Ya I thought of that in contest, but here you are still making the guess that after you find the first divisible by k number, you then just output n*k. Is there a proof on why this 0 must be periodic? Like maybe let the first position be x, how do you know there is not also a 0 between x and 2x? This is the uncertainty I had in contest which made me hesitant to submit.

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

huge part of solving problem C is realizing that it's a div 3 C which is a skill that only needed in code forces

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

    After upsolving this div3C I actually doubt I'm a pupil (Dropped to newbie after this contest). Time to climb up the rating again...

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

      I upsolved also but still didn't learn anything from it there is this comment which I couldn't understand yet but I will try more

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

        Yes, we need to try to get better. The newbie-pupil struggle...

        Btw the comment of that tester actually correct/good instinct. Good note

        → Reply
»
21 hour(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

whats the point of questions like F that require some kind of math theory and code that can be easily generated by gpt. I can assure you atleast 80 percent of the people who did it googled/GPTed it.

→ Reply
  • »
    »
    21 hour(s) ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    git gud and stop crying

    → Reply
    • »
      »
      »
      21 hour(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      get good at using GPT? Sure.

      → Reply
      • »
        »
        »
        »
        21 hour(s) ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        how about spending your time learning to solve problems instead of crying about not being able to solve trivial problems

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

          yes very trivial. Just know about some niche math theory. Stop trolling mate. lol.

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

    FYI, googling things is not considered cheating

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

    I solved it with a pen and a notebook in $$$7$$$ minutes (though not fully giving concrete proofs before coding, trusting my intuition), so umm.......

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

      can you go through your thought process? Did you prove the existence of pisano period in 7 minutes?

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

        Disclaimer: As said, I didn't fully prove it. It's just how strong an intuition proved to be in my mind to assert confidence.

        First, I see the periodic repetition in the sample, and the really questionable answer for sample case 3 (so close to mod, and given 1e18 was there, the operation should be something pretty simple).

        Then, I turn the notebook and draft some $$$k$$$. It dawns on me that it's truly periodic, except for $$$k = 2$$$ there's never a $$$[0, \frac{k}{2}, \frac{k}{2}]$$$ subarray in the modular sequence. The most concrete fact that pushes me into immediate coding is that Fibonacci sequence doesn't really take divisors into account, so in the perfect world, it should be something close enough to a normal random distribution of modulus, rendering the linear nature of the period size.

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

    I got my idea without googling I generated the Fibonacci sequence to check till 20th number and found that there will be cycle which is a fact I got to know later, but I couldn't implement it out in the contest

    → Reply
»
21 hour(s) ago, # |
  Vote: I like it -12 Vote: I do not like it

why did div3 not allow rating???

→ Reply
»
20 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

too unfortunate this 287855687 get wrong on problem C. I was soo close

→ Reply
»
18 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

good round, solved upto D hoping for pupil soon

got hacked on D for using unordered map though, upsolved using set.

overall a good performance on my part, performance of around 1200 (after hack), 1350 (before hack)

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

    how to know your new rate before the contest test end

    → Reply
»
18 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

why aren't people using two pointer to solve C

It's the approach I got during the contest and it's been accepted. After seeing post contest discussions I see a lot of people saying it should be solved using DP.

I will upsolve but I don't understand why didn't a lot of people solve it using two ptr during the contest.

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

I Will become a specialist in this contest. Lets go!

→ Reply
»
18 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

why contest unrated?

→ Reply
»
17 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help my G? I don't know why I got TLE on test 8, plz. 287869462

→ Reply
»
17 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

For F: https://www.geeksforgeeks.org/nth-multiple-number-fibonacci-series/ Added a few modulos and raised max n and got AC

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

    I was trying to find this code during the contest but I was not able to and couldn't implement out my idea :(

    → Reply
»
17 hours ago, # |
← Rev. 2   Vote: I like it -12 Vote: I do not like it

I was hacked in problem D. I already was unhappy by my performance in that since I was so close to submitting E, I derived the cycle but then failed on figuring out that it would (k-1)/2, I was trying k/2. But then D also got hacked because of something I can't figure out

Anyway,

I submitted this using an unordered_map which got TLE and was hacked :(

void solve() {
	int n;
	cin>>n;
	vll arr(n);
	cin>>arr;

	unordered_map<ll, int> mp;
	ll sum = 0;
	int ans = 0;
	fori{
		sum+=arr[i];
		if(sum == 0 || mp[sum] > 0){
			ans++;
			mp.clear();
			sum = 0;
		}else{
			mp[sum]++;
		}
	}
	cout<<ans<<endl;
}

Then I submitted using a multiset which got AC.

void solve() {
	int n;
	cin>>n;
	vll arr(n);
	cin>>arr;

	multiset<ll> mp;
	ll sum = 0;
	int ans = 0;
	fori{
		sum+=arr[i];
		if(sum == 0 || mp.count(sum) > 0){
			ans++;
			mp.clear();
			sum = 0;
		}else{
			mp.insert(sum);
		}
	}
	cout<<ans<<endl;
}

Isn't a mutiset slower than unordered_map?

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

    I think this passage Blowing up unordered_map, and how to stop getting hacked on it would be helpful.

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

      Yeah, just read it. Never thought STL could also be inefficient.

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

    Remember one thing donot use unordered map until and unless it is the only choice

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

      yeah. Learned a costly lesson. I think I deserved a rank around 3k. But cudn't solve E because of c/2 and (c-1)/2, got 6k rank. But then D got hacked, got 11k.

      So yeah, never using unordered_map or unordered_set again.

      Btw, did u get any idea about G?

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

        I am incapable of doing G as I haven't studied graphs properly yet know little basics only

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

guys that was my first contest and i've solved only one problem (first obv) and will i get rated after this?

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

    Yep, just have a bit of patience until testing is done.

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

Given the number of successful hacks for Problem D , it is so that deliberately the tests are weak so that the contestants can hack each other's solution and earn points?? JUST A POV :)

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

For problem E came up with this solution though cannot prove it and didn't manage to submit by some seconds :-))

Unfold

This basically tries to make permutation and "reverse-permutation" equal in <= N steps.

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

I got tle on test case 49 of D even after using custom hash in unordered_map.

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

I think question G is better than question F, question F can be written quickly by guessing the conclusion, and question C is also more difficult than question D and E.

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

When will the Rating's Be updated

is there any site that give the expected ones out

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

    Rating is already updated. You can use carrot extension.

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

Oh, NO. I want to regist but late!!

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

1259 still newbie T_T

→ Reply
»
11 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Arghhhh, why is https://mirror.codeforces.com/contest/2033/submission/287918494 TLEing for G? It's literally segtree + dfs which I hope is intended solution.

→ Reply
»
11 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the logic behind G

→ Reply
»
11 hours ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

UPDATE: the solution is correct except for the way I define the end of the range on which I calc dp table,
For example, if n = 5, we need to calc dp for 0, 1, 2
and if n = 4, then we need 0, 1 simply it's half-interval [0,ceil(n/2)) NOT [0,floor(n/2))
This line is wrong int limit = n / 2;

I tried to solve C with dp.
The idea is
dp[i][0] -- min shit in prefix [0, i] and corresponding suffix IF we do not swap at i
dp[i][1] -- same but if we do a swap at i

Clearly, or so I think, dp[i+1][0] can be computed from dp[i][0], and dp[i][1], same for dp[i+1][1]

But my code is not outputting correct result. Can someone help me identify the bug? is the approach wrong? or some bug in the code?

https://mirror.codeforces.com/contest/2033/submission/287926217

→ Reply
»
10 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone help me to get out of this i solved problem D during contest but it get's wrong answer on 9th test case while checking on updated test case then i change my data from int to long i though that might be the cause but now it is giving tle on test case 16 please help here is my code ````````````````````` int n = in(); long[] a = new long[n]; for (int i = 0; i < n; i++) { a[i] = inl(); } int cnt = 0; long pre = 0;

HashSet<Long> hs = new HashSet<>();
hs.add(0L);
for (int i = 0; i < n; i++) {
  pre += a[i];
  if (hs.contains(pre)) {
    cnt++;
    hs.clear();
    hs.add(0L);
    pre = 0;
  } else {
    hs.add(pre);
  }

}

out.println(cnt);

````````````````````

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

Can anyone help me with my submission for D, I use Java and I've noticed that I am getting tle if I use map.clear() in submission 287709751 but if I re-instantiate the map 287930490 it gets accepted.

Upd: Got it clear function just sets all entries to null by traversing the array and the size remains the same.

→ Reply
»
10 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

How can C be solved with binary search? I am asking because I noticed that problem C tags involved binary search for some time.
Also, I am curious to know how these tags are added. Is it detected somehow automatically from submitted solutions? I noticed that after I submitted my dp solutions, the dp tag was added again.

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

    Tags are added by people that can be "trusted" to handle tags properly, and by "trusted" I actually just mean people above a certain rating (I believe that would be CM)

    There actually was an instance when people mass-spammed tags on the D problem, and a similar thing likely happened on the C problem on a smaller scale.

    Circling back to the first question, if a binary search solution even does exist it would be slower than the intended solution for C (as shown in the editorial).

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

I was stuck at Verifying whether you are a human screen for more about 10 minutes. I tried giving the contest on mirror websites but for some reason, the problem statements weren't available. What is the point of having mirror websites if you can't access questions on them? By the time the page finally loaded there were already more than 7000 submissions on problem A

Such incidents of 1. Website not loading 2. Being stuck on the "Verifying if human" screen 3. Website crashing multiple times are getting more and more frequent.

MikeMirzayanov Look into this matter

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

How to solve G? Thank you

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

    Note that you can go to K-father from a vertex, and the answer is contributed by any vertex and the path of K-father.

    Let's define $$$dp_i$$$ means a vertex can go to its deepest son of $$$dp_i$$$ length, $$$cdp_i$$$ means a vertex can go to its the second deepest son of $$$cdp_i$$$ length(The paths do not intersect).

    You can get a new array $$$len_i$$$ means the longest path that the father $$$u$$$ of $$$i$$$ can reach without passing through $$$i$$$. It's either $$$dp_u$$$ or $$$cdp_u$$$.

    Now we want to know how long he could go. Note that $$$i$$$'s father $$$u$$$ contributes $$$len_u + 1$$$, $$$i$$$'s father's father $$$v$$$ contributes $$$len_v + 2$$$...

    So if we design $$$len_i$$$ as $$$len_i - dep_i$$$, our mission is to get the $$$\max$$$ on the path from the vertex and its K-father. When get the maximum of the path, add $$$dep_i$$$ back. Remember we have another choice is to go to the vertex's son. Just take the maximum value. Then use multiplication algorithm to solve it!

    This is my submission 287948215.

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

It confused me a lot. I thought my submission 287933697 is totolly $$$O((n+q)\log{n})$$$. Why I got TLE?

→ Reply
»
8 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

how did i do d,e,f but not c

→ Reply
»
8 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

How on earth is it possible? Problem D, TLE with std::unordered set but works all fine with std::set?

TLE-with-unordered-set

Okay-with-set

→ Reply
»
7 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi till when can we expect the text editorial ? Thanks ! @FBI

→ Reply
»
6 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by FBI (previous revision, new revision, compare).

→ Reply