FieryPhoenix's blog

By FieryPhoenix, 7 months 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 17.02.2020 18:35 (Московское время).

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. MiFaFaOvO

  2. 300iq

  3. ohweonfire

  4. yosupo

  5. ksun48

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

»
7 months ago, # |
  Vote: I like it +113 Vote: I do not like it

"Moo" as greetings is epic move

»
7 months ago, # |
  Vote: I like it +71 Vote: I do not like it

Farmer John? USACO Web 1.0 training site throwbacks

»
7 months ago, # |
  Vote: I like it +31 Vote: I do not like it

i love you

»
7 months 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!

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months 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.

  • »
    »
    7 months 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?

»
7 months 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.

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

At last a contest with duration > 2 hours.

»
7 months ago, # |
  Vote: I like it +40 Vote: I do not like it

william lin <3

»
7 months ago, # |
  Vote: I like it -47 Vote: I do not like it

S. Americans

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

Contest ID 1306 has gone..

»
7 months ago, # |
Rev. 2   Vote: I like it -18 Vote: I do not like it

[deleted]

»
7 months ago, # |
  Vote: I like it +39 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +14 Vote: I do not like it

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

»
7 months ago, # |
  Vote: I like it +16 Vote: I do not like it

»
7 months ago, # |
  Vote: I like it +78 Vote: I do not like it

Btw why it is combined?

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +119 Vote: I do not like it

      makes hacking more extreme

    • »
      »
      »
      7 months 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.

      • »
        »
        »
        »
        7 months 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.

    • »
      »
      »
      7 months 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.

»
7 months 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 :)

»
7 months ago, # |
  Vote: I like it +38 Vote: I do not like it

USACO2020 February Contest extra round :)

»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
7 months 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 :))

»
7 months 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?

  • »
    »
    7 months 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.

»
7 months ago, # |
  Vote: I like it -12 Vote: I do not like it

can anyone explain about problem hacking ?

  • »
    »
    7 months 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

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

      it was obscure to me thanks

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

      God Bless Our King

    • »
      »
      »
      7 months 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?

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

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

      • »
        »
        »
        »
        7 months 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.

»
7 months 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 .

»
7 months 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!

»
7 months ago, # |
  Vote: I like it +37 Vote: I do not like it

Finally a contest not during school!

»
7 months ago, # |
  Vote: I like it -28 Vote: I do not like it

What is "div1+div2"?

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +19 Vote: I do not like it

    div3 obviously

  • »
    »
    7 months 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.

»
7 months ago, # |
  Vote: I like it -23 Vote: I do not like it

///786/// finally the starting time of the contest is perfect and time length >2hours

»
7 months ago, # |
  Vote: I like it -59 Vote: I do not like it

I hope, you don't have coronavirus and the round will be okay!

»
7 months 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??

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

»
7 months ago, # |
  Vote: I like it -15 Vote: I do not like it

such an interesting round #621 (Div1 + Div2)

»
7 months 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?

»
7 months ago, # |
  Vote: I like it -38 Vote: I do not like it

Is it rated?

»
7 months ago, # |
  Vote: I like it -14 Vote: I do not like it

The time is not friendly to the Chinese

»
7 months ago, # |
  Vote: I like it -7 Vote: I do not like it

No one:
Literally no one:
fieryphoenix : Tags = moo

»
7 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Score distribution??

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

Focus on the new red rating point!

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

Standard scoreboard

  • »
    »
    7 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

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

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

phục hận gang

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

let's help farmer and his cow xD

»
7 months ago, # |
  Vote: I like it -28 Vote: I do not like it

tourist isn't that good anymore lol

  • »
    »
    7 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Look at yourself first before commenting on others !!

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

      emilia_clarke isn't that good anymore lol

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

      emilia_clarke why do I need to look at myself? I'm not gonna follow your rules.

»
7 months 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.

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months 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.

      • »
        »
        »
        »
        7 months 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.

      • »
        »
        »
        »
        7 months 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.

    • »
      »
      »
      7 months 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...

      • »
        »
        »
        »
        7 months 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.

»
7 months 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.

»
7 months 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?

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

»
7 months 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?

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

    it will fall asleep there

    Meanwhile Indian drivers.

»
7 months 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

»
7 months ago, # |
  Vote: I like it +56 Vote: I do not like it

MiFaFaOvO for president!

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

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

»
7 months 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.

»
7 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Hacks for B and D?

»
7 months ago, # |
  Vote: I like it -7 Vote: I do not like it

Pretest 9 for E?

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

what is pretest 9 in D??

»
7 months 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

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

How to solve D?

  • »
    »
    7 months 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.

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

what is pretest 15 in D?

  • »
    »
    7 months 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.

»
7 months ago, # |
  Vote: I like it +3 Vote: I do not like it

When real master reveals his real ability

»
7 months 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?

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months 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.

  • »
    »
    7 months 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.

»
7 months 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.

  • »
    »
    7 months 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.

»
7 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    7 months 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!!

»
7 months 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.

»
7 months ago, # |
  Vote: I like it -13 Vote: I do not like it

How to solve D?

»
7 months 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?

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months 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.

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

      With modulo operations it does not work so fine.

      • »
        »
        »
        »
        7 months 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.

      • »
        »
        »
        »
        7 months 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.

        • »
          »
          »
          »
          »
          7 months 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.

»
7 months 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 :(

  • »
    »
    7 months 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!

»
7 months 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 )

»
7 months 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?

»
7 months 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?

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

    B is trivial implementation, once understood.

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

      Can you explain logic behind solution of B.?

      • »
        »
        »
        »
        7 months 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.

        • »
          »
          »
          »
          »
          7 months ago, # ^ |
            Vote: I like it -13 Vote: I do not like it

          That's not an explanation

          • »
            »
            »
            »
            »
            »
            7 months 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))

            • »
              »
              »
              »
              »
              »
              »
              7 months 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].

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

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

»
7 months 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 ?

  • »
    »
    7 months 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...

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

      Thanks mate ! Passing arr by reference solved the issue !

»
7 months 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?

»
7 months 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 ¯_(ツ)_/¯

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

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

»
7 months 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.

  • »
    »
    7 months 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.

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

      But the only reason I added an extra case was because of their misleading announcement, else the solution was perfect.

  • »
    »
    7 months 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.

    • »
      »
      »
      7 months 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

      • »
        »
        »
        »
        7 months 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.

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

          True. They should have added this case for clarification. Thanks for your reply.

»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Very beautiful problems

»
7 months ago, # |
  Vote: I like it +56 Vote: I do not like it

Congratulations pikmike for becoming Red!!

»
7 months 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.

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

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

»
7 months ago, # |
Rev. 2   Vote: I like it -42 Vote: I do not like it

.

»
7 months 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.com/contest/1307/submission/71322234

  • »
    »
    7 months 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).

  • »
    »
    7 months 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.

  • »
    »
    7 months 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 :(

»
7 months ago, # |
  Vote: I like it +22 Vote: I do not like it

»
7 months ago, # |
Rev. 2   Vote: I like it +22 Vote: I do not like it

MiFaFaOvO is insane!

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

One of my favourite contests now.

»
7 months 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(); } }

  • »
    »
    7 months 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.

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

congratulations to the winners

»
7 months ago, # |
  Vote: I like it +5 Vote: I do not like it

E tests the participants' English level.

  • »
    »
    7 months 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!

»
7 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Many LGM dropped. :|

»
7 months 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.

  • »
    »
    7 months 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.

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

      Got it, thanks. Also how does someone come up with such ideas. Seems quite out of the blue.

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
7 months ago, # |
  Vote: I like it -16 Vote: I do not like it

Poor tourist :')

»
7 months 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"

  • »
    »
    7 months ago, # ^ |
      Vote: I like it +59 Vote: I do not like it

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

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

Contest is very good from USACO

»
7 months ago, # |
  Vote: I like it -39 Vote: I do not like it

I cannot believe that tourist is so bad at coding now. Woah.