On Aug/18/2018 17:35 (Moscow time) Educational Codeforces Round 49 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be **rated for the participants with rating lower than 2100**. It will be held on extented ACM ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given **7 problems** and **2 hours** to solve them.

The problems were invented and prepared by Vladimir Vovuh Petrov, Adilbek adedalic Dalabaev, Ivan BledDest Androsov, Mike MikeMirzayanov Mirzyanov and me.

Good luck to all participants!

Our friends at Harbour.Space also have a message for you:

Hi Codeforces!

Our Hello Barcelona Programming Bootcamp will be kicking off next month from Sept 26 — Oct 4, and we’d love to see you there!

The boot camp will once again feature the all-time greats Mike MikeMirzayanov Mirzayanov, Andrey andrewzta Stankevich, Michael Endagorion Tikhomirov, Gleb GlebsHP Evstropov, Artem VArtem Vasilyev, Ivan ifsmirnov Smirnov and other world renowned Russian coaches to train the participants.

You will be competing and learning side by side with some of the greatest teams in the world, while learning from the best coaches the ICPC has to offer.

Be sure to register before **September 1st so everyone has time to get visas if needed**, and of course for the Early Bird Discount of 5% or the Loyalty Discount* of 20% off registration for the boot camp!

*The loyalty discount is offered to universities and individual participants that took part in Hello Barcelona Bootcamps and Moscow Workshops ICPC.

Learn more about Barcelona ICPC Bootcamp

You can ask any questions by email: hello@harbour.space

Congratulations to the winners:

Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|

1 | Um_nik | 7 | 179 |

2 | isaf27 | 7 | 343 |

3 | RNS_KSB | 7 | 357 |

4 | eddy1021 | 6 | 157 |

5 | djp_cqq | 6 | 176 |

Congratulations to the best hackers:

Rank | Competitor | Hack Count |
---|---|---|

1 | halyavin | 200:-25 |

2 | eR6 | 87:-58 |

3 | Winniechen | 35:-13 |

4 | jhonber | 29:-1 |

5 | Kaban-5 | 19 |

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

Problem | Competitor | Penalty |
---|---|---|

A | arknave | 0:02 |

B | eddy1021 | 0:06 |

C | bekzhan97 | 0:12 |

D | teja349 | 0:12 |

E | step_by_step | 0:10 |

F | lee_sin | 0:24 |

G | uwi | 0:39 |

Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).See you again.

What will be the penalty, 20 or 10 ..??

10

Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).I prefer the penalty time. Every time I have ample time, but after submitting it many times, the score is lower. . .

Why those great bootcamps don't have public videos for participants not being able to manage to there ?

then why should some people go there on their own expense,they would also wait for videos/tutorials to get public.

true !

But both are not the same thing, getting videos are least you can hope!

## peace

Have anyone noticed that after Codeforces Round #503 and #504, although rating recalculated in users' profiles, RATING page and Top rated page didn't change?

Yeah, but the colour changed, so now the Top rated page has 9 nutellas and one red (who's in the 9th place)!

Even if the internet of machine room is out of service, I will open my wifi to play codeforces. come on!

Assalamu alaykum MikeMirzayanov!

When will you update

Rating?Wallaikumsalam

Assuming ACM ICPC rules, the problemset won't be sorted by increasing difficulty, right?

It will be sorted.

Thanks Numb!

are you linkin park fan?

no

Dumb

Hey, what will happen with Round 505? It starts tomorrow when hacking phase is still going on

Hacking phase is only 12 hours now, so they shouldn't collide.

Sorry. My bad! Thank you:)

halyavin is going to take part in the round! Stay determined!

How to solve F?

My idea was doing binary search. And for checking matching, we can use Hall's theorem.Here hall's theorem converts to checking each component has more exam days than students.

It gave TLE on 46th. So now I think the above procedure can be done with a dsu and a sort. Hopefully it should pass

Nice application of Hall's theorem.

Yeah DSU works

I managed to get it accepted this way (binary search + application of Hall's theorem) although several attempts were required.

Adding rank heuristic and getting rid of rand() calls in my implementation of DSU is what finally worked.

Code: 41803434.

I just binary search and matching. In the contest, I got WA on 17th because of the mistake of binary search :'( (41788874 ), just fix it and got AC. (Matching in O(n^2)) 41796159. Sorry for my bad English

Perhaps a 2-SAT solution exists?

Yes, I did 2-SAT with binary search: 41787621 (MLE Test 45).

We have two variables

V_{ai}andV_{bi}for each exam, withV_{ai}positive if we want to take examion daya_{i}.Of course, if the binary search value we are evaluating is smaller than

b_{i}(resp.a_{i}) thenV_{bi}(V_{ai}) has to be false.Then we just need to enforce "at most one exam a day", which I did by taking a prefix and suffix OR of the variables correp. to exams on a given day. Please ask for more details if the code / my description is unclear.

Note that this uses 6

Nvariables (3 for each day each exam is on).Hi! It took me quite a long time to understand the prefix/suffix OR idea. I reimplemented your solution using Tarjan algorithm for SCC, and got TLE on test 45. I generated random test of the same size, and it takes ~16 seconds. So I don't think it is possible get this solution accepted, the constant factor is just to big - the memory allocation for the graphs are the culprit I guess. Thanks for the idea though. (https://codeforces.com/contest/1027/submission/42493816)

Stopped creating a new graph in each binary search check, just set the variables which are out of range to false, got down to 7 seconds. Can't think of any other reasonable change. I would really like to get it accepted :(

https://codeforces.com/contest/1027/submission/42496525

I tried to reduce your binary search iterations via coordinate compression and now we have 42497321 — MLE Test 46.

To make testing easier (instead of local testing on random large instance), you can make mashup with only this problem, and change TL and ML to whatever you like.

thanks for the help & the hint!

So What's test 9 problem C?

No idea, to be honest. Just 25000 testcases of size 40 with random sticks.

I can provide you with generator and command line arguments if you need it.

Nah,I'll just cry in corner,Thanks anyway for the contest and nice problems

Forgot to sort the array :(

I have a feeling the time limit constraints are too strict. My java solution (equivalent of an acc C++ soln doesn't seem to pass..) Are the problems just meant to be solved in C++?

Two problems with your solution (that I also faced during contest):

First is your frequency arrays. You're recreating your freq array for every test case. If the number of test cases is 25,000 recreating that array so many times is very time consuming. You should instead reuse the frequency array and only clear an element the first time you access it during a test case.

The second problem is your output. You're using System.out which is much slower than using a PrintWriter. But that'll still get TLE. Instead, you should append all of your output to a StringBuilder and print once after doing all test cases.

I agree it's kind of annoying but sometimes you need to do annoying things to make things pass in Java.

Thanks for your help! I'll try the suggestions

One of the weirdest contests I ever seen !!! Solved C and D and couldn't solve A nor B !!!

Happened with me too earlier....When you overthink..XD

Even Radewoosh didn't solve A, Really seems weird....

whats test 5 in C ?

166666 testcases with lists of size 6: 3 pairs of equal lengths. I can provide you with generator and command line arguments if you need it.

Something likeAnswer100 100 104 104

Minimum difference might not give optimal answer.

In C is it not optimal that we always choose the two sides which have minimum difference and for those differences (of length and breadth) which are equal check for them explicitly whose given ratio (p*p/s) is smaller ?

not just the ratio.. you need to minimize x/y + y/x

Yeah but this would be minimum when x is closest to y (obtained by differentiating) and for those whose difference b/w x and y is same we compare which of ratio (x/y+y/x) is smaller. Did i miss something ? I guess i increased conditions and computation but still could not figure out why WA. Though your code make sense. Thanks !!

if you fix one of x or y.. then you can say that the other one has to be closer.. but that does not mean that the closest pair will be the answer

Yes, while differentiating i kept one of it fixed and then obtained relation. I had better calculated it comparing ratios :(..Could not even read other questions.

only adjacent ones need to be checked. we need to minimize (a/b) + (b/a) where a and b are the 2 sides. define x = (a/b), then we need to minimize x + 1/x which is done when x = 1. So checking only closest elements is sufficient

Actually what he said was that finding two closest (with min difference) does not give required answer.

For eg 18/2 is 9 and 500/100 is 5, smaller than 9 despite of having difference as 400 which is greater than that of former one.

Sorting in this case worked because

for a given elementif we want to check smallest possible ratio then we want just smaller one because all others will give a higher ratio (mistake i did by differentiating by keeping one variable fixed) because in this case we are talking with respect to particular element a[i].Could you explain how does one get from

p * p / area

to x/y y/x ???

p*p = 4*(x^2 + 2xy + y^2) area = xy divide them, 4*(x/y + 1 + y/x) so you have to minimize x/y + y/x.

Thanks man !

I was thinking about 1 1 2 2 15 15 20 20...

f(x, y) = (2*x + 2*y)^2/(x*y) f(1, 2) = 18, f(100, 109) = 16.03

this site plot functions with 2 variables, it can give you a visual vision for the function varaitions, hence you can find it's minumum.

Can you make it a hyperlink. Thanks Btw !! This is really helpful..got something interesting.

Didn't solve C... I'm feeling like a fool...

What's test case 23 in D and test case 9 in C ? :/

How to solve E?

An observation is that when the color of the first row and the color of the first column is determined, then the color of the whole matrix is determined, and the maximum area of the rectangle of the same color equals to the maximum number of consecutive grids of the same color in the first row multiplies the maximum number of consecutive grids of the same color in the first column. Thus you can do a dynamic programming computing for each k, how many arrays of length n such that the maximum number of consecutive grids of the same color equals to k, and then easily find out the answer.

When u get the observation but don't attempt it more after seeing the modulo (fft).

You don't need FFT, it's a very simple dynamic programming problem.

Read the question wrong. Sorry.EDITYeah I realised that but during contest I thought it was fft

I have a question, can you help me? qwq If the first element of two arrays is different, how do we merge the two arrays? For example: n = 2, and k = 2(k is the maximum number of consecutive grids of the same color in array) we can get: "00" "11" but I can't understand how to generate the matrix?

I faced an issue in this contest ! Read about it here(https://codeforces.com/blog/entry/61298) and present your views !

Is F binary search on day and apply halls theorem for checking the validity in the binary search ?

no~~

Why not? It works although one has to be careful about implementation — I got several TLEs before getting it accepted.

You can try mentos theorem.

What is mentos theorem. Couldn't get anything through google search. It will be helpful if you can provide any links.

damn...

This submission was made 20 seconds before the end. I started about 20 minutes late into the contest and I wrote the code for G in a real hurry so I didn't even know the code was going to pass a lot of tests.

I hoped for a miracle but guess that's not happening today :(

ㅠㅠ

What's test case 23 in D?

I was considering it as graph and finding the sum of minimum costs in cycles in different connected components, but got WA on test case 23.

Edit : It was a minor bug in implementation

Your solution fails on

Isn't the answer

`1`

in this case (the rat will come in the first room sooner or later so placing the trap on first room would work) or I'm missing something ? (My code is outputting`1`

but it also got WA in test case 23)My answer is 1.

And I think that's correct :|

you need to calculate minimum of costs which are part of a cycle.. not its branch

1->2->3->4->2.. here you have to consider 2,3,4 and not 1 bcoz 1 is not a part of the cycle

I am doing the same... I am first isolating a cycle and considering the minimum cost of elemenents in the cycle...

Also I'm taking use of the fact that there will be exactly one cycle in a connected component(considering it as undirected graph).. isn't it right?

yeah but see the test case in which you got wa.. there might be something wrong in your implementation

Just realised now that I can see that test case :|

How do you solve D? I realized the problem was much harder when it wasn't a tree.

UPD: Nvm you just dfs from two roots

Find minimum Ci in every cycles and add these minimum to answer.And note that cycle can be with one node(self loop).

41776119 It gave WA on test 5 in C. I tried to minimize l/b + b/l. Although I later ACed it by hardcoding the functions for area and perimeter, I still couldn't figure out my bug in the first approach. Any idea what's wrong? Thanks in advance.

Not completely sure, but the problem seems to be the line

maxx = (ll/bb + bb/ll);

maxx is an integer, and ll/bb+bb/ll is a float/double.

Damn, that was the bug. Spent an hour trying to debug it. Anyways, thanks a lot :)

actually i checked it on my computer and the problem is with this line:

`int maxx = LLONG_MAX`

xcode is smart enough to warn about wrong conversion:

`Implicit conversion from 'long long' to 'int' changes value from 9223372036854775807 to -1`

ideone example

Actually I have used #define int long long, so I didn't face that problem.

i was getting wrong answer in problem b in java because i was using Math.ceil() function. can anyone help me why this is happening ? failed submission http://codeforces.com/contest/1027/submission/41770896 Accepted submission http://codeforces.com/contest/1027/submission/41791415

Same, I used ceil function in c++ while in contest and it gave me wrong answer.

Contest Submission- http://codeforces.com/contest/1027/submission/41788167

Just removed ceil and used if else instead and it got accepted. http://codeforces.com/contest/1027/submission/41800586

using / on 2 ints will give answer in int. i.e ceil(5/2) means 5/2 is 2 so ceil(2) gives 2. If you want to use you can use 1.0*x/y this will give correct ans but still may have precision issues of very large values. so it's best to use custom ceil function.

My variables in ceil function were double not ints. Double variables shoudn't cause any problem I guess.

nn^2 can be very large so it causes precision issue try using long double that should work.

In any case it's not adviced to use double unless you can't do it with int.

Yes, long double worked. Thanks for the help! Should've tried using long double while in contest.

I was constantly getting logged out of my account during contest.Don't know what it was because of my slowed down wifi today or something else.It ruined my contest today

Same issue here

What is the complexity of memset in C++..? I read it is O(Size of Array to be initialized) but in Problem C, I used memset for an array of size 10000 in all the testcases and it passed all the pretests..How?

The memset function is highly optimized by those professional engineer, it's very fast.

There are some hardware acceleration inside menset(), for example, it can be done parallelly. Also you can set 8 bytes at a time if you are on a 64 bits machine

A solution for problem C:

This works because the smallest value must appear in the adjacent pair, here is a proof:

1.Let these two stick pairs have length a and b, minimizing P^2/S is equal to minimizing a/b + b/a.

2.Suppose b = a + d, d >= 0. a/b + b/2 = a/(a + d) + (a + d)/a, get derivative for d, it's positive in our concerned area, that means the minimum value must appear in the adjacent pair.

I didn't notice the rectangle constraint in the first glance, found it unsolvable. :(

You could have time travelled into the past (smaller rank) if you spent less time looking at the standings xD

Dear Mister,

You can notice that I solved C at the last minute.

So don't go around and assume that I spent it looking at the standings. ^-^

I solved F at the last second. XD

How to solve F?

I wonder why my solution for problem C runs 1840ms but others solution runs 421ms???

Because in every test cases you are clearing cnt array which is O(T * sizeof(cnt)).

Thanks for your help!

You're resetting cnt every test case even when n=4. 250000 testcases with n=4 and your solution should give tle.

Oh...I know it.Thanks for your reply!

It is not because of

`memset`

.Firstly, the complexity of the other's solution is not

O(Tnlog(n)) but it is something likeO(10^{6}log(10^{6})), and your complexity is notO(Tn) but it isO(T10^{4}), and here is the problem, because whenT= 250000 andn= 4foreachtestcase, then you will iterate, for each testcase, 10^{4}times while you could iterate over 4 elements atmost (n= 4).I solved it in O(T*nlgn) but still the solution was hacked by the test case that you mentioned and the verdict of the hack was TLE . I can't figure out the reason as I am only doing O(nlgn) operations in each test case . My submission

I have just finished testing your submission and the problem was with big I/O data. So, you just need to convert cin/cout in your code to scanf/printf.

Thanks a lot! I was really unable to find my mistake.

Welcome :)

Will adding this line solve the problem or I have to use printf and scanf ??

On my computer,

`scanf/printf`

were faster 3 times than`ios_base::sync_with_stdio(false)`

(the last one took almost 2111 ms but the first took 766 ms almost), but yes it will solve the problem on Codeforces.The time limit set in the today's contest was very stringent for python guys. I was getting a TLE for O(1) solution, whereas when I used fast I/O after the contest, my code passed all the test cases by just 1 millisecond and later on it was hacked by someone and the verdict was TLE. It would be great if you could increase the time limit by one-two second, for people coding in python. Since, everyone knows python is 5 times slower than c++. As increasing the TL by one second, won't allow any O(n) or above solution to run. So, if possible do it for both B and C.

Also, I wished to raise it as a general concern as well. Every time I code in python there is some TL issues. Why don't you guys provide a X5 multiplier for python similar to other coding sites? As it would encourage the use of python in CP. If the problems are specifically designed for c++, just tell it before the contest starts.

Python gets other advantages such as many inbuilt functions big integers etc. So it's a trade off.

I completely agree with you, but don't you think that there should be at least an AC in every programming language allowed, which passes the given time limit by a comfortable margin?

Why would you necessarily

wantto encourage the use of Python in CP? Lots of contests don't allow the use of Python (ICPC, GCJ, etc.) or it's completely infeasible to solve some of the problems in Python (FHC), so I don't see why CodeForces should encourage the use of Python in any way.EDIT: Made a mistake, ICPC and GCJ allow Python. However, for ICPC, solutions are only provided for C++ and Java, so it is not guaranteed that one can solve a question in Python. Same is probably true for GCJ now that it is judged on their servers rather than running input on our own machines.

Python is now allowed in all the contests like ICPC, GCJ and FHC. I didn't mean that I specifically want everyone to code in Python. If it seems so through my words, I am sorry. But what I meant is, if someone gets TLE on a perfect logic, then his interest goes low, even though he might be good at CP.

Can anyone explain why i was getting TLE in C when dealing with double and got AC when dealt with integers AC ....TLE

How to solve problem D ?

In a circular path of the mouse, we should place trap in the room with minimum cost. This same trap will work for those rooms also from which you can enter this cycle. Summing over all such rooms( corresponding to each cycle ) will give the answer.

what to do in this case ?

So you have the cycle 1-2-3-1 in this. Pick the room with minimum cost in this cycle (say room x). Also you can reach to this cycle from 4. This covers all the nodes. Answer will be cost of x.

Hint: When a loop is found, we can travel around the loop again to get the minimum cost.

Could anyone provide a hint for G? Also, I know F is about Hall's theorem, but how to implement it?

Hint for G — you can calculate answer for each divisor of

mindependently.Formula for G: Let

ord_{p}(x) be the smallest positive integerks.t.x^{k}≡ 1 modulop. Then answer isThank you!

how to solve problem B please help?

what i did is just find starting value (find value of (y,0) or (y,1) depend on case) then just add the value by x/2 or (x-1)/2 depend on case (my code)

that's a lot of case to handle, there should be another simpler solution like:

Hey can someone help me understand what is wrong with my solution? I am checking each adjacent numbers that are >=2 using a map and i am getting wrong answer on a list on the last test https://codeforces.com/contest/1027/submission/41804552

`float`

hasn't got the necessary accuracy. Change it to`double`

/`long double`

. See this test:yea this was the problem. I got AC now thank you very much!

Also don't use float unless absolute necessary. instead of a/b<c/d you can use a*d<c*b.

In problem C, is it mentioned somewhere that we have to minimize the length of sides as well after minimizing p^2/S. I am asking this because I submitted a solution where printing a larger side for the case when all sides are equal is giving wrong answer while if we take the smallest side Accepted is given.

Links to submissions:

Wrong Submission

Accepted Submission

If you look test 3 of your WA submission, you will see that you are printing numbers that doesn't belong to the input array (the judge says

"wrong answer Given lengths aren't present in the input list for list 5").You can check that minimizing is not necessary in this submission. I used your code but I didn't update the answer if I already found one, and it got AC.

I too initially thought that the sides might not be present but when I checked (Look at this submission) I found the sides are in fact present in the list.

PS: My previous submission said that the give side is not present in list 5. So I tried to print yes when whenever I found that side to check it.

Yeah, that's weird, but minimizing the lengths is not really necessary (I updated my previous comment with a submission link). I really don't know what's going on :P

Yeah that's the point. It is clearly mentioned in the question that you cant print any of the possible values. But they are accepting only the least one.

The submission I posted in my comment prints

`5314 5314 5314 5314`

for that input list, yours prints`2 2 2 2`

, and the judge says both of them are ok, so not only the smallest side is considered as correct. Maybe there is some kind of bug for some values. I'm sorry that I can't help you with that!When does system testing start?

it hasn't started even now.. Will the submissions won't be check at system tests(pretest + hacks) this time?

When will the rating be updated ?

When will the ratings change?

Can someone please provide the 5th list of test case 3 in C. I am unable to spot the error in my code.

Error : wrong answer Given lengths aren't present in the input list for list 5

Code : My Solution

You don't need the break in your loop. You don't finish reading the current list before proceeding to the next one.

Thanks a lot !! :)

I made the same mistake using the break in order to avoid TLE,it is the first time I meet this type of input which one testcase includes n tests.

This is the common pattern on codechef!!

Why system test doesn't start right after open hacking phase? Contestants always need to waiting long time for system test and it's really boring and annoying...

you can calculate by yourself,according to the standings and your points

before system test, standings are not real standing. I know how to calculate rating change, but that's not the point. we can know real contest result only after the system test. I want to know the real result, not the expected rating change.

and I really can't understand the reason why system test couldn't start automatically. I want to know the reason why we must need to waiting long time for starting system test.

I don't know either,maybe the server machine needs upgrade

What happened with the system test? The next contest will begin in 8 hours but the system test of this contest disappears.

When will the system test start?

The system tests are started!

Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).when the ratings begin change?

How long will take it to calcuate the rating changes?

Why the rating changing still can't be seen??

Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).I have solved C bt cant come up with a solution for B.. plz help!!

Rating has improved.I am happy.

The contest has helped me a lot !!!! thank you very much :)))

In Problem 1027F Session in BSU, Some people AC this problem by using Hungary Algorithm I can make the data to Hack Hungary Algorithm's solution (eg:41789514) How can I give my data to Codeforces? I only don't hope these people are mislead by Hungary Algorithm Sorry.I am not good in English,Can you get my meaning?

Here is the Generator:https://paste.ubuntu.com/p/c9W5P7msQk/