ch_egor's blog

By ch_egor, 5 years ago, translation, In English

Hi everybody!

These days Moscow is conducting the 4th International Olympiad of Metropolises that is an international competition for high school students from biggest cities and capitals all around the world. One of the disciplines of the competition is informatics. Rounds of the competition were prepared by the jury members invited from St. Petersburg, Minsk, Belgrade and Moscow olympiad scientific committee which you may know by Moscow team Olympiad, Open Olympiad in Informatics and Moscow Olympiad for young students (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516, 541, 545, 567).

Scientific Committee of the olympiad consists of: Chmel_Tolstiy, Jelena Hadži-Purić, Elena Andreeva, Zlobober, GlebsHP, andrewzta, meshanya.

The problems were developed by isaf27, cdkrot, manoprenko, GoToCoding, ch_egor, vintage_Vlad_Makeev, voidmax, grphil, malcolm under the guidance of GlebsHP and Zlobober.

Problems were adapted for codeforces by vintage_Vlad_Makeev and cdkrot, also thanks for MikeMirzayanov for systems codeforces and polygon, which was used to prepare problems of this olympiad. Also, thanks LHiC, voidmax and wrg0ababd for testing!

Good luck and high ratings for everybody!

Round will happen on Sep/04/2019 12:05 (Moscow time) and will last for two and half hours.

The round will consist of 8 problems and will be combined for both divisions. The round is rated for all participants.

P.S. We kindly ask everybody who knows problems of an onsite event not to participate in a round and not to discuss them in public, as this may be a subject for disqualification.

UPD1: Winners!

  1. jqdai0815
  2. gina0605
  3. never_giveup
  4. Radewoosh
  5. 244mhq
  6. cz_yixuanxu
  7. ko_osaga
  8. mango_lassi
  9. GoForIt
  10. ksun48

Editorial will be published soon.

UPD2: Editorial

Full text and comments »

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

By ch_egor, 5 years ago, translation, In English
Tutorial is loading...

(Developing and idea — vintage_Vlad_Makeev)

Tutorial is loading...

(Developing and idea — MikeMirzayanov)

Tutorial is loading...

(Developing — cdkrot, idea — jury)

Tutorial is loading...

(Developing — Sehnsucht, idea — Helen Andreeva)

Tutorial is loading...

(Developing and idea — VFeafanov)

Tutorial is loading...

(Developing and idea — Sender)

Tutorial is loading...

(Developing and idea — voidmax)

Full text and comments »

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

By ch_egor, 5 years ago, translation, In English

Hi everybody,

This Sunday there will be a Moscow programming competition for school students of grades from 6 to 9. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Open Olympiad, Moscow Team Olympiad and Metropolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507, 516).

Round will be held at 10:05 UTC on Saturday. You will be given 6 problems and 2 hours to solve them. Round will be rated for second division (rating below 2100). As usual, participants from the first division can participate in a contest out of competition.

Problems are prepared by vintage_Vlad_Makeev, grphil, cdkrot, VFeafanov, Sehnsucht, Sender, voidmax under my supervision.

Thanks to cdkrot for the round coordination and statement translation, and also thanks for MikeMirzayanov for systems Codeforces and Polygon, which was used to prepare problems of this olympiad.

Good luck everybody!

UPD1: Due to some last-minute changes, there will be 7 problems.

UPD2: Winners!

Div 2:

  1. Big_gold_date

  2. PinkieRabbit

  3. disposrestfuIIy

  4. Dobrobober

  5. szh0808

  6. prodakcin

  7. Argentina

  8. afedor

  9. bigelephant29

  10. Young25

Div.1 + Div.2:

  1. JustasK

  2. BigBag

  3. Egor.Lifar

  4. Big_gold_date

  5. waynetuinfor

  6. dreamoon_love_AA

  7. danya090699

  8. KrK

  9. Farhod

  10. PinkieRabbit

UPD3: Editorial

Full text and comments »

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

By ch_egor, 5 years ago, translation, In English

Hi everybody,

This Sunday there will be a 16th Moscow Team Olympiad, high school students competition based in Moscow that is an elimination contest for All-Russian Team Olympiad. This contest is prepared by Moscow Olympiad Scientific Committee that you may know by Moscow Open Olympiad, Moscow Olympiad for Young Students and Metropolises Olympiad (rounds 327, 342, 345, 376, 401, 433, 441, 466, 469, 507).

Round will be held at 10:05 UTC on Sunday and will last for 2 hours. Each division will have 6 problems.

Problems are prepared vintage_Vlad_Makeev, Glebodin, Andreikkaa, qoo2p5, mingaleg, Flyrise, cdkrot, achulkov2, grphil, Sehnsucht, Aphanasiy, Sender, DebNatkh, GreenGrape under my supervision with great help of GlebsHP, meshanya, Endagorion, Zlobober and Helen Andreeva.

Thanks to cdkrot for the round coordination and statement translation, and also thanks for MikeMirzayanov for systems codeforces and polygon, which was used to prepare problems of this olympiad.

Good luck everybody!

UPD1: The scoring distribution will be:

500 — 10001000 — 1500 — 2000 — 2500 for div. 1.

500 — 1000 — 1500 — 20002000 — 2500 for div. 2.

UPD2: Editorial

UPD3: Winners:

Div. 1:

  1. mnbvmar
  2. bmerry
  3. jcvb
  4. TLEwpdus
  5. WA_TLE

Div. 2:

  1. Ebola_Emperor
  2. Orange_User
  3. orbitingfIea
  4. little_waxberry
  5. fnch

Full text and comments »

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

By ch_egor, 6 years ago, translation, In English
Tutorial is loading...

(Developing — vintage_Vlad_Makeev, ch_egor, V--o_o--V, demon1999)

Tutorial is loading...

(Developing — ch_egor)

Tutorial is loading...

(Developing — ch_egor)

Tutorial is loading...

(Developing — halin.george)

Tutorial is loading...

(Developing — Sehnsucht)

Tutorial is loading...

(Developing — cdkrot, ch_egor)

Full text and comments »

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

By ch_egor, 6 years ago, translation, In English

Hello everybody!

Tomorrow in unusual time round will be held using problemset of Moscow programming competition for school students of grades from 6 to 9. Do not be tricked by the age range of the participants, Moscow jury always tries its best to select interesting problems of various topics. Problems were developed by halin.george, Sehnsucht, cdkrot, vintage_Vlad_Makeev and ch_egor.

Thanks to MikeMirzayanov for an excellent platform Codeforces for contests and an excellent platform Polygon, which greatly simplifies the preparation of contests.

Thanks to V--o_o--V for reducing the statements and translating them into english.

Hope to see you in the standings!

UPD1: Scoring 500-1250-1250-1500-2000-2750

UPD2: Our problemsetters are tired because of olympiad, so editorial will be a bit later. We apologize for it.

Winners:

Division 2:

  1. zzs_dasc

  2. Kataoka_Yuuki

  3. AkiLotus

  4. tshil

  5. WatchClannad

Division 1 + 2 (unofficial):

  1. uwi

  2. zzs_dasc

  3. fmota

  4. Kataoka_Yuuki

  5. eddy1021

UPD3: Editorial

Full text and comments »

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

By ch_egor, 8 years ago, translation, In English

If you notice typos or errors, please send a private message.

Div2A Free Ice Cream

Author: cdkrot
Developer: ch_egor

You just needed to implement the actions described in statement.

If you solution failed, then you probably forgot to use 64-bit integers or made some small mistake.

Correct solution:

C++ code
Python code

Div2B Little Robber Girl's Zoo

Author: ch_egor
Developer: ch_egor

We need to sort an array with strange operations — namely, to swap elements with even and odd indices in subarray of even length. Note that we can change the 2 neighboring elements, simply doing our exchange action for subarray of length 2 containing these elements. Also, note that n ≤ 100, and it is permission to do 20 000 actions, therefore, we can write any quadratic sort, which changes the neighboring elements in each iteration (bubble sort for example).
Complexity O(n2)

C++ code
Python code

Bonus: Is anyone able to search the shortest solution of this problem? If yes, what complexity?

Div2C Robbers' watch/Div1A Robbers' watch

Author: cdkrot
Developer: themikemikovi4

In this problem we use the septimal number system. It is a very important limitation. Let's count how many digits are showed on the watch display and call it cnt. If cnt more than 7, the answer is clearly 0 (because of pigeonhole principle). If cnt is not greater than 7, then you can just bruteforces all cases.
Depending on the implementation it will be O(BASEBASEBASE), O(BASEBASE) or O(BASEBASE!), where BASE = 7. Actually the most simple implementation is just to cycle between all posible hour:minute combinations and check them.
In the worst case, it will work in O(BASEBASEBASE).

C++ code
Python code

Bonus: Suppose the base is not fixed. Solve a problem with n ≤ 109, m ≤ 109, BASE ≤ 109. Can you do it in ?

Div2D Kay and Snowflake/Div1B Kay and Snowflake

Author: cdkrot
Developers: ch_egor, cdkrot

There are many possible approaches.

Solution by cdkrot:

Look at the all candidates for the centroid of the vertices v subtree. The size of centroid subtree must be at least of the vertex v subtree size. (If it isn't, then after cutting the upper part will have too big size)

Choose the vertex with the smallest subtree size satisfying the constraint above. Let's prove, that this vertex is centroid indeed. If it isn't, then after cutting some part will have subtree size greater than of subtree size of query vertex. It isn't upper part (because of constraint above), it is one of our sons. Ouch, it's subtree less than of selected vertex, and it's still greater than of subtree size of query vertex. Contradiction.

So we find a centroid.
We write the euler tour of tree and we will use a 2D segment tree in order to search for a vertex quickly.
Complexity

C++ code

You can consider all answers by one in dfs using this idea. Use std::set for pair (subtree size, vertex number) and at each vertex merge sets obtained from children. (Also known as "merging sets" idea)
Thus we get the answers for all vertex and we need only output answers for queries.
Complexity

C++ code

Solution by ch_egor:
Solve it for all subtrees. We can solve the problem for some subtree, after solving the problem for all of it's children. Let's choose the heaviest child. Note that the centroid of the child after a certain lifting goes into our centroid. Let's model the lifting.
Thus we get the answers for all vertex and we need only output answers for queries.
Complexity O(n + q)

C++ code

Div2E Optimal Point/Div1C Optimal Point

Author: cdkrot
Developer: cdkrot

Let's say few words about ternary search. It works correctly, but too slow.
It's complexity is , where n = 105, and v = 1018.
Don't use it.

Solution.
1) Let's make binary search on answer
2) Consider areas of "good" points (with dist  ≤ mid) for each source point.
3) Intersect those areas and check for solution.

This area can be decsribed by following inequalities:
(You can achieve them if you expand modules in inequality "manhattan distance <= const")

.. ≤ x + y + z ≤ ..


.. ≤  - x + y + z ≤ ..


.. ≤ x - y + z ≤ ..


.. ≤ x + y - z ≤ ..


.. denote some constants.

If you intersect set of such system, you will get system of the same form, so let's learn how to solve such system.

Let's replace some variables:

a =  - x + y + z


b = x - y + z


c = x + y - z


Then:

x + y + z = a + b + c


x = (b + c) / 2


y = (a + c) / 2


z = (a + b) / 2


Now the system transforms into:

.. ≤ a ≤ ..


.. ≤ b ≤ ..


.. ≤ c ≤ ..


.. ≤ a + b + c ≤ ..


We need to check if the system has solution in integers, also the numbers a, b, c must be of the same parity (have equal remainder after division by 2). (This is required for x, y, z to be integers too)

Let's get rid of parity constraint. Bruteforce the parity of a, b, c (two cases)

Make following replacement: a = 2a' + r, b = 2b' + r, c = 2c' + r, where r = 0 or r = 1. Substitute in equations above, simplify, and gain the same system for a', b', c' without parity constraint.

And now the system can be solved greedy (At first set a, b, c with minimum, and then raise slowly if necessary).

Total complexity is .

C++ code

Bonus. This task can be solved in a lot of modifications, for example euclidian distance instead of manhattan, 2d instead of 3d, floats instead of integers. How to solve this varations?

Div1D Kay and Eternity

Authors: platypus179, Endagorion
Developer: platypus179

Let's solve this problem with scanline. Go through all rows from left to right and maintain the array in which in j index we will store the number of points in a square with bottom left coordinate (i, j), where i is current row of scanline.

This takes O(MAXCORD2) time. Note that the set of squares that contain some of the shaded points is not very large, namely — if the point has coordinates (x, y), then the set of left bottom corners of square is defined as {(a, b)|x - k + 1 <  = a <  = x, y - k + 1 <  = b <  = y}. Let's consider each point (x, y) as the 2 events:
Add one to the all elements with indexes from y - k + 1 to y on the row x - k + 1 and take one at the same interval on the row x + 1. How to calculate answer? Suppose we update the value of a cell on the row a, and before it was updated the value x on the row b. Let add to the answer for the number of squares containing x points value a - b. We can implement the addition of the segment directly and have O(nk) for processing all the events that fit in time limit. To get rid of O(MAXCORD) memory, we need to write all interested in the coordinates before processing events (them no more than nk) and reduce the coordinates in the events. It takes time and O(nk) memory. Now we can execute the previous point in O(nk) memory.
Complexity is time and O(nk) memory.

C++ code

Bonus: time and O(n) memory.

C++ code

Div1E Travelling Through the Snow Queen's Kingdom

Authors: cdkrot, GlebsHP
Developers: ch_egor, cdkrot

Unfortunately, due to my, cdkrot, failure, it was possible to get Ac with O(nm) solution, I apologise for that.

We propose following solution:
Let's solve task with divide & conquer. At first let's lift l to the first index, where s was mentioned And lower the r to the last index, where t was mentioned. This will not affect answers, but will make implementation much more easy.

Let's look on all queries. For each query consider it's location relative to centre of edges array. If it's stricly on the left half or on the right half, then solve recursively (You need to implement function like solve(requests, l, r)).

How to answer on query, if it contains the centre? Let's precalculate two dp's:

dpr[i] =  bitset of vertices you can from to the vi or ui with l = m and r = i.

dpl[i] =  bitset of vertices you can go to starting from vi or ui with l = i and r = m - 1

vi and ui are vertices of i'th edge.

Using this dp the answer is yes if and ony if dpl[l][u] = true and dpr[r][u] = true for some u.

All above can be implemented using bitwise operations.
So the time is

C++ code

Full text and comments »

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