Canada Cup
By zxqfl, history, 8 years ago, In English

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.me/blog/entry/47974

Announcement of Canada Cup 2016
  • Vote: I like it
  • +313
  • Vote: I do not like it

Comments Comments (207)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it -23 Vote: I do not like it

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

Top 100 competitors in each division?

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

    Are you joking?

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

    My question too...

    Also in the contest page it's div1-div2 combined...

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

    The post has been updated: now members of both divisions will participate in the same contest.

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

      I won't forgive you... :/

      Got down-votes cause of you :/

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

        Someone want more downvotes... I read somewhere that downvote can have negative impact on behavior... Seems true.

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

    Then all div1 users would create div2 fakes

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

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

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

    <3

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

    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.

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

Is it rated?

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

    Read the third line of post

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

      sponsored by Diagram!

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

        So, read the 4th line. or hit ctrl+F and type rated and hit Enter. You will find the line stating that "This is a rated Codeforces round"

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

          I'm sorry wut? "hit" ???

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

          Such a genius man you are! Why aren't you red?!

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

    use your brain bro

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

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

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

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

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

Edit: Duplicate.

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

there is a tutorial for this contest ,right ?

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

Is there any separate registration for people residing in Canada ?

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

    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.

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

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

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

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!

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

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

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

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

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

    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.

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

Clashing with ACM ICPC India Regionals :(

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

...

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

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

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

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

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

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

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

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

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

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 ?

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

    Not that good of an idea right? Tried that a couple times, never works out...

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

      Yes, mind turned slower ...

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

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

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

I love combined rounds!

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

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

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

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

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

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

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

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

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

Score distribution?

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

Why there is no rng_58 in the leaderboard? :)

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

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

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

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

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

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?

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

Really nice contest and problems!

Thanks, author(s)!

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

solution for problem E please
My brain is burning

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

    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

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

      And since there're at most sqrt(T) unique numbers in the solution of greedy algorithms

      What numbers are you talking about?

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

        The coins

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

        If you contract the occurrences of the numbers, and only iterate on each unique coin x1..xn then their sum(occurence*sum) <= C.
        Since each unique coin need to be distinct, taking 1..sqrt(C) gives the most number of coins since sum(1..sqrt(C)) ~ O(C).

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

      your implementation is actually since you query Fenwick tree in binary search

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

        Yes, you're right.

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

          You can reduce it to by using a BST like the built in order statistics tree.

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

        http://codeforces.me/contest/725/submission/21696740

        std::set solution runs slower than yours :(

        I guess it's because Fenwick tree operations' constant factors are much smaller compare to those of BST.

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

          Instead of using set, you can store largest value less than any number from 1 to C, then your solutions will be reduced to C * sqrt(C)

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

      Can you give me a hint of how to prove that?

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

    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

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

Is greedy correct for problem D?

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

    yes

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

    I think it's binary search

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

      How did you use binary search?

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

        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.

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

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

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

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

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

              OMG you're right T_T

              Forgot that I'm adding lots of numbers of that magnitude T_T

              T-shirt + Rating => Gone

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

              Yes, I've limited sums by 2**62. It's ok since there is no subtraction. 21684744

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

        21682840. Here is my code.

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

how to solve D?

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

    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!

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

      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.

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

        Oh, i think your solution is better!

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

        What about multimap?

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

          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.

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

            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.

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

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

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

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

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

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

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

      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.

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

      Nice approach thanks

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

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

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

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

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

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

      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.

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

    It is already simple. Isn't it? 

    long long row;
char column;
cin >> row >> column;
    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I didn't know that works, Thanks.

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

        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.

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

.

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

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

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

How to solve C?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +67 Vote: I do not like it
    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).

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

      will be there only one repetead character?

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

        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?

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

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

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

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

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

        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

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

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

        so there is exactly one repeated letter

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

        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

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

        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

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

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

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

        From my last experience, such problem is normal for Div2C/Div1A.

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

      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.me/contest/725/submission/21678250

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

        Nice solution!

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

        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

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

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

    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

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

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.

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

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

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

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

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

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

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

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

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

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

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

Image

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

And hello Div.2. :)

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

sad... Failed System Test on B&C

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

Can someone explain the solution for C ? Thanks.

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

    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.

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

    look at this comment

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

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

this one

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

No upsolving or something wrong with me? :)

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

:)

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

Why we can't submit for practice ?

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

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

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

worst problems ever no idea just code

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

:(

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

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

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

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

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

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

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

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

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

      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.

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

        Hey, could you explain the idea of your solution?

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

          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.

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

almost got jcvb

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

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

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

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

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

    did u use ideone or any other public online compiler?

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

      Not really. I compiled all my programs with g++ (Codeblocks IDE) on my local PC...

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

why cant i practice now

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

cute problems :)

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

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

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

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

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

    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.

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

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

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

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

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

Rating is calculated separately for divisions?

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

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

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

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.

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

    I dont think it is a typo at all

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

    In that particular example, since the field is >>>>>, the ball will always fall from the field, no matter where it initially starts (will always go to the right)

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

can D be solved using Segment tree ?

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

    Yes but you can use simpler structures. For example heaps or sets.

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

Are editorials coming ?

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

Moose!

It's like Canadian cattle eh?

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

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 (๑•̀ㅂ•́)و✧

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

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

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

    I did something like that except it was in C. T_T

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

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?

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

    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.

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

Problem E:

100

1

5

What is the answer?

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

    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.

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

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!

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

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

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

When will the problems be available for practice?

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

    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.

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

Will the editorials be published?

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

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?

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

When will be editorial???

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

Editorial please.

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

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.

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

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

→ Reply