By PikMike, history, 5 months ago, translation, ,

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.

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
697 successful hacks and 674 unsuccessful hacks were made in total!

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

•
• +160
•

 » 5 months ago, # |   +5 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
•  » » 5 months ago, # ^ |   0 See you again.
 » 5 months ago, # |   -6 What will be the penalty, 20 or 10 ..??
•  » » 5 months ago, # ^ |   +13 10
 » 5 months ago, # |   0 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 5 months ago, # |   0 I prefer the penalty time. Every time I have ample time, but after submitting it many times, the score is lower. . .
 » 5 months ago, # |   +7 Why those great bootcamps don't have public videos for participants not being able to manage to there ?
•  » » 5 months ago, # ^ |   0 then why should some people go there on their own expense,they would also wait for videos/tutorials to get public.
• »
»
»
5 months ago, # ^ |
-12

true !

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

# peace

 » 5 months ago, # |   +65 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?
•  » » 5 months ago, # ^ |   0 Yeah, but the colour changed, so now the Top rated page has 9 nutellas and one red (who's in the 9th place)!
 » 5 months ago, # | ← Rev. 2 →   +1 The internet of machine room is out of service, sadly I have to use my wifi to play codeforces....
 » 5 months ago, # |   -23 Assalamu alaykum MikeMirzayanov! When will you update Rating?
•  » » 5 months ago, # ^ |   0 Wallaikumsalam
 » 5 months ago, # |   0 Assuming ACM ICPC rules, the problemset won't be sorted by increasing difficulty, right?
•  » » 5 months ago, # ^ |   +18 It will be sorted.
•  » » » 5 months ago, # ^ |   0 Thanks Numb!
•  » » » 5 months ago, # ^ |   +2 are you linkin park fan?
•  » » » » 5 months ago, # ^ |   0 no
•  » » » » » 5 months ago, # ^ |   +16 Dumb
 » 5 months ago, # |   +7 Hey, what will happen with Round 505? It starts tomorrow when hacking phase is still going on
•  » » 5 months ago, # ^ |   +18 Hacking phase is only 12 hours now, so they shouldn't collide.
•  » » » 5 months ago, # ^ |   +5 Sorry. My bad! Thank you:)
•  » » » 5 months ago, # ^ | ← Rev. 3 →   -44
 » 5 months ago, # |   +24 halyavin is going to take part in the round! Stay determined!
 » 5 months ago, # |   +5 How to solve F?
•  » » 5 months ago, # ^ |   +21 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
•  » » » 5 months ago, # ^ |   0 Nice application of Hall's theorem.
•  » » » 5 months ago, # ^ |   0 Yeah DSU works
•  » » » 5 months ago, # ^ | ← Rev. 3 →   +1 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.
•  » » » 5 months ago, # ^ | ← Rev. 6 →   0 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 Edit: TLE main test.
•  » » 5 months ago, # ^ |   +3 Perhaps a 2-SAT solution exists?
•  » » » 5 months ago, # ^ |   +6 Yes, I did 2-SAT with binary search: 41787621 (MLE Test 45).We have two variables Vai and Vbi for each exam, with Vai positive if we want to take exam i on day ai.Of course, if the binary search value we are evaluating is smaller than bi (resp. ai) then Vbi (Vai) 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 6N variables (3 for each day each exam is on).
•  » » » » 4 months ago, # ^ |   +5 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)
•  » » » » » 4 months ago, # ^ |   +5 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
•  » » » » » » 4 months ago, # ^ |   +3 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.
•  » » » » » » » 4 months ago, # ^ |   0 thanks for the help & the hint!
 » 5 months ago, # |   +6 So What's test 9 problem C?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +9 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.
•  » » » 5 months ago, # ^ |   +23 Nah,I'll just cry in corner,Thanks anyway for the contest and nice problems
•  » » » » 5 months ago, # ^ |   +10 Forgot to sort the array :(
•  » » » 5 months ago, # ^ |   0 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++?
•  » » » » 5 months ago, # ^ |   0 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.
•  » » » » » 5 months ago, # ^ |   +3 Thanks for your help! I'll try the suggestions
 » 5 months ago, # |   +3 One of the weirdest contests I ever seen !!! Solved C and D and couldn't solve A nor B !!!
•  » » 5 months ago, # ^ |   0 Happened with me too earlier....When you overthink..XD
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Even Radewoosh didn't solve A, Really seems weird....
 » 5 months ago, # |   0 whats test 5 in C ?
•  » » 5 months ago, # ^ |   0 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.
•  » » 5 months ago, # ^ |   +8 Something like8 1 1 3 3 100 100 104 104  Answer100 100 104 104Minimum difference might not give optimal answer.
 » 5 months ago, # | ← Rev. 2 →   0 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 ?
•  » » 5 months ago, # ^ |   +3 not just the ratio.. you need to minimize x/y + y/x
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 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 !!
•  » » » » 5 months ago, # ^ |   +1 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
•  » » » » » 5 months ago, # ^ |   0 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.
•  » » » » » 5 months ago, # ^ |   0 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
•  » » » » » » 5 months ago, # ^ | ← Rev. 4 →   +1 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 element if 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].
•  » » » 5 months ago, # ^ |   0 Could you explain how does one get from p * p / areato x/y y/x ???
•  » » » » 5 months ago, # ^ |   0 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.
•  » » » » » 5 months ago, # ^ |   +1 Thanks man !
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 I was thinking about 1 1 2 2 15 15 20 20...
•  » » 5 months ago, # ^ |   0 f(x, y) = (2*x + 2*y)^2/(x*y) f(1, 2) = 18, f(100, 109) = 16.03
•  » » 5 months ago, # ^ | ← Rev. 3 →   +1 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.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 Can you make it a hyperlink. Thanks Btw !! This is really helpful..got something interesting.
 » 5 months ago, # | ← Rev. 3 →   0 Didn't solve C... I'm feeling like a fool...
 » 5 months ago, # |   0 What's test case 23 in D and test case 9 in C ? :/
 » 5 months ago, # |   +18 How to solve E?
•  » » 5 months ago, # ^ |   +13 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.
•  » » » 5 months ago, # ^ |   -28 When u get the observation but don't attempt it more after seeing the modulo (fft).
•  » » » » 5 months ago, # ^ |   +32 You don't need FFT, it's a very simple dynamic programming problem.
•  » » » » » 5 months ago, # ^ | ← Rev. 3 →   0 EDIT Read the question wrong. Sorry.
•  » » » » » 5 months ago, # ^ |   0 Yeah I realised that but during contest I thought it was fft
•  » » » 5 months ago, # ^ |   0 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?
 » 5 months ago, # |   0 I faced an issue in this contest ! Read about it here(https://codeforces.com/blog/entry/61298) and present your views !
 » 5 months ago, # |   -8 Is F binary search on day and apply halls theorem for checking the validity in the binary search ?
•  » » 5 months ago, # ^ |   0 no~~
•  » » » 5 months ago, # ^ |   0 Why not? It works although one has to be careful about implementation — I got several TLEs before getting it accepted.
•  » » 5 months ago, # ^ |   0 You can try mentos theorem.
•  » » » 5 months ago, # ^ |   +34 What is mentos theorem. Couldn't get anything through google search. It will be helpful if you can provide any links.
 » 5 months ago, # |   +55 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 :(
•  » » 5 months ago, # ^ |   0 ㅠㅠ
 » 5 months ago, # | ← Rev. 3 →   +3 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
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Your solution fails on 2 1 1 2 1 
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +3 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)
•  » » » 5 months ago, # ^ |   +3 My answer is 1. And I think that's correct :|
•  » » 5 months ago, # ^ |   0 you need to calculate minimum of costs which are part of a cycle.. not its branch1->2->3->4->2.. here you have to consider 2,3,4 and not 1 bcoz 1 is not a part of the cycle
•  » » » 5 months ago, # ^ |   0 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?
•  » » » » 5 months ago, # ^ |   +2 yeah but see the test case in which you got wa.. there might be something wrong in your implementation
•  » » 5 months ago, # ^ |   +2 Just realised now that I can see that test case :|
 » 5 months ago, # | ← Rev. 2 →   -14 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
•  » » 5 months ago, # ^ |   0 Find minimum Ci in every cycles and add these minimum to answer.And note that cycle can be with one node(self loop).
 » 5 months ago, # |   0 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.
•  » » 5 months ago, # ^ |   +3 Not completely sure, but the problem seems to be the linemaxx = (ll/bb + bb/ll);maxx is an integer, and ll/bb+bb/ll is a float/double.
•  » » » 5 months ago, # ^ |   +1 Damn, that was the bug. Spent an hour trying to debug it. Anyways, thanks a lot :)
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0 actually i checked it on my computer and the problem is with this line: int maxx = LLONG_MAXxcode is smart enough to warn about wrong conversion: Implicit conversion from 'long long' to 'int' changes value from 9223372036854775807 to -1ideone example
•  » » » » » 5 months ago, # ^ |   0 Actually I have used #define int long long, so I didn't face that problem.
 » 5 months ago, # |   0 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
•  » » 5 months ago, # ^ |   0 Same, I used ceil function in c++ while in contest and it gave me wrong answer. Contest Submission- http://codeforces.com/contest/1027/submission/41788167Just removed ceil and used if else instead and it got accepted. http://codeforces.com/contest/1027/submission/41800586
•  » » » 5 months ago, # ^ |   0 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.
•  » » » » 5 months ago, # ^ |   0 My variables in ceil function were double not ints. Double variables shoudn't cause any problem I guess.
•  » » » » » 5 months ago, # ^ |   0 nn^2 can be very large so it causes precision issue try using long double that should work.
•  » » » » » 5 months ago, # ^ |   0 In any case it's not adviced to use double unless you can't do it with int.
•  » » » » » » 5 months ago, # ^ |   0 Yes, long double worked. Thanks for the help! Should've tried using long double while in contest.
 » 5 months ago, # |   +3 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
•  » » 5 months ago, # ^ |   0 Same issue here
 » 5 months ago, # |   0 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?
•  » » 5 months ago, # ^ |   +6 The memset function is highly optimized by those professional engineer, it's very fast.
•  » » 5 months ago, # ^ |   +3 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
 » 5 months ago, # | ← Rev. 4 →   0 A solution for problem C: Since it needs to form a rectangle, we only pick those sticks which have a equal-length pair. Sort these sticks, check every adjacent stick pair to find which one has the smallest P^2/S. 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. :(
 » 5 months ago, # |   -21
•  » » 5 months ago, # ^ |   +28 You could have time travelled into the past (smaller rank) if you spent less time looking at the standings xD
•  » » » 5 months ago, # ^ |   +13 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. ^-^
•  » » » » 5 months ago, # ^ |   +11
•  » » » » 5 months ago, # ^ |   +1 I solved F at the last second. XD
 » 5 months ago, # |   0 How to solve F?
 » 5 months ago, # |   +3 I wonder why my solution for problem C runs 1840ms but others solution runs 421ms???
•  » » 5 months ago, # ^ |   +2 Because in every test cases you are clearing cnt array which is O(T * sizeof(cnt)).
•  » » » 5 months ago, # ^ |   +3 Thanks for your help!
•  » » 5 months ago, # ^ |   +8 You're resetting cnt every test case even when n=4. 250000 testcases with n=4 and your solution should give tle.
•  » » » 5 months ago, # ^ |   +3 Oh...I know it.Thanks for your reply!
•  » » 5 months ago, # ^ |   0 It is not because of memset.Firstly, the complexity of the other's solution is not O(T nlog(n)) but it is something like O(106log(106)), and your complexity is not O(Tn) but it is O(T 104), and here is the problem, because when T = 250000 and n = 4 for each testcase, then you will iterate, for each testcase, 104 times while you could iterate over 4 elements atmost (n = 4).
•  » » » 5 months ago, # ^ |   0 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
•  » » » » 5 months ago, # ^ |   +1 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.
•  » » » » » 5 months ago, # ^ |   +3 Thanks a lot! I was really unable to find my mistake.
•  » » » » » » 5 months ago, # ^ |   0 Welcome :)
•  » » » » » » » 5 months ago, # ^ |   +3 ios_base::sync_with_stdio(false) Will adding this line solve the problem or I have to use printf and scanf ??
•  » » » » » » » » 5 months ago, # ^ |   +1 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.
 » 5 months ago, # |   -10 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.
•  » » 5 months ago, # ^ |   +22 Python gets other advantages such as many inbuilt functions big integers etc. So it's a trade off.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   -8 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?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +3 Why would you necessarily want to 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.
•  » » » 5 months ago, # ^ |   0 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.
 » 5 months ago, # |   0 Can anyone explain why i was getting TLE in C when dealing with double and got AC when dealt with integers AC ....TLE
 » 5 months ago, # |   0 How to solve problem D ?
•  » » 5 months ago, # ^ |   +1 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.
•  » » » 5 months ago, # ^ |   +5 what to do in this case ?
•  » » » » 5 months ago, # ^ |   0 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.
•  » » 5 months ago, # ^ |   0 Hint: When a loop is found, we can travel around the loop again to get the minimum cost.
 » 5 months ago, # | ← Rev. 2 →   0 Could anyone provide a hint for G? Also, I know F is about Hall's theorem, but how to implement it?
•  » » 5 months ago, # ^ |   +3 Hint for G — you can calculate answer for each divisor of m independently.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Formula for G: Let ordp(x) be the smallest positive integer k s.t. xk ≡ 1 modulo p. Then answer is
•  » » » 5 months ago, # ^ |   0 Thank you!
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 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: look at arithmetic progression pattern (my friend's code) look at diagonal value pattern
 » 5 months ago, # |   0 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
•  » » 5 months ago, # ^ |   0 float hasn't got the necessary accuracy. Change it to double/long double. See this test: 1 6 9998 9998 9999 9999 10000 10000 
•  » » » 5 months ago, # ^ |   0 yea this was the problem. I got AC now thank you very much!
•  » » » » 5 months ago, # ^ |   0 Also don't use float unless absolute necessary. instead of a/b
 » 5 months ago, # |   0 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 SubmissionAccepted Submission
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 5 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 5 months ago, # ^ |   0 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
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » 5 months ago, # ^ |   0 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!
 » 5 months ago, # |   +20 When does system testing start?
•  » » 5 months ago, # ^ |   0 it hasn't started even now.. Will the submissions won't be check at system tests(pretest + hacks) this time?
 » 5 months ago, # |   +8 When will the rating be updated ?
 » 5 months ago, # |   +6 When will the ratings change?
 » 5 months ago, # | ← Rev. 3 →   0 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 5Code : My Solution
•  » » 5 months ago, # ^ |   0 You don't need the break in your loop. You don't finish reading the current list before proceeding to the next one.
•  » » » 5 months ago, # ^ |   0 Thanks a lot !! :)
•  » » » 5 months ago, # ^ |   0 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.
•  » » » » 5 months ago, # ^ |   +1 This is the common pattern on codechef!!
 » 5 months ago, # |   +48 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...
•  » » 5 months ago, # ^ |   -27 you can calculate by yourself,according to the standings and your points
•  » » » 5 months ago, # ^ |   +39 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.
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   0 I don't know either,maybe the server machine needs upgrade
 » 5 months ago, # |   +29 What happened with the system test? The next contest will begin in 8 hours but the system test of this contest disappears.
 » 5 months ago, # |   +24 When will the system test start?
 » 5 months ago, # | ← Rev. 2 →   +13 The system tests are started!
 » 5 months ago, # |   0 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 5 months ago, # |   +5 when the ratings begin change?
 » 5 months ago, # |   +5 How long will take it to calcuate the rating changes?
 » 5 months ago, # |   +5 Why the rating changing still can't be seen??
 » 5 months ago, # |   0 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 5 months ago, # |   0 I have solved C bt cant come up with a solution for B.. plz help!!
 » 5 months ago, # |   0 Rating has improved.I am happy.
 » 5 months ago, # |   0 The contest has helped me a lot !!!! thank you very much :)))
 » 5 months ago, # |   0 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?
•  » » 5 months ago, # ^ |   0 Here is the Generator:https://paste.ubuntu.com/p/c9W5P7msQk/
 » 6 days ago, # |   0 I am getting RTE on test case 45 in D Anyone help Submission link : https://codeforces.com/contest/1027/submission/48291955 Using normal dfs to detect cycles