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

Hi Codeforces,

I'm excited to announce the Canada Cup, the first Codeforces contest to be sponsored by Diagram!

This is a rated Codeforces round (with T-shirts!) for both divisions which will take place on October 22 at 11:00am EDT.

Although the contest is organized in Canada, all competitors worldwide will be able to compete and win prizes.

The problems for this round were written me (zxqfl) and the Codeforces team. I'd like to thank:

  • My coauthors for contributing great problems to the round
  • GlebsHP for his help in preparation
  • MikeMirzayanov for creating Codeforces and Polygon
  • Tatiana_S for translation into Russian

I'd also like to thank Diagram for sponsoring the round. Diagram is interested in hiring software engineers, so please take a look at the information at the end of this post if you're interested. For anyone outside of Canada, they'd like me to let you know that Canada has friendly immigration policies for software engineers.

Both divisions will compete in the same contest, which will consist of 7 problems of the same difficulty level as a regular Codeforces round. The contest will last for 2.5 hours.

The score distribution will, of course, be announced later.

Here is some information from the round sponsor:

Prizes

  • The top 100 competitors will get a Diagram T-shirt.
  • Local winners (Montreal): Dinner with Francois Lafortune (CEO, Diagram), founders of Dialogue, and other Montreal technologists
  • Local winners (Toronto): Dinner with Karel Vuong (Director, Diagram), founders of Collage, and other Toronto technologists

About Diagram

Diagram is a venture launchpad building the next generation of Canadian-based global technology companies. By assembling teams of world-class founders pursuing big ideas for innovation in the financial and insurance industries, and surrounding them with capital, expertise, and infrastructure, they are betting big on their companies and equipping them with everything they need to innovate and build a better future.

Diagram’s investment portfolio includes the companies featured below and they all work with teams that leverage modern frameworks, cutting edge technology, and complex algorithms to deliver wellness and prosperity to all.

Diagram's Investment Portfolio

Collage is re-inventing the way Canadian businesses manage HR, payroll, and benefits. By offering a 100% free and comprehensive platform, Collage automates paper-based and manual business processes and HR administration in ways that are efficient and secure at scale, enabling companies to spend their time on the more meaningful aspects of business.

Dialogue is the best part of your company's health plan. By offering a range of healthcare services for your team, Dialogue helps to keep them happy, healthy, and performing at their highest potential. Dialogue is using machine learning, natural language processing, and AI to process text conversations, video interactions, and imagery sent from patients to their chatbot in real-time to provide accurate diagnoses of physical and mental health concerns.

Applying to Diagram

For those interested in an opportunity with Diagram or any our portfolio companies, please apply here.

UPD Scoring distribution is 500 — 1000 — 1500 — 2250 — 2500 — 3250 — 3500.

UPD The contest is over! Congratulations to the top 5:

  1. eatmore
  2. paulwang
  3. zemen
  4. mnbvmar
  5. riadwaw

If you won a prize, you'll be contacted soon.

UPD Editorial: http://codeforces.net/blog/entry/47974

Анонс Canada Cup 2016
  • Проголосовать: нравится
  • +313
  • Проголосовать: не нравится

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

"The top 100 competitors will get a Diagram T-shirt."

Top 100 competitors in each division?

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

Does Diagram or your companies offer any internship opportunities for undergraduate students? If yes, how can I apply for it?

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

    <3

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

    I work with Diagram. Unfortunately, we aren't looking to offer internship opportunities to students outside of Canada at this time. It's fair game for Canadians though!

    This is the first content we've sponsored but plan to do so again. This will definitely be a consideration in the future.

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

Is it rated?

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

It is clashing with the online qualifying round for ACM-ICPC Regionals of all sites in India. Most of the Indian programmers will miss this. :/

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

By the way, where is the announcement for Codeforces Round #377 ? It starts in a few hours...

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

Edit: Duplicate.

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

there is a tutorial for this contest ,right ?

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

Is there any separate registration for people residing in Canada ?

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

    I work with Diagram. If you're already residing in Canada, just let us know in a "cover letter" via the application form or send me a note directly.

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

А условия будут только на английском?

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

    Условия будут доступны как на русском так и английском языках.

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

What's happened with CF? Cannot access some pages including "Main"

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

The brand of this company is great.So I guess the T-shirt is great too.Hope my top 100 rank! To be a beautiful T-shirt's girl!

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

Too bad it conflicts with IEEE contest which happens on Saturday for 24 hours duration.

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

How many people are qualified as being "local winners"? Is it just the number 1? Btw, you're the best Jacob

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

    I work with Diagram. If any of the top 100 are local winners (Toronto or Montreal), we'll find some time to make this happen.

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

Clashing with ACM ICPC India Regionals :(

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

...

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

T Think There was Register option for this contest. But not now.

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

hope to see good statements and new problems away of hacking :D

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

    Congratulations you win the "Worst comment ever" prize keep up the good work.

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

Has anyone noticed that the contest starts at 11am EDT instead of 11.05am EDT?

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

I just had some beer and feel a littie drunk, but I really don't want to miss this round, good luck to me.
Does Anyone have this experience ?

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

I don't need a T-shirt ,, i need +200 and i'll be more happy ,thanks

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

I love combined rounds!

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

    I love them too , because in combined rounds you will never see unrated accounts in top 100

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

i am being unable to register in the round..!! :/ anyone else facing the issue??!!

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

Where is the contest registration link? Is it the application to Diagram?

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

unfortunately, the contest will be delayed for 5 minutes :p

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

Score distribution?

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

Why there is no rng_58 in the leaderboard? :)

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

    The leaderboard only shows members that took part in at least one contest in the last six months.

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

Number C : Poor statement. can't understand a single line.

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

My submission for C is running forever on test 2, where submissions made after my submissions are already judged. If I resubmit, I would lose points. Could you please look into it?

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

Really nice contest and problems!

Thanks, author(s)!

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

solution for problem E please
My brain is burning

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

    Key abeservation is:

    If you can make the greedy algorithm fail, you can do it by add just one coin. Prove it yourself. :)

    So we can try all the C possibilities. And since there're at most unique numbers in the solution of greedy algorithms, you can use a fenwick tree to find the largest number which can be used in greedy algorithm. This method works in .

    21687779

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

    you can iterate all the value from 1 to C, consider it the value of the coin you give to Alfred, and with each value just do brute force, the time brute force running is no more than sqrt(C), so the total complexity is C * sqrt(C), i didn't realize the second part in the contest. My friend's code : http://ideone.com/56lb0F

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

Is greedy correct for problem D?

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

    yes

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

    I think it's binary search

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

      How did you use binary search?

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

        I used the following (overcomplicated) approach:

        Sort by score, process from highest score: calculate how many balls you can spend so that you still have at least the same score as current participant. Then use binary search + two Fenwick trees to find how many participants you can delete, update answer if needed. Then add current participant's deletion cost to the trees and continue.

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

          I believe I did this and failed system test T_T (probably did something wrong)

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

            Maybe overflow? You can't compute the sum of all numbers. Anyway, I used three BITs to avoid this (long long and double for the same thing).

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

        21682840. Here is my code.

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

how to solve D?

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

    I used heap+sort! First of all, Let's sort ballons! Then, Let's insert everybody better,than us! Then, pop the people with minimum(weight-ballons+1)! Repeat it, until we can! Sorry for my english!

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

      oh, I wish I thought of using a heap! I used a map<int,int> with the second int counting the number of instances of the first.

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

        Oh, i think your solution is better!

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

        What about multimap?

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

          Extracting the minimum element will cost logarithmic time with both maps and multimaps, and constant time with heaps. So generally speaking a heap will be the fastest of three, but all of them will work within the time limit.

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

            map.begin() gets you the min element in constant time. source: http://www.cplusplus.com/reference/map/map/begin/ Edit: it is still probably slower due to map's logarithmic operations being slower, but the main benefit for heap would be it's simplicity.

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

              Wow, I never realized that... Thanks for pointing out :) Perhaps the implementation is keeping an internal pointer to make this possible in constant time.

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

            Extracting in heap is log n (**peeking** is constant). Same as in map.

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

          I could have used a multiset, but than erasing a single instance of an element is even less elegant.

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

      I wish I was as smart as you during the contest :) Really like your idea! I went further after contest: just use two heaps: one for better-than-us and another for worse-than-us and simple while-loop to put from one to the other to optimize current placement.

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

      Nice approach thanks

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

I really like D. Why don't you make B's input simpler by having a space?

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

    It's simple enough with scanf. scanf("%I64d%c", &x, &c);

    It adds a bit of personality to the task if u ask me.

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

      That's what I did, but it took me a while to remember how to read long longs with scanf. Also, removing the ios::sync_with_stdio(false); had me resubmitting D and loosing 50 points.

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

    It is already simple. Isn't it?

    long long row;
    char column;
    cin >> row >> column;
    
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I didn't know that works, Thanks.

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

        that's nice , but you must be very careful about it. note that if 'row' be double , this input '12e' will fail because 'e' is a scientific numbers notation.

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

.

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

Well, this time I would get D if there were 2 seconds more...

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

How to solve C?

  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +67 Проголосовать: не нравится
    1. We find the repeating character.
    2. Find two indices where this character is placed: i1, i2.
    3. Find the number of characters between the repeating character: dist = i2 - i1 - 1.
    4. If number of characters between them is 0 print "Impossible", otherwise it is possible and we proceed.

    I look at the sequence in the following way:

    So, basically, in the next steps I lay the loop (which is red in the picture) on the right side. The starting and ending characters I put on the left side (starting characters — on top and ending characters on bottom).

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

      will be there only one repetead character?

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

        Imagine that we are given a sequence of 26 characters and all english letters are in that sequence. How many repeated characters that sequence must have?

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

        yes, only one. Because length of iven string equals to 27 and all English letters occurs at least once. So 27-26=1

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

      What if there are 2 different repeating characters for example? love the drawing btw

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

        read the problem statement carefully :D Each English letter occurs at least once and the input is 27 letter so we have only one repeated character

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

        there are exactly 27 characters and each English letter will appear at least once

        so there is exactly one repeated letter

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

        You’re given a string s which consists of 27 upper-case English letters. Each English letter occurs at least once in s.

        The English alphabet has 26 letters, they tell us that every letter is going to appear at least once, then 27 — 26 = 1 letter can appear twice

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

        read the problem statement carefully! It says that there will be 27 characters in the input string and all 26 letters will be present there! So only one character can be repeated

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

      Are Codeforces problems getting harder recently? I was surprised to see this as a div1 A.

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

      I came up with the same solution, but you can make the implementation easier by noticing that this configuration is just the original string looped around the board (without repeating the character that appears twice). So you can just test all loops and see if there's a configuration that works: http://codeforces.net/contest/725/submission/21678250

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

        Nice solution!

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

        The right position in the loop is easy to calculate. Basically you put the first repeating character in the first row in the position 13-len(mid)/2, where mid is the part between two repeating characters.

        21674772

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

          Or even simpler: 21694212

          i = s.index(c)
          j = i + 1 + s[i+1:].index(c)
          if i + 1 == j:
              die("Impossible")
          
          s = s.replace(c, "", 1)*3
          mid = 13+(i+j)/2
          print s[mid-13:mid]
          print s[mid:mid+13][::-1]
          
  • »
    »
    8 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    First calculate the distance between the two repeated letter. Then put the letters snake-shaped.

    For example, if the distance is 5, then the rightmost part should be this:

       -> A -> x -> x
         /|         |
        / |         v
    <- y  x <- x <- x
    

    My submission here.

    sorry for my bad English

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

spent too much time on C and didn't have enough time for D, didn't find an easy wa to handle the tie cases.

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

I think the statement for problem G was ambiguous : what to do when a node receive messages from its parent and one of its children at the same time ? I had WA on test 4 even with the slow code I was using to test the fast code...

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

    There is the statement about this situation in the problem:

    "If some copy of Alice receives messages from children nodes and also receives the answer she is waiting for at the same instant, then Alice first processes the answer, then immediately continue as normal with the incoming messages."

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

      Oh, it is my fault then. I think that this kind of problem should have examples covering all corner cases though...

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

Sadness is when you pass E but failed C and D T_T

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

    Sadness is the contest ends just before you click submit to an accepted solution :(

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

Image

Solve E and gain 1090 points. I love this game but not rating! :)

And hello Div.2. :)

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

sad... Failed System Test on B&C

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

Can someone explain the solution for C ? Thanks.

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

    It's only impossible if there are two of the same letters next to each other. Also it's easily understandable that there will be exactly one letter that appears twice in the input string, since each letter must appear at least once and there's only one extra letter.

    Let's say that this was the letter 'A'. Then the string looks like this:

    s1 + "A" + s2 + "A" + s3

    I got AC by constructing the matrix like this:

    3333333A222

    111111111222

    It's always possible to get the input string by starting at the left start of the 1s, going right, taking 'A', getting the 2s by going right then down then left then back to 'A', then going left (and maybe down and right) to take all 3s.

    Of course, s1 and s3 are of varied length and can even be empty, but then simply make the one that's too long "spill" into the row above or below. Also you have to be careful to write the string s1 in reverse order.

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

    look at this comment

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

How did my solution for E pass system tests =)))))) I'm pretty sure it would get TLE tho xD

this one

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

No upsolving or something wrong with me? :)

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

:)

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

Why we can't submit for practice ?

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

Is it just me or no one can see others' solutions? :/

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

worst problems ever no idea just code

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

:(

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

Is F a greedy? I cannot submit now,plz someone who got F accepted tell me,thank you!

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

    (I didn't AC it)

    I think it is: always take the photo with the biggest sum of A and B. But the tricky part is to, at each point in time, check if it's possible that both players want to pass their turns, ending the game early. I'm pretty sure I've got the DP for this down, but I couldn't complete it during contest.

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

    Yep. It can be done greedily if you regard the value of a card as a+b since the scores that the two players get are a,0 and 0,b in both cases, where the difference would be a and -b respectively. So you can set this value for each card and greedily select the pictures.

    Of course you still have to handle some other cases :)

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

      Hey, could you please explain they way you derived this strategy ?

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

      Thank you,I've got F passed.From my point of view,the game is a little bit like the go chess,because both sides need to correctly calculate every step's value and choose the most valuable one.

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

        Hey, could you explain the idea of your solution?

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

          consider a quadruple x,y,xx,yy mentioned in the description,there are three condition: 1.x<=yy&&y<=xx. In this contion,the one who goes first suffers losses.So no one goes first,and this condition makes no sense. 2.doesn't satisfy the 1st contion,but satisfy x+y<xx+yy.In this condition,one will definitely get profits(as x>yy or y>xx),but he will get more profits only if he goes second,but the opponent will just let it be .And if the one who is to get profits want to "cash his check",he has to offer to go first.As is explained above, ans+=x-yy(or xx-y). 3.other conditions. We can assume the value as x+y(if the first is done,xx+yy),and apply a greedy strategy that obviously choosing the most valuable one from all the 3rd contions(if this one is the first then add the second into the priority_queue)one by one,using a priority_queue. Sorry for my poor English and wish you can get AC.

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

almost got jcvb

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

when I will be able to submit my solution for problem C. When problems will be added to problemset

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

Why did my submissions get ignored!? I'm 100% sure that I have written ALL of the code MYSELF. What's wrong!?

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

why cant i practice now

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

cute problems :)

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

Why so delay ? Why we can't submit the solution till now ? When the problems will be added to problemset ? Why till now, we can't see other's code ? Is there any reason for this ?

Update: Now it's ok :)

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

http://codeforces.net/contest/725/submission/21684455 what is 7th testcase,why its showing wrong answer for 7th testcase please help

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

    I didn't actually read your code. Just tested it. time for 1st attendant and time for 2nd attendant should be the equal. For example you got 6e=25 so that 8e=25 but your output is 31.

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

please .. why all my submissions skipped after the contests ?? .. during the contest I changed my laptob and IP is that relative ?

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

wrote 26 instead of 27 in problem C, dropped ~350 rank

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

Rating is calculated separately for divisions?

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

WA: for (int i = 0; i < 12; i++) AC: for (int i = 0; i < 13; i++) Lesson well learnt. :''D

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

I don't understand problem A, can someone tell me, how this statement make sense?

"In the second sample, any starting position will result in the ball falling from the field."

I'm still under the impression that is a typo, where it should say, any starting position will not result in the ball falling from the field.

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

can D be solved using Segment tree ?

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

Are editorials coming ?

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

Moose!

It's like Canadian cattle eh?

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

Pretests of B cover all cases except for where n = 4k + 3, leaving opportunities for hacking and necessity for system test, while maintaining a reasonbly strong testset. +1 for this setting (๑•̀ㅂ•́)و✧

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

I forgot to write "+1" in my D submission so I got a WA. I won't forgive myself...

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

I am thinking of solving problem G in this way, but I am not sure if this is correct.

  1. Build the heavy-light decomposition chains. O(N)

  2. Sort query by increasing pair(time+depth[initiator], initiator_id). O(MlogM)

  3. Upon query, ask the expected time that you will reach Bob, use the segment trees to binary search for the position you will get answer from. Each takes O((logN)^3)

  4. Update the segment trees, set the value of each node on the path to (time of response + depth[Node]), which is a geometric sequence(*Edit: arithematic sequence). Each takes O((logN)^2)?

I have heard that it is possible to use lazy propagation and keeping other values to maintain geotric sequences in a segment tree but I have never implemented it... Any thoughts?

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

    1,2 are correct. 3 and 4 can both be done in O((log n)²) by keeping the right information in the segment tree. It is an arithmetic sequence, not a geometric one.

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

Problem E:

100

1

5

What is the answer?

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

    You can assume that the answer, if it exists, is positive. In other words, Alfred's algorithm will work if Bob doesn't give him any coins.

    The sets are guaranteed to have an answer if nothing is added.

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

Problem D:

9
4 70
32 56
32 65
77 78
5 29
72 100
0 55
42 52
66 72

Can anyone explain this to me,why this test is 7 but we can give 77 78 2 balloons right? So it should be 6. Thank you!

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

    Final rankings:

    1, 72 100

    2, 66 72

    3, 42 52

    4, 32 56

    4, 32 65 (UPD: Dang it formatting)

    6, 5 29

    7, (4-2) 70

    8, 0 55

    I think you misunderstood the statement and ranked 6~8 incorrectly, note that "It means that one's place is equal to the number of teams with more balloons, increased by 1."

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

When will the problems be available for practice?

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

    They should be right now, but I am not sure if that's an issue for some participants. I have also had this issue before, after a day it should resolve itself.

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

Will the editorials be published?

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

This is the first time I win a prize on Codeforces, so I want to ask people here a few things. How long after the contest will the sponsor contact me? And how long does it usually take until I can receive my prize?

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

When will be editorial???

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

Editorial please.

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

How is this possible that points drain was not adjusted? This is by far not the first contest coordinated by GlebsHP with longer duration and few of them already had adjusted drain. Not adjusted drain is complete cancer, adjusting drain should have already became a habit without any exceptions.

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

Did anyone receive the T-shirt? As the last line of the blog mentioned, I have been contacted (multiple times) but the T-shirt has still not arrived. :(