Bayan Contest Warm Up round + 50 tshirts!
By BYN, 10 years ago, In English

  • Bayan warm-up round will be held on Sunday, October 5th 2014, 13:00 (UTC) and as indicated before, it will be held on Codeforces. Warm-up round is not a required round but top 50 are going to win t-shirts and it is going to be rated for both divisions.

  • Problems have been prepared by mruxim, mR.ilchi, havaliza . We have tried our best to make the problem-set interesting and competitive and we hope you enjoy it.

  • It is necessary to have a complete profile on contest.bayan.ir before the warm-up round! And please do make sure you have selected the correct t-shirt size!

  • We have upgraded our contest platform, and we've made sure everything is stable, tuned and robust now. Thanks to all those who helped us test the unstable version!

  • The unofficial Shortcut! Round is now accessible to all, so you can check the standings and the problems.

  • Qualification round which is the first official and required round of Bayan Programming Contest 2014-2015 will begin on October 9th so don’t forget to register right now at contest.bayan.ir if you haven’t already.

  • We've created a twitter account to publish Bayan Programming Contest news. Now you can follow us @bayan.

Update 1: The scoring will be: 500 – 1000 – 1500 – 2000 – 2500 – 2500

Update 2: Warm up round is finished now. We have decided to randomly give 5 extra tshirts to 5 contestants ranked between 51 and 550. And as mentioned before, we are going to have 5 random tshirt winners in our Qualification round too.

Update 3: Congratulations to top 50, specially:

  1. fotiIe96

  2. hogloid

  3. sankear

  4. flashmt

  5. TankEngineer

Update 4: Here are 5 lucky randomly selectes tshirt winners for this round:

  1. Dongmin

  2. zxqfl

  3. shimomire

  4. arthur.nascimento

  5. SlavaSSU

Update 5: marat.snowbear has published a good editorial for this round.

Announcement of Bayan 2015 Contest Warm Up
  • Vote: I like it
  • +282
  • Vote: I do not like it

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

Should we expect this to be like regular codeforces rounds with respect to judging? i.e: Is there pretests during the contest and final tests at the end or solutions are judged only once when submitted? Thanks!

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

    Do you translate problems ?

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

      no... I solve them(2 or 3 of them actually xD)

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

First long contest descriptions, now t-shirts. :)

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

Should my id on Bayan be same to my Codeforces id?

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

How to solve "Lake" from shortcut round?

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

Will the warm up round be a rated event on CodeForces?

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

    "and it is going to be rated for both divisions"

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

    Yeah, The warm up round will be a rated event on codeforces.

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

Should be account on contest.bayan.ir somehow "connected" to one on CodeForces (i.e some form with both names filled or same name or same email etc)?

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

    No. But later you would be asked to submit your Codeforces Handel in your Bayan profile.

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

      Oh, no problem, my Codeforces handle is tourist.

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

        So you should also be asked to submit your Codeforces password. If the Bayan admin can log in to your account, what you say is true

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

          wow, so secure.

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

          obviously no CF passwords are needed!

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

        "Oh, no problem, my Codeforces handle is tourist."

        So you should be able to receive our privet message on your codeforces panel!

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

          И вам привет!

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

          I think you shouldn't put exclamation mark there because it sounds like you're shouting. It's just a joke, keep calm :D

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

Does the contest use Codeforces rules or ACM-ICPC rules or something else?

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

    Usually warm-ups use ordinary Codeforces rules, if I'm not mistaken.

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

    The rules will be announced in the contest's email which you are going to receive day before the contest.

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

      Please consider shifting the round by 30 minutes to 1330 UTC. There is another contest running on hackerrank.com from 1030 to 1330 UTC. It is the main elimination round of a special codesprint organised for the indian students and most of us will miss this contest as a result.

      This is the link for the hackerrank codesprint: https://www.hackerrank.com/csindia14-er2

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

WTF? Sunday is an unlucky time for round. Normal people like me will get rest at that time.

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

    So, is it better to organize rounds when everybody is busy with his duties or when many people have free time? I think the answer is obvious (and TopCoder should learn it and stop organizing round in the middle (1PM in Poland) of Tuesday for example).

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

      I suppose TC is trying to cater to all timezones this way.
      But a true competitive programmer would always find time for a contest!

      And yes, during free time is better. Better than when travelling by plane, for example...

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

        But as far as I know, Tuesday 1 PM in Poland is not a reasonable time on Sunday in other time zone :P. 1 PM will be very good for me but on weekends, not when I'm at my university!

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

          Some parts of Russia? India (I think +6something from Central Europe)? China maybe? That's evening, and evening should be reasonable time.

          You've got a 6PM contest tomorrow, and you can also skip university things (I can talk, I've done some CF div2s partly during lectures :D).

          We can't always have perfect times, or China would ヽ༼ຈل͜ຈ༽ﾉ RIOT ヽ༼ຈل͜ຈ༽ﾉ

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

            You missed key point of my reply. When there is a Tuesday in Poland in all other places on Earth there is a day from set {Monday, Tuesday, Wednesday} and that set does not contain any weekend days ({Saturday, Sunday}), so this is quite easy to pick better day.

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

              Yes, I focused on the 1PM and not on the weekday... and that your next reply contained "time zone" didn't help either :D

              In that case, I have no idea either. Weekend is a better choice generally. Anyway, dirty random weekday peasants vs glorious Codechef fixed weekend times' master race :D

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

    Don't try to find normal people among competitive programmers

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

      you are a con and you are proud about it? it's nothing to add.

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

    Can a Programmer be a normal person? :)

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

Rated?

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

    So people nowadays just read the announcement title and jump straight to comments to ask "Rated?" without bothering to read even a first few sentences?

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

      Sorry, I miss it! (That sentence must be added just now... XD... ... why I couldn't find it at the first glance?)

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

    I can't see any high rated user to get downvoted (Xellos is an exception). Please remove her downvotes and give me instead.

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

Is the contest rated?

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

Is it rated?

Come on, people. Read the post before asking or you could at least ctrl+f "rated".

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

    thank you! ctrl+f really helpful!

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

Okaaaay, for once I'll be mainstream...

Rated?

UPD: And I get downvoted together with the other "mainstream" stupid questions :D

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

100 people asked about whether the contest is rated, but no one asked the much more important question: How many problems will be in the contest ?

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

    Who cares how many problems you need to solve as soon as you get (loose?) rating for it?

    Back to topic, if you look back the introduction topic you will see that it says '6 problems' there.

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

    Why do you ask ? are you planing to solve all the problems? :D

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

      To make sure I don't miss any problem. My eyesight is slightly weak.

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

We wish at least a Bayan Contest every month. The More Bayan Contest, the more competitiveness, the more preparation and finally the more chance to win a tshirts, at least in another contest .. :) :p

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

    Thank you for the kind words, but Bayan Programming Contest is going to remain an annual event.

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

      why always top 50 will get t shirt ? I always wonder if there is an announcement that last 10 will also get a t-shit how people will react and are they ready to lose rating only for that :D but I think give some T-shirt to random coder ( like me :p below average level coder to motivate him to do well ) like some TC round ( SRM 600 I remember ) will be more interesting .

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

        T-Shirts for last 10 is a horrible idea. There will suddenly be some newly registered accounts with pretests passed in problem A and 500 unsuccesful hacks.

        Random T-Shirts are cool, but that's Bayan's decision afterall.

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

          Good news then! As mentioned in our first announcement, we are going to have random tshirt winners in our Qualification round which is a 72 hour event and starts from 9 October. More details is available in the announcement.

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

          then only 30/40 rated account will be eligible for that :D main point is that am i ready to lose 250/300 rating only for a t-shirt :D another interesting idea can be like t-shirt for random place ( pre announce of course ) like t-shirt will go to 255 , 385 , 512 , 1012 placed people . how one will react then :D to get those position may be last minutes unsuccesful hacks :D

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

        How is giving T-shirts at random supposed to motivate people to do well in a contest? I can see how it helps to increase participation but not participants' effort.

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

          And how is not giving t-shirts at random going to motivate many people to (never mind doing well) compete at all? Most don't have a chance of getting into top 50, but they still compete anyway.

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

            This is really true for most participants. To be honest, there's absolutely no way I'll be in top 10 or 20 in a contest with bunch of red/yellow coders.

            I will be motivated if they choose 10 participants randomly out of, say, top 300, because it's not impossible to make it top 300.

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

what would happen, if you don't register at contest.bayan.ir?

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

the solution is not public after the contest since the 8.29

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

In case some user do not register for this contest on contest.bayan.ir and his place is in top-50 — his t-shirt will be given to person who ranked #51, or you'll just decrease number of prizes?

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

    We believe this would not happen, but in such case, we will save that tshirt.

    There has been more than 7000 registered users at contest.bayan.ir right now.

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

      I do not found address in the profile. How do you send us the t-shirt?

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

Will it be rated for Div 2 too?

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

Please consider shifting the round by 30 minutes to 1330 UTC. There is another contest running on hackerrank.com from 1030 to 1330 UTC. It is the main elimination round of a special codesprint organised for the indian students and most of us will miss this contest as a result. This is the link for the hackerrank codesprint: https://www.hackerrank.com/csindia14-er2

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

    It is a both Div 1 + 2 contest, so half hour would affect a lot in ratings. In normal contest, half hour would not have that adverse affect.

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

      Aren't u doing the codesprint today?

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

        Yes, I am doing. I won't do codeforces today. I had done it if it would have been a 2 Div 1 only round.

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

Scoring system?

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

    According to email with announcement, it will be round with standard CF rules and 500-1000-1500-2000-2500-2500 scoring distribution.

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

      Why I didn't receive the email? anyone else didn't receive it too ?

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

        Here is the email content. We will also update the post.

        Attention 1: The round starts on Sunday, October, 5, 2014 13:00 (UTC).

        Attention 2: The qualification round will be held on 9-11 October for 72 hours on http://contest.bayan.ir/en/.

        Attention 3: Top 50 will win tshirts.

        Hello, **** . Welcome to Bayan Programming Contest 2015 – Warm Up Round.

        We are glad to invite you to take part in Bayan 2015 Contest Warm Up (Div. 1 and Div. 2). It starts on Sunday, October, 5, 2014 13:00 (UTC). The contest duration is 3 hours for 6 problems. The allowed programming languages are C/C++, Pascal, Java, C#, Python, Ruby, PHP, Haskell, Scala, OCaml, Go, D and JavaScript.

        The round writers are mruxim, mR.ilchi and havaliza. Do not miss the round!

        Bayan 2015 Contest Warm Up (Div. 1 and Div. 2) will be held on Codeforces using regular Codeforces rules and it will be rated for both Div1 and Div2. The scoring will be: 500 – 1000 – 1500 – 2000 – 2500 – 2500. The round will be held on the rules of Codeforces, so read the rules (here and here) beforehand.

        The round will be for newcomers and participants from the both divisions. Want to compete? Do not forget to register for the contest and check your handle on the registrants page. The registration will be closed 5 minutes before the contest.

        Although this is a warm up round but top 50 will win tshirts. BTW, there will be another 100 tshirts for the official rounds which will be held on Bayan Contest platform (contest.bayan.ir)

        IMPORTANT: Make sure you have registered on contest.bayan.ir/en before the warm up round.

        If you want the breaking news, updates and rankings as fast as possible you can follow us @bayan on twitter now.

        We would like to thank MikeMirzayanov and Codeforces team for this great platform and this talented community.

        If you have any questions, please feel free to ask us on codeforces.com/bayan2015.

        Wish you high ratings and lots of geek tshirts!

        Bayan Team

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

what about the difficulty of problems?

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

Hey, I was trying to change e-mail of Bayan account for 2 hours. Finally I have no idea. Can you give me a hint?

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

    We have disabled email change for good reasons. We are also logging the country change.

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

Have not found the reason to register before contest, there is no connection to CF accounts. Is the registration for those who want to win t-shirts? So, I havn't any hope, but there was no place in profile to put t-shirt size.

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

    there are two profiles: on bayan.ir and contest.bayan.ir and the latter has place for t-shirt size.

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

how to solve C ???

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

    Hi.I think I solved C.This is how I done: first, you remove the -1 case.For that you can see if you have 2 conex components or you can look at he 2x2 squares.After this you take the first X, Y where you have matrix[X][Y]=='X', you look how far can you go from that position down and right and you will obtain l1 and l2.Now either, l1 is the high of the brush, wither l2 is the length.You fix which of afirmation is true and, than you can compute pretty easy the other(you know the number of columns of the brush and compute the number of rows).You make sure that it works and that's all.Take care at the second case which is a particualr one because you have just a simple ractangle, and in that case you have min(n, m) where n and m are the lengths of the rectangle.

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

      I found this approach ... i got WA on pretest #5. Thank you for responding :)

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

        Maybe you forgot one of the cases with -1.It is possible, at the end of the algorithm, that you don't find any solution. Here is a test which may fail on your solution, I think 7 5 XXX.. XXX.. XXXX. ..XX. ..XXX ..XXX ..XXX

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

    I'm not sure if this was the intended solution, but here was my approach:

    Let S be the leftmost 'X' cell in the first row containing an 'X', and let E be the rightmost 'X' cell in the last row containing an 'X'.

    First, fix a width w. We'll call a length l valid if we can start the top left of our brush at S and make a sequence of moves such that the bottom right of our brush ends up at E without our brush ever visiting a '.' cell.

    The important observation here is that once the width is fixed, the sequence of moves in a valid sequence does not depend on l. If there is a 'X' to the right of the top row of our brush, we must move right. Otherwise, we move down.

    What this means is that for all valid lengths, the number of squares we visit is decreasing as length decreases. And all invalid lengths are greater than valid lengths. So we can binary search for the first valid length that visits all 'X'-ed squares.

    The runtime is N (all widths) * log N (lengths) * 2*N (simluation).

    An implementation: http://codeforces.net/contest/475/submission/8099559

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

8087526 — problem A, "why should I write code if there are only 35 answer cases?" :D

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

some people solved B with targan algorithm and some other people solved it with floyd warshall XD :D come on guys! take it easy!! :D

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

    Even dfs was overkill for B .

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

      And what is better than dfs for B?

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

        This

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

          can you please explain what he has done ?

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

            You only stuck on corners, then if and only if there is any corner that has two incoming ways(thus no outgoing), moving from that point to other intersections will be impossible.

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

How is E solved for a tree?

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

    I assumed that for optimal solution the following statement will be true for at least one node (let's call it Root): "Every other node can reach the Root or can be reached from the Root". Then make a rooted tree from every node and you need to decide for each child whether it's direction should be from the root or to the root. The result in the children subtrees doesn't depend on the direction you choose. Now let's say you've chosen the direction in such a way that X1 nodes can reach the root (in other words they are directed to the root) and X2 nodes will be reachable from the root. Then in this case you will add to the result the number of pairs equal to:

    P = (X1 + size[root]) * X2 + X1 * size[root]

    So I calculated the weights of the each child subtree and then was checking which sums for X1 and X2 we can achieve (in a way similar to knapsack). For each achievable sum I was checking the formulae above. This has passed the pretests.

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

      I've found this approach... But how could we do the "similar to knapsack" part? I couldn't make that knapsack faster than O(N3) :(

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

        The knapsack on it's own will be O(MaxSum·Nsum) so given that you put it into a loop over all vertices it might seem to be O(N3) but it won't be that bad. The reason is that your Nsum is basically a number of children of some given node but if you sum all these values across all roots it won't be N2, it will be 2M = 2(N - 1). So it's O(N2) in total.

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

          Didn't you assumed for every vertex, every node in it's subtree can reach it or can be reached from it?
          In this line from your code : int rem = full_sum - x;
          It's amazing! Why it's always true?!

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

            Well, yeah, in order to calculate the answer the assumption should be like you stated it. But in order to prove that overall this strategy will give you the optimal result you need to use my original assumption :-)

            In this line x — a number of nodes from which you can reach the root. By our assumption for this particular root every node will be either reachable from it or you will be able to reach the root from it. So, given that fullsum is a number off all nodes in the tree except for the root, then it's clear that number of nodes reachable from the root will be like that.

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

              Thank for clear explanation!
              I didn't found that assumption... I was trying to use convex hull optimization to make it faster!
              You saved me! :P

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

what do you feel when you lock any problem then you discover it will fail ?

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

Contest like a sh.t

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

What is idea of solving of Problem C? I tried to figure out height and width of brush by defining the most left and top part of paint, then move it right or down one cell per time. Is it right idea?

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

After getting RE, I got WA. After getting WA, I got TLE.

Problem D hates me :((

P/s: I think the time limit is a bit strict

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

    I got Pretests passed with less than 0.3 seconds, and I've got an algorithm...

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

      Does not your solution rely on the number of prime divisors of the numbers from the array?

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

        No. Starting from any fixed L, gcd(A[L..R]) over all R can only have distinct values.

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

          But how to prove it?

          → Reply
          • »
            »
            »
            »
            »
            »
            10 years ago, # ^ |
            ← Rev. 3   Vote: I like it +4 Vote: I do not like it
            1. gcd(A[L..R]) = gcd(A[L..R + 1])
            2. gcd(A[L..R]) ≠ gcd(A[L..R + 1]) = gcd(gcd(A[L..R]), A[R + 1]) = d,
              d | gcd(A[L..R]) =  > d * 2 ≤ gcd(A[L..R])
            → Reply
      • »
        »
        »
        »
        10 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        No. I only use an O(Nlog^2N*(GCD complexity)) algorithm. But it stucks on pretest 11 :((

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

          I believe that the GCDs amortize out, so that overall complexity is still O(nlognlog(maxA)). This is because you should you should have O(n) values in total and each of them will only go through log(maxA) GCD steps in total over the course of running. Also I believe that you can get O(nlog(maxA)) overall but it really shouldn't be necessary.

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

How to solve D :(

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

    You always hope for math! why are you sad?

    anyway I'll give a hint: note that all intervals that start with the same index have at most O(log n) different values for GCD and they are sorted in non-increasing order.

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

A was fun LOL

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

This is my solution of E (I can't decide if it's correct from the samples, but intuition tells me it is):

  • all 2-connected components can be made into SCC; we're left with a weighted tree (vertex = SCC, weight = number of vertices in it) which we want to direct

  • consider a star with weights W[i] of sons of the central vertex c; we can see that if subset S of these sons has edges from them directed in the central vertex, then the answer is , which is maximum for as close to as possible

  • therefore, I guess that the optimal solution for a general tree is to make c the centroid, direct all subtrees towards it or away from it and decide on the subset of subtrees to be directed away from it so that the sum of weights of all vertices in them would be as close to as possible, which is O(N2) knapsack

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

    Yeah, while I didn't actually compete I did come up with that exact same solution. Seems pretty legit. Looking at any subtree, anything else you do in that subtree is only going to decrease the total number of connections from nodes in that subtree.

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

    Yeah, written the same thing, the system testing will show whether this centroid idea is correct, seems natural but I have no clue how to prove it.

    Success! :-)

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

Why did dreamoon_love_AA screw up his/her contest ?

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

Seems like a lot of people got WA on problem C at #5 test.

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

Post Updated.

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

For some reason no-one has asked, so... how to solve F ??

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

    I didn't ask because I didn't understand it

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

      Statement was really bad. I understood after asking a question during the contest. The problem is that you can split a grid into two parts by removing rows or columns with zero planets. Do this until you cannot make further moves. The number of remaining subgrids is your answer.

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

E can be done in O(n3 / 2 + m) if we group numbers of the same value (8096244) and in O(nlog2 + m) if we solve this knapsack by some FFT on base intervals (like binary tree somehow)

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

Strange contest! Many strong people failed on easy problems such as A!

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

Why i cant practise the tasks?

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

E is similar to http://main.edu.pl/en/archive/oi/20/pol...

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

    Exactly, it is. I copy-pasted my old code from this problem and thank to that I got E accepted :P. But I'm from Poland, so that is not that weird that I knew that problem. But why do you know that? Do you consider Polish problems as really nice ones :)? Or have you simply done half of the problems in the world :P?

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

      Polish problems are like The Simpsons. For any nice problem there is similar Polish problem as well as for any nice film there is The Simpsons episode with similar plot.

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

      I think many Chinese competitors are familiar with Polish problems like POI, PA and ONTAK. Many people translated these problem to Chinese voluntarily, even from Polish, and shared them with us. And some problems from PA are extremely hard, and interesting in my mind. I enjoy these Polish problems.

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

    And D is similar to CERC 2013 Magical GCD. F shares the same idea with SGU 550. :P

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

One of my friends says it will be unrated. Is it true?

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

Is there a tutorial for this round that is going to be published ??

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

May I submit solution after the contest?

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

Hello BYN, I have completed my profile on contest.bayan.ir before the warm-up round, but I did choose the size of the t-shirt is Large, could I change it to Medium now? I taking place 50 in this round, that's really close :P Btw, thanks for the greate contest

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

Is the contest rated? WA on problem A :(
It is the worst contest that I ever seen...

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

    Of course it's rated. And why is it the worst contest ever? All problems except A were very good. A was just a tricky simulation problem.

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

      I only said my opinion. Maybe it's because I get WA on problem A.

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

    A was a problem where you copy-pasted the picture into your code and did two trivial for-loops.

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

      So ?

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

        So the contest isn't at fault — the user is.

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

          OK. I think I'm so sad when I'm writing this comment :D

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

      Or as many did, not copy-paste some string and do non-trivial detail-oriented programming xD.

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

When are the ratings going to be updated?

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

Why does this get TLE? http://codeforces.net/contest/475/submission/8089790

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

    Maybe you have an infinite loop.

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

      I tried this on my pc. It gets executed in 42s :O. But I don't know why!

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

        The problem is that you have to mark visited once you push it in the queue.Like if I can go there and visited[there] == 0: queue.push(there), visited[there]=1

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

So no one that solved E actually proved that their solution is correct? This makes me kind of sad :(

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

    Well, it doesn't matter that much whether we have a proof or not, the question is whether problem setters had it :-)

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

Some of the submissions are totally the same (several solutions for task C), i think it is better to deal with this problem. :)

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

Can anyone tell what is the worst case time complexity of my solution for F?

8097771

First, I sort points by Y and I split into meta-universes in basis of Y coordinate.

Then, for each galaxy, I sort by X now and then again find meta-universes. Then for each new galaxy, I repeat this process. (alternate sorting by X and Y)

Or what is a case which would make this fail? (can't see cases fully on CF)

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

    I think it is N^2...I made the same solution.It is even N^2logN but when you split, logN bacomes very small.

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

    Well, the counter-test for that code seems to be a list of universes where in order to split the meta-universe you need to remove the last (by X or by Y) universe from it. Then every time you will sort and scan the entire sequence only in order to remove one element. O(N2·logN)

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

    I think this case will take O(N^2) time.

    O..O..O..O..O...

    Where 'O' is a planet.

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

      This test case takes O(2NlogN) time.

      We are done after the first time search() is run.

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

I think I'm going to be green from blue. But it is not so important :D

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

Finally I'm a Candidate Master :D

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

Tfw I'm one of the few that get a t-shirt (finally on a CF-hosted contest, too):

(sauce: Sandra and Woo webcomic )

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

I have a question — I solved B by BFS from each point and passed pre-tests, but after system testing I have got TL#45. Then I rewrite my solution with using of DFS — I have got AC — so, why BFS is slower then DFS? I am writing in C++, for BFS I use STL queue?

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

    You mark vertex as visited when you look at edges coming from it (right way is to do it when you add it in queue). I am pretty sure that it leads to exponential complexity. AC : 8098146.

    Upd. Yes, it leads to exponential complexity. Imagine such graph: 

    1 -> 2
1 -> 3
2 -> 4
3 -> 4

4 -> 5
4 -> 6
5 -> 7
6 -> 7

...

3n + 1 -> 3n + 2
3n + 1 -> 3n + 3
3n + 2 -> 3n + 4
3n + 3 -> 3n + 4

    You add vertex 1 to queue, then vertexes 2 and 3, then add 4 two times. So, you add 5 and 6 two times each, than add 7 four times and so on. Of course, exact this type of graph is impossible in problem's conditions, but I think you get it.

    Was glad to help.

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

    In BFS, you have to mark the node after pushing it to queue, not after popping! That's the reason of your TLE.

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

5 lucky randomly selected tshirt winners announced.

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

When is the tutorial for this round going to be published?

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

Why does this solution passes? Oo 8087726

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

    Because it's correct? :)

    Imagine the string is neither ok1 nor ok2. Then the graph is clearly not strongly connected because you won't be able to get out from one of the corners.

    Now suppose the string is ok1 or ok2. Suppose you want to go from A to B. First use whatever road you're on to go to the border, then rotate along the border until you're on the start of B's horizontal road and take it. This proves that all intersections are reachable from all other intersections.

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

      Thanks ffao ! I was also wondered why my code got accepted :p even i wrote that in this blog before seeing your post :p here is that comment .

      I understood it from your explanation . thanks again ! :)

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

Can som1 plz xplain d soln for problem D?

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

    Hint: this comment. You can also read my solution, it's pretty simple (a table of gcds of intervals of length 2k and binsearch on them).

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

is there an editorial BYN ???!!!???

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

Hello! I have found cheater again! Read it!

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

    Thank you.

    I really cannot understand why they cheat! Well, I think that Codeforces is a place to test myself and improve my programming skills; I absolutely want to know how they think or what they think Codeforces is!

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

Hey can you take tutorial ?

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

Wow, unexpected excellent result for me. I rarely appeared in the top of the scoreboard(8th place once in CF & 8th place once in SRM), so it's first time to see my handle on the announce post :)

Well, the next aim is to get the first place, I wonder(of course I know it's far more difficult)

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

    Same here, I didn't even think I would be able to win a t-shirt :)

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

Here is my solution for Prob F, but it got WA at test 8, and I haven't found mistake. I use D&C and binary search. The complexity is O(nlogn) http://codeforces.net/contest/475/submission/8100455

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

This contest seems a little hard to me, I have to train my coding level.

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

For Problem D, I found a hint in a previous comment, "all intervals that start with the same index have at most O(log n) different values". I have checked it writing some integers on paper, this is absolutely true statement. But can anyone please prove this statement or explain elaborately how to solve problem D.

Thanks in advance.

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

    gcd(x,y) > gcd(x,y+1);
    gcd(x,y) = gcd(x,y+1)*k; {k > 1}
    this situation can repeat at most log(10^9). Because k's minimum value is 2.

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

    Let our sequence be a1, a2, ..., an. Let us fix left end of substring (l). We have: gl = gcd(al) = al, gl + 1 = gcd(al, al + 1), ..., gr = gcd(al, al + 1, ..., ar). We can see that gx is divisible by gx + 1 for all . Why? Well, gx is greatest common divisor of al, ..., ax, so all other al, ..., ax common divisors, including gx + 1 are divisors of gx.

    So gx + 1 is divisor of gx. There are two cases: 1) gx + 1 = gx. So they are equal, and gx + 1 adds nothing to amount of different values. 2) gx + 1·k = gx for some k ≥ 2 and . So . This way gx + 1 is at least two times smaller than gx.

    So, every time new distinct value appears in row, it is at least two times less than previous distinct value. It means there are not more than of them.

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

      Thanks for your very nice explanation. Learning new thing is a gift to me. :)

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

      cool, this is great explanation, thanks.

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

My solution to Problem 475B - Strongly Connected City is here -> 8101961 . I got it accepted but I seriously doubt if it is wrong . I'm doubting because I've seen almost 20 codes and no one solved this in this way . Everyone implemented BFS or DFS or some other graph algorithms. Will you please have a look mruxim,mR.ilchi & havaliza ?? Where is the tutorial ???

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

    I think, there is no doubt of this solution. Many of the coders have solved this problem with almost same code as you. When you will search STATUS according to SOLUTION SIZE, then you will find many of solutions resembles with your code,

    You can find here

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

    Since the grid is too small(20*20), so I think ,using DFS needs a little thinking and some code like you, needs more thinking.And when running contest , this is an important issue.

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

      I actually think the same way, Although the solution can be written in a very faster manner, I did the DFS because it was OK for a 20x20 board and I was thinking about DFS as I was reading the statement.

      For me, finding a better solution might have taken much longer than coding a DFS function.

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

    Here is an explanation for such short solution:

    If outer streets (top, bottom, rightmost and leftmost) form a cycle (clockwise or counter-clockwise), then

    • by following that cycle, one can reach any junction on that cycle from any other junction on the same cycle.
    • moreover, independent of the directions of inner streets you can also reach all "inner" junctions from any "outer" junction. Therefore, if the outer streets form a cycle, then the answer is "YES".

    If outer streets do not form a cycle, then

    • there is at least one "corner" junction, for which both horizontal and vertical streets have directions towards that junction (otherwise, there it would be a cycle). Since one can not move out from such "corner" junction to anywhere else, the answer is "NO".
    → Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

why the title of problem D is CGCDSSQ ??!:D

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

why there is not a low rated participant in the randomly t-shirt winners list?

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

    3 purple :>

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

    Because it was chosen between participants who got 50-550th place, so high rated participants are more frequent than low rated participants in these places, so its normal

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

Could someone please tell me when the tutorial for this round is going to be published?

→ Reply