Educational Codeforces Round 40 [Rated for Div. 2]
By BledDest, 7 years ago, In English

Hello Codeforces!

On March 22, 9:05 MSK Educational Codeforces Round 40 will start. This will be a special round, branded by VTB and the Hello India x Russia Programming Bootcamp.

This round is held in collaboration with Hello India x Russia Programming Bootcamp and supported by the premier and international bank VTB, based in Russia.

Over 100 participants from the India side of the boot camp will be competing as individuals in this special online round!

JSC VTB Bank was founded in 1990, and its subsidiary banks and financial organisations (VTB Group or the Group) are a leading Russian financial group, offering a wide range of financial and banking services and products in Russia, the CIS, and a number of countries in Europe, North America, Asia, and Africa. VTB Group has the most extensive international network among all Russian banks, including more than 30 banks and financial companies in more than 20 countries.

The round will contain 9 problems, and you will have 3 hours to solve them. Problem authors are GlebsHP, vovuh, awoo, Xahandd and me.

We wish all of the participants good luck! Hope all of you will find something interesting in this contest.

UPD: Editorial is here.

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 fatego 9 366
2 black_horse2014 9 513
3 mjhun 9 524
4 BlackPuppy 9 663
5 l_love_chtholly 8 382

Congratulations to the best hackers:

Rank Competitor Hack Count
1 Linkus 229:-17
2 step_by_step 115:-20
3 Aemon 96:-13
4 applese 28:-2
5 im0qianqian 27:-2
1341 successful hacks and 1475 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
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

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

Comments Comments (124)
| Write comment?
»
7 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Great opportunity for Indian programmers, Best of luck guyz!

→ Reply
»
7 years ago, # |
  Vote: I like it +101 Vote: I do not like it

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.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It may be better if it is an ACM-style contest, it is completely an ACM style one.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the beauty of ACM-Style is ::

    1 — problems are not sorted

    2 — problems are equals in points ( result is the number of solved problems)

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't mind equal in points and penalty/time system, but then I think full feedback is necessary.

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

    I think Educational rounds should be unrated, according to reasons you have mentioned.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +18 Vote: I do not like it

      No, rated educational rounds has led to a huge boost in participation which is also good in its own way.

      → Reply
»
7 years ago, # |
  Vote: I like it +11 Vote: I do not like it

I really missed rated codeforces contests :D

→ Reply
»
7 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

plenty of problems !!!

→ Reply
»
7 years ago, # |
  Vote: I like it -52 Vote: I do not like it

Is It Rated?

→ Reply
»
7 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    Same buddy :) CF is LOVE

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Tomorrow my class coordinator is literally going to freak out due to my short attendance

      FightingForAttendance ;)

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Same Budddy. My college also have attendance criteria of 75 %. i HAVE HARDLY 40%. iT SUCKS.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 2   Vote: I like it +8 Vote: I do not like it

          Brother I have noticed now that I have added you in my friendlist 2-3 months ago . And I m learning a lot from your codes I think it's totally a coincident we just talked randomly in comments

          → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Me too!!

    → Reply
»
7 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it +46 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Wish all pupils to become specialists

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's a good time for Chinese student

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +41 Vote: I do not like it

Highest no. of problems ever for a rated contest?

→ Reply
»
7 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    → Reply
»
7 years ago, # |
  Vote: I like it +22 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Probably partially sorted if I had to guess. Wouldn't be surprised if C is harder than D, or E is harder than F, etc.

    → Reply
»
7 years ago, # |
  Vote: I like it +15 Vote: I do not like it

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.

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope the round will be steep.

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    So you are saying that students actually pay attention to lectures?

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I mean...may not have time to do it,especially for middle school students (poi

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

OMG 9 problems???3 hours???

is it something between ACM and Olympiad contests?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck everyone!

→ Reply
»
7 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Wow, 9 problems! Just like ACM.

→ Reply
»
7 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Some cells may be blocked by multiple obstacles.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Thanks, I misunderstood the meaning of cell for a second and accidentally thought it meant column.

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Second line contains max volumes, third line contains temperatures. So temperatures are 50 and 150, not 10 and 150.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thank you, should read input format next time :D

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        I also intuitively read the input like that :)

        → Reply
»
7 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What was test 20 on G? :(

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What was testcase 8 on D?

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

My solution to problem B has been hacked

For test 8

aaaaaaaa

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

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    There is no need for a segment tree. It can be done with sliding window technique. That will save a logn factor

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Yes I realized that later, thanks anyway.

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          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

          → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

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?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I know. But I just don't know how to use matrix multiplication. Can you explain? Thanks in advance.

      → Reply
»
7 years ago, # |
  Vote: I like it +68 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve H?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +33 Vote: I do not like it

    【这题可能有很多方法】 考虑枚举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.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain solution of problem G??!!

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
»
7 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Hacks, hacks everywhere!!!

→ Reply
»
7 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Shows Solved 4 out of 9

ss

But I solved only 2.

ssa

What's wrong???

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why brute force can pass problem I?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      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.

      → Reply
»
7 years ago, # |
← Rev. 4   Vote: I like it -10 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Where do you see that judge answer is 5?

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good problems. Thank you for interesting tasks.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does hack have points ?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem E?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +12 Vote: I do not like it

    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.

    → Reply
»
7 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why using Floyd Warshall for an unweighted graph ? just do a BFS..

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    → Reply
»
7 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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.

Разбор задач

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +79 Vote: I do not like it

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

They have been disappeared since Round 37 :(

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    There is also a ranking on who is the first to solve each problem.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Sorry, we got really lazy :D Will be posted in no longer than a hour.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow I got the first blood of E!

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

.

→ Reply