Блог пользователя zscoder

Автор zscoder, история, 8 лет назад, По-английски

Hi everyone, it's me again!

Codeforces Round #372 (Div. 1 + Div. 2) will take place on 17 September 2016 at 16:35 MSK,

After my last round, this will be my second round on Codeforces. I believe you'll find the problems interesting and I hope you'll enjoy the round.

This round would not be possible without danilka.pro who improved one of the problems that made this round possible, and also helped in preparing and testing the round. Also, thanks to all the testers, IlyaLos, HellKitsune and phobos and thanks to MikeMirzayanov for the awesome Codeforces and Polygon platforms.

ZS the Coder and Chris the Baboon's trip in Udayland is over. In this round, you'll help ZS the Coder solve the problems he have randomly came up with. Do you have what it takes to solve them all?

The problems are sorted by difficulty but as always it's recommended to read all the problems.

We wish you'll have many Accepted solutions and enjoy the problems. :)

As usual, the scoring will be published right before the contest.

UPD : There will be 5 problems in both division as usual.

Scoring :

Div. 2 : 500 — 1000 — 1500 — 2000 — 2500

Div. 1 : 500 — 1000 — 1500 — 25002750

Good luck and I hope you enjoy the problems!

UPD : Contest is over. I hope you enjoyed the contest and problems :) I'm sure some of you wants to see the editorial now, so here it is while we wait for System Test to start.

UPD : System tests is over. Here're the winners :

Division 1 :

  1. jqdai0815

  2. matthew99

  3. jerry

  4. Burunduk1

  5. JoeyWheeler

  6. LHiC

  7. SanSiroWaltz

  8. dotorya

  9. Arterm

  10. zeliboba

Division 2 :

  1. amethyst0

  2. JOHNKRAM

  3. huzzah

  4. Vax

  5. KyleChen

  6. LeiQ

  7. Tomer.Adar

  8. creatnx

  9. OrangePlus

  10. Yukikaze

Congratulations to them!

  • Проголосовать: нравится
  • +423
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).

»
8 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

I like Chris the Baboon...

»
8 лет назад, # |
  Проголосовать: нравится -33 Проголосовать: не нравится

hope that scoring distribution will be announced before the contest ... unlike the previous round

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    what is the benefit of scoring distribution before the contest ?!

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Sometimes we go to C before B if C contains 1500 points and B 1000 :) but if both have same points, we try to see each of them serially. that is the benefit I think.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I know. But I said before the contest. you can decide what problem to solve when you saw dashboard !

        (maybe it buys some time to think about it before the contest!)

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +88 Проголосовать: не нравится

        I think you should solve tasks instead of worrying about score

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).

»
8 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

last round was absolutely amazing for learning purpose! DP + GRAPHS + MATHS + ADHOC.. hope to see more such rounds in future covering diverse areas with good problems.. :) thank you.. :D

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Excuse me, this round overlaps with topcoder Google Sponsored SRM. Is there any possibility of changing the time of contest?

»
8 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

GL & HF :D

»
8 лет назад, # |
  Проголосовать: нравится -30 Проголосовать: не нравится

zscoder , It would be great if u could ensure that questions aren't googlable _/_

»
8 лет назад, # |
  Проголосовать: нравится +38 Проголосовать: не нравится

How come it's your second contest after such a short period of time? "We have a long queue, sorry for not answering".

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    We just worked with a huge pool of problems, part of which are gone to Round 369, another part come to this round.

»
8 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Good luck everyone and a high rating!

»
8 лет назад, # |
  Проголосовать: нравится -38 Проголосовать: не нравится

It's about one hour that I submitted a code, and it's still in queue!

hope there be no long queue during the contest.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Salute! Prolific problemsetter(potential writer of Round 373:P

»
8 лет назад, # |
  Проголосовать: нравится -21 Проголосовать: не нравится

Hope this time Codeforces's Server will Work Properly not like the last time ... Very disappointed with the last contest that that turned out to be UNRATED !!!

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It wasn't the previous one, it was the one before. Round #371 was correctly held, so it should be the same on Saturday.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think there is schedule conflict with SRM698 (1:00 AM GMT+9). Could we change the start time earlier or other day?

»
8 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

What is good to have a Korean problem setter?

NOW WE HAVE A FEASIBLE COMPETITION TIME FOR EAST ASIA. You are my hero man

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Last round of zscoder div2 B's test case was absolutely amazing . Pretest was passed in the contest for B , but i got wrong ans on test no. 116 . How amazing it is !

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

    Some of the later test cases actually came from successful hacks of the competition, so not all of them are done by me.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thank you ~~~~~ zscoder ~~~~~ for writting this contest :) the last contest you wrote was very cool.. Hope it will be also :)

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I'm glad you enjoyed the last round. I'm sure you'll find this round more interesting :)

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Good luck everyone and happy rating

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Has the server issue been solved? round 370 became unrated for this.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

thanks zscoder for your awesome contribution in codeforces.

»
8 лет назад, # |
  Проголосовать: нравится -33 Проголосовать: не нравится

i hope problems will have ideas this time because problem A&B in the previous round were just about coding with no ideas

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -39 Проголосовать: не нравится

    I do agree! last contest's A & B were less logic oriented, but more coding oriented, but problem D was really nice!

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This is my last contest before my school starts :( Gotta do well this time.

GL & HF everyone.

:)

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +24 Проголосовать: не нравится

    Not sure why you've been downvoted. I'll risk my reputation too.

    Good luck!

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      thank you I'm not sure why I got downvoted too I was just wishing good luck for everyone I don't see anything harmful in that.

»
8 лет назад, # |
  Проголосовать: нравится -41 Проголосовать: не нравится

Oh no, can you please make the contest time as usual as it was :(

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

good luck and high rating~

»
8 лет назад, # |
  Проголосовать: нравится -56 Проголосовать: не нравится

مش لازم تحشر اسمك ف كل المسائل .... فاكس الجو بتاع السبكي ده :V

»
8 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Maybe we can have more animals in coming contest's problems. I really enjoyed them xD. And sorry who is the Chris ???

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +37 Проголосовать: не нравится

    Well I think most people will like the problem to be straight to the point and simple to read and understand. (i.e. short statements)

    Chris is the guy who says he likes Chris the Baboon above. :)

»
8 лет назад, # |
  Проголосовать: нравится -15 Проголосовать: не нравится

Hope the round will as interesting as zscoder's last round.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

i hope it will contain more thinking and less knowledge , and good luck for everyone .

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good luck and have a hight rating, thanks you every one.

»
8 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

What does the tag "multiple-of-three-again" mean ? :"D

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

GL and high rating everyone!

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Can I rush into Div.1? jump ahead////

»
8 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

10 min delay.

»
8 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

why you guys do this at very last time? (the delay) :3

»
8 лет назад, # |
  Проголосовать: нравится +33 Проголосовать: не нравится

Swarm of comments about delay incoming...

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

:/

»
8 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

Now much smaller gap between Codeforces round and Topcoder SRM

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +30 Проголосовать: не нравится

The dalays are really annoying when I make plans taking into account the time and duration of a CF contest. Now I have a date and will have to leave 10 minutes before the contest ends, and I'm sure a lot of people are in the same situation. :/

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

Div 2 round starts 1 second after div 1. XD

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится
»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Div2B Pretest 6 is messing up a lot of people this contest

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Div2 B should specify that all '?' those that are not in the 26 range solution must also be replaced.I think even though many people got the logic right, not including this fact is giving them many penalties.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    i didn't just forget the "?"s but i kept outputing only the 26 letters substring , even when i fixed that i forgot replacing the "?"s . it was pretty clear in the problem statement but i didnt fully read it :( " This string should match the string from the input, except for the question marks replaced with uppercase English letters "

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

    Fuck. They have put wrong words in bold.

    'all the question marks with uppercase letters' should be ' all the question marks with uppercase letters'.

    Or even better:
    ' ALL the question marks with uppercase letters'

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    The problem states: This string should match the string from the input, except for the question marks replaced with uppercase English letters. There is no reason to believe it is enough to replace a minimal amount of question marks.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Yes, there are no logical reasons to believe in that, but there are psychological reasons. We are not computers, we are humans with biases :)

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится -92 Проголосовать: не нравится

Why do I have a wrond answer for presest 1??? Help me please. My answer for 1 pretest is the same as a correct one. here is the code:

map<char, int>a;

int main(){ ios::sync_with_stdio(false); string s; cin >> s;

string ss = "";
if (s.size() < 26)
{
    cout << -1 << '\n';
    return 0;
}

bool o = 0;
int l = 0;
for (int i = 0; i <= s.size() - 26; ++i)
{
    a.clear();
    bool ok = 1;
    string str = "";
    for (int j = i; j <= i + 26; ++j)
    {
       a[s[j]]++;
       str.push_back(s[j]);
       if (s[j]!='?'&&a[s[j]] > 1){
         ok = 0;
         break;
       }

    }

    if (ok)
    {
       ss = str;
       o = 1;
       l = i;
       break;

    }
}


for (int i = 0; i < ss.size(); ++i)
{
    if (ss[i] == '?')
    {
       for (char c = 'A'; c <= 'Z'; ++c)
       {
         if (ss.find(c) == ss.npos)
         {
          ss[i] = c;
          break;
         }
       }
    }
}

if (!o)cout << "-1" << '\n';
else {
    for (int i = 0; i < l; ++i)

       cout << s[i];

    for (int i = l; i <= l + 26; ++i)
       cout << ss[i - l];

    for (int i = l + 26 + 1; i < s.size(); ++i)
       cout << s[i];
}

}

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

    Don't post code during contest

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Seriously, Contest blog should be blocked during contest.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    you can't post code in here right now and i can't help you , but what i can say is that i had the same problem and it can be fixed.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      How?

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I used codeforces' "custom invocation" to test my code on their servers and track down the problem, i changed a while condition to a variable and I assigned the boolean statement to it (check my first two submissions on B) , i still dont know how did the code run correctly on my compiler and on ideone but gave -1 on CF

»
8 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

C is too hard :/

»
8 лет назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

Sadness is when you code D, but can't submit because you didn't solve anything else, and there's only time to solve A, and you don't even know if D will pass, so you don't want to risk it, so you're just sitting there, waiting for the contest to be over :(

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Missed D by a second :/

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain solution for Div.2 C? I got TLE on pretest 5 :/

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    Jump for i-th level is to number i * i * (i - 1) * (i - 1)

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can you explain that?

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +3 Проголосовать: не нравится

        You want the number before the sqrt to be i ^ 2 * (i+1)^2 since it must be divisible by i and be a prefect square whose root is divisible by i+1. Doing so would make the number the start of level i (for i > 1) be i * (i-1) (simple sqrt of the above expression with i larger by one). So you want to solve i * (i — 1) + i * x = i ^ 2 * (i+1)^2 i * x = i ^ 2 * (i+1)^2 — i * (i-1) x = i * (i+1)^2 — i*(i+1) x = i^3+2i^2+1

        for the transition from level 1 to 2 you want to get the number on the screen to 1 ^2 * 2 ^2 so you print 2

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Why not i*i*(i-1) — i + 2 ?

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        i * i * (i — 1) — i + 2 = i ^ 3 — i ^ 2 — i + 2

        If i = k + 1

        = (k + 1) ^ 3 — (k + 1) ^ 2 — k — 1 + 2 = k ^ 3 + 3 * k ^ 2 + 3 * k + 1 — k ^ 2 — 2 * k — 1 — k — 1 + 2 = k ^ 3 + 2 * k ^ 2 + 1

        Which is identical to what I proved above, just with a different definition for i(my i = your i — 1).

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I have passed pretests with this: for i in range [2, n] just outputed (i+1)^2*i-(i-1). I don't know if it is right or not.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I wish I had the time to participate the contest, when I came back from other stuff I solved the div2 questions pretty quickly. Feels bad to miss a train straight towards purple.

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

How to solve Div1 B?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It scares me when I spend 2 hours coding something and then a much stronger coder asks how to solve it :S

    Now I'm confused if I'm right. Well, at least I won't lose ratings.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится -20 Проголосовать: не нравится

    How I've tried:

    Set all unknown edges to 1.

    Find shortest path s->t (assume it's equal to L2)

    Then if L2 > L then there is no answer. Else if L2 = L, output graph else Count all edges on shortest path (assume cnt). If cnt = 0 then no soluton.
    one of edges set to L — L2 + 1. All other edges (outside shortest path) set to INF.

    But I didn't send my solution.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      That wouldn't work with e.g. 4 5 20 0 3 0 1 0 1 2 0 2 3 0 0 2 5 1 3 5

      because you will take the shortest path with the three '0' edges, fix them as 1,1,18, but then there will be a path of length 6 through one of the '5' edges.

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

      How do you select that particular edge whose cost you increase? Consider this case.
      5 5 10 0 4
      0 2 0
      0 1 1
      1 2 2
      2 3 3
      3 4 0

      Here, if you increase the cost of the edge 3-4, it works but it fails to find a solution if you choose the edge 0-2.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I had an idea and although I couldn't finish it in time, I will explain it because I believe it's correct. The minimum weight we can use for each edge is 1, so let's use it for every single edge with erased weight. Find the shortest path, say L'. If L'>L, then no solution. if L'==L, then we have found a solution. Assume L'<L and D=L-L' and again put 1 on every edge that doesn't have weight. Let's loop over the edges that have no weight and make the current weight from 1 to 1+D. After doing it for the current edge, let's find the shortest path and if it is L, we are done. Otherwise, it will be less than L and we can continue the process with the other edges. To do that fast, we can just binary search for the last edge that got its length increased before the shortest path became L :)

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Is my solution right? I hope it will pass the pretest.

    1, Run Dijkstra to find a shortest path (1).

    2, Assign the weights of "erased" edges on shortest path (1).

    3, For other "erased" edges, assign weight 10^15 (so (1) has more chances to be a shortest path of length L)

    4, Dijkstra again to check.

    5, Print the result.

  • »
    »
    8 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

    I didn't participate in the contest, but keeping an upper and lower bound of a node and run a Dijkstra should be a good idea.

    When visit a node: if a nearby edge is weighted do the same thing as Dijkstra and set the underground to the distance, and if there is no question marked edge then also set the lower bound to it. If there is a question mark edge, set the lower bound to dist+1 and upper bound to INF-1.

    Of course the Dijkstra will be ran under the upperbound.

    *I am a bit drunk right now, so I may miss out something important, and yes I typed "hit" instead of "bit" before I revised this...

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I thought to find all the simple paths between S and T. If on any one path number of zero weights >= (L-remaining weight on this path) then answer exist else answer doesnot exist.

    Now on this path we replace all zero weights by one except the last zero weight. On the last zero weight edge we put weight = L - X where X= number of zero weights on this path-1

    Now we can put INF on rest of zero weight edges so the given condition gets satisfied. I could not implement within the contest time. :( Can someone comment on the correctness of this solution ?

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      You need to run dijkstra again to confirm it is valid.

      4 4 13 0 3 0 1 0 1 3 0 0 2 11 2 3 1

      should answer "NO"

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Really, really good problems, thank you! :) I decided to start with C and finished it 15 minutes before the end. However it was better not to submit it without having another problem solved so I started B but couldn't finish coding it, both B and C were pretty nice :) I will send this code when system test is done, let's see if it passes :)

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

C Div 2. Anyone? How to solve it?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Count l from 1 to n and for each l output l == 1 ? 2 : l * l * l + 2 * l * l + 1. That's all you need to do.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    just for all i = 1..n output i * (i + 1) * (i + 1) — i + 1

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    number at level k can be of form t*k as it has to be multiple of k assume we add x times k to number then

    (t*k)+k*x= ((k+1)*r)^2 // rhs is to satisfy next level

    r=k is a solution of this equation x=(k+1*k+1 * k )-t it will be in range always as max it can go cube of 10^5

  • »
    »
    8 лет назад, # ^ |
    Rev. 3   Проголосовать: нравится +12 Проголосовать: не нравится

    Consider a constructive method:

    When you are in L(evel)4, you have number k.

    If you want to advance to L5, you have to make your number a perfect square and can divide by 5, also you have to make this target number 4-divisible because you add 4 for every press, then 5*5*4*4 may be a good choice.

    Let's try this simple idea from L1 to L5.you have:

    L1 2 --> 4 = 1*1*2*2

    L2 2 = 1*2 --> 36 = 2*2*3*3

    L3 6 = 2*3 --> 144 = 3*3*4*4

    L4 12 = 3*4 --> 400 = 4*4*5*5

    L5 20 = 4*5 --> ...

    This idea works really fine and performs beautiful.And now you can summarise the final expression Li = i == 1 ? 2 : (i)*(i+1)*(i+1) — (i-1) and now you are done.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Why is it
      (i)*(i+1)*(i+1) — (i-1)
      rather than this
      (i)*(i)*(i+1)*(i+1)

      I see the second formula in the pattern that you showed.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        When you are in Li, you already have i*(i-1) and your target is (i)*(i)*(i+1)*(i+1), the difference is i*i*(i+1)*(i+1) — i*(i-1) ,for a single push, you increase by i, so you gonna divide the difference by i, and you'll get (i)*(i+1)*(i+1) — (i-1).

        Sorry for omitting this process.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks everyone :)

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I like this round. Problems are so interesting!

I hope my rating will be increased.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can someone explain the solution of Div.2_B? I don't know why my code is wrong. so i want to compare right solution :>

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Do you print the whole string? Do you print any question marks?

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I change ? mark to alphabet.

      i passed till pretest 5, but i can't pass pretest 6.

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        You only replace the ?s in the substring. You need to replace every ? in the input.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).

»
8 лет назад, # |
  Проголосовать: нравится -26 Проголосовать: не нравится

plz don't open round more or I'll hate you

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

20709423 This is the submission for Div 2 B Can anyone tell me why this one fails on PRETEST 6

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

I really liked problem B! But I don't understand the reason behind its constraints. Does the solution intended to get AC? (Considering the 4s time limit...)

I had that solution but thought it'd fail. I was hoping to find O(n2 + nm) solution (or something like that), but I came up with an one!

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    could you explain your solution please

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 5   Проголосовать: нравится +20 Проголосовать: не нравится

      I think you can understand the whole solution by just looking at my submission! 20704461

      A brief description:

      First, consider the weights of erased edges equal to 1. Then run dijkstra and find the distance from s to any other vertex. Let d[v] be the distance between s and v.

      Let need be L - d[t]. Now run another dijkstra from s. We are aiming to add need to the distance from s to any other node that we could! When you are relaxing an edge vu, check if you can change the weight of this edge in order not to make the distance from s to u less than d[u] + need.

      So in the second run of dijkstra we add this extra if before relaxing the edge e = vu:

      if(isErased[e] && dist[v] + w[e] < d[u] + need)
      	w[e] = d[u] + need - dist[v];
      
»
8 лет назад, # |
Rev. 2   Проголосовать: нравится +16 Проголосовать: не нравится

Problems are really interesting and challenging, great!

Some personal feelings:

1.The difficulty progression from D2.C to D2.D is really harsh, I failed to figure out any workable solution in last half of the contest.Anyway, it's a good problem.

2.D2.C will give a really short constructive solution.It's beautiful, but also lost some fun of hacking.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I don't think this is a good codeforces round. No offence... Maybe just that i'm not good at solving these problems... My rating... Excited

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Maybe many-people thought "What the hell B pretest 6?"

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    My solution failed on pretest 6 because I didn't change all question marks to letters, or I wasn't printing the whole string, just a 26-letter substring.

»
8 лет назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Problem Div 2D. Is it true that we have to find shortest path that contain the least amount of erased edge?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please help!!! I dont know whats wrong with those B->http://mirror.codeforces.com/contest/716/submission/20707069 C->http://mirror.codeforces.com/contest/716/submission/20710823

Its more likely that I am wrong in C..... I understand the editorial but I dont know whats wrong with mine

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Same here dude! :( ! I still have no clue why my submissions are wrong despite implementing the same methods

»
8 лет назад, # |
Rev. 6   Проголосовать: нравится +10 Проголосовать: не нравится

Allow solutions with finding 1/x (modulo mod) using mod — 2 as a power instead of phi(mod)-1 pass pretests in Div1C is the evilest thing I've ever seen :D

»
8 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

As I am unable to submit because of pending systests, can someone look at my code for div 2 D and let me know if it will pass?

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Всем привет:) Помогите понять, как работает этот код по Adiv2 на тесте
~~~~~
1 2
3
~~~~~
Это решение читает N+1 чисел. Может кто объяснить, как работает scanf ?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Если числа в input кончились, то он считывает последнее => получается тест

    1 2
    3 3
    
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    Там считывается N чисел. scanf("&d",&x); — ничего не считывает.

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Problem Div2-B 716B - Complete the Word was similar to this recent problem 701C - They Are Everywhere. I just copied my solution from that round.

»
8 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

I was printing only 26 letters for Div2B. OMG.

»
8 лет назад, # |
  Проголосовать: нравится +29 Проголосовать: не нравится

Div 1B RIP.

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится -27 Проголосовать: не нравится

.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

RIP B :( div1 & div2

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).

»
8 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

zscoder is really lucky for me. In his last round, I got  + 119 and now expecting  + 130.

The questions were really nice! Hope to see more rounds from you :D

»
8 лет назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

Can anyone tell me why am I getting WA here.
It reads WA on 9 because "Integer 0 violates the range [1, 1000000000000000000]" whereas 0 is the vertex not the weight.
This looks fishy. Anybody any clues?

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Very Very Very bad round for me! Back to Earth Again After flying high last time out

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    lol, -89 is not that bad, I got -122 once.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    I got a -109 because B failed systest. I only had to change literally one line. Imagine how I feel man. If you look at my rating, the last two contests I participated in were the worst. Coincidentally, both contests were written by zscoder lol ;(

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

      I'm sure u'll be back with a bang. I can completely understand what this feels like. Sometimes, its all about what kind of day ur having. Let this miserable feeling drive u to completely finish the next contest.

»
8 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

Eagerly waiting for editorial

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by zscoder (previous revision, new revision, compare).

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Finally became blue for the first time today :) :D

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What in 22 test in div1 B?

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is correct answer for test case #44 for problem B. Is it -1.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I got wrong answer on test case 44 for problem B (Div2). That happened because I misread the question and instead of looking for substring I looked for subsequence.

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I liked the prerequisites section for each problem in the editorial, that is very helpful. Hope that next editorials will have this section.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to get full test of any problem in problemsets? Not just the first few numbers.

»
8 лет назад, # |
Rev. 4   Проголосовать: нравится +13 Проголосовать: не нравится

LOL worse did this contest and got +644.

Does this set a record? :D

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Yeeeaaaahhh!!11!

    Must notify, that my previous round was much more better, and that time i got only +319.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In div2 B pretest 6, http://mirror.codeforces.com/contest/716/submission/20710802

Seriously,is that a bug?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Your solution outputted the string: ABABABBABDEFGHIMNOPQRABABABABATUVWXYAAAAAABABABABAAAAAAAAAAKLCSJBAAAAAAAAAZ, which obviously does not contain a valid substring.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Auctully,it "contains all the letters of the English alphabet exactly once"

      Try to count it,I have counted that my output and Jury's answer have same number of 'A',also other alphabet,just different of position.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In the second problem the required output is : "If there is no way to replace all the question marks with uppercase letters such that the resulting word is nice, then print  - 1 ". so I understand that i should print the nice sub string which contains the letter only once and all the alphabet letters .. so how could test six be correct ? I mean , the problem statement is not clear enough concerning this part that i should print the whole string not only the required nice sub string

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    From problem statement, This string should match the string from the input, except for the question marks replaced with uppercase English letters. So you should print the whole string.

»
8 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Please check this out , my submission for div 2B #372 Running the same code on ideone and my pc gives me correct answer , while CF compiler does something else. Is it some bug, costed me rating loss , please check ... Help me out if i am doing wrong somewhere! Ideone link — http://ideone.com/tJdGrc My submission link CF — http://mirror.codeforces.com/contest/716/submission/20716292

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    You are printing a "?" at the end of the correct string! Recheck it :) Specially the print statements

    I tried it using G++ and i got the correct answer ! No idea why CF prints an additional ? :(

  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Size of ans should be at least 27, and ans[26] = 0.

    • »
      »
      »
      8 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      It worked . But why is it so ? Could you please explain ? Why do g++ compiler shows correct answer while Cf compiler doesnt??

      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Compiler is allowed to do anything with invalid program including sometimes producing expected output. Read this.

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Great Contest It Was... Thanks To ZS-the-Coder !!! Waiting for your next one ...

»
8 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

Div. 2 B solution with using regexes 20716509, Perl.

»
8 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

Hey guys can you help me with something at problem div2 D? :)

If you replace all zeroes with 1 and you run Dijkstra you should obtain the shortest path from S to T.

If it is less than L, then it should be a solution.On this path(which contains now 1 instead of zeroes) you transform an 1 in a number which should make this path's length L.The rest of zeroes in the graph(which were transformed in 1) should become a huge number as 10^18.

Why this approach doesn't work? I mean if it were to be another path from S to T lower than the path we just transformed, it could be just in one condition.There was an path which contained no 0 in the first place because if it were to be a path with an zero, it would have become a number which surpasses L in the first place.

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    Consider this test:

    4 4 5 0 3 
    0 1 0
    1 3 0
    1 2 2
    2 3 1
    

    After changing zeros to ones you get the shortest path from 0 to 3: 0-1-3

    Its length is 2, so you need to add 3 to one of the edges. If you choose 1-3 (because there's no reason not to choose it), the length of this path becomes 5. However, the shortest path from 0 to 3 is now 0-1-2-3 with length 4.

    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I figured out after minutes why I was wrong :)).You are right.Thanks for helping :)

»
8 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Hi Guys! I got a runtime error on test 84 in Div2 B problem. Here the length of the string is less than 26. But my loop is as follows: for(i=0;i<=s.length()-26;i++) and it gives rte but instead if i store s.length()-26 in a variable,say p, and write the loop as for(i=0;i<=p;i++) its getting accepted. Can you please give me a reason as to why this is happening? My rte code: http://mirror.codeforces.com/contest/716/submission/20693471 My ac code: http://mirror.codeforces.com/contest/716/submission/20713665 Please help me out. Thanks in advance!

  • »
    »
    8 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

    because s.length is an unsigned variable so when you do "s.length — 26" it turns to a big number because it can't be negative so you should do an if statement before the loop that is like:

    if(s.length < 26){

    cout << -1;

    return 0;

    }

»
8 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I sign up Codeforces Round #372 yesterday and joined the competition and AC THE A,B,C.But today,when I log in and search my contests "Codeforces Round #372"disapear and I can't know my score.Why? who can help me?

»
4 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I know I shouldn't be asking this kind of question, but

can anyone who sees this comment please please explain where am i going wrong in this code for Complete the Graph. I am calculating minimum distance from t to all other vertices and then calculating minimum distance from s and updating the edges. I have also tried commenting my code for first time to make it easier to understand. Please help me. I have been stuck on this question for 8 days and now I am finding it hard to move on from this.

I would really appreciate your help.

Please help