Alekhine's blog

By Alekhine, 2 weeks ago, In English,

Greetings Codeforces Community! We bring you the July Long Challenge 2019. Brace yourself for 10 intense days of non-stop coding challenge starting on 5th July.

All programmers across the globe are welcome to participate. Problems are available in English, Hindi, Bengali, Russian, Mandarin and Vietnamese.

If you have some original and interesting problem ideas, and want them to be used in CodeChef's contests, you can share them with our admins here: www.codechef.com/problemsetting/new-ideas

Joining me on the problem setting panel are:

Hope you enjoy the problems!

Read more »

 
 
 
 
  • Vote: I like it
  • +72
  • Vote: I do not like it

By Alekhine, history, 3 months ago, In English,

CodeChef May Challenge will start in ~63h ( May 3 15:00 IST )

You will have 10 days to solve 8 puzzles. This time the problems are more accessible, so I expect a fierce battle in the approximation problem. See you in the ranklist!

The puzzles were cooked by

  • Setters: Danya Smelskiy (smelskiy), Lewin Gan (lg5293), Abhinav Jain (iamabjain), Vivek Chauhan (vivek_1998299), Xusheng Wang (wxs02wxs0103), Ashish Gupta (ashishgup), Vinay Katare (vinay_katare), Misha (mishaprigara), Alei Reyes (alei).
  • Testers: Arash (silversoul), Michael Nematollahi (watcher)
  • Editorialist: Alexander Kulkov (melfice)
  • Statement Verifier: Jakub Safin (xellos0)
  • Translators: Fedor Korobeinikov (gomelfk), Hu Zecong (huzecong), Team VNOI (songuku95), Mohammad Solaiman (solaimanope), Akash Srivastava (devils_code)

PS. If you are interested in setting problems for CodeChef, send your ideas to problems@codechef.com, or via this form. Alekhine reviews the odd proposals, and Alexey Shirov Zayakin the even ones.

Read more »

 
 
 
 
  • Vote: I like it
  • +52
  • Vote: I do not like it

By Alekhine, 6 months ago, In English,

CodeChef January Cook-Off starts in ~72h (Sunday, 20th January, 2019 at 21:30 IST). As ussual you will have 5 puzzles to solve in 150 minutes.

The character of the contest is Ada — the most intuitive girl I have ever met.

I challenge top coders to get full score in topcoder time.

By the way, the contest clash with the north regional junior chess championship of my country, so to me seems like a notorious coincidence.

good fun and have luck!

Contest log:

  • -24:00:00. Pran found a corner case on ADAROKS that I didn't contemplate, We fixed our solutions ad added more data.
  • 00:05:45. 28 acs for ADASCOOL in div1 and 14 in div2, Atreus is leading in div1.
  • 00:15:00. Div2 users found the cakewalk problem, stefdasca is leading in div2. In div1 lhic solved ADAMTR, his solution is similar to tester, I used 2-SAT as a blackbox.
  • 00:40:00. Internal Server Error :( now we know they upgraded their nginx to 1.4.7.
  • 00:43:00. CodeChef is up again, moreover Saiphani724 solved ADAMTR and is leading in div2. Pran predicts 4 perfect scores in div1, I predict 10.
  • 01:00:00. KrK solved ADAPWNS, now he is first and lhic is second.
  • 01:12:00. lhic aced ADAFUN, but he is still second because he didn't solved ADAPWNS, the problem is a trie dp, so its kind of standard.
  • 01:20:00. I noticed that my countrymate The_Blitz is participating in div2. It seems that having a chess handle is not helping him in the contest.
  • 01:32:00. uwi only solved 2 problems, did he gave up the contest after the server down?
  • 01:40:00. yashChandnani solved ADAFUN, now he is first!
  • 01:44:00. raveman solved ADAROKS, the top of the scoreboard in div1 is changing a lot!
  • 01:54:00. KrK solved ADAFUN and took the lead again, however I think raveman will winn, because he already solved ADAROKS which is harder.
  • 02:10:00. uwi is still on board it seems he had a hard time with ADAROKS, his solution fails on a case added by the tester (uwi, complain with pran), also I noticed that the educational hero pikmike is taking part in the contest, he managed to solve ADAPWNS, and is in the top 20.
  • 02:21:00. I bet raveman will winn, Pran bets on lhic.
  • 02:30:00. No participant got perfect score. Congrats to the winners!

Div 1:

 KrK

 lhic

 raveman

Div 2:

 Saiphani724

 andrew_ucla

 stefdasca

I'll add some hints for solutions in my blog: https://aleigorithms.wordpress.com/2019/01/17/codechef-january-cook-off-2019/

Read more »

 
 
 
 
  • Vote: I like it
  • +135
  • Vote: I do not like it

By Alekhine, history, 7 months ago, In English,

2018 was a semiprime year with great contests and some notorious coincidences.

From the problems that I proposed, my favourite was HAMEL, I invented it by mixing the definitions of eulerian and hamiltonian paths, the deterministic solution involves matroids, however many people solved it with randomization. Another problem of my hand that I liked was PWRTREE because it has a nice combinatorial solution by interpreting the digraph as an elimination tournament.

I didn't took part in CodeForces contests this year, but while training for snackdown I found an interesting problem in the Gym about constructing a maximum matching of line graphs.

Read more »

 
 
 
 
  • Vote: I like it
  • +99
  • Vote: I do not like it

By Alekhine, history, 7 months ago, In English,

SnackDown 2018 elimination round starts in ~8 minutes. Top 300 get T-shirts

Let's discuss the problems after the contest!

Read more »

 
 
 
 
  • Vote: I like it
  • +69
  • Vote: I do not like it

By Alekhine, history, 9 months ago, In English,

CodeChef October Mega-Cook Off 2018 starts in ~48h, (sunday 21 11:00 PET).

You will have 2.5h to solve 5 puzzles. My last contest was April Cook-off, ussually I only set one contest per year, so this year I broke the curse!

The character of the contest is Chef Ada, she is the most intuitive girl I have ever met. Sometimes she can solve a problem before I finish telling the statement!

Hope you enjoy the problems. See you in the ranklist!

Upd. This time there will be also statements in spanish. Spanish is a complex language, let's hope I didn't miss any accent mark:)

Contest log:

  • 11:08 many WAs in PUMPWAT. maddythakker takes the lead in div2.

  • 11:13 megabidoof ACed PUMPWAT, even tester had a couple of WAs in this problem

  • 11:24 kingofnumbers frightened me, numbers of equal height in the tests of PUMPWAT? false alarm, only the sample had a repeated element. Actually in the original version there was hills with equal height, but I decided to made the problem easier, and forgot to fix sample input.

  • 11:30 I just noticed zemen is in div2! with two div1 problems solved, he could be first in div1 in this moment.

  • 11:49 user:AlexDmitriev solved PWRTREE, he is still first

  • 12:00 zemen finally solved PWRTREE in div2

  • 12:31 KrK and uwi solving only two problems in a cc contest after 90 minutes? that is not often seen

  • 12:45 AlexDmitriev solved ADASHOP, IMHO it took him too much time, there are no submissions for ADAFARM yet.

  • 12:56 The blue coder (3 stars) zemen :) got perfect score in div2, wondering if he could get perfect score in div1.

  • 13:22 hatter from belarus solved ADASHOP skipping PWRTREE, that was an wise decision, I think PWRTREE is harder. Now he is 4th in div2.

  • 13:27 ADAFARM has only one submission, and unfortunately it is RE (sorry Golovanov399)

  • 13:35 Congrats to the winners!

Div 1.

  1. AlexDmitriev

  2. isaf27

  3. nuip

Div 2.

  1. zemen

  2. andrey_efremov

  3. Januzaj497

Read more »

 
 
 
 
  • Vote: I like it
  • +99
  • Vote: I do not like it

By Alekhine, history, 9 months ago, In English,

IPSC starts in ~12h (6 October 2018, 15:00 UTC).

Let's discuss the problems after the contest!

Read more »

 
 
 
 
  • Vote: I like it
  • +32
  • Vote: I do not like it

By Alekhine, history, 11 months ago, In English,

CodeJam World Finals starts in less than 15h (Friday 11:30 PET).

What are your predictions?

Let's discuss the problems after the contest!

Read more »

 
 
 
 
  • Vote: I like it
  • +71
  • Vote: I do not like it

By Alekhine, history, 11 months ago, In English,

HackerCup R2 starts in ~24h (August 04 12:00 PET).

Let's discuss the problems after the contest!

Read more »

 
 
 
 
  • Vote: I like it
  • +22
  • Vote: I do not like it

By Alekhine, history, 12 months ago, In English,

The last online round of topcoder starts in less than 1h.

14 top coders qualify to the finals.

Let's discuss the problems after the contest!

Read more »

 
 
 
 
  • Vote: I like it
  • +54
  • Vote: I do not like it

By Alekhine, history, 12 months ago, In English,

HackerCup R1 starts in ~24h (July 21 12:00 PET).

Let's discuss the problems after the contest!

Read more »

 
 
 
 
  • Vote: I like it
  • +114
  • Vote: I do not like it

By Alekhine, history, 13 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it
  • +55
  • Vote: I do not like it

By Alekhine, history, 14 months ago, In English,

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

Let's discuss the problems after the contest!

Read more »

 
 
 
 
  • Vote: I like it
  • +236
  • Vote: I do not like it

By Alekhine, history, 15 months ago, In English,

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

 inYourdreaM  owly  stark_arya

Read more »

 
 
 
 
  • Vote: I like it
  • +44
  • Vote: I do not like it

By Alekhine, history, 16 months ago, In English,

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

Read more »

 
 
 
 
  • Vote: I like it
  • +44
  • Vote: I do not like it

By Alekhine, history, 19 months ago, In English,

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.

Read more »

 
 
 
 
  • Vote: I like it
  • +86
  • Vote: I do not like it

By Alekhine, history, 2 years ago, In English,

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 alei
  • Primary Tester and editorialist: Hussain Kara Fallah Deadwing
  • Secondary Tester: Kacper Walentynowicz Miyukine
  • 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.

Read more »

 
 
 
 
  • Vote: I like it
  • +38
  • Vote: I do not like it

By Alekhine, history, 3 years ago, In English,

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: alei (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 Miyukine 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:

Alice

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

Tweedle-Dee and Tweedle-Dum

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 + r1, and when Dum can remove only a number of stones of the form k·x + r2

Math Hatter

BONUS. Find the lexicographically smallest solution.

Mock Turtle
Queen of Hearts

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

Read more »

 
 
 
 
  • Vote: I like it
  • +68
  • Vote: I do not like it

By Alekhine, history, 4 years ago, In English,

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)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)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 v1 - 1, v1 - 2, ..., v2 + 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 riwj' - rjwi' > 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 (ri, wi), (rj, wj), (rk, wk) 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 Sj 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 Sj.

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

Read more »

 
 
 
 
  • Vote: I like it
  • +83
  • Vote: I do not like it

By Alekhine, history, 4 years ago, In English,

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: galois (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

Read more »

 
 
 
 
  • Vote: I like it
  • +523
  • Vote: I do not like it