• Final round of 3rd Bayan Programming Contest will be held on Friday, May 1st 2015. The setup time starts at 7:00am IRST, and the round begins at 8:00am IRST.

• Awards and certificates of previous rounds' winners will be shipped after the onsite event.

• Contestants will be using their own laptops during the competition. We will also provide a monitor, a keyboard and a mouse for each participant.

• We will be reaching out to finalists about their flight and accommodation details through email.

• We've done our best in preparing the software and hardware infrastructure, and assuring the quality of the problemset, so we hope everyone would enjoy the event!

• We'll release the problemset publicly after the closing ceremony.

Updates:

• Egor will be blogging about our final round. So if you'd like to stay up to date, don't miss his posts.

And the winners are:

(Participants Qualified for the Final Round of Bayan Programming Contest 2015)

• If you are a t-shirt winner, double check your information on your Bayan Contest Profile.
• T-shirts will be sent after the final event which is going to be on early 2015.
• We might invite one of the t-shirt winners as our event blogger to the onsite final.
• Finalists will receive invitation emails and will be asked to send us a copy of their passport. The invitation letter will be send from "contest at bayan.co.ir".
• Unfortunately we found some cheaters and also people with duplicated accounts. As mentioned before they will be banned for ever from Bayan Programming Contests.
• To view the Source codes, log in to contest.bayan.ir, select the round and on the scoreboard click on the score for each problem.
• T-shirt Winners of Bayan Programming Contest 2014-2015
• High ranked countries in top 50
• High ranked countries in top 100

A. New Rock Paper Scissors

The O(n²) solution is straight forward, although it can be solved in O(n) but it was not required. Even the O(n) seems easier to implement, but some cases might be missed. That's why the easiest problem of the contest turned out to be a little tricky. You see both kind of solutions in the scoreboard.

B. Bayan Health Bracelet

In this problems you had to find the first condition that is met. If carefully implemented one can get accepted with no hassle.

C. Grid History

The following two statements should hold for a valid grid:

• If the board is checkered, two cells have the same parity, if and only if they are colored the same.
• Let x be the value of a cell, and y be the value of the first cell with greater value than x. The length of the shortest path from x to y among the cells with value greater than or equal to x, is not greater than y - x.
• two greatest values of the board must differ by one.

Checking the first statement can be trivially done in O(nm). The second statement needs to be checked for every cell x on the grid, leading to an overall O(n²m²) time complexity, by running BFS nm times on the grid.

D. Towers

Here is a good explanation by W4yneb0t, that gives a good perception on the solution.

The visible surface is at least the sum of the highest towers in each column, plus the highest towers in each row, plus the top surfaces.

For each k, you want to minimize the number of columns and rows that contain a tower taller than k. Put the k highest towers in the smallest (by perimeter) rectangle that can contain them. This rectangle is either a square, or has sides that differ by 1, or has one side length equal to min(n, m). So, this is the lower bound for the area, and since we can actually do that for all k at the same time, it's also the upper bound.

To calculate the number of ways, let's say you have the number of ways to pack the tallest ab towers in an a × b rectangle, with a ≤ b, and want to calculate the number of ways to pack the (a + 1)b tallest in an (a + 1) × b rectangle. You can extend the rectangle in either 2 or 4 directions (4 when a = b < min(n, m), 2 otherwise), and arrange b towers along the side in 2^b - 1 ways.

E. Water Barrels

At time zero, the water reaches the first barrel. Now assume that we already know the first k barrels that water reached them. Take the lowest pipe going out of these barrels, say it's located at height h. So all of these k barrels will be watered to height h, unless they are already reached height h. So with these information, we can calculate the time that water reaches k + 1-th barrel. The whole algorithm runs in O(n² + m).

• As a exercise, try solving it in O(nlgn + m).

F. Merge

Let's have a bottom-up definition of a block. At first, each single black cell is called a block.

A set of blocks are called diagonally-shaped, if each two consecutive blocks touch each other at their corners. It can be easily seen that they will indeed look like a diagonal. Now consider a maximal diagonal-shaped set of blocks on the grid; We call their square-hull a block too; And we call those blocks, children of the new big block. According to this definition, if the answer isn't -1, the whole grid must be a block.

Here are some facts about the blocks:

• Black cells in each block can be merged into a single sub-square on the grid.
• Not every merge-able sub-square is called a block.
• Each block has a unique diagonal direction, which can be used to decompose it to it's children.
• Diagonal direction of each block is opposite of it's children's diagonal direction.

Now let's make a tree, using our blocks and the children definition we had. Notice that the whole grid is the root.

Let ans_u be the minimum sum of cells in block u, in the optimal merging plan for this block, so the answer to the problem is ans_root. Let v₁, v₂, ..., v_k be the children of vertex u. The last merge operation in this block, merges v₁, ..., v_p with v_p + 1... v_k, for some p.

• It can be proven that in optimal solution, one of these parts is merged completely before the other one starts merging. in fact, the bigger part should be merged first. Why?

At this point we have an O(n³) solution. For each block u, let's define dp_i, j as the minimum sum of cells in blocks v_i, ..., v_j, after merging them into one sub-square. So ans_u equals to dp_1, k. For each i and j, we should choose the last move, i.e. choose some p, (i ≤ p < j), and update dp_i, j from dp_i, p and dp_{p + 1, j}. The details of it are just some boring calculations.

To improve this solution to O(n²), we just need to see that in the optimal solution, dp[i][j] will be updated from p = i or p = j - 1.

..

Special thanks goes to havaliza, mR.ilchi, haas and mruxim for preparing the problems and the editorials. Hope you enjoyed the problems.

Elimination Round will start today, 14:30 (UTC) and only contestants who have passed Qualification Round will be eligible to participate.

Score for each solved problem is calculated based on these values:

• n = No. of accepted submissions
• t = Contestant's submission time
• p = Number of contestant's wrong attempts

To receive the latest news fast, follow us on twitter: @bayan

Update 1: The Elimination round is over, and let's face it: It was far from good!

Yes, we're aware of all the issues, and we know that nothing is more nerve-racking than facing those issues during a competitive contest. So, first thing first, we'd like to sincerely apologize for all the inconveniences caused.

In last hours, we thought that the contest has become too hard, so we made a major wrong decision: omitting a hard problem and adding a simple problem as our first question without enough time. Hint: never make any changes to the problem set in a hurry.

Update 2: Editorial is on the way. Source codes will also be avalible in a few hours.

Update 3: Unfortunately we have found some cheaters. As mentioned before they will be banned for ever from Bayan Programming Contests.

Update 4: The editorial is now available.

In a few hours, Bayan Qualification round begins.

Qualification round will be held as our first official and required round of Bayan Programming Contest 2014-2015. It will begin on October 9th, 06:00 (UTC) for a 72-hour period, and solving only one problem is enough to advance you to the elimination round. This round is going to be an easy event with 3 very easy problems and 5 random participants will be receiving t-shirts.

Whether you are testing your luck for a random tshirt or are aiming for one of 100 tshirts of elimination round, or even if you are already planning for your trip to Tehran, you should not miss the qualification round. (contest.bayan.ir)

Please do make sure that you have fully read the main contest announcement. Lots of your questions has been already answered there.

We would like to thank MikeMirzayanov and his team specially Maxim Akhmedov (Zlobober) once again for all their efforts before and during the warm up round. Polygon was also handy and helpful for problem setting and team collaboration.

To join the stream you can follow contest's updates @bayan and you can follow the images on our Instagram page.

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

Thank you all for participating in Bayan Programming Contest 2014-2015. We honestly didn't expect to host around 2500 contestants for the Shortcut! round.

We had hosted 7 successful rounds with previous stable version of our platform, but due to major changes in it, we needed to test the new version, and that's why we planned to add the Shortcut! round as an opportunity "mainly meant to help us actively test our new contest platform".

Round Issues

Although we were prepared to face some issues, we seriously never expected to lose about 20 minutes of the contest. We were experiencing about 550 requests per second from more than 12,000 IPs! With the start of the round, the burden was increased to 700 req/sec.

We first tried to mitigate the attacks, and then we tripled our computing power by adding CPU cores as fast as we could, after which the situation became more stable.

As we've mentioned before, our official tournament starts after our warm-up round on Codeforces, and we'd like to ensure you that we'll be working hard enough to improve both our contest platform and network facilities, and make your next experience an awesome one.

Thank you once again for your your active presence in our Shortcut! round.

Results

So, congratulations to Kazuhiro Hosaka who stood on the 1st place by solving the 3rd problem (and thus owning the problemset) in the very last moments of the round, and won the direct ticket to the final event!

As we promised before, top 5 contestants will be receiving Bayan Programming Contest 2014-2015 t-shirts:

1. Kazuhiro Hosaka hos.lyric
2. Gennady Korotkevich tourist
3. Ivan Zdomskyi ballon
4. Nathan Azaria nathanajah
5. Peter Bejda piob

You enjoyed Bayan Programming Contest 2012-2013? Now we are happy to unveil Bayan Programming Contest 2014-2015! This will be Bayan's 3rd public programming contest and we have made several improvements and did our best to make the whole tournament even more fun! To register visit contest.bayan.ir right now!

Introducing the rounds

We are going to host 5 rounds:

1. The first round is named Shortcut!. Shortcut! round is mainly meant to help us actively test our new contest platform, but since we'd like to thank all the people participating in this round, the winner will bypass "all" intermediate rounds, and directly advance to the final onsite event! Top 5 contestants will also get a T-shirt. Shortcut! round is not going to be too hard and there is only 1 hour to solve 3 problems, making it harder to predict the round winner!

2. Warm-up is our second round and honoured to be hosted on Codeforces. Warm up is also not a required round but it is going to be rated for both divisions and the top 50 are going to win t-shirts.

3. Bayan Programming Contest officially begins with the Qualification round. It is going to be an easy event, and solving one problem is enough to advance to Elimination round. If you missed Shortcut! Round, make sure to get familiar with our new platform during this round. Also, 5 random participants will be receiving t-shirts.

4. Elimination round is the most challenging online round in this tournament. Top 100 participants will be receiving t-shirts, but only top 20 from 20 countries will get the chance to compete in the final (onsite) event.

5. Final round will be an onsite event. To find the onsite event's look and feel, you can watch this 4 minute video clip. More details will be announced later.

UPDATE:

Shortcut! Round Terms & Rules

• Shortcut! round will start at 13:00 UTC, 29 August 2014.
• Shortcut! round consists of three programming tasks and competitors will have just one hour to solve them.

Solving Problems

• Competitors may solve problems by any means and are free to use any programming language, library or computational application to solve problems. Given an input file, you should submit a correct output together with the source code used to produce that output within the specified time limit.
• Not submitting any file during the time limit, will be considered as an unsuccessful attempt.
• Both input and output formats are crucial. Adhere them precisely to avoid getting solutions judged as wrong.

Penalties

• Competitors may not use more than one user account.
• Competitors may not communicate with each other during the contest.
• Your output must be reproducible using the source code you provided.
• All submitted source codes will automatically get analyzed for code plagiarism detection.
• Cheaters will be banned forever from Bayan programming contests.

Judging

• Do not submit irrelevant clarifications during the contest.
• The decision of the judges are final in all matters.
• All source codes of the competitors will be published after each round.
• Bayan's staffs are not allowed to participate in the contest.

Score Calculation Method

• n = No. of accepted submissions
• t = Contestant's submission time
• T = Total contest duration
• p = Number of contestant's wrong attempts