By BledDest, 4 weeks 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, 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
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 GuYueNa 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  

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Great opportunity for Indian programmers, Best of luck guyz!

»
4 weeks 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.

  • »
    »
    4 weeks 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.

  • »
    »
    4 weeks 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)

    • »
      »
      »
      4 weeks 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.

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

I really missed rated codeforces contests :D

»
4 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

plenty of problems !!!

»
4 weeks ago, # |
  Vote: I like it -52 Vote: I do not like it

Is It Rated?

»
4 weeks 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 :(

»
4 weeks 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!

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    Same buddy :) CF is LOVE

    • »
      »
      »
      4 weeks 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 ;)

      • »
        »
        »
        »
        4 weeks 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.

        • »
          »
          »
          »
          »
          4 weeks 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

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Same buddy.

            • »
              »
              »
              »
              »
              »
              »
              4 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Same I too bunked my lectures for contest :P

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Me too!!

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it -12 Vote: I do not like it

    Great courage of a newbie :O

    I encourage you ;)

»
4 weeks 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.

»
4 weeks 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 :<

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Well, at least the Ducks won!

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't follow hockey, just liked the movies :P

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

Wish all pupils to become specialists

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

It's a good time for Chinese student

»
4 weeks ago, # |
Rev. 2   Vote: I like it +41 Vote: I do not like it

Highest no. of problems ever for a rated contest?

»
4 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

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

  • »
    »
    4 weeks 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.

»
4 weeks 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 ?

  • »
    »
    4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I have exam at that time so I have to miss the round :(

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

ufff No.

I have to miss the round

»
4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope the round will be steep.

»
4 weeks 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...

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

codeforces seems to be usual unusual contests

:: unusual contests will became usual

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    • »
      »
      »
      4 weeks 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

»
4 weeks 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?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good luck everyone!

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Wow, 9 problems! Just like ACM.

»
4 weeks 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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Some cells may be blocked by multiple obstacles.

    • »
      »
      »
      4 weeks 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.

»
4 weeks 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

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thank you, should read input format next time :D

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +7 Vote: I do not like it

        I also intuitively read the input like that :)

»
4 weeks 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?

  • »
    »
    4 weeks 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...

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What was test 20 on G? :(

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What was testcase 8 on D?

»
4 weeks 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???

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 weeks 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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Yes I realized that later, thanks anyway.

»
4 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What was testcase 7 on C?

is this right?

200000

1 2 3 ... 199999 200000

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

  • »
    »
    4 weeks 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.

    • »
      »
      »
      3 weeks 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

      • »
        »
        »
        »
        3 weeks 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.

        • »
          »
          »
          »
          »
          3 weeks 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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks 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?

  • »
    »
    4 weeks 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.

»
4 weeks 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

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve H?

  • »
    »
    4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain solution of problem G??!!

  • »
    »
    4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

»
4 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Hacks, hacks everywhere!!!

»
4 weeks 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???

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why brute force can pass problem I?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

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

    • »
      »
      »
      4 weeks 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.

»
4 weeks ago, # |
Rev. 4   Vote: I like it -10 Vote: I do not like it

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

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Where do you see that judge answer is 5?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Good problems. Thank you for interesting tasks.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Who is blackhorse_2014 and RNS_RMH??

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Does hack have points ?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem E?

  • »
    »
    4 weeks 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.

»
4 weeks 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)

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
4 weeks 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?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

»
4 weeks 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.


Разбор задач

»
4 weeks 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 :)

»
4 weeks 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 :(

  • »
    »
    4 weeks 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.

  • »
    »
    4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow I got the first blood of E!