# | User | Rating |
---|---|---|

1 | tourist | 3735 |

2 | MiFaFaOvO | 3681 |

3 | Um_nik | 3553 |

4 | Benq | 3376 |

5 | ecnerwala | 3295 |

6 | maroonrk | 3229 |

7 | TLE | 3223 |

8 | Radewoosh | 3216 |

9 | scott_wu | 3209 |

10 | Petr | 3205 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 203 |

2 | antontrygubO_o | 191 |

3 | pikmike | 187 |

4 | Monogon | 185 |

5 | vovuh | 184 |

6 | Ashishgup | 182 |

7 | Um_nik | 180 |

8 | SecondThread | 173 |

9 | Radewoosh | 172 |

10 | McDic | 162 |

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.

(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**

The *O*(*n* ^{2}) 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:

- 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* ^{2} *m* ^{2}) time complexity, by running BFS *nm* times on the grid.

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 thank. Put thekhighest 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 tomin(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

abtowers in ana×brectangle, witha≤b, and want to calculate the number of ways to pack the (a+ 1)btallest in an (a+ 1) ×brectangle. You can extend the rectangle in either 2 or 4 directions (4 whena=b<min(n,m), 2 otherwise), and arrangebtowers along the side in 2^{ b - 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*(*n* ^{2} + *m*).

- As a exercise, try solving it in
*O*(*nlgn*+*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:

- 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* _{1}, *v* _{2}, ..., *v* _{ k} be the children of vertex *u*. The last merge operation in this block, merges *v* _{1}, ..., *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* ^{3}) 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* ^{2}), 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:

**Update 4:** Here are 5 lucky randomly selectes tshirt winners for this round:

**Update 5:** marat.snowbear has published a good editorial for this round.

Announcement of Bayan 2015 Contest Warm Up

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:

- Kazuhiro Hosaka hos.lyric
- Gennady Korotkevich tourist
- Ivan Zdomskyi ballon
- Nathan Azaria nathanajah
- 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!

We are going to host 5 rounds:

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.

**UPDATE:**

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

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

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

- 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 for each solved problem is calculated based on these values:

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

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.

Our special thanks goes to MikeMirzayanov for perfectly hosting our elimination round on Codeforces. We'd also like to thank ivanromanov for his great coverage of the event.

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.

Have fun

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!

Good Luck

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.

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.

- No age restriction is proposed for the elimination round. However, only participants older than 16 are eligible to take part in the onsite event.
- No Bayan employee nor their families may take part in the contest.
- Iranian contestants will advance to the final event in a different process, and thus they are NOT allowed to participate in the Codeforces round.

- will be held November 1st,
- is an individual event,
- takes 3 hours, with ACM/ICPC rules,
- cheaters are banned forever!
- Top 20 participants will be invited to on-site contest in Tehran, All accommodation expenses are covered by Bayan. Flight expenses for top 10 participants are paid as well.
- Top 100 contestants will receive the contest's T-shirt.

- Results will be posted here.

- Overall workflow of advancing to the onsite event is illustrated below:
- We will be having lots of interesting side-activies. Detailed schedule will be announced soon. Stay tuned!

- 1st prize: Gold Medal + 3 Gold Coins (24 gr total) + $1000 Iranian Handicrafts
- 2nd prize: Silver Medal + 2 Gold Coins (16 gr total) + $1000 Iranian Handicrafts
- 3rd prize: Bronze Medal + Gold Coin (8 gr) + $1000 Iranian Handicrafts

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/10/2020 05:47:42 (i1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|