zscoder's blog

Codeforces Round #372
By zscoder, history, 8 years ago, In English

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 — 2500 — 2750

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!

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

Comments Comments (228)
| Write comment?
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

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

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

I like Chris the Baboon...

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

    Sorry this is for the sake of making the statements shorter to read :)

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

      shorter statement, better life! ;)

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

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

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

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

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

      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.

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

        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!)

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

        I think you should solve tasks instead of worrying about score

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

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

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

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

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

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

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

    There is 25 minutes after cf round according to clist.by.

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

    Last time I checked there is a 25 minutes break between them (which is the reason this time was chosen in the first place)

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

GL & HF :D

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

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

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

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

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

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

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

Good luck everyone and a high rating!

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

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.

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

    I wonder if you've ever heard of Photoshop. :P

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

      and I wonder if you've ever heard of Trust :P

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

        You got me wrong buddy, I was talking about cropping the image to remove unnecessary part. :P

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

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

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

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

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

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

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

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

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

    This contest ends 25 minutes before the SRM.

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

      Never mind, I didn't relize that the starting time had been changed.

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

What is good to have a Korean problem setter?

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

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

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 !

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

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

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

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

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

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

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

Good luck everyone and happy rating

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

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

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

    Round 371 was rated and was held without any problem.

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

thanks zscoder for your awesome contribution in codeforces.

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

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

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

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

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

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

GL & HF everyone.

:)

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

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

    Good luck!

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

      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.

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

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

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

good luck and high rating~

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

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

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

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

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

    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. :)

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

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

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

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

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

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

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

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

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

    My last round was round 369, and 369 is a multiple of 3.

    This round is round 372, another multiple of 3.

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

GL and high rating everyone!

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

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

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

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

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

10 min delay.

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

    Why? Will that mean a slow website today?

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

      maybe because about 1k more people registered for today.

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

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

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

    They usually do it because the servers are overloaded

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

      Y dont u stop posting useless comments to ease some load off the server

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

        How is answering his question useless? Anyways, the load of one comment is negligible relative to 8k users loading a page.

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

      will that cause "in queue" verdict? :(

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

        No, queue will be empty because nobody will be able to submit :D

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

Swarm of comments about delay incoming...

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

:/

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

Now much smaller gap between Codeforces round and Topcoder SRM

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

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. :/

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

Div 2 round starts 1 second after div 1. XD

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

Missed the contest due to calendar bug :/

https://calendar.google.com/calendar/embed?src=br1o1n70iqgrrbc875vcehacjg%40group.calendar.google.com

shows 14:35 UTC

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

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

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

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.

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

    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 "

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

    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'

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

    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.

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

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

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

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];
}

}

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

    Don't post code during contest

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

    Seriously, Contest blog should be blocked during contest.

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

    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.

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

      How?

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

        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

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

C is too hard :/

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

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

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

Missed D by a second :/

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

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

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

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

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

      Can you explain that?

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

        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

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

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

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

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

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

    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.

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

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.

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

How to solve Div1 B？

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

    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.

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

    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.

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

      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.

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

      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.

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

        "You God Damn Right!". Thanks for anti-test.

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

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

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

    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.

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

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

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

    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 ?

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

      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"

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

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

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

C Div 2. Anyone? How to solve it?

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

    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.

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

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

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

    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

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

    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.

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

      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.

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

        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.

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

    Thanks everyone :)

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

I like this round. Problems are so interesting!

I hope my rating will be increased.

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

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 :>

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

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

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

      I change ? mark to alphabet.

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

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

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

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

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

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

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

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

    Why did you dislike this round?

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

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

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

    Because replace all the question marks with uppercase letters

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

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!

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

    could you explain your solution please

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

      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];
      → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

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.

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

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

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

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

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

    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.

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

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

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

    That' s for sure. This can effect the result a little bit.

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

    I tried such approach... But got WA on pretest 4... Maybe i made a mistake...

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

    Yes, otherwise L might be less than the number of erased edges on the chosen path, and you'll be printing NO.

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

Please help!!! I dont know whats wrong with those B->http://codeforces.com/contest/716/submission/20707069 C->http://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

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

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

    → Reply
»
8 years ago, # |
← Rev. 6   Vote: I like it +10 Vote: I do not like it

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

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

    The great evil plan of choosing all M as prime in all pretests. >=]

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

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?

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

    After assigning you should check if the path you got at the beginning is still the shortest one after you removed all the zeroes.

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

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.

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

I was printing only 26 letters for Div2B. OMG.

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

Div 1B RIP.

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

.

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

RIP B :( div1 & div2

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

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

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

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

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

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?

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

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

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

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

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

    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 ;(

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

      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.

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

Eagerly waiting for editorial

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

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

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

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

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

    Unfortunately became blue for the first time in over half a year :( D:

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

What in 22 test in div1 B?

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

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

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

    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.

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

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

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

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

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

LOL worse did this contest and got +644.

Does this set a record? :D

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

    Yeeeaaaahhh!!11!

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

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

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

Seriously,is that a bug?

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

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

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

      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.

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

        You need to have A-Z in consecutive 26 positions! Its a substring and not a subsequence

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

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

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

    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.

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

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://codeforces.com/contest/716/submission/20716292

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

    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 ? :(

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

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

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

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

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

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

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

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

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

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

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

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.

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

    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.

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

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

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

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://codeforces.com/contest/716/submission/20693471 My ac code: http://codeforces.com/contest/716/submission/20713665 Please help me out. Thanks in advance!

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

    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;

    }

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

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?

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

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

→ Reply