Автор BledDest, 6 лет назад, перевод, По-русски

Привет, Codeforces!

22 марта в 9:05 MSK начнётся Educational Codeforces Round 40.

Это будет особенный раунд — он будет проводиться в сотрудничестве с Hello India x Russia Programming Bootcamp и при поддержке банка ВТБ.

Более 100 участников сборов в Индии будут принимать участие в этом раунде совместно с участниками с Codeforces.

Банк ВТБ был основан в 1990 году, и он и его дочерние организации (Группа ВТБ) составляют одну из лидирующих финансовых групп в России, предоставляя различные финансовые услуги и товары в России, СНГ и некоторых странах Европы, Северной Америки, Азии и Африки. Группа ВТБ включает более чем 30 банков и финансовых организаций более чем в 20 странах.

В этом раунде будет 9 задач, на решение которых отводится 3 часа. Авторы задач — GlebsHP, vovuh, awoo, Xahandd и я.

Удачи всем участникам! Надеемся, что каждый найдёт для себя что-то новое и интересное в этом контесте.

UPD: Разбор задач.

Поздравляем победителей:

Место Участник Задач решено Штраф
1 fatego 9 366
2 black_horse2014 9 513
3 mjhun 9 524
4 BlackPuppy 9 663
5 l_love_chtholly 8 382

Поздравляем лучших взломщиков:

Место Участник Число взломов
1 Linkus 229:-17
2 step_by_step 115:-20
3 Aemon 96:-13
4 applese 28:-2
5 im0qianqian 27:-2
Было сделано 1341 успешных и 1475 неудачных взломов.

И, наконец, поздравляем людей, отправивших первое полное решение по задаче:

Задача Участник Штраф
A 300iq 0:01
B gisp_zjz 0:04
C rhs0266 0:12
D szbszbszb 0:10
E 999qs999 0:21
F fatego 0:26
G Magolor 0:11
H fatego 0:18
I wakaka 0:31

  • Проголосовать: нравится
  • +184
  • Проголосовать: не нравится

»
6 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Great opportunity for Indian programmers, Best of luck guyz!

»
6 лет назад, # |
  Проголосовать: нравится +101 Проголосовать: не нравится

I wanted to make a suggestion. Since the educational rounds tend to have weak pretests to promote hacking, is it possible that the leaderboard is not acm style? The combination of well demarked difficulties (F>E>D..>A), weak pretests and acm style ranking is killer. People doing B C D with A getting hacked (clearly tougher) get ranked below A B C ers. This is unfair in my opinion.

»
6 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

I really missed rated codeforces contests :D

»
6 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Special start time, Special contest duration, Special number of problems, Special contest !!!

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

plenty of problems !!!

»
6 лет назад, # |
  Проголосовать: нравится -52 Проголосовать: не нравится

Is It Rated?

»
6 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

This should have been a good time for Chinese programmers, but i am still at school that time :(

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

Тот случай, когда утро начинается не с кофе)

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

In India it is at 11:35am,I m leaving my college classes tomorrow especially for this round!

»
6 лет назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

This is my first time seeing a rated contest with 9 problems! Hope i can handle it.

»
6 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Damn I wish this could be my first contest here but it's 2 hours too early for me :<

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

9 problems in Educational Round. Codeforces is on fire!!

»
6 лет назад, # |
  Проголосовать: нравится +46 Проголосовать: не нравится

I hope problem statements will be short, otherwise it would be new reading book named "Educational Round 40" by BledDest.
Btw Happy Novruz for all guys.

»
6 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Wish all pupils to become specialists

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

It's a good time for Chinese student

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +41 Проголосовать: не нравится

Highest no. of problems ever for a rated contest?

»
6 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

The problems are still sorted in increasing order of difficulty right?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Hopefully they will be because i don't want to read all the problems and not be sure which one is harder.

»
6 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

As Contest will contains 9 problems, should i consider them sorted or not ?

»
6 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Why is the contest at such an unusual time on a week day? it would be nice if it could be shifted a couple of hours.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I hope the round will be steep.

»
6 лет назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

9 Problems? I wonder the actual rule of the contest...

UPD: Maybe I'm not very familiar with educational rounds...Seems that it's ACM-ICPC rules when I viewed the past educational rounds...

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Great time for Chinese workers!(Maybe not for students :P

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

OMG 9 problems???3 hours???

is it something between ACM and Olympiad contests?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good luck everyone!

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Ну что, пацаны? Аниме? 9 задач?

»
6 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Wow, 9 problems! Just like ACM.

»
6 лет назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

Дизлайкните пж чтобы вклад опустить.

»
6 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

For F, are we guaranteed that obstacles of the same kind do not intersect?

i.e. would this be allowed?

2 5

1 2 4

1 3 5

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

For problem E, on the first sample case, why can't we take 3ml from the first tap and 5.4ml from the second tap? We get 3*10 + 5.4*150 = 840, 840/8.4 = 100

»
6 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Never tried to output long double using printf, and today had to. Since I was trying to avoid %Lf specifier (due to %Ld warnings etc.), I thought that %I64f might work, and it worked! However, it works on my local machine, and not in the judge (Got WA#1 using GNU G++11), so in the end I used %Lf. Does anyone know what is the problem with %I64f?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It seems that %Lf dosen't work before G++14 on MinGW. And %lf, %f also don't work...It seems that only cout works...

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In fact there're 3 Examples in problem B :)

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What was test 20 on G? :(

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What was testcase 8 on D?

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

My solution to problem B has been hacked

For test 8

aaaaaaaa

My answer is 4. What's wrong???

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Was segment tree + binary search for G TLE'ing for everyone? :/

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve C?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    You need to find the differences b/w the values of two consecutive cells. There should be only two difference values : 1. '1' for any two consecutive elements in a row. 2. 'y'(no of columns) for any two consecutive elements in a column(one above other).

    There is no constraint on number of rows(x). So you can output 1e9 for each case. Note : Also you need to check the border contraints.

    • »
      »
      »
      6 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Also you need to check the border constraints What are these border constraints. I see some codes checking something like (a[i]-1)/y != (a[i-1]-1)/y then print NO. Where does it come from? I feel so stupid

      • »
        »
        »
        »
        6 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        (a[i]-1)/y represents row in which a[i] lies.[e.g. let y=4 and a[i]=5, then (5-1)/4=1 means 5 belongs to row 1(0 indexed)]. (a[i]-1)/y != (a[i-1]-1)/y this condition can be used if a[i] and a[i-1] differ by 1. It basically checks whether a[i] and a[i-1] differing by 1 belong same row or not.

        • »
          »
          »
          »
          »
          6 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

          I thought that A[i][j]=y*(i-1)+j where j belongs to [1...x], so that constraint didn't make sense, but now everything is clear, since j is in [1...y] Thank you

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Чем отличаются тесты 7 и 8 в задаче С?

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

How to solve Problem F?

I think it can be solved by matrix multiplication, but I can't come up with a solution. Any ideas?

Btw, when will the editorial be published?

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    Let's assume for a moment that there are no obstacles at all. If a vector (v_{1}, v_{2}, v_{3}) represents a number of paths ending in a cell (i, n) for some n, then (v_{1} + v_{2}, v_{1} + v_{2} + v_{3}, v_{3} + v_{2}) does the same for n+1. For a large n we can compute the vector efficiently using a matrix multiplication.

    Let's get back to the original problem. The board can be separated with vertical lines into O(n) rectangles of two kinds:

    • rectangles with no obstacles,

    • rectangles with at least one row fully occupied by some obstacle.

    The first case can be solved using the algorithm from section 1. The solution for the latest one requires a straightforward cases analysis and can be done in logarithmic or constant time depending on a case.

»
6 лет назад, # |
  Проголосовать: нравится +68 Проголосовать: не нравится

Good job l_love_chthoIIy, l_love_chtholly, I_AM_CHTHOLLY, IamChtholly in the first run! Viva Chtholly! :D

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve H?

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +33 Проголосовать: не нравится

    【这题可能有很多方法】 考虑枚举lca的深度(k)以及两点的深度(i,j)。 写出式子后发现可以发现枚举了k和j的时候,i的可行取值是一个后缀。 于是先加再乘就好了。

    [This question may have many methods] Consider enumerating the depth of lca (k) and the depth of two points (i, j). After writing the formula and finding after enumerates k and j, the feasible value of i is a suffix. So first plus and then multiply.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

can someone explain solution of problem G??!!

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Binary search and greedy. Let's binary search for answer(let's call it x). Now start from beginning, and if sum in range [max(1, i — r), min(n, i + r)] is less than x, increase min(n, i + r) value by x — sum. Now just check if sum of increases <= k.

»
6 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Hacks, hacks everywhere!!!

»
6 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Shows Solved 4 out of 9

ss

But I solved only 2.

ssa

What's wrong???

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why brute force can pass problem I?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    bitset is very fast. but i think fft is better.

    • »
      »
      »
      6 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      The most naive brute force without bitset or FFT can pass Problem I.It takes about 3.5s on the largest data that the lengths of two strings are 125000 and 62500,although it will take about 4e9 operations in total.

»
6 лет назад, # |
Rev. 4   Проголосовать: нравится -10 Проголосовать: не нравится

................

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Good problems. Thank you for interesting tasks.

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Why there're North Korean contestants here , like blackhorse_2014 and RNS_RMH??

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Does hack have points ?

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve problem E?

  • »
    »
    6 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

    First split all taps into "cold" with t_i < T, "warm" with t_i > T, and "ideal" with t_i = T. Note that you should always turn all "ideal" taps on completely since they do not change the temperature but contribute to the entire volume.

    Then you have to balance "cold" and "warm" taps so that they kind of cancel out. Note that if you have at least one "cold" and one "warm" tap unused, you can increase total volume keeping the temperature constant by adding some volumes from both of the taps. This means that you can either use all "cold" taps, and then compensate with some "warm" taps, or use all "warm" taps and compensate temperature with some "cold" taps — depending on total temperature coming from all taps on.

    As for compensation, I guess you can use a greedy approach — sort all the "compensation" taps in the order of |t_i — T| difference, and then turn them on one by one until you reach the desired temperature. It is easy to show that it is always better to turn the "less temperature-influencing" tap on first.

»
6 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Solutions using Floyd Warshall Algorithm are accepted in D, HOW ?? O(10^9)

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I don't understand how the penalty is computed. I solved ABCDE.

My submission times were: A 00:05 B 00:15 C 00:42 D 01:14 E 02:12

Codeforces gave me a penalty of 268, which is 5 + 15 + 42 + 74 + 132, so that would normally be correct. However, I actually submitted E twice. The first time I got a Wrong Answer on test 1. So then shouldn't my actual penalty be 268 + 20 = 288?

  • »
    »
    6 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    Codeforces ignores penalty from compilation error and WA on test 1 verdicts .

»
6 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

The author of this blog is asleep, I have no way to update it, sorry. It will be updated in a couple hours.

Here is the editorial.


Разбор задач

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Low level screencast on my alternate account just for fun. Feedback and comments are welcome and encouraged :)

»
6 лет назад, # |
Rev. 2   Проголосовать: нравится +79 Проголосовать: не нравится

Will this round have the ranklist and the hacker ranklist? :P

They have been disappeared since Round 37 :(

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Wow I got the first blood of E!

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

.