... I'm tired, I'm retired

I was away from cp for a while, and I'm getting a bit rusty, so I decided to train a bit.

On Tuesday 13:00 UTC, I'll be solving problems from a past ICPC regional. You can join me by registering in the Dinossaur training Series #00 at A2OJ.

We'll use problems from Live archive, so don't forget to link your Live Archive account in A2OJ.

UPD. Live Archive is down. We'll use problems from UVA (clear cookies if necessary:)). 11 puzzles 4h.

UPD. Unfortunately A2OJ was not reading submissions from UVA (complaint with ahmed_aly :)), and the standings ended up empty.

UPD. Problems were from Dhaka 2013. Stay tuned for next training!

Code Jam R2 starts in ~24h (Saturday, May 19th 14:00 UTC)

Let's discuss the problems after the contest!

CodeChef April Cook-Off 2018 will be on Sunday, 22nd April, 2018 at 21:30 IST.

This is the first contest that I set this year. So far I set only one contest per year, so it can be called alei yearly contest :)

There will be 5 puzzles for each division, and you have to solve them in 2.5h. I challenge top coders to solve it in yandex time i.e ~100 minutes.

The puzzles are based on the problems faced by Suzumo in his daily life at ChefLand.

See you in the ranklist!

UPD. Congratulations to the winners!

Div 1

tourist (perfect score) natsugiri ilyakor

Div 2

YogayoG owly stark_arya

March Cook-Off starts in less than 3h.

Setters are kefaa and chemthan.

Let's discuss the problems after the contest.

UPD. Contest is over. Congrats to the winners!

uwi

LHiC

dreamoon_love_AA

2017 was a prime year with great contests and some notorious coincidences.

From the problems that I proposed, my favourite was BCYCLES, it is about covering twice every edge of a bicubic graph using cycles. The idea was colouring the edges with 3 colours and then make the cycles using alternating colours.

From problems that I saw in CodeForces my favourite was Symmetric Projections, IMHO it is not a hard problem, but I liked the property that every axis with momentum 0 passes through the center of mass.

Hello Codeforces!

I’d like to invite you to CodeChef June Cook-Off that will start at 21:30 IST of 18th June 2017 (check your time zone here). There will be 5 problems and it will last 2.5 hours.

This is my second Cook-off, my previous round was on august 2016 — at this rate my rounds are going to be called Alei yearly contests!

• Problem Setter: Alei Reyes Morphy
• Primary Tester and editorialist: Hussain Kara Fallah Pepe.Chess
• Secondary Tester: Kacper Walentynowicz kpw29
• Mandarin Translator: Hu Zecong huzecong
• Vietnamese Translator: Team VNOI
• Russian Translator : Sergey Kulik CherryTree

No registration is required, anybody with a CodeChef handle can participate.

Hope you enjoy the puzzles!

UPD. I'm really sorry for the inconvenient with problem KNICOV. Testers also arrived to the same greedy solution and I was overconfident since it was an easy problem.

UPD. Hints, comments, solutions

ADACRA: Group Us and Ds in blocks, what happens with the number of blocks after performing one operation?

SNACKUP: I came up with this problem while doing research on the double cycle cover conjecture. The problem is about finding a set of cycles such that every edge is in exactly two cycles.

CENTREE

KNICOV: This was expected to be the easiest problem of the round, I underestimated it and now you can see the consequences.

For n=2 the answer is

..**.. ..**.. ..**..
..**.. ..**.. ..**..

For n=3 I thought that the same patterns produce the correct answer but it turns out that fewer knights are required. I had a proof, but it was incorrect :(

I missed the dp solution which is the bulletproof

ADADET: ~10 minutes before the round I generated new test data, but solutions of testers didn't match! I got very nervous, it turns out that I was comparing files with diff and the testers output were in differente format (spaces, line breaks). Hint: Think in the structure of the convex hulls.

Hello CodeForces Community!

I’d like to invite you to the CodeChef August Cook-Off. As usual, the CookOff will be on the second last Sunday of the month.

Joining me on the problem setting panel are:

• Problem Setter: Morphy (Alei Reyes)
• Problem Tester: kingofnumbers ( Hasan Jaddouh)
• Editorialist: PraveenDhinwa (Praveen Dhinwa)
• Russian Translator: CherryTree (Sergey Kulik)
• Mandarin Translator: huzecong (Hu Zecong)
• Vietnamese Translator: VNOI Team
• Contest Admin and Language Verifier: PraveenDhinwa (Praveen Dhinwa)

Especial thanks go to kpw29 for his appreciation of the problem-set before I send it to CodeChef, he have a good taste in programming contests so I'm glad he found the problems interesting.

The contest theme is based on Lewis Carroll's book Alice's Adventures in Wonderland. Problems are not sorted by difficulty, so I highly recommend to read all of them. This is my second time as problem setter, you can see my previous round at CF328.

I hope you will enjoy solving the problem set. Please give your feedbacks in the comments below after the contest. You can find the rest of the details about the contest below.

Time: 21st August 2016 (2130 hrs) to 22nd 2016 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Details: https://www.codechef.com/COOK73

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Prizes: Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: https://www.codechef.com/laddu. (For those who have not yet got their previous winning, please send an email to winners@codechef.com)

Good Luck and Have Fun! Hope to see you participating!!

UPD. My sad story: I wake up very early to take part on AtCoder, and then to moderate the CodeChef contest, but just before the start of AtCoder there was a power outage on my city :(. Fortunately the contest admin, translators, and tester were able of handling the contest all by themselves :).

UPD. Congrats to the winners!

ksun48

anta

uwi

Here are some hints and bonus to all problems:

BONUS. What is the minimum number of lines that we have to draw to cut every cell?

BONUS. Solve the problem when Dee can remove only a number of stones multiple of x, and when Dum can remove only a number of stones multiple of y

BONUS. Solve the problem when Dee can remove only a number of stones of the form k·x + r₁, and when Dum can remove only a number of stones of the form k·x + r₂

BONUS. Find the lexicographically smallest solution.

BONUS. Can the problem solved efficiently for a general graph? for a planar graph?

Problem A. PawnChess

Player A wins if the distance of his nearest pawn to the top of the board is less than or equal to the distance of the Player’s B nearest pawn to the bottom of the board (Note that you should only consider pawns that are not blocked by another pawns).

Problem B. The monster and the squirrel

After drawing the rays from the first vertex (n - 2) triangles are formed. The subsequent rays will generate independently sub-regions in these triangles. Let's analyse the triangle determined by vertices 1, i, i + 1, after drawing the rays from vertex i and (i + 1) the triangle will be divided into (n - i) + (i - 2) = n - 2 regions. Therefore the total number of convex regions is (n - 2)²

If the squirrel starts from the region that have 1 as a vertex, then she can go through each region of triangle (1, i, i + 1) once. That implies that the squirrel can collect all the walnuts in (n - 2)² jumps.

Problem C. The Big Race

Let D be the length of the racetrack, Since both athletes should tie .

Let M = lcm(B, W), then D = k·M + r. None of the athletes should give one step further, therefore r ≤ min{B - 1, W - 1, T} = X.

D must be greater than 0 and less than or equal to T so  - r / M < k ≤ (T - r) / M.

For r = 0, the number of valid racetracks is , and for r > 0 the number of racetracks is .

Iterating over all possible r, we can count the number of racetracks in which Willman and Bolt ties:

Note that . That means that for exactly M values of r.

We can count the number of values of r in which , and the values of r in which . Each of the remaining values v₁ - 1, v₁ - 2, ..., v₂ + 1 will appear exactly M times.

Problem D. Super M

Observation 1: Ari should teleport to one of the attacked cities (it doesn't worth going to a city that is not attacked since then she should go to one of the attacked cities)

Observation 2: The nodes visited by Ari will determine a sub-tree T of the original tree, this tree is unique and is determined by all the paths from two attacked cities.

Observation 3: If Ari had to return to the city from where she started, then the total distance would be 2e, where e is the number of edges of T, that is because she goes through each edge forward and backward

Observation 4: If Ari does not have to return to the starting city (the root of T), then the total distance is 2e - L, where L is the distance of the farthest node from the root

Observation 5: In order to get a minimum total distance, Ari should chose one diameter of the tree, and teleport to one of its leaves.

The problem is now transformed in finding the diameter of a tree that contains the smallest index for one of its leaves. Note that all diameters pass through the center of the tree, so we can find all the farthest nodes from the center...and [details omitted].

Problem E. BCPC

Let’s represent the reading and writing speeds of the students as points in a plane. Two students i, j are compatible if ri'·wj' - rj'·wi' > 0 this equation is identical to the cross product: (ri', wi') × (rj', wj′) > 0. Using this fact is easy to see that three students i, j, k are compatible if the triangle (r_i, w_i), (r_j, w_j), (r_k, w_k) contains the point (x, y). So the problem is reduced to count the number of triangles that contains the origin.

Let’s count the triangles that have two known vertices i and j (look at the picture above). It is easy to see that the third vertex should be inside the region S. So now we have to be able of counting points that are between two rays, that can be done using binary search (ordering the points first by slope and then by the distance to the origin).

Now given a point i, let’s count the triangles that have i as a vertex (look at the picture above again). We have to count the points that lie between the ray iO, and every other ray jO (the angle between iO and jO must be  ≤ 180).

Let S_j denote the number points that are between the rays OR and jO, then the number of triangles that have i as a vertex are . This summation can be calculated if we pre-calculate the cumulative sums of S_j.

The overall complexity is O(n·log(n)).

Codeforces Round #328 (Div. 2) will take place on October 31, 19:30 MSK, as usual Div. 1 participants can join out of competition.

Problem Setter: Morphy (Alei Reyes)

Coordinator: GlebsHP (Gleb Evstropov)

English to Russian translator: Delinur (Maria Belova)

Codeforces and Polygon: MikeMirzayanov (Mike Mirzayanov)

Hope you enjoy the problem set.

The score distribution will be announced later.

UPD. Score Distribution: 500 — 1000 — 1500 — 2000 — 3000

UPD. Problem Analysis is available

Congrats to the winners!

Div. 2

shamir0xe

lbn187

SuperLoser

Div. 1

uwi

NanoApe

Haghani