By BledDest, 12 months ago, ,

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, PikMike, Sahaand 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
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 GuYueNa 0:10
E 999qs999 0:21
F fatego 0:26
G Magolor 0:11
H fatego 0:18
I wakaka 0:31

•
• +184
•

 » 12 months ago, # |   +5 Great opportunity for Indian programmers, Best of luck guyz!
 » 12 months ago, # |   +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.
•  » » 12 months ago, # ^ |   0 It may be better if it is an ACM-style contest, it is completely an ACM style one.
•  » » 12 months ago, # ^ |   0 the beauty of ACM-Style is ::1 — problems are not sorted 2 — problems are equals in points ( result is the number of solved problems)
•  » » » 12 months ago, # ^ |   0 I don't mind equal in points and penalty/time system, but then I think full feedback is necessary.
•  » » 12 months ago, # ^ |   -21 I think Educational rounds should be unrated, according to reasons you have mentioned.
•  » » » 12 months ago, # ^ |   +18 No, rated educational rounds has led to a huge boost in participation which is also good in its own way.
•  » » » » 12 months ago, # ^ |   +4 Maybe, but some rules need to be changed, I think.
 » 12 months ago, # |   +11 I really missed rated codeforces contests :D
 » 12 months ago, # |   +12 Special start time, Special contest duration, Special number of problems, Special contest !!!
 » 12 months ago, # |   +1 plenty of problems !!!
»
12 months ago, # |
-52

#### Is It Rated?

 » 12 months ago, # |   +9 This should have been a good time for Chinese programmers, but i am still at school that time :(
 » 12 months ago, # | ← Rev. 2 →   +7 In India it is at 11:35am,I m leaving my college classes tomorrow especially for this round!
•  » » 12 months ago, # ^ |   -7 Same buddy :) CF is LOVE
• »
»
»
12 months ago, # ^ |
+5

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

# FightingForAttendance ;)

•  » » » » 12 months ago, # ^ |   0 Same Budddy. My college also have attendance criteria of 75 %. i HAVE HARDLY 40%. iT SUCKS.
•  » » » » » 12 months ago, # ^ | ← Rev. 2 →   +8 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
•  » » » » » » 12 months ago, # ^ |   0 Same buddy.
•  » » » » » » » 12 months ago, # ^ |   0 Same I too bunked my lectures for contest :P
•  » » 12 months ago, # ^ |   +1 Me too!!
•  » » » 12 months ago, # ^ |   0 All the best for contest!
•  » » » » 12 months ago, # ^ |   0 Your professor was asking about you!!!Hehe
•  » » 12 months ago, # ^ |   -12 Great courage of a newbie :OI encourage you ;)
 » 12 months ago, # |   +14 This is my first time seeing a rated contest with 9 problems! Hope i can handle it.
 » 12 months ago, # |   +4 Damn I wish this could be my first contest here but it's 2 hours too early for me :<
•  » » 12 months ago, # ^ |   +3 Well, at least the Ducks won!
•  » » » 12 months ago, # ^ |   0 I don't follow hockey, just liked the movies :P
 » 12 months ago, # |   +8 9 problems in Educational Round. Codeforces is on fire!!
 » 12 months ago, # |   +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.
 » 12 months ago, # |   +15 Wish all pupils to become specialists
•  » » 12 months ago, # ^ |   +10 And all specialists to become experts :)
•  » » » 12 months ago, # ^ |   +23 And all Experts to become Candidate Masters xD
•  » » » » 12 months ago, # ^ |   +15 And all Candidate Masters to become Masters... wait!!!
•  » » » » » 12 months ago, # ^ |   +8 and all spammers to stop spamming :)
 » 12 months ago, # |   0 It's a good time for Chinese student
 » 12 months ago, # | ← Rev. 2 →   +41 Highest no. of problems ever for a rated contest?
•  » » 12 months ago, # ^ |   +21
•  » » » 12 months ago, # ^ |   +3 That was 5 hours contest.
 » 12 months ago, # |   +7 The problems are still sorted in increasing order of difficulty right?
•  » » 12 months ago, # ^ |   +6 Hopefully they will be because i don't want to read all the problems and not be sure which one is harder.
 » 12 months ago, # |   +22 As Contest will contains 9 problems, should i consider them sorted or not ?
•  » » 12 months ago, # ^ |   +3 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.
•  » » » 12 months ago, # ^ |   +12 they need to declare this in the blog
 » 12 months ago, # |   0 I have exam at that time so I have to miss the round :(
 » 12 months ago, # | ← Rev. 2 →   0 ufff No.I have to miss the round
 » 12 months ago, # |   +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.
 » 12 months ago, # |   0 I hope the round will be steep.
 » 12 months ago, # | ← 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...
 » 12 months ago, # |   0 codeforces seems to be usual unusual contests:: unusual contests will became usual
 » 12 months ago, # |   +1 Great time for Chinese workers!(Maybe not for students :P
•  » » 12 months ago, # ^ |   +3 So you are saying that students actually pay attention to lectures?
•  » » » 12 months ago, # ^ |   0 I mean...may not have time to do it,especially for middle school students (poi
 » 12 months ago, # |   0 OMG 9 problems???3 hours???is it something between ACM and Olympiad contests?
 » 12 months ago, # |   0 Good luck everyone!
 » 12 months ago, # |   +1 Wow, 9 problems! Just like ACM.
 » 12 months ago, # |   +7 For F, are we guaranteed that obstacles of the same kind do not intersect?i.e. would this be allowed?2 51 2 41 3 5
•  » » 12 months ago, # ^ |   +8 Some cells may be blocked by multiple obstacles.
•  » » » 12 months ago, # ^ |   +5 Thanks, I misunderstood the meaning of cell for a second and accidentally thought it meant column.
 » 12 months ago, # |   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
•  » » 12 months ago, # ^ |   +3 Second line contains max volumes, third line contains temperatures. So temperatures are 50 and 150, not 10 and 150.
•  » » » 12 months ago, # ^ |   +3 Thank you, should read input format next time :D
•  » » » » 12 months ago, # ^ |   +7 I also intuitively read the input like that :)
 » 12 months ago, # |   +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?
•  » » 12 months ago, # ^ |   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...
 » 12 months ago, # |   0 In fact there're 3 Examples in problem B :)
 » 12 months ago, # |   0 What was test 20 on G? :(
 » 12 months ago, # |   0 What was testcase 8 on D?
•  » » 12 months ago, # ^ |   +3 when ui > vi
 » 12 months ago, # | ← Rev. 2 →   +6 My solution to problem B has been hackedFor test 8aaaaaaaaMy answer is 4. What's wrong???
•  » » 12 months ago, # ^ | ← Rev. 2 →   +4 You can copy at most once!!!
•  » » 12 months ago, # ^ |   +3 Answer is 5(copy is operation too).
•  » » 12 months ago, # ^ |   +1 Thanks got it
 » 12 months ago, # |   0 Was segment tree + binary search for G TLE'ing for everyone? :/
•  » » 12 months ago, # ^ | ← Rev. 2 →   +3 There is no need for a segment tree. It can be done with sliding window technique. That will save a logn factor
•  » » » 12 months ago, # ^ |   +5 Yes I realized that later, thanks anyway.
 » 12 months ago, # | ← Rev. 2 →   0 What was testcase 7 on C?is this right?2000001 2 3 ... 199999 200000
 » 12 months ago, # |   0 How to solve C?
•  » » 12 months ago, # ^ |   +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.
•  » » » 12 months ago, # ^ | ← 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
•  » » » » 12 months ago, # ^ |   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.
•  » » » » » 12 months ago, # ^ | ← 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
 » 12 months ago, # |   0 Чем отличаются тесты 7 и 8 в задаче С?
 » 12 months ago, # |   0 what is the Best Way to Solve problem G: Castle Defense?Actually, I have used Very Naive approch to solve it Which will give TLE in Advance Cases.(Presently getting WA on 8th)http://codeforces.com/contest/954/submission/36494396
 » 12 months ago, # | ← 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?
•  » » 12 months ago, # ^ | ← 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.
•  » » » 12 months ago, # ^ |   0 I know. But I just don't know how to use matrix multiplication. Can you explain? Thanks in advance.
•  » » » » 12 months ago, # ^ |   +22 Clear?
•  » » » » » 12 months ago, # ^ |   +4 Yeah. Thank you very much.
 » 12 months ago, # |   +68 Good job l_love_chthoIIy, l_love_chtholly, I_AM_CHTHOLLY, IamChtholly in the first run! Viva Chtholly! :D
•  » » 12 months ago, # ^ |   +50 Viva Chtholly! :)
•  » » » 12 months ago, # ^ |   +50 We all love chtholly!!!
•  » » » » 12 months ago, # ^ |   +29
•  » » 12 months ago, # ^ |   +39 Viva Chtholly!
•  » » 12 months ago, # ^ |   +39 Viva Chtholly! :)
•  » » 12 months ago, # ^ |   +38
•  » » » 12 months ago, # ^ |   +13 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!
 » 12 months ago, # |   0 How to solve H?
•  » » 12 months ago, # ^ | ← 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.
 » 12 months ago, # |   0 can someone explain solution of problem G??!!
•  » » 12 months ago, # ^ |   +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.
•  » » » 12 months ago, # ^ |   0 Thanks
 » 12 months ago, # |   0 can anyone tell me why i am getting the diff output of same code at diffeent ide's when i submit at codeforces it giving me diff ans but at geeks for geeks ide it gives diff one why is it so?
 » 12 months ago, # |   +16 Hacks, hacks everywhere!!!
•  » » 12 months ago, # ^ |   +4 Have a nice hacks!
 » 12 months ago, # |   +4 Shows Solved 4 out of 9But I solved only 2.What's wrong???
•  » » 12 months ago, # ^ | ← Rev. 2 →   0 The first screenshot was before your solution on B and C get hacked
•  » » » 12 months ago, # ^ | ← Rev. 2 →   0 I know, but why it's not updated?
 » 12 months ago, # |   0 Why brute force can pass problem I?
•  » » 12 months ago, # ^ |   +11 bitset is very fast. but i think fft is better.
•  » » » 12 months ago, # ^ |   +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.
 » 12 months ago, # | ← Rev. 4 →   -10 ................
•  » » 12 months ago, # ^ |   +3 Where do you see that judge answer is 5?
 » 12 months ago, # |   0 Good problems. Thank you for interesting tasks.
 » 12 months ago, # |   0 Who is blackhorse_2014 and RNS_RMH??
 » 12 months ago, # |   0 Does hack have points ?
•  » » 12 months ago, # ^ |   0 Not in Educational rounds
 » 12 months ago, # |   0 How to solve problem E?
•  » » 12 months ago, # ^ | ← 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.
•  » » » 12 months ago, # ^ |   0 Thanks , got it now.
 » 12 months ago, # |   +8 Solutions using Floyd Warshall Algorithm are accepted in D, HOW ?? O(10^9)
•  » » 12 months ago, # ^ |   0 Why using Floyd Warshall for an unweighted graph ? just do a BFS..
 » 12 months ago, # |   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:12Codeforces 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?
•  » » 12 months ago, # ^ |   +6 Codeforces ignores penalty from compilation error and WA on test 1 verdicts .
 » 12 months ago, # |   +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. Разбор задач
•  » » 12 months ago, # ^ |   +4 Thanks . Nice contest/editorial !
 » 12 months ago, # |   0 Low level screencast on my alternate account just for fun. Feedback and comments are welcome and encouraged :)
 » 12 months ago, # | ← Rev. 2 →   +79 Will this round have the ranklist and the hacker ranklist? :PThey have been disappeared since Round 37 :(
•  » » 12 months ago, # ^ |   +23 There is also a ranking on who is the first to solve each problem.
•  » » » 12 months ago, # ^ |   +16 Hope it will be published.
•  » » 12 months ago, # ^ |   +18 Sorry, we got really lazy :D Will be posted in no longer than a hour.
 » 12 months ago, # |   0 Wow I got the first blood of E!
 » 8 months ago, # |   0 .