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.

what???????????Why is it not rated for div-2 competitors?.what is it???it's not rated because it's going to be a hard contest!

Nooooooooooooooooo

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

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

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

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

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

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

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

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.

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

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.

UPDBesides, here you could see some people giving you two good reasons for that: 1) overcrowded server. 2) hard problems.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".

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

Yes

Thanks!

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

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

when i try to open problem A:

Unable to parse markup [type=CF_TEX]

UPD:just fixedSorry, i haven't see previous post.

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

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

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.

What's test #8 in problem F?

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

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.

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

a9999999b

1#######1

c1111111d

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

Go to brom b to c.

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.

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

onlythese junctions.I think, that path

abc, goes throughactoo."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.

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.

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.

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.

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

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

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.

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

Read my comment here http://www.codeforces.ru/blog/entry/5722#comment-110211. I also had WA9 but quickly realized what the problem.

How to solve E?

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.

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

How to solve problem C?

I want to know ,too

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

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

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

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.

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.

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.

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.

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.

I see, thank you.

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

If he can pass another junction there are tests like

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

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

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

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

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?

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.

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.

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.

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

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

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.

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

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.

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

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

For Problem D, Gassa's AC code 2482976 make assumption that for

n= 63 and everyp, there is always a solution for this problem. I just tried the case when the input is just 1, ..., 63 in order, and every primep≤ 50000, and the assumption does hold. Anyone know how to prove this?Edit: Just tried 63, ..., 1, and the assumption holds too.

I just thought that for

n= 63 (actually it is 127 in the submitted solution), there are 2^{63}subsets which we can take, something like 2^{63}/ 64 of them have zero XOR, and these subsets "behave randomly" modulop, so the probability of finding the solution is very high.If

pand 10 (base) are somehow dependent, the randomness assumption can break. The only valid cases arep= 2 andp= 5 but these numbers are too small to break the solution. However, my solution could be wrong for non-primepsuch as multiples of 10 000.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?

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

F — Race

This is an old Peykan.

Isn't it a Javanan? :D

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

UPD:Now it is fixed.Has anyone received the T-shirt?

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

that was my problem too :D so i gave my t-shirt to my younger brother :D

I also did not receive it :(

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

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