Kirill_Maglysh's blog

Codeforces Round #935 (Div. 3)
By Kirill_Maglysh, history, 9 months ago, translation, In English

Pay attention to the unusual round start time.

Hello, Codeforces!

Codeforces Round 935 (Div. 3) will start at Mar/19/2024 11:05 (Moscow time). The problems are expected to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating of 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ICPC). Thus, solutions will be judged on preliminary tests during the round, and after the round, it will be a 12-hour phase of open hacks.

You will be given 8 problems and 2 hours and 15 minutes to solve them.

Note that the penalty for the wrong submission in this round is 10 minutes.

Remember, that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory 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, then the round will be rated for you.

The problems are based on VKOSP.Junior. Authors: Kirill_Maglysh, NToneE, Gadget.

We would like to thank:

  1. Vladosiya for coordinating the round.

  2. nigus, Gheal, KKT_89, Noinoiio, systy, FBI, SiERic, moonpie24, nik.danilov, SashaT9, Pa_sha, FedShat, an_na, khaser, Ghevar, Boris_Ber, PUFL, blook, yakuri354, iluminat_Btopou_AkkayHT for testing.

  3. gurovic for improving the quality of the statements.

  4. MikeMirzayanov for Polygon and Codeforces platforms.

Всем удачи!

UPD: Editorial is out

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

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

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

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

Different start time.

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

    Thanks! Added to the announcement

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

      Pay attention to the unusual round start time. ,hmm but whyyyyy, dont we deserve a reason -_-

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

        The round is based on an onsite competition mentioned in the announcement, which, unfortunately, could not be postponed to the usual round start time :/

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

Yay! Div3 Round. Note the unusual time!

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

You are right ... but why not thank me for participating ?

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

As a tester, I tested some tasks

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

It's on my birthday!!! But I have to go to the school ... T_T

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

Hope to bring my rating back after this round

Good luck for everyone!

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

why such an unusual time?, it's hard for lot of participants to be able to give the contest at that time :(

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

if i dont submit anything or may submit the first one,will my rating fall?

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

    If you do not submit anything.Your rating will not fall.

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

    Any submission results in a rated contest. It won't be rated if you did not make a single submission tho, even you registered beforehand

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

Why is the timing so unusual? Problemsetters please try to hold contests in the regular times only as it's really inconvenient for people studying in universities(as most of them are students) and it's quite difficult to make it on a weekday on such an odd time.

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

    CF Round >>> School/University 2hr lecture

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

      Definitely, but low attendance == repeat course == :(

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

        make good friend == do proxcy == problem solve

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

          College uses biometric attendance machines == cutoff thumbs to give to friend for proxy == slow typing speed. Problem created.

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

      1hr contest reset 1hr mid semester exam

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

    maybe the olympiad will be hold at the same time

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

      as a participant of the olympiad, it is held at the same time

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

I want to author a Div.3 , how I can do ? Vladosiya

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

If someone register above 1600 rating then will they get Negative rating?

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

    if someone has rating 1600 or higher, he/she can register for the round unofficially and the rating won't be affected.

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

Very poor timing

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

What an unsual time! Maybe there will be less participants than usual days orz.

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

Cf round >>>>>>> school

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

[Deleted]

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

I can solve atmost 4 to 5 in Div4. Unfortunately can solve only 1 in div 3. Hope B to H will be very hard.

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

Sleep schedule ruined enough to the point where a 1 AM contest will not affect my mental state. Good luck to all my fellow competitors, and may you gain a cool new color!

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

Time would mess up my sleep schedule. Good luck to all my fellow contestants. It's hard for me to be able to give a competitor at that time :(

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

Wishing everyone a great round and a positive delta !

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

I appreciate the unusual start time, much more convenient for me since contests are typically at 2am for me. You guys should do this more often :)

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

Is this site VKOSP.Junior is available in English?

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

I am excited about Div3 but this time wont allow me to participate

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

School Time here in China :(

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

    School time at 4:00 pm :skull:

    (I hope that the school starts late right?)

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

speedforces!

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

Thanks for this "unusual time". In the month of ramadan this time is perfect for me( from Bangladesh)

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

    also in Iran. for the usual timings, Iftar is at 18:30, and the round is at 18:05. it was really hard

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

fun fact!
today is the last day of the persian calendar (I guess it's called new years eve)
so, if the round was at it's usual time, most of persian users couldn't participate, so thanks for this
love from Iran, Happy nowrooz <3

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

What an unusual start time! But it's suitable for Chinese students.

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

OMG , being in the class, I did not know at the end of which.

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

great questions, but I wonder if problem setters intentionally make div3D easier than div3C most of the time. Problem C took way too much time to understand and implement.

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

    How to do D ?

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

      DP

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

      Assuming $$$f(i)$$$ is the minimum cost to stand at exactly position $$$i$$$, we have $$$f(i) = a_i + \sum_{j=i+1}^{n} min(a_j, b_j)$$$.

      The answer will be the minimum of $$$f(i)$$$ under $$$1 \le i \le k$$$. All $$$f(i)$$$ can be calculated through a linear iteration of the array from $$$a_n$$$ back to $$$a_1$$$.

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

        Nice solution, I tried to think in greedy way for some time and then gave up and settled with DP

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

          At this point I don't know if this solution of mine is classified as DP or greedy :D

          Kinda a mixture of both, DP in the way speeding up the calculation, greedy in the fact that $$$a_i$$$ and $$$b_i$$$ can interchange freely in the background without damaging the solution's validity.

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

      while i > m, if a[i] <= b[i] jump to i

      then find i <= m, with minimum cost of jump

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

Announcement for C was given only after I asked about n/2 being floating point number. Explanation could have been better, wasted so much time in C due to that

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

    But overall problems were good. Not too easy. Even A and B required some math work.

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

Problem Statement of B and C was not good. Especially C

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

Unusual timing and kinda tough.

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

C makes me want to broke my keyboard.

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

In java,

Спойлер
→ Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

problem C showed me how i suck at indexing

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

    I can't do indexing without visualizing it every time like no matter how many time I have done it before, I have to draw , so maybe this can help you I think that its either you draw and figure out the index things or you memorize them

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

how to E

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

    Follow the given algorithm strictly and at last swap positions of l and x's index

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

      Why this works can you give idea or intuition

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

        At all mids,

        If p[mid] <= x, l=mid else r=mid;

        So, basically you have to find what is the last index where l was updated.

        and in some cases, l may not be updated at all, there after simply swapping the l's position and x's position will make your array valid.

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

          please, bro, explain me : when the last ind you updated is greater than target and in between the process mid come to our target. now if we swap last ind and target then mid again comes to the last ind and moves in the wrong dirn because initially the num is =target but now it it > tar. in between my code got accepted without thinking this how i am still confused.

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

            From my code,

            https://mirror.codeforces.com/contest/1945/submission/252251419

            I will not actually swap them

            First I will let this loop run

            where my l is getting updated only if p[mid-1]<=x

            ll l=1,r=n+1;

            while (r-l>1)

            {

    ll m=(r+l)/2;

    if(p[m-1]<=x){
        l=m;
    }

    else{
        r=m;
    }

}

            and now after breaking out from them loop I will not care about the r. I will only think about the l.

            Now if l == target's index then no problem else swap is required

            so the answer will be

            1 l target's index

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

              case 1: p[l] <=m (getting l after running binary search described in problem) then if we swap and run the binary search again . mid goes to the same values and we get our tar at l.

              case 2 : p[l]>m we are returning the ans as swapping final ind and tar. problem : if mid goes to the ind of tar (now a bigger num is present) then our binary search is not same as our initial binary search.

              why this still give accepted verdict ? if lo is changed from 1 then it always goes to num<=tar , if mid reaches larger num then hi will take the place of larger num . therefore either lo is getting no<= tar or it remain at 1 , if it remains at 1 then still our approach works

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

              now I got this last part(why does this still give an accepted verdict ?), if I am wrong somewhere please correct me. thanks bro for help.

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

    Repeated this process until found a solution:

    • select an ind randomly.
    • swap x and a[ind].
    • check if one operation is enough on the modified array. If yes, then break
    • else swap x and a[ind] back.
    → Reply
»
9 months ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

ㅤ

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

C was implementation heavy....

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

    before the edit, there were multiple solutions that they didn't accept.

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

Ignore this comment. Deleted the tutorial, will wait for open hacking phase to complete.

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

Got the idea of problem E in just 10 minutes and the rest of the time passed just doubting myself that it cannot be this easy!!!

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

sorry to say, but the worst div3 statement i've seen in a while. It's just a troll if you don't have even the basic knowledge of english and you just set a problemset with whatever you want. Just a waste of time

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

Requesting to launch more contests on this time during the Ramadan! It becomes hard to attend the contests in the regular time during ramadan!

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

B,C and H are the most awful problems ever.

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

worst div3 ever seen

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

    What an Extraordinary, Mind blowing Fantastic steps!! Tutorials please, Sir tickbird.

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

    Skill-issued bird. Why don't you comment from the ac that part in the contest?

    " had to use std::lcm for some reason, waste hour and 4WA until realize overflow :( " ?

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

    good Python job

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

statement of c was not clear at all

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

Man B & C was laden with the weight of implementation intricacies.!!

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

    I beg to disagree. I would say that B and C are somewhat odd than usual, partially wordings, partially mathematical involvements, but implementations for them are nowhere near intricate.

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

      Master, are you taking my comment personally? You see I am not as skilled as you Master. I am a newbie in Codeforces parlance. So I'm not as good at simple thinking & solutions as you are, Master.

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

        Firstly, I think I should apologize if my words somehow felt like a personal attack. I never meant it that way.

        Secondly, however, I do think my point still stand. Of course, there will be an observable bias coming from me, with more experiences around. However, I do understand where you are coming from to counter-argue, as I had been there (or so I thought).

        For the problems themselves, B is a straight-up math problem, and C literally asks you to do whatever it tells you to.

        Of course, it's not that easy at a glance for newcomers: B's nature might seem dodgy to code at first thinking of how to fit the timespan, or is it required to explicitly define the optimal timespan; C — for now we ignore all the problem statement issues — looks confusing for newer contestants for maintaining the left and right side of the split.

        Still, what I wanna say to defend my point is, it's possible, and very likely, to generalize and abstract your thought process for a clean execution. The mathematical nature of B makes it a three liner if you understand how the math works, C is much cleaner to code once you could visualize how the states of the two sides change when we move the boundary.

        Of course, you don't have to take my thoughtstreams above all at once. One thing, you need to develop your own. Another, it's a steady learning process. You'll get better the more you spend your time thinking and improving. For now, I only state what I did at the original comment, as an opinion that what you have witnessed in your experience is incomplete — I won't say mine is already complete and perfect, but at least today I could cover yours a bit.

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

Is it just me or today's G and H are worth Div2E at least...?

I was quite close to clear G, but cannot really make it — I thought it was just simulating the process but the initial queue order screwed me over.

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

https://mirror.codeforces.com/contest/1945/submission/252233278 Where is my C wrong, can anybody pls help

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

How did you solve F?

i thought it's a ternary search...

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

    Basically, you do what you are told to greedily.

    Loop through all $$$k$$$ that satisfies $$$2k - 1 \le n$$$, each $$$k$$$'s answer will be the $$$k$$$-th largest element over the unaffected indices multiplying by $$$k$$$ itself.

    To maintain the elements properly, we can make two BSTs (or more regularly streamlined in C++ STL as std::multiset), one for the available elements, one for the already chosen one. Choose the largest element from available and throw it to chosen for the act of taking mushroom, and erasing element from either multiset (prioritizing available over chosen) for the act of "cursing".

    My implementation, for reference: 252244274

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

      Thank you

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

      Can you tell what is wrong in my solution? This is my solution for F.

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

        Can't tell at a glance, but if your it iterator is meant to get the max value around, is it a little bit too dangerous to let it "hang" around with all those multiset insert/erase calls?

        Maybe consider renewing it every time you need it. I don't yet see any other suspicious code, but stay alert while debugging.

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

How is the ans for the third test in problem F "8 2". Shouldn't it be "6 2"?

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

    we are picking mushrooms with strength {4, 5}, min = 4, and there are 2 mushrooms so ans = 4 * 2 = 8.

    Honestly, I was irritated due to very less or no notes in any of the problems.

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

      Ramadan Mubarak Brother. I got it.. thanks!

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

why in C in "101" answer is 2 but not 0?

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

    1.5 — 2 < 1.5 — 0, 2 is the closest index possible to middle

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

      The authors are not at all adept, and could not write that n/2 is not an integer division.

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

        Yes, They could have simple mentioned n/2 it was decimal division. But other than that, the problem was written in a confusing manner and was lengthy, we cant blame them for that.

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

a lot of people solved b : (m * 2 — m) / a + (m * 2 — m) / b + somethings and no body will know why LOL

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

    pattern recognition from test cases

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

      how to guess (a/m) + (b/m) + 2.
      it's so hard

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

        try this m=m+1 and then ans= ceil (m/a) + ceil(m/b) ,it will be the answer Reason: Consider the [a,a+m] and [b,b+m] to be included by incrementing m.

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

        https://imgtr.ee/images/2024/03/19/8f04bf5b44e908e9eb17be606d4e3021.png

        this is the second test case in the first sample

        the first line for the first installation
        and the second line for the second installation

        just notice that in the first line the fireworks firing at time 3 will end at time 13 so any one which will be fired before or with in the 13 is included

        that's how I figured it out I hope it helps

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

    The number of fireworks from an installation at any moment first increases and then becomes constant. The sum of these constant values from both these installations is the answer.

    This constant value from first firework is equal to (m+a)/a and from second firework is (m+b)/b. You just need to sum them.

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

Can anyone give me intuitive understanding that why Following the given algorithm strictly and at last swapping positions of l and x's index is correct for Problem E?

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

    Consider 2 cases, whether the target is among the elements visited by binary search.

    If not, we can just swap the last l index with the position of the target since that will not change the search sequence itself.

    If yes, we see that swapping the order of any p[m] <= target will not affect the search sequence, since we are setting the left limit regardless every time.

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

      Still not understood the Yes part. Can you please Elaborate.

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

        If $$$p_m \le x$$$, assign $$$l = m$$$.

        Say we pick two indices $$$i, j$$$ from the visit sequence such that $$$p_i \le x$$$ and $$$p_j \le x$$$. If we swap $$$p_i$$$ and $$$p_j$$$, will the visit sequence change?

        To add on to this, if $$$x$$$ is in the search sequence and is not $$$p_l$$$, then on the final time we set $$$l$$$, $$$p_l < x$$$. We can apply the previous statement to these two indices.

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

      What if a[l]>target and target is visited ? In that case, search sequence will be altered ?

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

        p[l] can only be larger than target if we have not visited target, since we only set $$$l = m$$$ if $$$p_m \le x$$$.

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

          I used this logic during the contest and got WA on test2. Did your solution pass ?

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

            I looked at your submission and I think you calculated m incorrectly. I submitted your code with this change

            ll m = l + r >> 1

            and it passed. link

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

              Generally, you would do l + r >> 1 for calculating m, but to avoid integer overflow you can do l + (r - l >> 1).

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

              Yeah, you are right. Unlucky me. Thank you for your help.

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

      The 'm' value that you're talking about should not be visited as mid value in the Binary Search, Right?? So we have to pick that index 'm' that is not visited during the binary search as well as it satisfies the condition p[m]<target.

      How are we sure that one such m will always exist???

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

        The m I am talking about is the m in the problem statement. If we visit the target index during the binary search, we can always switch it with the last time we set l (see logic in previous comment).

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

    First I assume that you are saying why this works, swap(1, position(x)) and then swap(1, l). or n instead of 1.

    Solution with 2 swaps

    UPD : Now, I get your question, my friend also told me this solution.

    Solution with 1 swap
    → Reply
    • »
      »
      »
      9 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thank you for the two-swap solution. I was wondering why two swaps are even allowed when it could be solved with at most one swap so easily. I thought it was meant to mislead us, haha.

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

252273129 It is the solution for Problem D.I don't know why I'm getting wrong answer on test case 3,jiangly approach and my approach is same even though I'm getting WA.Please help me to find the mistake.

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

    You defined int as long long, however INT_MAX stays at its original value i.e. $$$2^{31}-1$$$, which might be smaller than the actual maximum possible answer of around $$$10^{14}$$$.

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

Contest authors:

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

is the Special Judge right?

$$$p_l$$$ may be $$$3$$$ at last.

UPD: I'm sorry. I was wrong, $$$p_l$$$ is 4.

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

can anyone tell me how to find the interval of size m where maximum multiples of a and b are present?

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

    both fireworks will be launched simultaneously at LCM(a,b).It is always optimal to take the interval from lcm(a,b) to lcm(a,b)+m inclusive. in some cases lcm(a,b) will be greater than 1e18. but intervals lcm(a,b) — lcm(a,b)+m and 0 — m+1 will have same no.of multiples of a and b. so answer is (m+1)/a + (m+1)/b + ((m+1)%a != 0) + ((m+1)%b != 0)

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

      why m+1 ? why not only m?

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

      just increase 1 just after dividing m/a works, but i don't understand how m+1/a works, can you elaborate ?

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

        As per the question range is given as x,x+m inclusive so there are going to m+1 numbers irrespective of whichever range we take. Then we are finding multiples of a,b in those numbers

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

        I did not get how 1 + m/a works

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

Overall didn't enjoy the contest. Problem A was ok, for B I didn't like the method. A and B could have been swapped. C was horrible, I had to read the problem statement 4-5 times. There was some clarification about not rounding up n/2 was weird. I feel you were going for a heavy implementation round to make the problems more difficult, sadly I am not a fan of it. D and E were smartly designed and I have fun solving them. But for E, I didn't like how I had to put seed values as 1 and n+1...like I spent 20 mins to figure this out, which I felt could have been improved.

What is done is done. Thank you for the contest! I appreciate your efforts for the round <3.

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

https://mirror.codeforces.com/contest/1945/hacks/1006163

~10 mins after the contest was finished, I realized I forgot to handle one case lol. This submission should fixed it. Anyway, my screencast is still processing and will be available here.

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

for D just a easy greedy! XD 

#include <bits/stdc++.h>
#define int long long
#define rep(i, j, n) for (int i = j; i <= n; i++)
#define pii pair<int, int>
#define psi pair<string, int>
#define pis pair<int, pair<string, int>>
using namespace std;
template <class T>
using pqg = priority_queue<T, vector<T>, greater<T>>;
template <class T>
using pql = priority_queue<T, vector<T>, less<T>>;
int n,m;
int a[200010];
int b[200010];
int c[200010];
void solve() {
  cin>>n>>m;
  rep(i,1,n){
  	cin>>a[i];
  }
  int aws=0;
  rep(i,1,n){
  	cin>>b[i];
  }
  aws=0;
  rep(i,m+1,n){
  	aws+=min(a[i],b[i]);
  }
  int mins=a[m];
  int sums=a[m];
  for(int i=m-1;i>=1;i--){
  	sums-=a[i+1];
  	sums+=b[i+1];
  	sums+=a[i];
  	mins=min(mins,sums);
  }
  cout<<aws+mins<<endl;
}
int32_t main() {
  ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  int t;
  cin >> t;
  while (t--) {
    solve();
  }
  return 0;
}
→ Reply
»
9 months ago, # |
  Vote: I like it +78 Vote: I do not like it

This contest was an undercover div 2.

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

reading >>>> div1

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

In D-Question, (considering 1based indexing), how does taking the sum of indices m+1 to n inside the min variable actually matter?

My code(give WA on tc3) Code

Correct code Code

By just taking the ans variable out of that min part and directly adding, problem gets fixed I get it that it is more simpler, but I want to know why taking it inside the min part gives problem. Thanks in advance for your help.

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

either bro is too smart or bro is alt id of MikeMirzayanov

check this out

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

Any small hint for e pls :)

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

In C, n/2 is not an integer division could save my 1.5 hours

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

Problem E (Binary Search) Video Editorial : (Audio : Hindi)

YOUTUBE EDITORIAL LINK --Click Here

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

it should have been 2:30 or 3:00 Hours contest , 2:15 wasn't enough

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

Does anyone know why my approach for G is incorrect? Basically I'm using a priority queue to check whether there's someone who already ate with higher priority than the current front of the original queue. I take the appropriate first guy and then schedule its insertion to the priority queue. I'm taking into account order of insertion when multiple ppl are to be inserted at once so idk what's wrong.

https://mirror.codeforces.com/contest/1945/submission/252292126

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

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

What an unusual start time!

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

H problem hint please:
i concluded that its enough to choose 2 elements for gcd and rets n-2 for bitwise and.. not able to proceed further.

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

    I've added hints for H : GCD is Greater on CF Step

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

    Fact : we only choose 2 elements for gcd.

    Proof
    ThinkHint 1
    ThinkHint 2
    ThinkHint 3
    ThinkHint 4
    ThinkHint 5
    ThinkHint 6
    ThinkHint 7
    ThinkHint 8
    ThinkHint 9

    Complete Solution

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

    I haven't implemented this yet, but I think it should be fast enough:

    Спойлер
    → Reply
»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

statement for problem B was very bad and problem C has a problem in the first sample, last test case, if you output 4 it should be correct but its saying wrong the answer should be either 0 or 4 I think but I reformated my code to check for the 0 case first

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

    No, It is stated that you have to print the least no if the difference(n/2-1) is equal.

    Least of 0 and 4

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

in problem C: i have read the statement 10 times and i am still confused why in 4th test case answer is 3 and not 2

testcase ->

000

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

    omg on each side never mind I thought half of the residents in total should be satisfied!!

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

252362491

What is wrong in this solution of problem F?

Can anyone explain ?

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

    I had the same problem.

    See this case:

    3
7 5 8
3 1 2

    The answer is 10 2, not 14 2.

    That's because we remove the elements with indexes $$$p_i$$$, like, choosing $$$k = 2$$$ mushrooms, the magic of the element with index 3 will be zero, because $$$p_1 = 3$$$, so the array will be:

    7 5 0
3 1 2

    It's not the one with index $$$1$$$ or the element with $$$p_i = 1$$$, it's v[p[1]].

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

      This is so confusing, the samples don't have cases like this and the notes don't help.

      Honestly, the problem is good, but I don't know why doing these things just to "overcomplicate" a problem. It's not harder, it's just boring.

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

Dear Codeforces Moderators,

Thank you for bringing this issue to my attention. I would like to address the concern regarding the similarity between my solution and those submitted by other participants.

I want to assure you that I did not intentionally violate any rules or attempt to copy solutions from other contestants. As a beginner on Codeforces, I have been working on developing my own coding templates and algorithms to improve my skills.

I acknowledge that unintentional leakage or accidental similarities can occur, especially when using common coding practices or templates. I have been working independently to solve problems and have not accessed solutions from other sources during the contest.

Unfortunately, I am unable to provide conclusive evidence to explain the coincidence in this case. However, I assure you that I will take this incident seriously and take steps to avoid similar situations in the future. I understand the importance of maintaining the integrity and fairness of Codeforces contests.

If there are any further steps I need to take or additional information you require, please let me know. I am committed to upholding the rules and guidelines of Codeforces and will cooperate fully with any investigation into this matter.

Thank you for your understanding and consideration.

Sincerely, Nuredin Bedru

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

When will the ratings be out?

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

I didn't get B. If both are starting at the same time, then ans should be infinity. Can somebody explain.

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

    That would just be $$$2$$$ simultaneous fireworks. $$$a$$$ and $$$b$$$ are at least $$$1$$$ so two fireworks of the same type would be at least $$$1$$$ minute apart, rendering them unable to stack indefinitely on top of each other i.e. we always have a finite answer.

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

      sorry bro, i didnt get. Could you please explain with an example. for example 1 1 1.

      In this case both will fire at 1 min then again 2nd min and it will go on. And they are visible for 1 min. So it should be inifinity.

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

        The problem was about what is the maximal possible amount of fireworks visible at one moment. Also for any a and b, both fireworks will start simultaneously at lcm(a, b).

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

Every problem statement is comparatively large. As a South Asian, I had to struggle with it. :)
By the way, I enjoyed the problems <3

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

Imagine getting hacked for not commenting the debug statements.

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

    Codeforces definitely needs an option to redirect stderr to /dev/null.

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

How long does it usually take for rating changes to come, and why is it taking so long for this contest's rating changes ???

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

    Because of the large number of participants in Div. 3/Div. 4 competitions, system testing takes a lot of time. And these types of contests have a 12-hour phase of open hacks.

    Please be patient as the user ratings will not be updated until the system testing is complete, which usually takes 1-2 days.

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

Nowadays, Codeforces is taking quite long time for rating updation!

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

I had a solution using binary indexed trees for problem F. But for some reason the case with single value is processing weirdly. https://mirror.codeforces.com/contest/1945/submission/252426399 I have added comments to debug, for the case 1 , 1 ,1 output is coming as 2. can someone help on this ?

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

Can somebody tell me the approx rating of all problems???

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

Wow, that's a 100 rating increase!

https://mirror.codeforces.com/bestRatingChanges/13072503

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

Where is the solution? Sorry I couldn't find it

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

standard question

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

Problem D: Did anyone get stuck at Q2: 4663rd test case? How did you fix it?

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

Can someone explain what is wrong in my submission of Problem F ? 252497347

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

Can someone explain why I got my rating decreased after submitting a code that got approved?

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

I am quite new in the platform,can anyone tell me even though I submitted 2 answers and both of them got accepted why did my rating not changed ?

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

I have used ideone.com compiler to run my code with public access so this may be the reason for my code to be found same. I will use another compiler with proper safety in future contests.

→ Reply