SlavicG's blog

Codeforces Round 918 (Div. 4)
By SlavicG, 13 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, sparkles, 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

Comments Comments (222)
| Write comment?
»
13 months ago, # |
  Vote: I like it +4 Vote: I do not like it

Thank you

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

very handsome.

→ Reply
»
13 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
»
13 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
»
13 months ago, # |
  Vote: I like it +15 Vote: I do not like it

Thank you! Nice photo.

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

Every div 4 is good

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

Hope to be a great contest before Christmas...

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

Are there watermarks on those Christmas hats?

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

so handsome

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

It will be my first Div 4 participation ^_^

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

I would aim to solve >80% problems.

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

The cap on your head looks edited

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

As a tester, Santa helped me test the contest

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

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

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

flamestorm face reveal!?!?!!

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

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

As VIP testers, this was our testing room:

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

i wanna be specialist on this contest :)

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

Best of luck to all participants!

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

As a tester, I changed my color.

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

Hoping I could reach specialist :D

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

Can't wait to get +ve delta

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

Merry Christmas!

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

Thanks for the round!!

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

Good luck everyone

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

in queue LOL

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

Thanks for the round !!!

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

Loved the problems on this round <3

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

Awesome problems, guys! Keep it up!

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

Nice contest

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

    Really? Can you send code

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

      I don't know how it is possible:)

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

Screencast and Solutions to all problems

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

    This video is unlisted btw.

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

      Still clueless could you explain it to me?

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

        problem

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

          does solving this problem will help me understand E ?

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

          I'll try to do using this hint.

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

            GL

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

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

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

can I do F in PYTHON without use SortedList?

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

    (Co-ordinate compression + segment Tree) will work too.

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

Can anyone explain ideas behind F and G?

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

    Problem F can be soved using ordered set.239369576

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

    Bro really overthinking B

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

    read this blog

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

      now it doesn't matter my F got hacked blind me couldn't see there is insertion operation on vector in worst case case it's O(n^2) but the article says O(n * log(n))

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

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

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

    you don't need Ordered Multiset for F.

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

my face when tourist got hacked ._.

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

    what test was he hacked on?

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

      I don't know. I think there is no way for us to know that right now

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

What was the idea of F? Segment trees?

→ Reply
  • »
    »
    13 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
  • »
    »
    13 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
  • »
    »
    13 months ago, # ^ |
    ← Rev. 2   Vote: I like it +1 Vote: I do not like it
    hint
    hint2
    → Reply
»
13 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
  • »
    »
    13 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
»
13 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
»
13 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
»
13 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
»
13 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
  • »
    »
    13 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
»
13 months ago, # |
  Vote: I like it +2 Vote: I do not like it

lol. tourist's solution of G got hacked.

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

can we solve f without fenwick tree

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

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

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

My Screencast
Post contest discussion stream

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

Thx

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

why O(nlogn) solution not pass problem F?

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

Hack this, please!

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

F can use sweep line?

→ Reply
»
13 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
  • »
    »
    13 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
»
13 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
»
13 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
»
13 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
  • »
    »
    13 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
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      no idiot it's n sized vector with each element equal to 1e13

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

Where can I find the editorial? or is it unavailable

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

    editorial

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

          Thanks bro, maybe I should be more patient

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

Editorial when?

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

    don't worry system is retesting them again

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

        system testing is going on, wait for sometime

        → Reply
»
13 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
»
13 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
  • »
    »
    13 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
»
13 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
  • »
    »
    13 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Spoiler
    Why?
    → Reply
»
13 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
»
13 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
»
13 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
»
13 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
  • »
    »
    13 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
»
13 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
»
12 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
»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

SlavicG why u retired

→ Reply
  • »
    »
    6 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