cgy4ever's blog

Codeforces Round #190
By cgy4ever, 11 years ago, In English

Hello, everyone!

Do you want to train your skill by a contest before ACM/ICPC Finals?

Codeforces Round #190 will take place on Friday, June 28th at 19:30 MSK. This is the last chance to practice, don't miss it!

I am cgy4ever from China, and this is my first round on Codeforces, I hope you will love it.

As usual, there will be 7 problems: 2 for Div2, 2 for Div1 and 3 for both. I am the writer of them. And I would like to thank Gerald and sdya for testing, and MikeMirzayanov for the Codeforces project including polygon system.

Good luck and have fun!

Update 1: The score distribution for Both Division is regular (500-1000-1500-2000-2500). The main character of all problem will be: Fox Ciel. (See here for more info)

Update 2: Also thanks Aksenov239 for helping prepared this round, including translate the problem statement into Russian. And I'm sorry for the delay of judgement at the beginning of this round. Fortunately it goes better now.

Update 3: I have write a draft of editorial for this round when you are solving problems.

You can read it here.

Note that I didn't do any proof read and there are some typesetting issue. Anyway, I will improve it and this version is just for someone who is urgent to know the intended solutions.

Update 4 Contest complete! This round will be rated!

Congratulations to the winners:

Div2:

  1. Baklazan

  2. phidnight

  3. kingofnumbers

  4. pawel.jasinski1986

  5. Ronnoc

Div1:

  1. YuukaKazami

  2. rng_58

  3. Egor

  4. tmt514

  5. chnlich

And after this round, ivan.metelsky becomes our new International Grandmaster!

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

Comments Comments (130)
| Write comment?
»
11 years ago, # |
  Vote: I like it +75 Vote: I do not like it

Hope it will be a successful Chinese round. \^o^/

cgy4ever is also a writer for topcoder, you can find problems authored by him here.

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

Hello World!

It's my first comment on this article.
I'll write some interesting experiences and academic articles there.
I'm an OIer and maybe I'll be an ACMer latter.

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

This is your website http://cgy.ac/ :P ;)

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

    Nice design:


    <h2>cgy.ac</h2>
<br>
Hi! I'm <b>cgy4ever</b> and this is my new website.
    → Reply
»
11 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Thank you cgy4ever for the contest! I love contests that have been made in china!

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

So many cheaters participate :D

about 250 fakes now

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

http://codeforces.net/contestRegistrants/322/page/1?order=BY_RATING_ASC it's fake

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

    That's interesting! What do all these fake accounts mean? Are they supposed to be cannon fodder for easy hacking? Will they be banned by the admins?

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

      If each one of them will be in a high place(for example with solved ABCD(E) on positions 50-900) then many real users will lose rating extensively xD

      But it's difficult to send solutions in all these accounts for their owner. Maybe he(she) has special script :)

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

        in other way: if each of them will send one wrong submission, ratings of all the real users will be increased )

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

    theirs count really increased last 15 minutes(about 400 now)

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

      And now 850 o_O

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

        maybe they want to get a record number of participants in div2 round

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

        more than 1200 now!!!

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

          more than 1650 now!!!
          upd1. more than 2100 now!!!
          upd2. more than 3300 now!!!
          upd3. more than 3500 now!!!
          upd4. more than 3700 now!!!

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

            it looks like somebody hacking the system -.-" i think the best way is to delete all new registered accounts and notify them to register again (of cox use captcha for new registration).

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

            about 1900 now!!!! O_o UPD: 2400!

            wtf?!

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

              The speed is 47/minute. So there will be about 14000 fake accounts before the contest.

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

    I think it's finally about time Codeforces implemented captcha and e-mail address verification for new accounts.

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

      then also need to remove old fakes

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

      And for the old accounts too. Seems that there are lots of fakes which are already registered.

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

      maybe before registering to a contest there must be a captcha system as well

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

      I think custom questions are better protection than captcha. At least my little forum site was spammed despite the captcha, but after introducing several simple questions the spam accounts were no longer appearing. I would start with a question: "What is the handle of the highest rated coder at CodeForces?" (2nd, 3rd good as well).

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

        It would probably work against generic bots that try to spam on many websites at once. But this "attack" seems to be targeted specifically at Codeforces, because they're not only creating new accounts, but also registering them for a contest. Thus the attackers could easily adjust their tools.

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

        your example of question "What is the handle of the highest rated coder at CodeForces?" is not good ,because new users may not be familiar with codeforces rating system , furthermore this question can be answered easily using scripts

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

      Yes, I agree with you about captcha. Codeforces need one!, and I think this is not funny thing! I hope MikeMirzayanov will do something for that! now you think, if owner of all of these fake accounts was one person and he could get Accept for 4-5 problems, the real persons position starts from 2000!! and ratings...!

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

        of course , these accounts will be deleted before starting this round

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

          Yes, Thanks MikeMirzayanov, all of these accounts have been deleted...!

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

            But Codeforces needs e-mail verification or captcha system. Without them, this toxic users strike again...

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

      Agreed.

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

    wow!!! The rate of producing of this fake accounts is as fast as reproduction of bacteria!! In last 5 minutes, number of this accounts increased by 200!!!

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

      The next milestone is coming: 200000 registered users :)

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

      it would not be surprised to see more than 10,000 participants before the registration closes if nothing is going to be done by admin :(

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

    I don't understand. How were you able to say that they are fake?

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

      When he posted this comment there was a lot of fake accounts but they were deleted by admins

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

On seeing many fake entry I doubt of contest being rated.

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

Someone's gonna cheat today XD (look at the list of registrants)

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

If all fakes will downvote all somebody's comments he'll look like JKeeJ1e30 or worst :)

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

    then the cheater is sooooooo hungered for cheating (not only rating but also upvotes) :D

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

    If unrated user downvote your comment — this don't care your contribution or just fall to one point (likely first) — the power of votes depends on rating.

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

All this users will be banned before the contest.

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

I think all these fake accounts have a goal that they want to tell to MikeMirzayanov that there must be captcha or e-mail activation system at the beginning of creating account. It's completely right. Codeforces has a bad log in system too. If you want to find someone's password, it's enough to using brute force scripts or programs. Because there isn't any security protection in the log in system. In my opinion, Headquarters must build a security system to the log in part. Simply, it can be captcha or anything that can block the attackers.

PS: Sorry for my bad English. Thanks...

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

I do not like fakes, we should use codeforces to learn programming, algorithms ... in a good way.

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

You need to look into the registration system!

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

with reference to this comment i think codeforces should set a limit of participants.

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

    and if the fakes will be registered to contest before other people ...

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

    If there will be any limit of participants, there could be aggrieved users... But if registration has captcha system or e-mail activation registration method, there won't be any fake users.

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

      about e-mail:

      his owner can register them using some tempmail systems. And if he has script to register on CF , he also can make that script for mail systems

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

Please stop spamming with your comments about fake accounts. Make a blog about it so that others could skip reading it. I want to read interesting info about the round here. Minuses to all spammers.

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

why so much new ????

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

STUPID JUDGING DELAY AGAIN!!!! DAMNNNNNNNNN

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

All the submissions are "In queue" :(

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

"In queue"... Classic Codeforces Round once again.

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

The submission has been in queue for last 10 min or so....:(

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

Div1 B /Div2 D is yugioh game :)

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

Nice Contest!! Superb questions i love CF

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

Now that the contest is finished, how was Div2 B supposed to be solved?

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

    This is based on my solution (which unfortunately fails for one single case, but fixed in this solution):

    Take as many mixed bouquets as possible, then take as many single-colored bouquets as possible. This gives the first answer, call it greedy.

    However, when there is at least one flower of each color, it's possible that if we give up one mixed bouquet, we can make more single-colored bouquets (example is 3 5 5). So we take all but one mixed bouquets, then take as many single-colored bouquets as possible. This gives the second answer, call it almostgreedy.

    Take the greater of these.

    If you're not convinced that this is the correct answer, you can proceed further by giving up two mixed bouquets if possible to get another answer. Take the greatest of these. (If you give up three mixed bouquets, you immediately get one bouquet of each color, so the net total is zero. So it doesn't worth trying.)

    For example:

    3 6 9 -> greedy = 3 + (3 - 3) / 3 + (6 - 3) / 3 + (9 - 3) / 3 = 6 and almostgreedy = 2 + (3 - 2) / 3 + (6 - 2) / 3 + (9 - 2) / 3 = 5, so the answer is 6.

    3 4 5 -> greedy = 3 + (3 - 3) / 3 + (4 - 3) / 3 + (5 - 3) / 3 = 3 and almostgreedy = 2 + (3 - 2) / 3 + (4 - 2) / 3 + (5 - 2) / 3 = 3, so the answer is 3.

    3 5 5 -> greedy = 3 + (3 - 3) / 3 + (5 - 3) / 3 + (5 - 3) / 3 = 3 and almostgreedy = 2 + (3 - 2) / 3 + (5 - 2) / 3 + (5 - 2) / 3 = 4, so the answer is 4.

    0 2 2 -> greedy = 0 + (0 - 0) / 3 + (2 - 0) / 3 + (2 - 0) / 3 = 0. We cannot do almostgreedy because there is no red flower; there's no mixed bouquet to give up. So the answer is 0.

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

    Think about this case : 8 8 9 the correct answer is 8 not 7 . we make 2 red bouquets and 2 green bouquets and 2 blue bouquets and and 2 mixing bouquets. I think this is the critical case .

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

      Solutions that greedily takes mixed bouquets solve 8 8 9 correctly. The 3 5 5 hack fails both solutions that greedily takes mixed bouquets and solutions that greedily takes colored bouquets. All solutions must have a way to handle backtracking for that particular hack.

      However, the trick doesn't stop there. Solutions that implement the backtracking must also handle 0 2 2 correctly (it cannot backtrack).

      In my opinion, the critical cases are 3 5 5 and 0 2 2.

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

    Simply, we can make mixing bouquet 0, 1 or 2. This is because that if we make 3 or more, it equals to we make 1 of each color. And '2 2 0' is a really strong hack data...

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

    First, note that you never need to make more than 2 mixing bouquets. Because you can change every 3 mixing bouquets into 3 single-colored bouquets (1 red, 1 green and 1 blue). So if you decided to make 3a+b mixing bouquets (with b = 0, 1 or 2), then you can always leave b mixing bouquets and change 3a mixing bouquets into 3a single-coloured bouquets.

    So the entire solution requires you to check 3 cases: choose 0, 1 or 2 mixing bouquets first, then create the remaining single-colored bouquets in a greedy way.

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

Nice problems, both of them are good. I hope all get nice ratings ^^

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

Very nice!Clear and short problem statement, also the problems is interesting and nice, thank you :)

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

Can anyone tell me about the pretest 10 of div.2 — B ?

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

2 points above second place...

I am too lucky :)

Also I think Problem E is much simpler than Problem D.

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

    Congratulations :) For me D was easier.

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

      You are much smarter than me:).

      the problem E is a quite standard dynamic programming optimization problem.

      It is such kind problem that if you know the background knowledge,then it is very easy.

      Problem D is kind of like TC 1000pts .It require some deep insights.So I think compare those two kind,maybe swap D,E is better.

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

Problem div2 D / div1 B can be solved with O(N log N + M log M) Why the constrains are too low?

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

    Because quasilinear solution required too much technics, that do not constitute problem essence, while add to complexity

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

      The official solution (the one listed in the editorial, at least the greedy one that I also used) is also quasilinear, so I don't agree on "too much techniques that do not constitute the problem's essence". But I do think that optimizations aren't necessary; the problems themselves aren't trivial to solve, so giving a low constraint doesn't matter if the solution itself is hard to find.

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

        By techinics I meant all that 2 pointer/multiset stuff

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

          I didn't use multisets, so I'm not sure how multisets help here. But for the two pointers, I agree somewhat (I found a solution without two pointers that run in O(NM) which is basically iterating over all Ciel's cards for every Jiro's card). In my opinion, the former (sort all cards and use two pointers) is easier to think of and to code (so is not that hard to come with), but of course opinions might differ.

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

      I solved with time (n+m)*log(n+m) and there are no much technics. I think it's very easy.

      Here is it:
      3979263.

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

    Because problem can be solved with min-cost-max-flow, as you can see from WJMZBMR code.

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

    To fool and mislead solvers. Common practice. It's better (more difficult) when constraints don't suggest the solution.

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

      maybe, When I solved it with O(N log N + M log M) I had doubts about my solution because these low constraints but I got Accepted

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

Quite fast testing today in Div-2, especially in the beginning. Hope to see new rating to be fast-updated in the same way.

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

    It was because problems in Div-II have smaller constrains.

    → Reply
»
11 years ago, # |
← Rev. 5   Vote: I like it +14 Vote: I do not like it

Will participants who used e-maxx.ru be banned? I saw some solutions where were used hungarian algorithm and mincostflow implementations from e-maxx.

Add: I suppose it will be honest, especially in case of last things on abbyy cup.

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

    Captain butthurt detected. The fact that u spent about an hour debugging your 200 lines (template already excluded) mincost instead of using hungarian (which I suppose u just don't know) made you that rotten, didn't it?

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

    What really matters is finding the solution to the problem.

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

Deleted. Oops repeat, sorry.

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

    Also, who used prewritten code and something like that?

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

I think the user who sent the disgusting pictures should be banned.

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

first time get blue color after waiting 29 contest :)

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

    Congratulations!

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

    I am wondering that nobody will dare you to ask which compiler do you use :P

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

      :|

      Let me enlighten you a bit: you are goddamn inappropriate, aka IOIt.

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

How can [user:cgy4vever] participate in his own contest ?

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

Is there a way we can download test case or see entire data in a test case?

When I see the test case for which my program failed, it truncates the data and I am not able to see the complete test case.

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

DIV1 A is awesome! But it would be more interesting, if moves count to reach the end point was also required to calculate.

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

Hey friends....

When codeforces round 191 is going to commence...????

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

    It hasn't been scheduled yet. When it is, a panel will appear on the right side of the page, informing of the time remaining until the registration/contest.

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

      After how many days is it likely to be scheduled?

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

        Depends. Sometimes there are many successive rounds, sometimes there are none at all for a longer time. It shouldn't take longer than a week, I guess...

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

          Well ,there was a lot of time after the 188th contest too,I was hoping that we would be having a contest soon.

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

      Now it is showing ABBYY Cup 3.0 — Onsite (2 weeks). Does that mean there won't be any contest for 2 weeks?

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

        No. It's just the only scheduled contest so far, not the earliest one. Well, I slipped up: it's the earliest one of the scheduled ones :D but some other, earlier, contest may be added later on.

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

good contest

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

How is Commander Ciel solved (Div2 E or Div1 C)? Am I right that after finding the optimal root, the build process looks like:

  • current = 'Z', highest = 'A'
  • If node has one child, just continue using&incrementing current rank until you come to the highest, then drop current to 'Z' and --highest ('B'), then repeat from 'Z' to 'C' ... and if you're not done after 'Z'-'Z', then it's impossible
  • If node has more than one child, use highest rank in this node, drop current to 'Z' and --highest for child subtrees

If this is correct, I think that the optimal root must be the tree center (the node which minimizes tree height), but I'm getting WA on case 13.

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

    Set current rank as 'A'.

    1. Find center of tree — v.
    2. Set v rank as current rank.
    3. Repeat 1-3 for all subtrees with lower current rank.

    Impossible test doesn't exist because on every itteration diameter divides by 2, so 26 letters enough.

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

      Your solution is wrong. Read more here. You need to use another type of "center of the tree", which has no common with its diameter.

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

Congrats to cgy4ever on qualifying for Facebook Hacker Cup onsite finals.. All the best :)

→ Reply