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.
(Participants Qualified for the Final Round of Bayan Programming Contest 2015)
The O(n2) 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.
In this problems you had to find the first condition that is met. If carefully implemented one can get accepted with no hassle.
The following two statements should hold for a valid grid:
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(n2m2) time complexity, by running BFS nm times on the grid.
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 2b - 1 ways.
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(n2 + m).
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:
Now let's make a tree, using our blocks and the children definition we had. Notice that the whole grid is the root.
Let ansu be the minimum sum of cells in block u, in the optimal merging plan for this block, so the answer to the problem is ansroot. Let v1, v2, ..., vk be the children of vertex u. The last merge operation in this block, merges v1, ..., vp with vp + 1... vk, for some p.
At this point we have an O(n3) solution. For each block u, let's define dpi, j as the minimum sum of cells in blocks vi, ..., vj, after merging them into one sub-square. So ansu equals to dp1, k. For each i and j, we should choose the last move, i.e. choose some p, (i ≤ p < j), and update dpi, j from dpi, p and dpp + 1, j. The details of it are just some boring calculations.
To improve this solution to O(n2), we just need to see that in the optimal solution, dp[i][j] will be updated from p = i or p = j - 1.
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:
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.
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.
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:
Update 4: Here are 5 lucky randomly selectes tshirt winners 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".
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.
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:
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!
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!
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.
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.
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.
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.
Final standing is accessible from our official page. Congratulations to our winners:
We hope all the participants have enjoyed the contest.
A short clip of overview of the contest is available here.
We'll do our best to put the problem-set in the gym as soon as possible.
Since the final round has finished, we'll start shipping the T-shirts of elimination round winners in 10 days.
So you were in the top 100 of Bayan 2012/13 elimination round? Congratulations! We're just about to start shipping the T-shirts. Unfortunately, some of the users had not provided the required information in their profile. If you are one of them, please send your detailed contact information and T-shirt size to contest (at) bayan (dot) co (dot) ir in the next 48 hours.
Have a nice time!
Elimination round is over!
Thank you all for participating in the elimination round of Bayan Contest. The final results are available. We had more than three thousand registered users for the contest on Codeforces and one third of them were able to solve at least one problem. In the meantime 1100 Iranian contestants participated in our local contest and half of them solved a problem.
We tried hard to prepare a challenging-yet-fun problemset.
The problem "241G - Challenging Balloons" was inspired from a real story! The problem described in the story was used in CEOI 2011 (Task Balloons), and the provided algorithm was the author's solution during that contest — which got the full mark indeed.
According to statistics, "241D - Numbers" was the hardest problem. A tricky approach to the solution is to ignore large inputs and solve the problem for small values of n. You may observe that it is possible to find the demanded subset within a small part of input. During the contest, no one solved all the problems but there was at least one successful attempt for each of them.
We hope you enjoyed it all!
As stated before, Top 100 contestants will be receiving T-shirts. So, update your contact information and T-Shirt size in your Codeforces profile. We'll start sending the prizes as soon as possible.
The winners will receive invitation letters — to the on-site event — soon. If you are one of them make sure your contact information is up-to-date.
Congratulations to all the participants, specially the winners. See you in Tehran!
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.
Because of unusual calculation of rating for this contest. The rating will be updated with delay.
Bayan is a software development company working on large-scale web applications. Currently working on a Search Engine, we face serious algorithmic challenges every now and then, and we try to provide solutions using state-of-art techniques, including Machine Learning, Natural Language Processing, etc. Salam, being one of its subprojects, is a Meta Search Engine focusing on retrieving relevant results for Persian queries.
We also hold an annual programming event in which talented programmers compete. Problems of the contest are prepared by Bayan employees who have experience of IOI and ACM/ICPC. The previous contest had a wide range of audiences. About 2000 contestants participated in the last year's opening contest.
This year, we have planned to invite participants from other countries as well. The elimination round will be held on Codeforces with ACM/ICPC rules. Top participants are invited to attend the on-site event in Tehran.