SlavicG's blog

Codeforces Round 918 (Div. 4)
By SlavicG, 11 months ago, In English

Happy Holidays Codeforces! 🎅

mesanu, flamestorm and I are very excited to invite you to Codeforces Round 918 (Div. 4)! It starts on Dec/28/2023 17:35 (Moscow time).

The format of the event will be identical to Div. 3 rounds:

  • 5-8 tasks;
  • ICPC rules with a penalty of 10 minutes for an incorrect submission;
  • 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
  • after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
  • by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).

We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.

Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as a trusted participant of the fourth 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 1400 or higher in the rating.

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

Special thanks to the VIP testers: AlperenT, KrowSavcik!

Thanks a lot to the testers: Qualified, Kaushal_26, htetgm, MADE_IN_HEAVEN, sandry24, hbarp, Vladosiya, LucaLucaM, Gheal, tvladm, Dominater069, haochenkang, xiaowuc1, pashka, vrintle, BucketPotato!

And many thanks to Vladosiya for translating the statements!

We suggest reading all of the problems and hope you will find them interesting!

🎄 🎄 🎄 Good luck to everyone and enjoy the holidays!!! 🎄 🎄 🎄

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

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

Thank you

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

very handsome.

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

I promise to solve at least 4 problems.

P.S. Cool photo!

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

    and you kept your promise!!

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

    I kept my promise, I can die with a clear conscience.

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

This is my first out of competition and first unrated round

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

Thank you! Nice photo.

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

Every div 4 is good

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

Finally, this is my first unrated contest... I hope I will be able to solve all problems under contest time .... Merry Christmas and happy new year to all ....

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

I think conducting the div4 contest is the best holidays gift for the people having rating less than 1400.

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

Hope to be a great contest before Christmas...

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

    Christmas was on the 25th, it's the 28th now :)

    (unless you're talking about Orthodox Christmas on the 7th of January :D)

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

Div4 should be arranged more frequently. Hoping for a great contest!

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

Are there watermarks on those Christmas hats?

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

thank you for this ! I hope my rating will slightly increase. I was demotivated for a long time due to failures after failures

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

Hopefully with this contest I can enter green :)

→ Reply
»
11 months ago, # |
← Rev. 3   Vote: I like it -16 Vote: I do not like it

I hope to reach pupil after this contest, insha-allah.

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

i hope to retain the magic colour even after 10th jan with this round

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

so handsome

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

It will be my first Div 4 participation ^_^

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

I would aim to solve >80% problems.

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

Pupil! Pupil!

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

The cap on your head looks edited

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

As a tester, Santa helped me test the contest

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

This will be my second participation at codeforces. Last was Div 3 I couldn't solve a single one.

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

I think I will be green this year, Insha Allah. Hopefully, this round will be great for me. I wish I could do it.

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

Wow! Dominater069 was a tester. That's great!

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

flamestorm face reveal!?!?!!

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

div 4 time yay! thank you for the div 4 contest!

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

I hope I will be pupil after this round

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

As an unemployed tester, I wish all participants happiness and employment.

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

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

As VIP testers, this was our testing room:

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

i wanna be specialist on this contest :)

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

Good luck to everybody ;)

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

Best of luck to all participants!

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

I wish you all a happy game, and I wish you a good score.

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

As a tester, I changed my color.

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

Hi, can I do red testing for this round? (hehehehe)

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

thank you

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

Eh, 2022-2023 is over, it was not like 2020, which is good, but I remember it as one of the most important years, I hope that next year will be successful for you all

zac-durant-6-Hz-PU9-Hyfg-unsplash-1080x675

I hope that for many every new year will only be better

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

My first Div.4 participation too! As a noob, hope the questions are friendly to me so that I can solve questions that less than 1300 smoothly. good time!

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

Hoping I could reach specialist :D

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

Thank you!

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

Can't wait to get +ve delta

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

Merry Christmas!

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

The best ending of the 2023 with div4. BTW nive picture!

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

As a specialist, my first unrated contest,unfortunately I can't participate

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

****___After Long Time___****

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

Just hoping for +ve delta in this one

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

love it！

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

I hope the problems are as easy as it is to spot the fake caps in the picture ;)

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

Happy Holidays to everyone and Merry Christmas. Coding in holidays may not be possible for many but Respect to you if you are here

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

Thanks for the round!!

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

handsome photo, the last competition in 2023

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

Good luck everyone

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

This is the day i will say goodbye to my green name

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

do well everyone

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

in queue LOL

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

in the statement of Problem D:

mistake: 1<=n<=2*10^5 correction: 2<=n<=2*10^5

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

So many people have registered for this round that I had to wait 20 minutes to see the verdict for problem A.

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

Thanks for the round !!!

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

Loved the problems on this round <3

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

Awesome problems, guys! Keep it up!

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

Nice contest

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

Is the person replying to the questions during the contest a bot or online human???

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

Fun fact: $$$G$$$ can be solved using GPT $$$4$$$ without any hints.

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

    Really? Can you send code

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

      Check my sibmissions. (As you can see i participated unofficial, so it must mot be cheating or smth else:) )

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

    How do you get it accepted with 170ms? I tried your code, and got 2000+ms. Where is the difference from?

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

      I don't know how it is possible:)

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

Screencast and Solutions to all problems

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

it's over,

I will never reach cyan 🤡

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

Is MO decomposition in F an overkill? :D

My solution: 239387414

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

    might be, solved it using ordered sets, although i believe the author had a simpler solution for F of a Div 4!, btw what was your reasoning behind G?

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

      Basically we clone each vertex $$$n$$$ times. Each clone will be a pair, where first element is number of vertex and second is bicycle we use after we visit this vertex. So, now we just use dijkstra algorithm to find min path to ($$$n$$$, $$$any$$$-$$$bicycle$$$). You just need to find some transitions when you start using different bicycle. Something like this.

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

    You can compress the coordinates, sort the intervals and then use fenwick or segment tree to calculate the answer.

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

    Yeah, it's just nlogn inversion count using merge sort

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

what is the idea of E? i felt its harder than F and evne G ( if i got the idea of G correct)

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

    think about the prefix sums of the odd-index and even-index arrays. What can you say about the prefix sum values at the left and right endpoints of a good subarray?

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

    Let $$$\mathrm{sum_{even}}$$$ denote the sum of values on even indices on our current subarray, and define $$$\mathrm{sum_{odd}}$$$ similarly.

    $$$\mathrm{sum_{even}} = \mathrm{sum_{odd}}$$$

    $$$\mathrm{sum_{even}} - \mathrm{sum_{odd}} = 0$$$

    Now, multiply all values on odd indices by $$$-1$$$ in the original array. The condition now becomes

    $$$\mathrm{sum_{even}} - (-1) \cdot \mathrm{sum_{odd}} = 0$$$

    $$$\mathrm{sum_{even}} + \mathrm{sum_{odd}} = 0$$$

    The left side is just the sum of the current subarray. Thus, we need to find a subarray with sum $$$0$$$ $$$\Leftrightarrow$$$ you need to find two equal prefix sums.

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

      got it amazing problem and solution thanks alot !

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

      Still clueless could you explain it to me?

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

        What part of my comment did you not understand?

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

          As to why we need that particular subarray where all the odd incidces sum up to zero and why do we need to use prefix sum here.

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

            why we need that particular subarray where all the odd incidces sum up to zero

            That's not what I said; odd indices shouldn't sum up to zero. Let me try to explain everything again with more details.

            Let $$$\mathrm{sum_{even}}$$$ denote the sum of values on even indices on our current subarray, and define $$$\mathrm{sum_{odd}}$$$ similarly.

            According to the problem statement, we need to find a subarray such that $$$\mathrm{sum_{even}} = \mathrm{sum_{odd}}$$$

            Subtract $$$\mathrm{sum_{odd}}$$$ from both sides:

            $$$\mathrm{sum_{even}} - \mathrm{sum_{odd}} = \mathrm{sum_{odd}} - \mathrm{sum_{odd}}$$$

            $$$\mathrm{sum_{even}} - \mathrm{sum_{odd}} = 0$$$

            Now, let's multiply all values on odd indices by $$$-1$$$ in the original array. Thus, $$$\mathrm{sum_{odd}}$$$ becomes $$$-\mathrm{sum_{odd}}$$$ in our new array.

            This means that the required condition is now

            $$$\mathrm{sum_{even}} - (-\mathrm{sum_{odd}}) = 0$$$

            $$$\mathrm{sum_{even}} + \mathrm{sum_{odd}} = 0$$$

            For any subarray, $$$\mathrm{sum_{even}} + \mathrm{sum_{odd}}$$$ is just the sum of that subarray. This is because every element in the subarray is either counted in $$$\mathrm{sum_{even}}$$$ or in $$$\mathrm{sum_{odd}}$$$.

            Now, we just need to find a subarray with sum $$$0$$$.

            Let $$$p_i = a_1 + a_2 + \dots + a_i$$$, i.e. the array $$$p = [p_1, p_2,\dots, p_n]$$$ is the prefix sum array of $$$a_1, a_2,\dots, a_n$$$. Remember that this array $$$a$$$ is the one from input, with all values on odd indices multiplied by $$$-1$$$.

            Recall that $$$a_l + a_{l+1} + \dots + a_{r} = p_r - p_{l-1}$$$, i.e. the sum of a subarray of $$$a$$$ can be expressed as a difference of two prefix sums.

            Since we need a subarray with sum $$$0$$$, we need two prefix sums $$$p_r$$$ and $$$p_{l-1}$$$ such that $$$p_r - p_{l-1} = 0$$$

            Add $$$p_{l-1}$$$ on both sides:

            $$$p_r - p_{l-1} + p_{l-1} = p_{l-1}$$$

            $$$p_r = p_{l-1}$$$

            This means that we just need to find two equal values in the prefix sum array. Remember to also include $$$p_0 = 0$$$ in your prefix sum array, since this might be needed when $$$l = 1\ \Leftrightarrow\ l-1 = 0$$$.

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

    a -> pref sum of odd indidces b -> pref sum of even indices for range l...r to be valid ar — al = br — bl -> (ar — br = bl — al) now you know how do it. it's similar to 2 sum problem

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

      implemented the (ar-br) = (al-bl) through n^2 approach but got tle in 3rd TC , didnot get what is two sum problem mentioned in your post can you provide a reference for that i'll go through it O(n^2) approach

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

        problem

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

        hint : a + b = c => a = c — b think of bs. then further how can you optimes it

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

          I'll try to do using this hint.

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

            GL

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

              solved it 239414558, initially I didnot get why 'two sum' in this question , but after knowing the 'subarray sum' problem got to know how two sum can be used to find a subarray of sum equals k, and I also read some post explaining about multilping -1 to alterntive ele. ThankYou for the help alpha1215

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

                glad i could help you btw an advice never use unordered map in contest it can tle

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

                  any other alternative for map in this question, and also i tried solving F in O(n^2) considering a person meets every person whose staring and ending points are inside his starting and ending point, but the soln needs to be optimised

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

                  for first ques you can use simple map it's fine for F yo can sort the people based on their starting position now person i will meet every other person j such i < j < n if the j'th person has ending position less than i'th person after this observation it becomes a classic problem counting the inversions in array to do this there are many the method i know to do this is divide and conquer but during contest i used heap my 239336078

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

    you can solve it with a set , make every even index element negative then loop on the array and insert the prefix sum till i in the set , and find if you have the same prefix already , if true then its a YES .

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

      yeah thanks the implementation isn't a problem but the idea is really amazing i think i need to practice math or maybe need a brain transmission XD

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

can someone tell me if my approach for G is correct or not for every node i (min time to reach from 1 to i) + (min time to reach i to n) ans is min of all those nodes;

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

    Trying same thing from hours but don't know why it's not working... I hope some explain flaw in this approach

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

      I think the above approach assumes that the optimal route would involve a direct path from 1 to i and then i to n, and this surely is the case in the first sample test case. However, it may not always be the case as the minimum time route is a walk(not a path always) for the problem.

      Consider the modified weights and bike slowness:

      5 5
1 2 2
3 2 1
2 4 5
2 5 20
4 5 100
10 5 3 1 2

      In this case you may observe that the optimum route goes as 1-2-3-2-4-2-5. So, the solution in this case is time(1,3) + time(3,4) + time(4,5). This can be generalized and you can make test cases where the optimum route is a combination of many simple paths, and so the assumption that time(1,n) = min over i{time(1,i) + time(i,n)} fails.

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

        The optimum route is a combination of many simple paths

        Thank you so much for explaining. :)

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

Loved the problemset. Solved 6 problems

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

can somebody say why 239395416 getting TLE on 21st testcase?

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

What is the time complexity of my code? Isn't it O(nlogn)? 239378769

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

    distance is $$$O(n)$$$

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

      I thought distance is faster, is there any alternative variation to what I wanted to do?

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

    Time complexity of the distance method is O(N), which means your final complexity is O(N^2)

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

can I do F in PYTHON without use SortedList?

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

Could someone please explain how to approach problems like E? TIA

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

    We just have to found the subarray (with certain sum x) whose sum of odd and even places is same. what we can do is if we multiply -1(either of the odd or even position) now we just have to find the contiguous subarray with 0 sum that can be done by maintaining a prefix sum and a set(basic hashing)...

    You can take help by this video..

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

Can anyone explain ideas behind F and G?

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

    For F, you can see that 2 intervals contribute to the answer only if 1 is completely into another. Noy you can compresd all the coordinates, sort the intervals by ascending xleft coordinate and use segment or fenwick tree to calculate the answer. Tou can see my code for more details.

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

      for some reason, I am unable to view your submissions. Could you please share your code, or tell me how to maintain number of intervals between two coordinates l and r using segment tree?

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

    Problem F can be soved using ordered set.239369576

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

      can you explain it

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

      I kept on thinking the entire contest that set can't count elements greater than an element in log(n) time. Didn't know that something like ordered_set exists in cpp. Thank you so much for your elegant solution.

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

Nice contest, B was a bit diff, I hate working with 2D arrays

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

    Bro really overthinking B

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

    Tell me one thing, did you copy C? Someone for whom traversing 2D array is tough, had template in C (but not in A and B where it might be useful) which was anyways not required.

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

i have used this code to count the no. of inversions i changed it little bit. so i hope this is not considered as cheating and my submissions will not be skipped as many participant may used the same code

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

I have no idea why this code is printing an additional character, and it costed me a good contest. Can anyone help me figuring out this?

→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it 
        if(i + 3 >= n){
       fin += s[i], fin += s[i + 1], fin += s[i + 2];

       cop.push_back(fin);
       i += 2;
       cc++;
       break;
    }

    Here, what if i + 2 >= n

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

in problem F why the answer for this input is 9 ?

6
2 6
3 9
4 5
1 8
7 10
-2 100
→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    point(4,5) meet with (3,9) at 2nd sec ->count=1; point(2,6) meet with (4,5) at 3rd sec ->count=2; point(1,8) meet with (4,5) and (2,6) at 3rd,5th sec ->count=4; point (-2,100) meet with every other point at 7th,8th,10th,11th,12thsec ->count=4+5=9;

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

    You must find all $$$a_i > a_j$$$ such that $$$b_i < b_j$$$.

    The $$$(a_i, b_i)$$$ and $$$(a_j, b_j)$$$ pairs that meet this criteria are as follows:

    • 1 8 greets -2 100;
    • 2 6 greets -2 100 and 1 8;
    • 3 9 greets -2 100;
    • 4 5 greets -2 100, 1 8, 2 6 and 3 9;
    • 7 10 greets -2 100.

    So in total there are 9 greetings.

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

finally i'm LGM after this round

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

Can any one tell why my submission to G is giving WA ? Also a clarification i need, if Salvic is at city C and has bought some k bikes till now, then he can use any bike(1 to k) to travel to neighbouring cities of j right ?

My latest submission

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

    He can only use bikes from the cities he has travelled through, i.e. only the bikes from the cities that lie on the path(or walk) from city 1 to city C.

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

      right, then probably I understood problem right though late but still.. like the implementation above covers this fact !

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

Can someone please explain the test case 1 of problem G? how is 19 achieved?

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

    1 -> 2 -> 3 -> 2 -> 4 -> 5

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

    1 -> 2 time = 10 2 -> 3 time = 10 + 2 3 -> 2 time 10 + 2 + 1 2 -> 4 time = 10 + 2 + 1 + 5 4 -> 5 time = 10 + 2 + 1 + 5 + 1 total time = 19

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

    I'll denote the fastest bike that we currently have by $$$b$$$.

    The steps are as follows:

    • Start in city 1.
    • Buy the bike in city 1, now $$$b = 5$$$.
    • Go to city 2, it takes $$$5 \cdot 2 = 10$$$ minutes.
    • Buy the bike in city 2, now $$$b = 2$$$.
    • Go to city 3, it takes $$$2 \cdot 1 = 2$$$ minutes.
    • Buy the bike in city 3, now $$$b = 1$$$.
    • Go to city 2, it takes $$$1 \cdot 1 = 1$$$ minute.
    • Go to city 4, it takes $$$1 \cdot 5 = 5$$$ minutes.
    • Go to city 5, it takes $$$1 \cdot 1 = 1$$$ minute.

    Elapsed time: $$$10 + 2 + 1 + 5 + 1 = 19$$$.

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

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

u look like kenzo tenma and johan liebert

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

Hello Everyone What is this trusted participant thing? I see the standings have a trusted participant tag. I participated after long tume. Will this round be unrated for me?

→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it +10 Vote: I do not like it
    Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.
    → Reply
»
11 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Amazing contest!!! Solved all except E lol. Ordered Multiset FTW in F.
Thanks for the great round SlavicG mesanu flamestorm and all testers.

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

my first impression on divs (^O^)/

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

Hoping to become a pupil. Also can anyone explain the test case for F? -10 10 -5 5 -12 12 -13 13 How is it 6?

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

    Everyone greets each other. (-5,5) and (-10,10) meet at 5 (-5,5) and (-12,12) meet at 5 (-5,5) and (-13,13) meet at 5 (-10,10) and (-12,12) meet at 10 (-10,10) and (-13,13) meet at 10 (-12,12) and (-13,13) meet at 12

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

    t = 0. A is at -5, B is at -10, C is at -12, D is at -13.

    t = 10. A is at 5, B is at 0, C is at -2, D is at -3.

    t = 15. B is at 5 and greets A. C is at 3, D is at 2. 1 greeting.

    t = 17. C is at 5 and greets A. B is at 7, D is at 4. 2 greetings.

    t = 18. D is at 5 and greets A. B is at 8, C is at 6. 3 greetings.

    t = 20. B is at 10, C is at 8, D is at 7.

    t = 22. C is at 10 and greets B. D is at 9. 4 greetings.

    t = 23. D is at 10 and greets B. C is at 11. 5 greetings.

    t = 24. C is at 12, D is at 11.

    t = 25. D is at 12 and greets C. 6 greetings.

    t = 26. D is at 13.

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

my face when tourist got hacked ._.

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

What was the idea of F? Segment trees?

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

    dp[i][j] = shortest path from i -> j where s[j] is the smallest

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

    sort elements in terms of a[i], find the inversions of array b after sorting (this can be handled by ordered multiset, fenwick tree, segment tree or even merge sort)

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

Geothermal King of Div4 contests. He ACs the entire problemset so quickly lol.

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

stared at G for over 2 hours, ggs

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

How to solve E ? and someone can give me a countertest for 239242264

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

    If you get the answer in the first 2 lines so that you don't input the next lines.

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

Not even a clue how to solve E by prefix sum and Why to find a zero prefix sum with the addition of sum being calculated with multiplying by -1 to odd indicies :(

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

    sum_odd(l, r) = sum_even(l, r)

    <=> sum_odd(l, r) — sum_even(l, r) = 0

    or

    <=> sum_even(l, r) — sum_odd(l, r) = 0

    we can either pick sum of odd elements or even elements, and negate it, now it turns into the classical problem of finding out whether a subarray of sum 0 exists

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

handsome!

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

why this solution gets time limit on test 3: https://codeforces.me/contest/1915/submission/239385030

isn't time complexity of it O(n*log n)

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

How to solve E and F? can anyone explain it easily! thanks in advance.

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

Knew about them 30 minutes before the contest and now it's everywhere

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

F is the worst problem I have faced till now, why did these tests allow O(n^2) solutions to squeeze in? I did not expect O(n^2) solutions to pass at all.

→ Reply
»
11 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it 
int n ; cin >> n ; 
    vector< pair<int,int> > v ;
    for(int i = 0 ; i < n ; i++){
        int a, b ; cin >> a >> b ;
        v.push_back({a,b}) ;
    }
    sort(v.begin(), v.end()) ;
    set<int> s ;
    int ans = 0 ;
    for(int i = 0 ; i < n ; i++){
        auto it = distance(s.upper_bound(v[i].second), s.end() );
        ans += it ;
        s.insert(v[i].second) ;
    }
    cout << ans << endl ;
→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    std::distance works in O(n), so your code is O(n^2).

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

      how to do then just subtraction shows error

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

        You cannot subtract two rb tree iterators. Use an ordered multiset.

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

lol. tourist's solution of G got hacked.

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

div 4 should have more questions..like same number of questions like div2 after D considering as div 2 A

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

My screencast: https://youtu.be/1cdLQi_0_XQ?si=J7HiLQiXyFT0fe_u finished in 29 mins

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

I solved 4 problems and Iam a new comer and this contest is unrated for me. Can I know why?

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

    I am not trying to be rude but can you please read the announcement blog again?

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

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

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

can someone try to hack my G solution? https://codeforces.me/contest/1915/submission/239320792
I feel like it should be able to get TLE. I followed an approach similar to bellman ford algorithm. I looped through j and used
dist[1 to i] = min(dist[1 to i], dist[i to j] + s[j]*greedy_dist[i to j])
to relax the nodes like in bellman ford

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

    It seems like the time limit is enough for bellman ford. Try to come up with a case with maximum case and it only takes 2652 ms for your solution to pass.

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

can we solve f without fenwick tree

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

Can anyone please tell what is wrong in this method for problem G ?

int main(){
    ll tt;cin>>tt;
    while(tt--){
        ll n,m;cin>>n>>m;
        vector<vpll> v(n+1);
        rep(i,m){
            ll x,y,z;cin>>x>>y>>z;
            v[x].pb({y,z});
            v[y].pb({x,z});
        }
        ll a[n+1];
        rep1(i,n)cin>>a[i];
        set<vll>q;
        q.in({0,a[1],1});
        ll inf = 1e14;
        vector<vll>dis(n+1,vll(1001,inf));
        rep1(i,1000)dis[1][i] = 0;
        while(q.size()){
            
            ll d = (*q.begin())[0];
            ll i = (*q.begin())[2];
            ll mn = (*q.begin())[1];
            q.erase(q.begin());
            if(dis[i][mn]<d)continue;
            for(auto it : v[i]){
                ll ch = it.fi;
                ll wt = it.sec;
                ll x = min(mn,a[ch]);
                if(dis[ch][mn]>d+mn*wt ){
                    dis[ch][mn] = d+mn*wt;
                    q.in({dis[ch][mn],x,ch});
                }
            }
        }
        ll ans = inf;
        rep1(i,1000)ans = min(ans,dis[n][i]);
        cout<<ans<<endl;

    }
}

dis[i][j] means minimum distance to reach ith node if the minimum slowness factor is j to reach node i.

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

    because you are initializing that time to reach node $$$1$$$ for every slowness is $$$0$$$, which is wrong, since you can reach back to node $$$1$$$ after taking the slowness of some other node and then procees with that for further $$$optimal$$$ answer but you block it since when it reaches node $$$1$$$ its sees the time to be minimum($$$0$$$) already.

    small test case

    Hope that helps !

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

everybody talking about tourist hacked problem, but

i got hacked on E for using unordered_map instead of map. it's the first and last time i got hacked for this.

Here a useful blog about that: https://codeforces.me/blog/entry/62393

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

Idk my solution to G was different from most so...

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

maybe i can say win998244353 and ah_shit_here_we_go_again both team worked acc.

They are committed in a completely chaotic order and have different code styles.

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

239194376 why is it TL? can some one pls look)

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

My Screencast
Post contest discussion stream

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

I was thinking about this problem F, It's something like count the number of inversions in an array

I solved using ordered_set, binary trie and merge sort(Submission), and I know how to solve using Fenwick tree/Seg Tree.

I wanted to know if there is something easier I can do

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

    If:

    • Walker 1 starts behind walker 2
    • Walker 1 ends in front of walker 2

    Walker 1 will greet walker 2.

    This is true because if walker 1 starts in front of walker 2, it will reach walker 2's end before walker 1, and if walker 1 ends behind walker 2, it will stop before it reaches where walker 2 stopped.

    So we can sort the starting points in ascending order, and then for each walker, we can count how many walkers greet them by counting how many of the walkers we've iterated through so far have an endpoint ahead of our current walker. The order statistic tree facilitates this very cleanly (and at 1/10th the speed). 239357334

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

      It's not too slow, you can use this(Fast IO) to speed up your code

      ios_base::sync_with_stdio(false); cin.tie(NULL);

      I submitted your code again: submission

      It's running in 202ms

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

Thx

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

why O(nlogn) solution not pass problem F?

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

    Why wouldn't it work? My solution is $$$O(n log (n))$$$

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

      239429264 I do believe this is O(nlog(n)) if I'm not mistaken

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

        The distance method's runtime is O(N). So your solution is O(N^2).

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

          interesting, I've been thinking distance will always run in O(1)

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

            my n*logn*logn solution passed for F using merge sort tree.

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

Hack this, please!

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

Thank you for such fun round!

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

Can anyone please help me understand why 239392696 for problem E is hacked despite O(n)? Even 239438693 raised tl. TT

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

F can use sweep line?

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

can somebody explain it out why my code is getting error for question "CAN I SQbUARE"

for _ in range(int(input())): n = int(input()) x = list(map(int,input().split())) s = 0 for i in x : s+=i 

if(pow(s,0.5)*pow(s,0.5)==s):
    print("YES")
else :
    print("NO")
→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It's not true that a number is a square number if $$$pow(s, 0.5) * pow(s, 0.5) = s$$$. That is only true if the result of $$$pow(s, 0.5)$$$ was an integer. Since the function returns a floating point number, that floating point number times itself will often be equal to s, so your solution will say "YES" for many non-square numbers.

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

can someone tell on which test case my solution of e got hacked

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

    In short, you shouldn't use unordered_map in CodeForces (or other hackable contest), check this.

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

In problem E, unordered_map gives TLE, but map gives accepted verdict. Could anyone please let me know why?

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

    Maybe 2e9lg2e5 steps usually runs faster than the limit of 1s; (# of testcases) * (nlgn) = (1e4) * (2e5 * lg2e5)..?

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

My rating was 772 , and I haven't solve a single problem before in div4. But yesterday I solved two problems. It was supposed to increase my rating. But my rating remains the same. Why ? Can anyone explain please.Why this contest was unrated for me (:

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

    Rating will be distributed soon. Good to see another fellow named "Nabid"

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

I have created account this account year before and I had given the first contest today. This was unrated for me and my contest rating is also showing as unrated. I solved four questions in this round. Can I know the rules of rating and why Iam not rated?

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

In 1915F - Greetings,

I don't know why the First code get TLE, but the Second code passes. I'm not sure about the reason. Can you explain?

First java code : 239385944 — using Treeset, headtail method

Second java code : 239456229 — using ArrayList, BinarySearch method

Is there a significant difference in the time complexity between the two codes?

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

It's my first Div 4 participation

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

Why my rating has not increased after giving codeforces round 918 contest. I registered for it an hour before but it is showing unrated. My rating is below 1000

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

    It will increase after the rating for contest get updated.

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

Have the tasks been retested yet?

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

I'm actually a bit confused regarding this round, as my rating is below 1400 and yet after solving 2 questions, my rating hasn't been increased. If anyone could please help me explain the situation please.

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

Can anyone explain why me solution got AC? it has a time complexity of n^3 https://codeforces.me/contest/1915/submission/239328701

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

    WOW, the size of vector d is 1e13..... I didn't know we could make a vector this big.

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

Why haven't our profile ratings changed ? My rating is 870. It should've boosted or decremented my rating

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

Will there be system testing for this round?

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

Is this contest Unrated?

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

Where can I find the editorial? or is it unavailable

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

    editorial

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

      Hi, can I know when will be rated? I just participate this contest yesterday, but my profile rating didn't change til now

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

        I don't know accurately but i think it Wil take 6-7 hours more

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

          Thanks bro, maybe I should be more patient

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

thank you!

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

One person has been abusing me by sending messages because I hacked his/her solution in this contest. Is there a way to report that person?

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

For anyone who wants to know more about similar problems like G.

Here is a great blog on shortest path modelling:

https://codeforces.me/blog/entry/45897

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

Editorial when?

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

    editorial

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

      Thanks, where is it published. I cant find the link in Contest Announcement

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

        They have not published it yet in this post NeverSpot gave me the link I can only find it through the contest author's blog

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

When will the rating get released?

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

I solved 5 out of 7 problems and they were accepted. Now it shows only 2 out of 7 were submitted ? What the hell. I just checked 3 hours ago it showed 5 out of 7 were accepted

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

    don't worry system is retesting them again

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

      I analysed and realised that any submission after 40 minutes was being ignored by the software system

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

        system testing is going on, wait for sometime

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

Is it possible for a solution to be rejected due to TLE during system testing even if the submission was earlier accepted during the contest ?

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

During the contest I solved 4 questions but now it is showing that I solved only two questions somebody kindly help

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

I would like to ask why this submission receives a WA in the new testcases (C) https://codeforces.me/contest/1915/submission/239236542

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

    You are typecasting to double, so it is possible that some value which is not perfect square can also match(due to precision issues). You had to typecast to long long. If it was a perfect square, then only it will match

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

      Oh, it is quite a silly mistake lol. Thank you very much!

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

thank you!!

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

Bro rip lmao A-E was easily doable in an hour. Failed E because of using unordered_map and in C forgot to use long long once.

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

Hey SlavicG, I think there was something wrong for me, my rating is less than 1400 and this contest should be rated for me, but it shows that it isn't the case, it also shows that in my profile. How can I solve that?

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

Is there anyone else who gave this round for the first time(unrated before this) and even after 24hours your account is still showing unrated??????

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

    I wasn't unrated before giving the contest, but my rating hasn't been updated yet.

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

Will i be rated if i have given contest first time and solved 4 problem in this div4 round??

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

is this contest unrated ?

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

it was a nice contest for me.... happy coding for everyone

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

Why did my F TLE？ https://codeforces.me/contest/1915/submission/239528521

→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Spoiler
    Why?
    → Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why was this unrated for me? I've never been >1400 so I'm really confused

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

What is the problem with the unordered_map? I used the same solution just a little change using map instead of unordered_map got AC on problem E.

Why is this happening?

TLE submission:

AC submission:

UPD: Found solution on this

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

I participated in the contests and solve few problems while I'm newbie then why didn't I recived any points yet

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

I have submitted the contest on time but havent been rated for it yet, how much time does it take usually?

It's my first division 4 contest and I'm quite new to the platform..someone please guide me

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

I don't know why my rating is not updated. Can anybody help?

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

    Wait for 24-48 hours after the contests

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

Thank you!

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

In Question E

Why unordered_map has given TLE in test case 16

But ,using normal ,it gets accepted,Although we are using only find function of map

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

    because worst case of find in unordered_map is O(n)

    but in map is O(log n)

    so in some case, it will TLE.

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

FINALLY

I am a specialist NOW

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

Could someone please help me find the editorial? Or perhaps lead me to the solutions of E, F and G questions? I tried to implement the solution of vgtcross given in the comments under but I am not sure where I have messed up. Here is the submission. 239587509

→ Reply
  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • The editorial is here. You can find it by going to the contest dashboard (problem list); on the bottom right, there is contest materials -> tutorial.
    • About your solution to E, it seems like you were able to get it working. About the use of unordered_map, you should probably read this (unless you did already).
    → Reply
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you. Appreciate the help.

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

I solved two questions in the contest and both were correct then why did i get an overall negative 28 and a penalty of 54

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

.

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

I became Specialist...

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

Hello! This is my first ever comment on CF. I have a question regarding prob F. I have 2 codes: one uses a vector to store left boundary of interval & one uses a set. The one using a vector is getting accepted, but the one with the set is giving TLE. Does anyone know why is that? Here are the links of the 2 submissions.

https://codeforces.me/contest/1915/submission/240288584 https://codeforces.me/contest/1915/submission/240288739

Thank you in advance :)

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

    https://codeforces.me/blog/entry/45902

    distance() is O(n) -> complexity being O(n^2) when using set

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

      Thank you so much. But isn't inserting in a set 0(logn) & inserting in a vector 0(n)? Doesn't that make up for the difference? ie In a set : insert log n and distance n. In a vector: insert n and upperbound logn

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

        tf sorcerery is this

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

          Inserting in a vector is O(n) too. So how does this submission get accepted? Isn't it O(n^2) also? If you figure it out please lmk.

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

            I'm really not sure why this is working. Possibly because vectors use the hardware much better than sets — was reading this — https://stackoverflow.com/questions/20960936/fastest-insert-c?rq=3

            either ways, the solution with vector is theoretically worse time complexity and definitely O(n^2).

            You should use a self balancing binary tree such as red black tree when doing this problem (like using ordered set from gnu pbds package) instead of vector. eg my submission — https://codeforces.me/contest/1915/submission/239449554

            i think possibly the time limit on this problem being 5 seconds is a lot and should be 2 seconds. But honestly im impressed this even runs till the end without timing out. freaky stuff.

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

              Thank you soo much! Just another note: if you observe the running time of the code using vector, the time is almost reduced by half something which I cannot find an explanation for.

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

although i could not take part in it on time,but after i vp,i feel good?happy everyone

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

All my attempts were ignored due to the fact that my code for task E in logic coincides with others. I didn't post or take the code anywhere. Due to the fact that we are solving 1 problem, the logic of the code may also be the same. Please can you fix this![user:System]

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

I really want to author some problems for Div.4 it really improves my skills Hope to contribute in coming Div.4 Rounds mesanu , SlavicG , flamestorm , MikeMirzayanov

I have an ideas for it .

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

SlavicG why u retired

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

    I haven't retired! I am just busier than before. But we are working on a new div 4 round as we are talking now!

    → Reply