By BYN, 8 years ago,

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

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

• +118

 » 8 years ago, # |   -39 what??????????? Why is it not rated for div-2 competitors?.what is it???
•  » » 8 years ago, # ^ |   +37 it's not rated because it's going to be a hard contest!
•  » » » 8 years ago, # ^ |   +6 Nooooooooooooooooo
 » 8 years ago, # | ← Rev. 3 →   +5 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).
 » 8 years ago, # | ← Rev. 2 →   +4 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
•  » » 8 years ago, # ^ | ← Rev. 2 →   +15 Rooms are meaningless since there are no hacks in contests with ACM ICPC rules.
 » 8 years ago, # |   +4 It's not a very good decision to make it unrated for the 2nd division. I destroys competitiveness, contest will become usual training.
•  » » 8 years ago, # ^ | ← Rev. 2 →   +17 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)!!
 » 8 years ago, # |   0 Could you please explain your reasoning for making the contest unrated for div. 2?
•  » » 8 years ago, # ^ | ← Rev. 2 →   +4 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:-)
•  » » » 8 years ago, # ^ |   +1 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.
•  » » » » 8 years ago, # ^ |   +4 I think the problems are too hard for Div 2, so there would be many contestants who solved 0 problems.
•  » » » » 8 years ago, # ^ | ← Rev. 3 →   0 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.
•  » » » » » 8 years ago, # ^ |   0 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".
 » 8 years ago, # |   +10 Once again — is prewritten code allowed just as in a typical Codeforces round?
•  » » 8 years ago, # ^ |   +5 Yes
•  » » » 8 years ago, # ^ |   +4 Thanks!
 » 8 years ago, # |   +12 input/output will be standard or files? I'm sorry, if this is written somewhere, I didn't find it :) thanks
 » 8 years ago, # | ← Rev. 2 →   +4 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
 » 8 years ago, # | ← Rev. 3 →   0 when i try to open problem A:Unable to parse markup [type=CF_TEX]UPD: just fixed
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 Sorry, i haven't see previous post.
 » 8 years ago, # |   -44 in problem C, can i shoot to the edge of mirror? will i give points and will the beam be reflected?
 » 8 years ago, # | ← Rev. 4 →   -15 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..
•  » » 8 years ago, # ^ |   +7 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.
 » 8 years ago, # |   +5 What's test #8 in problem F?
•  » » 8 years ago, # ^ |   +11 You are not allowed to go through other junctions when you is travelling between two on the list
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 8 years ago, # ^ |   0 Well, at least for me that fixed problem (I assigned weights for edges based on time)
•  » » » » 8 years ago, # ^ | ← Rev. 3 →   +3 a9999999b1#######1c1111111dIt's better to go from junction "a" to "b" througth "c" and "d".
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   0 a1d 1.1 b9c Go to brom b to c.
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 8 years ago, # ^ |   +62 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.
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   +11 "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.
•  » » » » » 8 years ago, # ^ |   +19 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.
•  » » 8 years ago, # ^ |   0 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.
•  » » » 8 years ago, # ^ |   +2 Ok, then consider the following example:3 3 3 a1b 1#1 d1c 2 1 ac 3 2The 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.
•  » » » » 8 years ago, # ^ |   +4 Such test is prohibited. They say that string contains ALL junctions in order that the hero passes.
•  » » » » » 8 years ago, # ^ |   0 In this case, such test is invalid too and I see no reason for WA8.
•  » » » » » » 8 years ago, # ^ |   0 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.
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 I found the problem, but I got wrong answer at #9 all the time.:(
•  » » » 8 years ago, # ^ |   0 Read my comment here http://www.codeforces.ru/blog/entry/5722#comment-110211. I also had WA9 but quickly realized what the problem.
 » 8 years ago, # |   +19 How to solve E?
•  » » 8 years ago, # ^ |   +22 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.
•  » » » 8 years ago, # ^ |   0 Yeah, I've already read some AC codes and understood the solution. Thanks anyway!
 » 8 years ago, # |   +3 How to solve problem C?
•  » » 8 years ago, # ^ |   +8 I want to know ,too
•  » » 8 years ago, # ^ |   +3 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).
•  » » » 8 years ago, # ^ |   +16 Whoops, I missed the fact that the beam can not reflect from the wall. Thank you.
•  » » » 8 years ago, # ^ |   +3 In case this technique isn't known to anyone, it's described in the analysis of Google Code Jam 2012 QD.
•  » » 8 years ago, # ^ |   +7 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.
 » 8 years ago, # |   +63 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.
•  » » 8 years ago, # ^ |   +8 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.
•  » » » 8 years ago, # ^ |   0 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.
•  » » » » 8 years ago, # ^ |   +8 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.
•  » » » » » 8 years ago, # ^ |   0 I see, thank you.
•  » » » » 8 years ago, # ^ |   +8 It would be true if all transfer times were same. Unfortunately, time needed for moving from one cell to another can vary.
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 8 years ago, # ^ |   0 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.
•  » » » » » 8 years ago, # ^ |   0 My contradiction was described above. Actually, I thought that I've just missed this in statement.
•  » » » » » » 8 years ago, # ^ |   +5 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".
 » 8 years ago, # |   +9 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. :)
 » 8 years ago, # |   +15 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?
•  » » 8 years ago, # ^ |   +49 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.
•  » » » 8 years ago, # ^ |   +8 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.
•  » » » » 8 years ago, # ^ |   +3 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.
•  » » » » » 8 years ago, # ^ |   0 There are only 2 ways to realize there is no penalty for G during the contest. Get G Accepted. In this case, it doesn't affect the result. Look into other contestants' submission history and found the issue. In this case, my reaction was "display error on the scoreboard".
•  » » » » » » 8 years ago, # ^ |   0 It's not true. Wrong submissions are marked in the standings as -n.
 » 8 years ago, # | ← Rev. 2 →   +16 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.
•  » » 8 years ago, # ^ |   +8 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 :)
•  » » 8 years ago, # ^ |   +8 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.
•  » » 8 years ago, # ^ |   +18 I'm wondering if anyone above the 10th place will pay for the flight out of their pocket.
•  » » 8 years ago, # ^ |   +13 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..
 » 8 years ago, # | ← Rev. 3 →   +19 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.
•  » » 8 years ago, # ^ |   +14 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.
•  » » » 8 years ago, # ^ |   +27 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?
 » 8 years ago, # |   0 Hi there, Can anyone tell me what's wrong with this? Thanks in advance ;)F — Race
 » 8 years ago, # |   +41 This is an old Peykan.
•  » » 8 years ago, # ^ |   +14 Isn't it a Javanan? :D
 » 8 years ago, # | ← Rev. 3 →   +3 There are some troubles with the show of problem.Please check it.UPD:Now it is fixed.
 » 7 years ago, # |   +37 Has anyone received the T-shirt?
•  » » 7 years ago, # ^ |   +24 I've just received it in Vinnytsia. It's a pity, but T-shirt is one size smaller than I expected it to be.
•  » » » 7 years ago, # ^ |   0 that was my problem too :D so i gave my t-shirt to my younger brother :D
•  » » 7 years ago, # ^ |   0 I also did not receive it :(
•  » » 7 years ago, # ^ |   +28 Today I received one. it's cool,but I think its' a polo shirt and not a T-shirt.
•  » » 7 years ago, # ^ |   +14 I have received it today in Riga, thanks! :)