Hello, my dear lovers of algorithms and data structures.

Codeforces Round 380 will start on November 20 (Sunday), 09:05 (UTC). It will be based on Technocup 2017 Elimination Round 2. So, if you are a Russian-speaking high-school student, please take part in the Technocup 2017.

Many thanks to KAN, GlebsHP, fcspartakm, Levshunovma. Hope to extend the list soon because of testers. Also some problem ideas are mine.

I hope you will like problems. It will be 6 problems in each division.

Good luck and bugless code

Scoring:

- TK Elim 2 and Div 2: 500-1000-1750-1750-2000-2500
- Div 1: 750-750-1000-1500-2000-2500

**UPD 1:** Here are our winners!

Top-5 in the Technocup stage:

Top-5 in Div.1:

Top-5 in Div.2:

And if I am not a Russian-speaking high-school student, I should register in

`Codeforces Round #380 (Div. 2, Rated, Based on Technocup 2017 - Elimination Round 2) ???`

Yes, the registration will be open soon.

Great, now I can happily miss another boring university day :D

Yep, it's usually boring on Sundays in university

Believe me, It's always boring :p

Me too it's a bad university.

Sunday is not weekend in all countries :)

Oops, my bad

That is true, Saturday is also not a weekend in all countries.

Now i am saying, boring university is better than negative rating change :p

What will you learn in that case? :)

NO :3

Does the Division 2 contest get all the same problems as the actual Technocup round or are there going to be unique problems as well?

Division 2 will contain the same set of problems as Technocup Round. Division 1 will contain harder problems.

The one didn't write "thank ... and Mike Mirzayanov (MikeMirzayanov) for the great platforms Codeforces and Polygon" in contest description.

The one actually is MikeMirzayanov...

Just a cold joke, too cold maybe.

The midterm exams start tomorrow, which gives me only two options :(( :

A- Participate in the contest and let the exams go to hell.

B- Let the exams go to hell and participate in the contest.

What do you people think?

Participate in the contest :)

Go to the exam :) If you don't participate on a div2, nothing will happen, You can do it virtual contest :) But You'll not have a virtual xm or something like that!

i would suggest to go for A, because contest comes first :p

Will the problems be in english as well?

Sure

Codeforces on fire. It's MikeMirzayanov--the elegant one.

Probably got my birthday gift from Codeforces.

Div1 Contest on my birthdayHB

Ty

Happy birthday bhai :)

If i will register in Technocup 2017 — Elimination Round 2, would I have rating change or not? The same question about Codeforces Round #380 (Div. 2, Rated, Based on Technocup 2017 — Elimination Round 2). Will I participate in technocup olymp?

If you register for Technocup 2017 — Elimination Round 2, you will get both rating change and participation, if you register for Codeforces round 380, you will get just the rating change.

whaaaaat???!!! Besides the rating change , What can I get if I participate in Technocup 2017 and get a high rank :D

The midterm exams start tomorrow, which gives me only two options :(( :

A- Participate in the contest and let the exams go to hell.

B- Let the exams go to hell and participate in the contest.

What do you people think?

That you copy pasted this.

Will division 2 in English? :/ when I registered, I saw Russian sentence :/ so,if the contest will be taken in English please make the reg. page in English.

yes.

How hard will it be compared to a div 2 round ( like round #379 )? I wanna know if i can solve anything or not

I think it'll be like 379 or a little bit harder. You can solve something I assume! :)

You can see problems from the Technocup 2017 Elimination Round 1.

Is it rated?

The System testing should start now because it takes long time

Is Div 1 rated?

yes

I would be sad to miss this contest due to Zonal Computing Olympiad being held at same time in my city ...

i've waited this round for 2 weeks, wish it will be an excellent round LOL

It happens; )))))

great :)

what a hurry contest where just ended one Regional :)

by the way All the best to all

It's "TLE" when I used "cin" for Problem B(div2)! Sad ~,~!

Same here... Had to use ios..

worse than that passed pretest with excution time = 880ms and noticed after 1 hour

Strange..used cin but didn't get TLE, 22345324

Can anyone hack any submission during contest???

Strongest pretests in DIV1 — rare hacks :(

t<sin A brought me down by 100+ ranks already :DHow to solve Div 2 D and E?

D seemed like binary search to me but couldn't get anything concrete in time. :/

I solved D using greedy and C using binary search, dunno about E.

How?

In C use binary search to find the least powerful engine that will fit into the time. In D find the maximum number of ships that can be placed in the board. The answer is the maximum number of ships minus real number of ships + 1. Then just shoot so that you remove a possible ship with each shot.

It's funny how C problems are harder to pass than D problems now. :D

They had the same score. But yeah, this D was easier to code than the A imo lol.

Find all the empty segments, and the max. number of ships placeable in the field is sum of (length of segment i / b). Let the number be x, and you need to shoot at least x-b+1 times to ensure a hit. Then just shoot at places where the number of placeable ships will decrease for a sure.

D — greedy — one should take every kth consecutive zero if a=1, dont take last a-1 such places.

E — consider height of tree to be 1..n-1, calculate answer as function of distinct values not present and values lying outside, take min overall.

Worse div1 contest ever!

no interesting problem

no hack

Boring contest

If I don't fail system test, this round will be my best round ever.

Good luck to me.

UPDATE: Failed E T T

Still top 100 so nice job anyways!

OMG !!! I hate all problems where arrays length is not standard. For example why in problem C array

`G`

is '2e5' ???? I had -200 for this mistake. HATE NOT STANDARD ARRAYS LENGTH PROBLEM.UPD#NOPROBLEMWITHNOTSTANDARTARRAYSLENGTHWhat exactly do you consider 'standard array length'? You have different constraints in each problem, it literally takes a second to look at them. Don't whine.

I'm saying that there's no big difference in length 1e5 and 2e5. So I can't understand why they took 2e5?

.

Can you explain me?

How to solve Div1 D? I used DP[left][right][k] and it passed pretests with 1.7 sec, but it doesn't seem to be a correct solution..

You may notice, that

`k <= 100`

and`-100 <= right - left <= 100`

UPD: where 100 is surely = O(sqrt(n))So, will pass?

I don't think so. But with understanding of this constraints it'll be

O(n^{2})Thanks, I will think about it

Ah, so the number of states will be less than 4000 * 200 * 100 = 80000000.. Thx for explaining!

In fact, this can be done in O(N^2) memory if you just memoise using a map. This is because the number of papers Igor and Zhenya have taken in total differs by at most O(sqrt(N)) (To increase the difference after they have made an equal number of moves, you have to increase k, and k is O(sqrt(N))). So this actually runs in O(N)*O(sqrt(N))^2= O(N^2). Memoisation ensures that you only use memory proportional to number of states visited.

I read your solution submitted during the contest, is there any trick on implementing? I did almost the same thing as in your code but just got TLE

I always add "fflush(stdout); _Exit(0);" in the end of the main() function. When I use many maps or sets or the elements are too many, it reduces the running time about a few hundred milliseconds.

Consider branching like this:

if (k <= mem) { ... } else { ... }

instead of

if (k <= rem) { ... } if (k + 1 <= rem)

because it is unnecessary to check "k + 1 <= rem".

I submitted your solution with these two micro optimizations, and it was accepted. 22377001

Wow! That works! Thank you!!!

It seems that I have to be very careful with the constants of solutions when their complexity is near the boundary.

Looks like O(n*k) solutions passed pretests in div2 C. I should have hacked...

I wonder how many of these were submited.

My solution with binary search didn't pass until I wrote .sync_with_stdio(0). How could O(n*k) pass then?

What is the time of this solution: http://codeforces.com/contest/738/submission/22354478 ?

O(nlogn + klogn) I think.

Lets hope system testing isn't late today?

Now it's running!

UPD: uh-oh... It seems that queue is stopped?!

How to avoid TLE in DIV2 B? Tried ios.. and scanf but couldn't pass.

Use prefix sums.

I used prefis sums with cin and got TLE, that's really annoying

prefix sums for Div2 B?

Yes, so you can know if there is anything on the right,left, up or down

Oh. I used a different method.I was able to get AC using normal cin. You can refer to my way here:

(Ignore the functions before main() ) 22349678

_how can get the solution or tutorial ?

They'll publish it tomorrow or later.

Div1 systest paused???

They noticed that systest today is a little bit fast, so they paused it a bit because CF traditions says it should be slow.

I think so.

They started div2 testing. Looks like they can't do both at the same time...

.

What does on fuel mean? If you mean tank capacity, my binary search works in 0.2s (it's 0..1e9 but it should not matter)

Maybe I have done some mistake but Sampson's comment implies same. See lots of binary search solutions failing — http://codeforces.com/contest/737/submission/22346839

I am pretty sure that the reason for your TLE is integer overflow:

Oops :( Thanks.

Had the same problem, forgot that it would be ~4*1e9 which makes more than 2^31.

Honestly I don't see any point setting TL = 1s for Div 1 A so that log(2e9) or slightly slow binary search can't pass.

Edit: My apology. This solution actually fails because of integer overflow when computing (lo + hi) / 2 as pointed out by -Secta-.

Same thing.

My apology. Thank you for pointing out my mistake.

It is not because of slow binsearch, but because of hanging binsearch. They have overflow or other mistakes in implementation.

Even solution with extra internal binary search (e.g.

O(n·log^{2}n)) passes the tests and fits in half of TL.Feels bad when failing 3 contests in two days. :'(

My wrong solution 22349543 passed systest, but it will fail on this test:

Correct output: 5

My output: -1

I just noticed it just after contest end that I forgot to handle that case, to fix that I should add

`else x-=V[n]*(llu)h-S[h-1];`

on 34th line.Edit: Wow so fast rating change =)

my solution for problem B(div 2) in pyth2 is giving TLE and same solution in pypy2 is accepted,,

poor testing in python

Pypy is much faster than python I think.

Yes, i think it uses JIT compilation, so it usually should be faster.

that's why there's pypy compiler

What is the test that does this? :)

I think

`1`

`o`

This is where I got WA. -_-

Nice contest !

Sure.

lol

I got TLE on systest on the same test I got accepted in pretests with 920 ms. I used prefix sums on line and columns.

this

Mysterious TL in problem A for div 1, test 9Why is there TL on test 9 in my this solution? http://codeforces.com/contest/737/submission/22357999 It has return code -1, but still even checker should print RE, I don't understand why is it so. Maybe some of you know?

Probably slow IO?

Dunno, it could have been IO, but some of my friends solved it with cin's and they have 250 ms on this test.

cin/cout http://codeforces.com/contest/737/submission/22362184

Oh, ok. Thanks, I'm lol.

If the size of input/output is large enough and you want to use cin/cout, you have to call "std::ios_base::sync_with_stdio(false)" first.

I had TLE using cin and cout, but after I used scanf I got AC.

Welcome to CodeForces buddy.

If you insist on using cin, cout make sure you are using c+14 and use

`ios::sync_with_stdio(false)`

.Potato quality pretests making my tomato quality codes to fail since 2 onion type of contests.

Pretests are actually meant to be potato quality

You must be fun at LAN parties.

Could anyone help me to find my mistake in problem C ?

http://codeforces.com/contest/737/submission/22349523

I am very eager to know...

UPD : FOUND

22356216 What is the problem a***b != a***b ?

You also output "?".

No I didn't run my code,it's ok for all sample tests..

No. Stop spamming. http://codeforces.com/contest/738/submission/22362803 (last line difference)

you outputed "a***b?", not "a***b"

The participation was rather low today, and I assume the reason for this a slightly more difficult problem A(div 2).

People have come to the contest and decided against submitting I presume. Wouldn't it be great to have a topcoder like system, where u are on the leaderboard if u open the contest ?

Its much more difficult to get a positive rating change with such low participation.

That could be the case for div2; however, for div1 main reason of low participation seems to be a lot of other contests clashing with CF round — OpenCup stage, bunch of regionals (SWERC, CERC, NWERC); also some teams are on their road home from MIPT training camp.

Issue you mentioned has been discussed a lot of times already, and I don't think there are going to be some changes on it in near future. This system itself is really vulnerable

(simply register another account to read problems I guess). It needs a lot of harsh actions — like checking IP addresses of contestants etc. Nowadays people aren't even banned for having multiple accounts or competing in teams using single account(when one account sometimes makes submissions from 2 or 3 cities during a contest). I'm personally fine with it in case we have to choose between platform improvement or having more contests — and improving "fair play" system :) I'm sure that I'm not at the top not because of cheaters but because of other contestants being much better than me :)Is the rating system broken?

I was ranked 995 and my rating changed from 1448->1446(-2). Edit:Nvm, I guess it's due to low participation.

22356216 What is the problem a***b != a***b ?

you print something strange at the end! I think it's '/n';

Please help,i tried on all sample tests and answer is ok,you can run it if you want..

It's actually '/0', he has array out of bounds.

Ohh thank you,I'm new on CF,sorry for spamming I thought my message wasn't sent so I clicked it too many times..

Didn't pass C because I didn't sort the array in which I binary searched. How the hell did it even work?

I was wondering why my solution to (div2)B wasn't working until I noticed that I'd erased the part which was reading the data and that I'd been processing uninitialized 2d array. :D

I am very heated up right now(actually, not really) I was solving 729A - Интервью с Олегом. I thought I had did answer and submitted my code, and I got a "wrong answer". I looked at the test cases, and tried it on my program, but in my program, it printed the right answer.

## include <stdio.h>

char d[101]; int N; int f(int n) { for (int i = n; i < N; i += 2) { if (d[i] == 'g'&&d[i + 1] == 'o') continue; else return i; } } void fill(int a, int b) { int cnt = 1; for (int i = a; i < b; i++) { if (cnt > 3) d[i] = 0; else d[i] = '*'; cnt++; } return; } int main() { scanf("%d", &N); scanf("%s", d); for (int i = 0; i < N — 2; i++) { if (d[i] == 'o' && d[i + 1] == 'g' && d[i + 2] == 'o') fill(i, f(i + 3)); } for (int i = 0; i < N; i++) { if (d[i] == 0) continue; else printf("%c", d[i]); } } this is the code. I've got stuck on test case 2. What is wrong with it???

f doesn't return anything if it goes on until the end of the string

thank you very much :D

Hi, it's more convenient to post your whole submission. Let's say: 22363876. Also, as tfg has noted, your function f doesn't return any number if the control gets out of

forloop without ever evaluating else clause. The behaviour of functionfis therefore probably undefined and it just so happens that it returns correct value on your (and mine) computer, but not on the OJ. One way to modify this could be for example:CodeThat being said, it might not be the most beautiful solution to your problem. By the way, if you compile your program with "-Wall" flag, it gives you a warning:

Spoilerthank you very much :D, I'm new here, so I didn't know how to ask... Sorry

Hey, how to solve Div1B?

Thanks.

We have to change as few zeroes as possible to ones so that it is impossible to place

aships on the zeroes. Calculate for the initial configuration how many ships can be placed. After that, greedily remove the possibility of placing a ship, whenever there arebconsecutive zeroes (i.e. change theb-th consecutive zero to one). Do it until fewer thanaships can be placed.Got it. Thanks a lot!

Any suggestions for div2E?

I used this idea: consider it to be a tree, so each node has it’s depth (number of superiors) If the tree has it’s total depth K, then there should be all integers in range 0 – K and not any deeper than K.

So, for each K in range 1 — N I check how many changes I need to make in order to make the tree with depth equal to K. Any idea why it wouldn’t work?

Here is the link of my try.

That's the right idea.

You check how many changes you need to make to create a tree with total depth from 1<=K<=N-1 (a tree with only a 0 has depth 0). All numbers from 1 to K must be present (there will be only one 0) so to do that you check if you can use the numbers > K to fill the gaps since you will have to change them anyway (to K or some other number lesse than K). If it still isn't enough, you will have to use the numbers from 1 to K to fill any missing gaps. If you consider the numbers that are 0 and aren't the chief as N, you will get the right answer since they are wrong and you need to change them.

Thanks!

My wrong was that I used only those who had 0 depth to fill the gaps, didn't use those which are > K

When will be editorial?

When will the editorial published? I couldn't figure out the solution of C. Can anyone explain it please.

Sort the cars by their volume of fuel and use binary search to find the first car that can arrive to the destination in time, lets say it's the k-th car. Then just itterate through all cars from k to n and pick the one which costs the least.

My code. Sorry but it's pretty ugly :D

Thanks a lot i got it.

creepersteve7

Could u explain / prove these lines of code ?

`d2=a[p].first-d;`

`d1=d-d2;`

`time+=(2*d1+d2);`

thanks in advance !

D1 is the distance he will travel normally and D2 is the distance he will travel accelarated. So we have D1+D2=D, where D is the total distance. Also he uses 1 l/km in the first case and 2 l/km in the second so D1+2*D2=V, where V is the volume of fuel. So we have D2=V-D, D1=D-D2. The we just find the time. I'll leave proving the time formula as homework :D

We can binary search the least fuel

fwe need to get to the destination in time. And the answer is the cheapest car whose fuel limit is larger than or equal tof. Now the question is: how to check if we can get to the destination in time with a certain fuel limit.Denote the distance between a pair of adjacent gas stations as

d, the distance we need to drive in accelerate mode asa, the distance we need to drive in normal mode asb, the fuel limit asv, and the shortest time we need to get to the destination ast.In order to get to the destination as fast as possible, we should use as much fuel as we can.

If 2

d≤vwe can always drive in accelerate mode, i.e.`t += d;`

. Ifd>vthen we don't have enough fuel even if we always drive in normal mode, so`return false;`

in your check function.Now we only need to consider the case when

d≤v< 2d. Because we need to use as much fuel, so we have the following two equations:2

a+b=vanda+b=d.Solve them, and we get

a=v-dandb= 2d-v, i.e.`t += (v-d) + 2*(2*d-v);`

You can check my code for more details. Remember to use

`long long`

type or set the upper limit of the binary search to a little bit more than 1e9. I set the upper limit to 2e9 during the contest and it overflows :(My code: 22361702

I try to use an unordered_map to solve Div1.D during the contest but got TLE on pretest 9. After the contest I checked some successful submissions made by others and found that they also use unordered_maps. Are there any tricks when using unordered_map to speed it up?

Not sure if this is the case here, but sometimes they have testcases that specifically catch unordered_maps. I think it's stupid, but it's happened in the past that you need to use the normal map (which is a bst) to pass the test-cases which are designed to specifically beat unordered_maps.

When will the editorial be published? Or is it published already? The last round of technocup didn't link it's editorial to the problem page so I am concerned that the same thing might happen again.

Looking for help in solving div1E.

I have drafted the minimum time should be max single machine/child play time, and I should rent second machines greedily by the length of play time queue. However, I have no idea how I should cope with providing a valid schedule.

mfw practicing a day after the contest was held