Bayan 2012/13 — Elimination Round
By BYN, 11 years ago, In English

Hi everybody!

Time for Bayan Programming Contest 2012/13 — Elimination Round.

The problemset has been prepared by Bayan employees. We've tried our best to make it interesting, competitive and a little-bit different! We'd like to thank Mike Mirzayanov (MikeMirzayanov) and Gerald Agapov (Gerald) who helped us during problemset arrangement process.

The contest is individual and will be held with ACM-ICPC rules. It will be having English statements only. Also, it will be rated for Div-1 contestants, but we expect Div-2 participants to enjoy it as well.

This round will be a 3hr round with 7 problems to solve. Just like most of ACM-ICPC contests, problems are not supposed to be sorted in order of difficulty. Also, the registration will be open until the end of contest, so be sure to double-check the timing.

Top 20 participants will be invited to the onsite event — Tehran, and Top 100 will be receiving T-Shirts. More details about the prizes is explained in our previous blog post.

Just to emphasize some rules, avoid participating with more than one usernames. Also, you should not collaborate or contact anyone about the problems.

Good Luck!

UPD: The contest is over. Congratulations to all the winners, specially:
1. tourist
2. cerealguy
3. rng_58
4. peter50216
5. Egor
6. PavelKunyavskiy

Because of unusual calculation of rating for this contest. The rating will be updated with delay.

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

Comments Comments (84)
| Write comment?
»
11 years ago, # |
  Vote: I like it -39 Vote: I do not like it

what??????????? Why is it not rated for div-2 competitors?.what is it???

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

I hope you can make it rated for div.2 participants, it can make div.2 participants more interesting, so they can solve the problems better (because all of the participants want to make their rating higher).

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

what's the problem if the contest will be rated for both div. I think if they put each Div in separated rooms ,it will be fair like any contest each div has it's own standing and rooms but this time will be the same problems. I think also some div2 blue coders have ability to compete with div1 thanks

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

    Rooms are meaningless since there are no hacks in contests with ACM ICPC rules.

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

It's not a very good decision to make it unrated for the 2nd division. I destroys competitiveness, contest will become usual training.

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

    Do you think CF-admins didn't think about making some slightly different problemset for div.2 competitors? Obviously, there's some problem about it — too much people competing (compare to middle-crowded Codeforces round) or some trouble with native (i mean, Iranian) organizers or so. Don't cry and get ready for Codeforces Round #148 (Div. 2)!!

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

Could you please explain your reasoning for making the contest unrated for div. 2?

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

    Do you really want to hear the answer on your question? Maybe, you won't like it ;-) ... or maybe it's too complicated to understand (and forgive, either) for div.2 competitors:-)

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

      I'll be frank: I don't like it no matter what the reason.

      But I still want to know, because if I do know the reason, it won't make me feel any worse and at least I'll be able to understand better.

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

        I think the problems are too hard for Div 2, so there would be many contestants who solved 0 problems.

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

        I don't get it. It seems to me that your better understanding is the reaction on getting the answer you wanted. But you say, this is the cause. Makes my head go round, really.

        UPD Besides, here you could see some people giving you two good reasons for that: 1) overcrowded server. 2) hard problems.

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

          Why would my better understanding be the reaction on the answer I want? I don't want a specific answer, I wouldn't ask if I did!

          And what I want to know is the responsible ones' reason. If it's like saying "div. 2 guys, this ain't for most of you".

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

Once again — is prewritten code allowed just as in a typical Codeforces round?

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

input/output will be standard or files? I'm sorry, if this is written somewhere, I didn't find it :) thanks

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

Unable to parse markup [type=CF_TEX] I get that when i try to open problem A. What's the problem? ///EDIT : It got fixed atleast for me

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

when i try to open problem A:

Unable to parse markup [type=CF_TEX]

UPD: just fixed

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

in problem C, can i shoot to the edge of mirror? will i give points and will the beam be reflected?

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

It seems not a good idea to make it unrated for div-2.it is 2’clock in china..and now it seems a wasting -time night for me..

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

    Don't be all about rating, the main idea is to learn something after all + it would've been quite unfair to make it rated because most of the div2 participants would've get their rating decreased, the tasks are too hard for div2.

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

What's test #8 in problem F?

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

    You are not allowed to go through other junctions when you is travelling between two on the list

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

      And what's the problem? If I travel along shortest path between two junctions, it's a straight line. Obviously, if there are junctions on it, it's impossible to travel between these junctions.

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

        Well, at least for me that fixed problem (I assigned weights for edges based on time)

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

        a9999999b

        1#######1

        c1111111d

        It's better to go from junction "a" to "b" througth "c" and "d".

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

        Go to brom b to c.

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

        There is an ambiguity in the problem statement. Let k be 4 in the last sample. Then in 4-th minute we are in the process of traveling from one block to another and it is unclear what to output. I have WA9 when output the final position and get AC in other case. Maybe this may helps.

        UPD. All above examples are wrong since the junctions in the input are exactly those junctions that we meet during travel.

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

      Can authors tell me, where exactly in the problem statement it's said that you have to pass only these junctions.

      I think, that path abc, goes through ac too.

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

        "We know the initial position of the Old Peykan and the sequence of junctions that it passes to reach its destination"

        It hints that all junctions Peykan passed are in this sequence.

        And I absolutely agree that it's strange to write about shortest path when mentioning the only permitted path.

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

          This sentence sounds closer to the one, that we were supposed to understand, but anyway it's not formal enough.

          Your expression "it hints" is good one, yes it just hints.

          I asked about ambiguity in shortest paths, but I was answered that input is so, that there is unique shortest path.

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

    Maybe the test, where the shortest path between some pair of junctions lies across another junction. I solved this test by replacing Floyd matrix with the original one.

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

      Ok, then consider the following example:

      3 3 3 a1b 1#1 d1c 2 1 ac 3 2

      The path goes from 2 1 to 1 1 and then it has two options — go through 'b' or go through 'c'. So there are two different answers.

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

        Such test is prohibited. They say that string contains ALL junctions in order that the hero passes.

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

          In this case, such test is invalid too and I see no reason for WA8.

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

            This test is correct because we have an edge between "a" and "b". And according to the problem statement you must use this very edge and not any shortest path between these nodes.

            So, although we could get from "a" to "b" by "acdb" path we should use "ab" directly.

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

    I found the problem, but I got wrong answer at #9 all the time.:(

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

How to solve E?

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

    In E we have a system of inequalities d[j] — d[i] <= 2 and d[i] — d[j] <= -1, if there is an edge (i, j). It can be solved by the standard method with Ford-Bellman algorithm.

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

      Yeah, I've already read some AC codes and understood the solution. Thanks anyway!

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

How to solve problem C?

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

    I want to know ,too

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

    According to the Dirichlet principle, a laser ray can be reflected only N times, so you can just naively trace it to the position, where it'll get after [0; N] reflections (I mean: you should "unroll" the box vertically).

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

      Whoops, I missed the fact that the beam can not reflect from the wall. Thank you.

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

      In case this technique isn't known to anyone, it's described in the analysis of Google Code Jam 2012 QD.

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

    Let 1<=C<=N is number of intersected mirrors. You may reflect all picture a lot of times.

    So the ray is the straight line with finish r +/- 100 * C or 100-r +/- 100*C. (depends of parity C)

    Then check if line intersect mirrors.

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

I'm disappointed with Problem F (Races) statement. I may be missing something in the text, but:

First, it is not stated that the shortest path is unique, and if it is not, which of the paths should be considered.

Second, it is not obvious what is the exact position of Old Peykan while he moves between two consecutive blocks for several seconds.

So I had to submit two clarification requests to figure that out.

However, if these are indeed ambiguities in the problem statement (and not my fault of not noticing the answers to the above points), I believe the best judges' action would be to broadcast these answers and not just reply to me.

Well, in the end, I didn't accept the problem, and being unsure whether it's my bug or another statement ambiguity is a bad feeling for a contestant.

Nevertheless, thank you for the contest! I liked the problems.

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

    UPD: I found out the third point I missed in the statement, and I consider it's poorly formulated, too.

    It should be emphasized that we can not pass other junctions when moving between two consecutive junctions from the string. Otherwise, it could be understood the other way: we are given the sequence of junctions, and we should visit these junctions in this sequence; however, it is not prohibited to visit other junctions between the junctions of the required sequence.

    For now, I don't see any direct contradiction with this understanding in the problem statement. If there is indeed no such contradiction, please consider rejudging the problem so that both understandings can pass.

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

      As I think, this condition doesn't really matter, does it? Well, if there is path between junctions that does not pass through others, it's a straight line. So, it's the shortest path and solution which looks for it (without condition) should work perfectly.

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

        As moving through different blocks takes different time, it is natural to consider a path to be shortest if it takes the least time to travel, not the least number of blocks.

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

        It would be true if all transfer times were same. Unfortunately, time needed for moving from one cell to another can vary.

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

      If he can pass another junction there are tests like

      c1d
1#1
a1b

      with multiple solutions when moving from a to d. As there is no sentences like "if there are multiple solutions ...", I thought that the junctions list is full.

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

        If you see the ambiguity, that is, ask yourself "can we visit other junctions while traveling between two consecutive points of the given route?", there are indeed a few hints in the statement that the answer is "No".

        The problematic case is when you see only the "Yes" alternative: there seems to be nothing that contradicts it and forces you to invent that question. I read it like "some points are to be visited in the given order, and the path should be the shortest", and the statement didn't help me to figure out that there are additional restrictions on the path.

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

          My contradiction was described above. Actually, I thought that I've just missed this in statement.

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

            Well, I also thought "can there be multiple solutions", submitted a clarification request, and the judges answered "No". They perhaps thought "No, it is obvious from the problem statement", but with my understanding, I misinterpreted it as "No, we guarantee that there are no such test cases".

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

Problems are interesting, especially the last one (Problem G). I hope someday I can create some problems like this and then make a contest here.

Today I'm a bit luck, my randomized solution passed problem D. (Though I don't know why it can pass.) And then I become red again. :)

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

Great and interesting problems.

But there is a bug in penalty time calculation for problem G.

No matter how many times you WA on G, you got 0 penalty time.

Can we get this fixed?

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

    In codeforces if you fail test 1 you don't get penalty (to avoid submission mistake). No one got penalty for G because G has only one testcase.

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

      That is under the assumption that test 1 is the sample test 1. However, problem G is different and I think it makes sense to have penalty for test 1.

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

        During the contest a lot of coders could think "There is no penalty for problem G, so I can submit as many times as I want". If there will be penalty for this problem, it will be not fair for those contestants.

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

          There are only 2 ways to realize there is no penalty for G during the contest.

          1. Get G Accepted. In this case, it doesn't affect the result.
          2. Look into other contestants' submission history and found the issue. In this case, my reaction was "display error on the scoreboard".
          → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            It's not true. Wrong submissions are marked in the standings as -n.

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

I think there's some people who will give up participating Bayan onsite because of the flight expenses.

Then,I wonder that , invited contestants will be only people whose rank is lower than or equal to 20th, or include some people whose rank is upper than 20th.

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

    They also have to consider if the rankings will be affected by the penalties from problem G (as said before, right now no one gets penalties). I think they should :)

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

    And I have similar question about top10, whose flight expenses are paid. It will be top10 from the contest or top10 among contestants who will take part in onsite round.

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

    I'm wondering if anyone above the 10th place will pay for the flight out of their pocket.

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

    If someone in the top20 just gives up the chance, will the chance be handed down to the following contestants?BTW, it's quite expensive to fly there..and poor for the 11th,who was just so close to get a free flight..

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

For Problem D, Gassa's AC code 2482976 make assumption that for n = 63 and every p, there is always a solution for this problem. I just tried the case when the input is just 1, ..., 63 in order, and every prime p ≤ 50000, and the assumption does hold. Anyone know how to prove this?

Edit: Just tried 63, ..., 1, and the assumption holds too.

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

    I just thought that for n = 63 (actually it is 127 in the submitted solution), there are 263 subsets which we can take, something like 263 / 64 of them have zero XOR, and these subsets "behave randomly" modulo p, so the probability of finding the solution is very high.

    If p and 10 (base) are somehow dependent, the randomness assumption can break. The only valid cases are p = 2 and p = 5 but these numbers are too small to break the solution. However, my solution could be wrong for non-prime p such as multiples of 10 000.

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

      I have thought about that too, so I strongly believe that the assumption is true. But I still want to find a complete proof.

      By the way, would there be editorial for this contest?

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

Hi there, Can anyone tell me what's wrong with this? Thanks in advance ;)

F — Race

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

This is an old Peykan.

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

There are some troubles with the show of problem.Please check it.

UPD:Now it is fixed.

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

Has anyone received the T-shirt?

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

    I've just received it in Vinnytsia. It's a pity, but T-shirt is one size smaller than I expected it to be.

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

    I also did not receive it :(

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

    Today I received one. it's cool,but I think its' a polo shirt and not a T-shirt.

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

    I have received it today in Riga, thanks! :)

    → Reply