Kirill_Maglysh's blog

Codeforces Round #935 (Div. 3)
By Kirill_Maglysh, history, 6 weeks 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

»
6 weeks 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
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Different start time.

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

    Thanks! Added to the announcement

    → Reply
    • »
      »
      »
      6 weeks 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
      • »
        »
        »
        »
        6 weeks 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
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Yay! Div3 Round. Note the unusual time!

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

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

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

As a tester, I tested some tasks

→ Reply
»
6 weeks 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
»
6 weeks 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
»
6 weeks 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
»
6 weeks 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
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

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

    → Reply
  • »
    »
    6 weeks 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
»
6 weeks 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
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    CF Round >>> School/University 2hr lecture

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

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

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

        make good friend == do proxcy == problem solve

        → Reply
        • »
          »
          »
          »
          »
          6 weeks 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
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      1hr contest reset 1hr mid semester exam

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

    maybe the olympiad will be hold at the same time

    → Reply
    • »
      »
      »
      6 weeks 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
»
6 weeks 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
»
6 weeks 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
  • »
    »
    6 weeks 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
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Very poor timing

→ Reply
»
6 weeks 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
»
6 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

Cf round >>>>>>> school

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

[Deleted]

→ Reply
»
6 weeks 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
»
6 weeks 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
»
6 weeks 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
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Wishing everyone a great round and a positive delta !

→ Reply
»
6 weeks 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
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Is this site VKOSP.Junior is available in English?

→ Reply
»
6 weeks 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
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

School Time here in China :(

→ Reply
  • »
    »
    6 weeks 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
»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

speedforces!

→ Reply
»
6 weeks 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
  • »
    »
    6 weeks 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
»
6 weeks 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
»
6 weeks 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
»
6 weeks 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
»
6 weeks 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
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How to do D ?

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

      DP

      → Reply
    • »
      »
      »
      6 weeks 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
      • »
        »
        »
        »
        6 weeks 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
        • »
          »
          »
          »
          »
          6 weeks 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
    • »
      »
      »
      6 weeks 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
»
6 weeks 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
  • »
    »
    6 weeks 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
»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

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

Unusual timing and kinda tough.

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

C makes me want to broke my keyboard.

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

In java,

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

problem C showed me how i suck at indexing

→ Reply
  • »
    »
    5 weeks 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
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to E

→ Reply
  • »
    »
    6 weeks 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
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why this works can you give idea or intuition

      → Reply
      • »
        »
        »
        »
        6 weeks 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
        • »
          »
          »
          »
          »
          5 weeks 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
          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            From my code,

            https://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
            • »
              »
              »
              »
              »
              »
              »
              5 weeks 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
            • »
              »
              »
              »
              »
              »
              »
              5 weeks 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
  • »
    »
    6 weeks 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
»
6 weeks ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

ㅤ

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

C was implementation heavy....

→ Reply
»
6 weeks 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
»
6 weeks 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
»
6 weeks 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
»
6 weeks 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
»
6 weeks ago, # |
  Vote: I like it -6 Vote: I do not like it

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

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

worst div3 ever seen

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

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

    → Reply
  • »
    »
    6 weeks 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
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    good Python job

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

statement of c was not clear at all

→ Reply
»
6 weeks 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
  • »
    »
    6 weeks 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
    • »
      »
      »
      6 weeks 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
      • »
        »
        »
        »
        6 weeks 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
»
6 weeks 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
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I guess G was pretty tough considering jiangly took almost an hour to solve G

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

    Definitely, clist rates G at 2593 and H at 2766.

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

      Holy hell, no wonder....

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

      It's nice to hear that, since I solved H in the contest. But my solution was so simple that I think the difficulty of H will be at most 2200.

      UPD : I have posted my solution in this comment.

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

        I think you don't understand how problem difficulties work.

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

          I do, div3 problems get a lot of time after the contest before they are assigned a difficulty, there were a lot of problems in this contest and so most of the people could not reach H. I think in 2-3 days, it will have more than 400 solves (and of expert — CM range people (that's how problem difficulties work, right?)).

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

      can u explain ur solution for problem F?

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

        Maintain an ordered set of shrooms with nonzero magic power. There are two operations: remove a value and find k-th maximum. ordered_set supports both in logarithmic time.

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

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

→ Reply
»
6 weeks 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
  • »
    »
    6 weeks 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
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you

      → Reply
    • »
      »
      »
      6 weeks 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
      • »
        »
        »
        »
        6 weeks 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
»
6 weeks 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
  • »
    »
    6 weeks 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
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    6 weeks 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
    • »
      »
      »
      6 weeks 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
      • »
        »
        »
        »
        6 weeks 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
»
6 weeks 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
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    pattern recognition from test cases

    → Reply
  • »
    »
    6 weeks 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
»
6 weeks 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
  • »
    »
    6 weeks 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
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        6 weeks 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
    • »
      »
      »
      6 weeks 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
      • »
        »
        »
        »
        6 weeks 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
        • »
          »
          »
          »
          »
          6 weeks 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
          • »
            »
            »
            »
            »
            »
            6 weeks 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
            • »
              »
              »
              »
              »
              »
              »
              6 weeks 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
            • »
              »
              »
              »
              »
              »
              »
              6 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

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

              → Reply
    • »
      »
      »
      6 weeks 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
      • »
        »
        »
        »
        6 weeks 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
  • »
    »
    6 weeks 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
    • »
      »
      »
      5 weeks 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
»
6 weeks 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
  • »
    »
    6 weeks 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
»
6 weeks ago, # |
  Vote: I like it +47 Vote: I do not like it

Contest authors:

→ Reply
»
6 weeks 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
»
6 weeks 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
  • »
    »
    6 weeks 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
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      why m+1 ? why not only m?

      → Reply
    • »
      »
      »
      6 weeks 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
      • »
        »
        »
        »
        5 weeks 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
      • »
        »
        »
        »
        5 weeks ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        I did not get how 1 + m/a works

        → Reply
»
6 weeks 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
»
6 weeks ago, # |
← Rev. 2   Vote: I like it +59 Vote: I do not like it

https://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
»
6 weeks 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
»
6 weeks ago, # |
  Vote: I like it +78 Vote: I do not like it

This contest was an undercover div 2.

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

reading >>>> div1

→ Reply
»
6 weeks 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
»
6 weeks 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
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Any small hint for e pls :)

→ Reply
»
6 weeks 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
»
6 weeks 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
»
6 weeks 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
»
6 weeks 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://codeforces.com/contest/1945/submission/252292126

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

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

What an unusual start time!

→ Reply
»
5 weeks 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
  • »
    »
    5 weeks 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
  • »
    »
    5 weeks 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
  • »
    »
    5 weeks 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:

    Spoiler
    → Reply
»
5 weeks 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
  • »
    »
    5 weeks 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
»
5 weeks 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
  • »
    »
    5 weeks 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
»
5 weeks 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
  • »
    »
    5 weeks 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
    • »
      »
      »
      5 weeks 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
»
5 weeks 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
»
5 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

When will the ratings be out?

→ Reply
»
5 weeks 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
  • »
    »
    5 weeks 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
    • »
      »
      »
      5 weeks 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
      • »
        »
        »
        »
        5 weeks 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
»
5 weeks 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
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Imagine getting hacked for not commenting the debug statements.

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

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

    → Reply
»
5 weeks 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
  • »
    »
    5 weeks 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
»
5 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
»
5 weeks 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://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
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

Wow, that's a 100 rating increase!

https://codeforces.com/bestRatingChanges/13072503

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

standard question

→ Reply
»
5 weeks 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
»
5 weeks 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
»
5 weeks 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
»
5 weeks 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
»
5 weeks 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