FieryPhoenix's blog

Codeforces Round #621 (Div. 1 + Div. 2)
By FieryPhoenix, 5 years ago, In English

Moo! (Hello Codeforces!)

I’m very excited to invite you to Codeforces Round 621 (Div. 1 + Div. 2), which will take place on Feb/17/2020 18:35 (Moscow time).

In this round, you will be helping Farmer John and his prized cow Bessie cowmplete some fun tasks.

The contest will have 7 problems and is combined and rated for both divisions. The duration is 2 hours and 15 minutes. The problems are prepared by me (FieryPhoenix) and dragonslayerintraining. We tried very hard to make them interesting and hope that you will enjoy them too!

This round would not have been possible without the wonderful coordination by adedalic and cdkrot. Thank you so much to the testers as well for all the invaluable advice: tmwilliamlin168, walnutwaldo20, nikolapesic2802, bfs.07, Rods, lynmisakura, JustasLe, and hocky. As always, thanks to MikeMirzayanov for the best systems Codeforces and Polygon.

Good luck and more importantly, have fun and learn something new!

UPD: The scoring distribution is 500 — 1000 — 1500 — 2000 — 2500 — 3000 — 3500

UPD: Editorial

UPD: Thank you for participating! Huge congratulations to the winners!

  1. jqdai0815

  2. 300iq

  3. ohweonfire

  4. yosupo

  5. ksun48

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

Comments Comments (180)
| Write comment?
»
5 years ago, # |
  Vote: I like it +113 Vote: I do not like it

"Moo" as greetings is epic move

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

Farmer John? USACO Web 1.0 training site throwbacks

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

i love you

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

Farmer John comes to codeforces! Anyway, thanks for the later start time, I know we’re pretty under represented here in the Pacific coast, but it feels really nice to finally have a time that is not before 6:30 a.m.. Hoping for a great contest!

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

    The contests are still always in the morning for US people, which is a disadvantage for people who aren't morning people and people who have to work/go to class. It would be nice to change up the start times more like Project Euler does.

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

      Today US people are grateful to George Washington for taking away that disadvantage.

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

    btw, do you know any sites similar to Codeforces that host contests more accessible to Pacific coast people?

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

I always feel so grateful that there are always people dedicate their time and efforts and come up with cool problems and contests so we can all participate regularly enough. Love Codeforces, love you guys <3 <3.

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

william lin <3

→ Reply
»
5 years ago, # |
  Vote: I like it -47 Vote: I do not like it

S. Americans

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

Contest ID 1306 has gone..

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -18 Vote: I do not like it

[deleted]

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

The "MOO!" is so kind! Hope for a USACO round!

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

Thanks for codeforces and authors of this contest!Good luck everyone！

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

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

Btw why it is combined?

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

    I second this question. Combined makes hacking more extreme, adds two impossible problems for div2, while for div1 it adds two trivial problems where reading speed matters most.

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

      makes hacking more extreme

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

      I agree with most of the criticism, but a few counterpoints/clarifications:

      What is wrong with hacking being more extreme? Are you saying this gives extra incentives for div1 people to focus on hacking rather than solving new problems? If that's the argument, then I think it's valid. But hacking as a general concept isn't bad, and it isn't immediately apparent why more of it would be a negative thing.

      I agree that the problems added for div1 are annoying, but I personally know people who have studied algorithms to graduate level and beyond who don't often compete in contests that would likely not do well in a normal div2 contest because of slow speed, but may do better on a div1+div2 combined contest. Perhaps such people are not numerous enough to warrant the combined contest, though.

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

        I agree with most of the criticism, but a few counterpoints/clarifications

        He didnt said much. There is a long discussion on cf (which I failed to find) with a conclusion that combined rounds should be avoided as far as possible. Both comments were made keeping that in mind.

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

      In the end we decided to make round combined due to unique reasons relating to problem difficulties and contest duration.

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

My second contest! Hope, I will be "blue" after it

Good luck to all participants :)

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

USACO2020 February Contest extra round :)

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

Daily contest : CF Round 620 / ABC 155 / CF Round 621 :)

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

I think this is Div.3 because Div.1 plus Div.2 is equal to Div.3 :))

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

What is the difference between codeforces global round and codeforces combined round?

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

    I think the global rounds were a special edition sponsored by some company or something, the combined ones are regular rounds.

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

can anyone explain about problem hacking ?

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

    hacking is to give a testcase that makes a solution to a participant fail(i.e Wrong Answer,runtime error, time limit exceeded)

    who is the defender

    the owner of the code that you try to hack

    what does he do

    he do nothing ,if his solution is absolutely correct then no one can hack his code

    how to hack

    On the dashboard, click the padlock icon for locking a problem (Note, that you can not send your solution for a problem after locking it). Then go to room results, where you can see roommates codes for the problems you've already locked (you can see a certain solution by double clicking on it in the room results table). After you've opened someone's solution, you can consider it and then hack it. When hacking a code, you're entering some testcase on which that code is most likely going to fail (it may be wrong answer, or running out of time/memory limit). When you want to enter a large testcase, you can send test generator instead of typing it. Test generator must be your program which produces a file with a testcase in it. After hacking a code, you can see hacking results. There are two possible outcomes: "Successful hack" — it means the code failed, and you're rewarded with 100 points for that. Otherwise, it's "Unsuccessful hack" (the code did not fail) and you get minus 50 points for that.

    quoted from kingofnumbers

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

      it was obscure to me thanks

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

      God Bless Our King

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

      Is one only vulnerable to hacking if he/she locks his/her own problem? Or is everyone in the room vulnerable?

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

        if you lock your problem you can hack anyone in your room

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

        As stated above, only those who lock their problem can hack (others in their 'room'). Conversely, you are vulnerable to getting hacked by those who do, regardless of whether or not you have locked your problem.

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

hope it will not include mo's algorithm as cow bessie is here .

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

You shouldn't have Bessie and Farmer John cowmplete tasks in a Codeforces contest.

At this rate, they won't have enough time for the upcoming USACO contest!

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

Finally a contest not during school!

→ Reply
»
5 years ago, # |
  Vote: I like it -28 Vote: I do not like it

What is "div1+div2"?

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

    div3 obviously

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

    That means, all contestants (both Div1 and Div2) will be able to give the contest as a rated contestant.

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

as this contest is for both div 1&2, will different rating algorithm be used for this contest??

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

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

When the round is (Div. 1 + Div. 2) is the levels of the problems Div. 1 or Div.2 or Div. 3÷2?

→ Reply
»
5 years ago, # |
  Vote: I like it -38 Vote: I do not like it

Is it rated?

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

The time is not friendly to the Chinese

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

Score distribution??

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

Focus on the new red rating point!

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

Standard scoreboard

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    It have been long since the last time the standard scoreboard occur.

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

phục hận gang

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

let's help farmer and his cow xD

→ Reply
»
5 years ago, # |
  Vote: I like it -28 Vote: I do not like it

tourist isn't that good anymore lol

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

This is probably the first time I leave the contest in the middle just because of boredom. Thank you, problem E statement.

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

    E was actually pretty nice imho. Even though it seems like some tedious crap at first, it turns out to have a clean non-trivial non-magic non-standard solution.

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

      Did I miss something on E? It seems like the solution is just "choose one cow to be the cow on the left who moves furthest to the right" and do a O(M) scan to find how many assignments of cows satisfy that criteria. Implementation wasn't the nicest.

      Then again, I probably missed some implementation tricks.

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

        I did exactly that (more precisely, for each scan, look at each sweetness group, count the number of cows in that sweetness group that can go to the left, how many to the right and how many to both).

        Idk, I thought it was cool. Implementation isn't nice, but I definitely wouldn't call the problem boring.

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

        Yeah, you always have to choose the last cow from the left, but then you have the following problem: choose some points from the "left part" and "right part" such that for each given pair $$$(l_i, r_i)$$$, the situation where $$$l_i$$$ is chosen from the left part and $$$r_i$$$ from the right part simultaneously never happens, $$$S_{l_i}$$$ for all chosen $$$l_i$$$ are all distinct and similarly for $$$S_{r_i}$$$. The pairs are sleeping places of cows.

        The implementation of the rest is simple (~25 LOC for me): group cows by $$$f$$$ and for each value of $$$f$$$, find the number of pairs $$$(l_i, r_i)$$$ that 1. lie in the (left part, right part), 2. (in the left part, out of the right) and 3. (out of the left, in the right part); then, the number of ways to choose 2 cows is $$$(n_1+n_2)\cdot(n_1+n_3)-n_1$$$, and if that's 0, then $$$2n_1+n_2+n_3$$$ is the number of ways to choose 1 cow. It's $$$O(N)$$$. The value of $$$f$$$ for the chosen last cow from the left is handled separately and even more easily.

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

      I read it several times and still could not understand the setup :( Probably spent too much time at countryside to perceive cow problems abstractly...

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

        Maybe I just had luck reading it. I agree that the statement is ugggh.

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

Bessie and John, come like a wind

Magically, stop right here

Left us with, a great contest

Chaotic, yet arousing.

Bessie and John, left like a dream

Where are you, the green of grass (AC)

Left us with, yellow results (WA)

Magically, rating gone.

(Written by a contestant, who find the beauty of Literature in CP)

P/s: We need a way to make a paragraph in CF comments, it will promote poetry in CF.

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

What the ...

MiFaFaOvO (or dls) AK this contest when there are still an hour to go?

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

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

E problem

The moment a cow eats hi units, it will fall asleep there, preventing further cows from passing it from both directions.

Meanwhile Indian cows: You guys can do that?

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +58 Vote: I do not like it

hashtag TouristSoldier you're still number one in our hearts tourist

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

jqdai0815 for president!

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

    This guy is though, after finishing the problems, resent problem D

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

One of my most bad rounds so far, predictor says aprox -120...

Was not able to solve B and not C. Feels sic. :/

Edit: And how redicolus simple the solution to B is, omg.

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

Hacks for B and D?

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

Pretest 9 for E?

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

what is pretest 9 in D??

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

Did anyone else solve problem D using binary search on the answer and segment tree? :( Overkill

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

How to solve D?

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

    Find distances from vertex 0 and vertex n — 1 to all the others using BFS. Now sort the special vertices according to the distance to source. Iterate over all the special vertices except the last one. For each of them find the best "pair" : the vertex that is not closer to the first vertex than the one currently being considered, and that is as far from the last vertex as possible (you can build an array of suffix maximums to do this step in O(1) ). Now using the distances we computed, just get the length of the shortest path with this vertex added. The rest is trivial.

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

what is pretest 15 in D?

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

    Maybe it will be like this: Shortest path from field 1 to field n has no special field, but when added one road the answer charges.

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

When real master reveals his real ability

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

There is a problem about problem E:

"Two sides" means which of the pictures below?

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

    If I understand correctly, the "two sides" means the top picture.

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

      In fact it means the first picture, and a lot of my friends including myself misunderstood the statement.

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

    And in addition, You can pass the samples whether or not you misunderstand the statement. And you will probably get WA on pretest 9 if you misunderstand it.

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

What's the expected complexity in F? My $$$O((n+q) \cdot \log(n))$$$ times out.

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

    I got AC (71329978) with $$$\mathcal{O}((n + q) \log n)$$$ in 670ms.

    I had one HLD path query and two binary searches on the path array per input query.

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

Try to hack my $$$O(k^2)$$$ for D: 71334468

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    But why it passed as per constraints this must fail or time out. I do not tried just because I was not getting approach less than O(k^2) complexity!!

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

can someone explain why this solution gives runtime error on pretest1 .Solution using vectors... and the next submission using arrays passed please explain!!! Solution using arrays.

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

How to solve D?

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

What is the reason for 1 second TL for E? Can you please explain?

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

    Absolutely +1 to this question.

    Had to spend 5 minutes making non-asymptotical optimizations to my Kotlin solution.

    Meanwhile, a cubic solution wouldn't fit into 2 seconds either.

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

      There were a few $$$O(n^3)$$$ solutions with heuristics that we tried to cut.

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

    It seemed tight to me at first too, but with $$$O(N)$$$ arrays + most passes being linear, cache efficiency is high and $$$N^2$$$ is just 25 million.

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

      With modulo operations it does not work so fine.

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

        25 million modulos = 0.37 s locally (admittedly 64-bit, but also weaker than CF machines) and that's supposed to be the heaviest thing in the $$$O(N^2)$$$ solution.

        If 25 million modulos are a serious threat of exceeding TL for a solution that doesn't use anything else slow, that's a problem. Who knows, we'll see.

        UPD: Yep, the same time for modulo and under 0.5 s worst case.

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

        Isn't your solution complexity $$$O(N^2 log MOD)$$$ ? This is almost billion modulo operations, which is really big amount.

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

          Nope, it's not. Values till n are memoized and I am counting inversed values only for these values.

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

Problem E:

Two sides, the left and the right. Hmmm...that's it!

image.png

And this can pass all 4 examples.

Have to say goodbye to legendary grandmatster :(

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

    I am very sorry that this was unclear, and we did not receive a single question about it. Best of luck on future rounds!

    → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +17 Vote: I do not like it

tourist solved the first problem in less than a minute :O I didnt even read the problem statement in that time (probably my page also not opened by then :P )

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

I tried something different for G, I take the edges (u,v,w) such that d[v]-d[u]=w. Then find the mincut in this graph. This gives us the edges whose weight we should increase simultaneously to increase the length of shortest path. So if the remove these edges and again run a dijisktra than the distance of nth node should give us the weight until when we need to keep increasing the weights of the edges of mincut and we can stop this process if the nth node is not reachable. But this gives me WA on pretest 14. Any ideas why this solution is wrong?

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

Explain to me what your criteria is to say B was easier than C?

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

    B is trivial implementation, once understood.

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

      Can you explain logic behind solution of B.?

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

        In one step the cow can jump at most max(a[]) distance. The last two jumps need not to be direct jumps, the cow can jump a bit left, or right with the first of the both last jumps.

        See the tutorial for formulars.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it -13 Vote: I do not like it

          That's not an explanation

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

            Think of it this way: If D is already a distance that you can jump, only then will the answer be 1

            Else, we have to create a polygon such that D is a side of it. The condition for any distance x being a side of a polygon is that it is <= the sum of all other sides

            Therefore, just take the biggest element and the answer will be max(2, ceil(D/big))

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

              Now this is an explanation (to y'all down-voter haters!).

              Thanks [user:Aggu_010000101].

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

Do you know what about may be the 17th test task E?

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

Why does the code with complexity O(len(s)*26*log(len(s)) times out in C ?

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

    look at this: LL countGreater(vector<LL> arr, LL n, LL k)

    each time you call it, the vector arr will be copyed once. So you get a TL.

    Sorry for my poor English...

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

      Thanks mate ! Passing arr by reference solved the issue !

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

Pretests for D seem a little weak, even some LGMs got problems. Actually, I expected this because the answer is just a shortest path length which in some (most?) cases will be not changed after the optimal edge addition. What was the reason for not asking for the optimal edge as well?

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

Awesome contest! I wish pretests were a little bit stronger for D, but you win some and lose some ¯_(ツ)_/¯

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

As time progresses, the frequency of WA in Problem D increases. Interesting...

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

In the announcement, it was written "positive difference" rather than non negative for question C. Then how are they considering single character occurence? The value of d is zero in that case. I got my solution failed in the main test because of their cheap mistake.

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

    If you look below the sample input and output it clearly shows that zero difference is possible. That being said, the problem statement should have been fixed.

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

    d can be anything in this case, but the sequence contains only the first element.

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

      Still the announcement was quite ambiguous. Just look at the status of question C with Wrong answer at test 36. All the people are having same problem for case of n = 1

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

        I think the statement was clear, it even explained the first example in detail right in the text. In particular, it says and aaabb is hidden 1 time, suggesting that progression on size 1 is valid.

        On a separate note, I think it would make sense to have a case with a single character in the pretests.

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

Very beautiful problems

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

Congratulations awoo for becoming Red!!

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

It seems for D people who sorted special fields based on distance from field '1' (let's call this sorted array with special field indices as ar[]) and checked the shortest distance after adding edges between just ar[i] and ar[i+1] had passed.
Is there an explanation for this ? or is it due to weak tests?
For example, look at this submission.

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

Congratulations amnesiac_dusk for becoming International Grandmaster and First Rank in India!!

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it -42 Vote: I do not like it

.

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

hello everyone , I have submitted third question in this contest (621 div1 + 2) after submission it is showing runtime error on test 36. but in my compiler the answer is exactly coming what the answer of test 36 also on multiple online compiler like ideone.com but they are giving correct answer also i have checked my code there is no chance of runtime error on test 36. please anyone help in this matter ! https://codeforces.net/contest/1307/submission/71322234

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

    Nasty mistake is here:

    ll i=s.size()-2

    s.size() is an unsigned type, as a result, if s.size() == 1, i becomes 4294967295 (unsigned -1).

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

    You can't use s.size()-1 as s.size() is unsigned number.

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

    I am sad for you :( Your bug is in the line 10, s.size()-2 will give you RTE, so you should have cast it first. I ran your code after fixing this and it is AC :(

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

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +22 Vote: I do not like it

jqdai0815 is insane!

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

Can anyone explain this logic for the D problem

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

One of my favourite contests now.

→ Reply
»
5 years ago, # |
  Vote: I like it -46 Vote: I do not like it

It is unbelievable that following code can not AC;

include <bits/stdc++.h>

using namespace std; int n,x,ans; int a[100005]; void solve() { ans=0; cin>>n>>x; for(int i=0;i<n;i++){ cin>>a[i];ans=max(ans,a[i]); if(a[i]==x){ cout<<1<<endl;return; } } // cout<<a[0]<<endl<<endl; if(x<ans) { cout<<2<<endl;return; } else { if(x%ans!=0){ ans=x/ans;ans++;} else ans=x/ans; } cout<<ans<<endl; } int main() { int t; cin>>t; while(t) { t--; solve(); } }

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

    Don't paste solution like this. Give link for solution. Also mention the problem no.

    As far i understand it is a solution for problem B which was failed.

    The reason is you must take whole input when there is multiple test cases. Suppose you have array of length 5 and you get answer after taking 3 input you get the answer. If you stop taking input here then 4th element of array will be n for next case which is not supposed to do.

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

E tests the participants' English level.

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

    Yes, it was a little difficult to word the statement concisely, but we felt the problem was too nice to discard for that reason. I hope your overall experience was still positive!

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

Many LGM dropped. :|

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

I don't understand how complexity of F is $$$n*log(n)$$$. The number of non-overlapping rest stops for a given node can be very large, and I have a concrete counter-example for $$$O(n^2)$$$, if I understand the editorial correctly. Can anyone please explain proof of complexity.

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

    The number of non-overlapping rest stops for a given node indeed can be large, but only if we consider the distance $$$k$$$. But there is at most one group of rest stops on distance $$$\frac{k}{2}$$$ and the author solution uses this fact.

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

another D : 1016F - Road Projects

→ Reply
»
5 years ago, # |
  Vote: I like it -16 Vote: I do not like it

Poor tourist :')

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

Codeforces translators:

using weird words like haybale

at the same time can't see the difference between feeding and eating

EDIT: Uh, it seems I was wrong. I can't comprehend how "giving food" is the only meaning of "feeding" I can find, but at the same time Internet provides example "cows feeding in meadow" or "baby feeds one a night" wtf?. Who is it feeding? I would use "being fed"

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

    Do you think the authors from the USA wrote statements in Russian?

    → Reply