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

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 |

Great opportunity for Indian programmers, Best of luck guyz!

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.

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

the beauty of ACM-Style is ::

1 — problems are not sorted

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

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

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

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

Maybe, but some rules need to be changed, I think.

I really missed rated codeforces contests :D

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

plenty of problems !!!

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

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

Same buddy :) CF is LOVE

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

## FightingForAttendance ;)

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

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

Same buddy.

Me too!!

All the best for contest!

Your professor was asking about you!!!Hehe

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

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

Well, at least the Ducks won!

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

I hope problem statements will be short, otherwise it would be new reading book named "Educational Round 40" by BledDest.

Btw

Happy Novruzfor all guys.Wish all pupils to become specialists

And all specialists to become experts :)

And all Experts to become Candidate Masters xD

And all Candidate Masters to become Masters...

wait!!!

and all spammers to stop spamming :)

It's a good time for Chinese student

Highest no. of problems ever for a rated contest?

Your text to link here...

That was 5 hours contest.

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

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

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

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.

they need to declare this in the blog

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.

I hope the round will be steep.

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...Great time for Chinese workers!(Maybe not for students :P

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

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

OMG 9 problems???3 hours???

is it something between ACM and Olympiad contests?

Good luck everyone!

Wow, 9 problems! Just like ACM.

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

Some cells may be blocked by multiple obstacles.

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

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

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

Thank you, should read input format next time :D

I also intuitively read the input like that :)

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?

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

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

What was test 20 on G? :(

What was testcase 8 on D?

when ui > vi

My solution to problem B has been hacked

For test 8

aaaaaaaa

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

You can copy

at most once!!!Answer is 5(copy is operation too).

Thanks got it

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

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

Yes I realized that later, thanks anyway.

How to solve C?

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.

`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(a[i]-1)/yrepresents 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)/ythis 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.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Чем отличаются тесты 7 и 8 в задаче С?

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?

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.

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

Clear?

Yeah. Thank you very much.

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

Viva Chtholly! :)

We all love chtholly!!!

Viva Chtholly!

Viva Chtholly! :)

http://codeforces.com/contest/940/standings

I think we need more of those, something to remember for next New Year's handle change. Just imagine how cool would the scoreboard become!

How to solve H?

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

can someone explain solution of problem G??!!

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.

Thanks

Hacks, hacks everywhere!!!

Have a nice hacks!

Shows Solved

4out of 9But I solved only 2.

What's wrong???

The first screenshot was before your solution on B and C get hacked

I know, but why it's not updated?

Why brute force can pass problem I?

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

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.

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

Where do you see that judge answer is 5?

Good problems. Thank you for interesting tasks.

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

Does hack have points ?

Not in Educational rounds

How to solve problem E?

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.

Thanks , got it now.

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

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

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?

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

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.

Разбор задач

Thanks . Nice contest/editorial !

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

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

They have been disappeared since Round 37 :(

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

Hope it will be published.

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

Wow I got the first blood of E!

.