Hello, Codeforces!
Today, 17th of October at 17:35 MSK Codeforces Round #377 for second division participants will take place. As usual, first division participants are able to participate out of rating.
The round problems are taken from the problemset of regional stage of the All-Russian school team programming olympiad which was taking place yesterday in Saratov. The problemset for onsite competition was invented and prepared by Mike MikeMirzayanov Mirzayanov, Ilya IlyaLos Los, Danil danilka.pro Sagunov, Vladimir vovuh Petrov and Roman Roms Glazov. We are thankful for pre-solving competition problems to many of Saratov State U teams' participants. One problem in the round will have a bit harder version than at the competition.
Nikolay KAN Kalinin and Tatyana Tatiana_S Semenova helped us preparing problems and translating for the round — thank you! Thanks to Mike MikeMirzayanov Mirzayanov for the Codeforces and Polygon systems.
There will be 6 problems and 2 and a half hours to solve them at the round. We wish you the best luck!
If you are a participant of the yesterday competition in Saratov, please, do not register for the round and do not participate in it, also do not discuss the problems before the round ends.
UPD Scoring: 500-1000-1500-2000-2000-2500
UPD2
Congratulations to the winners!
Div.2
Div.1
As soon as the time of registration to the round was a bit early, there may be some first division participants taking part in a line with a second division participants. There are not many of them, so (and due to technical problems) this will be left as is.
Due to NEERC subregionals in Saratov, rating will be updated tomorrow.
UPD3 Editorial
A fibonacci number Round... 377 is 14th fibonacci number.
It's also:
sum of squares of first 5 prime numbers,
25-th semiprime number,
7-th centered octahedral number,
47-th Sophie Germain semiprime,
and thousands more on oeis :)
And a whole number round as well.
Bracing myself. Downvotes are coming
Please don't comment inept things.
Ejemmm... Not really...
Not sure if this counts
It was floor(pi) round.
It was floor(pi * 100)
My contribution points are too high. I need to bring them down.
ROFL
:D :D
is it rated!?
In the registrants list I see a few Div. 1 participants that are registered officially (there is no "*" before their handle).
Here's an example.
I think they weren't in div1 when they registered for the contest (before yesterday's rating changes) :D
I wonder if their ratings would change today :P
Daniar LOL
Oh, wait, I AM SUPERSTAR NOW
me too
Today I will leave grey for good. ..... Or not XD
Commenting here will not help you to leave gray.Try to give focus on problem solving. That will help you to leave gray. wish you to be green :)
indeed.
good luck Bro
He seems he's a green coder now ☺ congrats man
mission accomplished
congrats
Please shift the contest timing by 10-15 minutes..
3 Rated contest in 3 days (Round 375,376 and 377 ) and (15,16,17).
375-15
376-16
377-17.
it's a record of codeforces 3days in a row reated contest and also interesting 5-5,6-6,7-7;
The Graduation Year field in the application form only accepts numbers under 2010.
Fixed, thanks!
The platform doesn't allow me select my country. Please resolve this issue. Thanks.
Nigeria existed, why do you want to create a new Nigeria?
After updating my country to Nigeria (in settings > social) and clicked "Save changes", that's the dialog that appears. If Nigeria already existed, then why pop out that dialog identifying Nigeria as a new country? Then since it is identified as a new country, I go ahead and fill in its 2-letter code and click "Save", then I get "Code is already in use". How does that tally? Hope you see my point.
Change your country to "Нигерия"(copy this, its Nigeria in russian). It will help
Why there is not rating update for Techno cup round for some Div 2 users who registered late?
One problem in the round will have a bit harder version than at the competition.
There will be 6 problems
*Grabs popcorn and get ready for a hell level Div2F.
It's not necessary problems to be from A to F, it could be dobule D (as it was before (D1), (D2)) or any other problem can be doubled
Pay attention, Problems may be not sorted by difficulty.
Let is delay 10 minute as usual :)
Its showing i'm an official participant in this contest !
i had registered yesterday when i was still blue :p
Bug in CF ?
http://codeforces.net/blog/entry/47816?#comment-321100
Yes!
he could have had a breakfast and a supper, but a dinner, or, probably
what??
Here the "but" refers negative.
Such as: I will go anywhere but there.
Not an old issue, but there should be more efforts on translating into English statements.
Round is very nice !
I only didn't realized that in second task case n=1 answer is always 0 :( Actually I thought it is special case and add one extra if :D You could put n>=2, that wasn't very clear.
Same with me , got hacked , lost around 400 points -_-
Anyway problem set were good this time
RIP all C submissions with initialization of ans < 2e18, and then taking minimum.
How do you solve C?
Code
Let M = max(b, d, s)
If M = 1, answer would be 0.
Now I considered all 9 cases, whether he enters before B, before L, before S and leaves after B, after L, after S. For each case, find what should the exact number of meals should be, and subtract the current value of (b, d, s) and take minimum.
Not sure if my code is correct, but i take max(b,d,s) — 1, which is the number of days of maximum full 3 meals. From there just minus the rest if the number of meals is smaller than that
Number of days is max(a, b, c), so you can calculate answer easily.
take input in an arry and sort it.
make 3 cases : 1. when all are equal 2. when only last 2 elements are equal 3. else and proceed. happy coding. :)
This passed pretests. Not sure if it'll pass the full tests. http://ideone.com/EgztAG
If there are numbers b , d , s
then if mx = max(b , max(d,s));
then, answer = max(0 , mx-1-b) + max(0 , mx-1-d) + max(0, mx-1-d) :)
I initialized ans=-1 :'(
In B, what is the answer for the following testcase?
n=1, k=5 and a[1]=1
should be zero as it was mentioned arr[0] and arr[n + 1] = K
Missed that part. :(
I will get a wa for handling the case n=1 separately.
Almost all Hacks for B is n=1 ! :) The answer should be 0...
For task C, why is 3 1 2 = 1?
the extra breakfast is from the last day. you have 2 days of full 3 meals, and 1 day with only breakfast
But if you have 2 days of three full meals, won't you miss dinner twice?
For 3 1 2 Come before breakfast today and go after breakfast on 3rd day(day after tomorrow ) ,In this way only one lunch is missed.
Oh, I see. Thank you!
so it looks like this day 1 : b d s day 2 : b d s day 3 : b
sum up 3b 2d 2s, so you miss dinner once
Hack case for C ?
I hacked one with 0 3 1 ans: 3
0 1000000000000000000 0
n=1 , ans =0 while some people printed k-a[0].
eg:- 1 10 2
can someone help me understanding the output of 4th sample case of problem C ?
input
1000000000000000000 0 1000000000000000000
output
999999999999999999
You can go into the sanitorium just before the supper and leave just after breakfast.. This case is similar for cases like N M N where N > M.
okay.. I guess I was moving in the wrong direction I guess.
thanks for the explanation.
Approach for problem E?
I am pretty sure greedily finding matches for the next smallest adapter works. Keep computers in a set/dictionary that you can do O(1) lookup on, and remove them when an adapter matches with them.
My solution goes as follows:
Sort all the computers and sockets. Then, find all the pairs where socket power is the same as computer power. Because of the sorting, this can be done in O(n+m) time with two indices. (By moving an index forward when its power is smaller than the other's, and skipping if the socket/computer is already in use). Then I add adapters to all of the sockets and repeat, finding all the matches. You only need to do this around 31 times until all socket powers will become 1.
My code was the 5th fastest overall.
Edit: An identical solution is proposed in the editorial.
Can you prove this greedy solution please?
Sure, I'll try.
Because one socket can only be used once, and a computer only requires one socket, there is no situation where we shouldn't join a socket and a computer if we can.
The task description also defines that we should use as few adapters as possible. This is accomplished by checking smaller amounts of adapters (starting with 0) before trying more. It is always better to connect a socket to a computer earlier, when there are fewer adapters, than later. So a socket with a smaller power will be connected to a computer before trying a socket with more power and therefore more adapters in between.
Thanks a lot, I don't know why I found that hard to prove that during the contest (Maybe due to pressure).
How to solve C ?
let n=max(a,b,c)
now depending on his arrival and leave time, there can be seven possiblities for number of breakfast, dinner and supper available. they are:
b=n,d=n,s=n b=n,d=n,s=n-1 b=n,d=n-1,s=n b=n-1,d=n,s=n b=n,d=n-1,s=n-1 b=n-1,d=n,s=n-1 b=n-1,d=n-1,s=n
for each of these cases , find the minimum number of foods he can miss
Number of days in sanatorium = max(a, b, c).
Then you have 3 case: 1. max = a, it means that you came in morning, also it means that you leave morning (you miss dinner and supper in last day because it's optimal)
Then easy to calculate answer = max(0, (a — b) + (a — c) — 2)
The same logick for other case.
Sorry for poor english.
Suppose the given values are a[0], a[1], a[2]. Sort a and subtract a[0] from all the elements. Now the answer is
This is because any triple b, d, s where difference of any pair is at most 1, is valid.
I tried F using Bridge Tree + Euler Tour got MLE
I saw people getting AC using the same ! can someone help ? here's the link to my code
http://codeforces.net/contest/732/submission/21541116
Hi,
I am guessing that the issue might be because of the implementation of bridge tree mentioned in my blog. It is not very memory efficient because of the global queue used. I realized that once when i got an MLE in a bridge tree problem. You can try changing it with a more memory efficient implementation. For eg, I wrote this better implementation. You can have a look at this:
http://pastebin.com/c7hMLzVw
Edit : Updated the blog as well.
https://tanujkhattar.wordpress.com/2016/01/10/the-bridge-tree-of-a-graph/
Yes, your blog was surely helpful !! Thanks for the update :)
Problems difficulty is perfect.
What's the idea for solving F ?
if u remove all the bridge edges, u'll get different connected forests. Choose the forest with maximum number of nodes as the center and direct all other forests towards this since there is only one way to orient the bridge edges. So choosing the largest forest will maximiize the minimum sum required.
Then Do a euler tour to give the orientation by adding edges between nodes that have odd degree. Nodes having odd degree are always even.
similar concept was use here : http://codeforces.net/contest/723/problem/E
The overall complexity is of the order O(n+m).
My idea on F.
We can see that it is optimal to let every biconnected component to form a directed cycle as this won't affect it's potential on other biconnected component. So we should always try to form a cycle for every biconnected component first.
Then we contract all biconnected component and this would form a tree. Now we can do binary search for answer.
Every cities's ri will have at least x. As every node in tree represent a biconnected component in the graph, ri will initially be no. of cities in biconnected component i. Lets consider node u, if it's ru is more or equal to x, it should let the edge between u and its parent and direct it to u. So its parent's r value will be increased by ru. Else, the edge should direct its parent.
Now dfs again and for every edge that are directed to its child, we can increase its r value.
So if every ri is >= x, x can be obtained.
edit :
lol I failed system test because I read the problem wrongly and thought ri is the number that cities can go to city i. But the idea is still the same for the problem.
ac code : http://codeforces.net/contest/732/submission/21563511
Well I passed the system testing with a pretty simple solution. First of all we should notice that the answer of the problen is the maximum size of a bicconected component. Then to get how the edges will be directed, first you convert each bicconected component into a strongly connected one and you are left with the edges between the strongl/bi-connected components. It's simple to see that the compressed by strongly connected component s graph is a tree. So you make the component with the maximum size as a root of the tree. Then you make all edges between the components to go to their parents so that you can reach the root from each one of them. In this way you get alogN (N+M) solution.
PS: I wrote an O(N+M)logN one because I used a map to easily access edges but this can be done in O(N+M) too.
I am surprised that no one mentioned tarjan algorithm, I think that's the most straight forward way to solve it as you may have already a template coded.
All you have to do is to find the minimum among the most compressed node in each connected component, and memorize them as roots. Initialize them as the root and reverse all the edges, there's your answer.
For E, why is a solution, that iterates through the number of adapters on all of the sockets at once, assigning greedily to each socket whenever a PC with the same power exists, wrong?
I can't find a bug in my code so I guess it's in my approach.
Code: http://codeforces.net/contest/732/submission/21541488
When you sort pc[], you lose the ordering of the computers. There is no way to output the computers in the right order in line 3 of your output.
Thank you so much, I'm an idiot xD
Can anyone explain how to do D? Was it dp?
Binary search
Oh ok thanks!
Binary search. It's easy to verify if the first x days works by choosing the last test day for each exam in those x days and seeing if there are enough days to study before them.
How did you check? Did you use a priority queue?
Just sort by latest exam day <= x, and do exams in this order.
I went through the first x days backwards to get the days I would take the test. Then I went through the test days forwards. If it was a test day kept track of how much time would be used for that test. If there is not enough time to prepare, l = mid and try with bigger x.
Can you give me your code?
Not accepted yet: http://codeforces.net/contest/732/submission/21539380
Do a binary search over the number of days starting from day one to day X
To ace M exams you need at least M days + the required days to prepare, i.e. lower bound L = M + sum of required times
Now, to check if it's possible to do so in X days, start from the last day and do the following:
tests = 0
days_needed = 0
if it's a day off OR we took the test already:
else:
After last (which is the actually the first) day, check if tests is equal to number of subjects AND days_needed == 0
You can binary search the answer. To check if a particular number N of days works, we can assume we take every test at the latest possible opportunity (within the first N days). If not all the tests can be taken in that time, or we don't have time to study for all of them (and this is pretty easy to determine), then N is too small.
Have any bruteforce solution of D(without binary_search).
Here's my bit complicated approach : Iterate on the exams, and maintain count of total free days available till now, which are not assigned.
When an exam comes that has not been taken, if its required days are <= count, then mark this exam as done(for now), otherwise, we have two choices, either forcibly take this exam on this day by marking some of the previously done exams as false and adding (their preparation days + 1 exam taking day) to count , or just not assign this exam for now.
We will try to do the first choice if its possible by cancelling some previous assigned exams first. And also take care that any exam that we are cancelling, its next occurrence exists and is before next occurrence of our current exam, otherwise we can just wait to assign current exam on its next occurrence.
To get next smallest occurences of previously done exams, i have used a set. As we are cancelling exams, we remove them from the set. Also, when assigning an exam, insert its next occurence in the set.
Code
The same approach can be taken to linear complexity:
In the binary search idea, we first guess the answer (the earliest day when we can pass). Similarly, in this approach, we guess the first day we can pass, except we guess sequentially.
Suppose day D is the first day in which all subjects have appeared. Then to check if we can pass everything by day D, for each subject, we take note of its last exam date. (It can be proven that it does not hurt to take any exam late) For each day G (for guess), we check whether we can pass every exam we sit for up to that day. Specifically, the number of days required to pass every exam before a fixed day is the number of exams before the day + the number of days required to study for those exams. If we are able to pass every exam up to day D, then we output D. Otherwise, there is a certain earliest day, say D2, for which we are unable to pass every subject before that.
The problem at D2 may be resolved if G increases: since we always sit for the latest possible exam, we might shift an earlier exam to after D2, hence solving the problem at D2. Specifically, for each exam we shift to after D2, we are reducing the number of days required at D2 by the number of days required to prepare for the exam + 1.
Whenever D2 is no longer a problem, we can check in constant time whether D2+1 is problematic (if we maintain, for the current G, when the exam for each subject is). When D2 is G+1 (i.e. D2=G is not a problem), then it means we have found the smallest G in which we can pass all exams.
Since every increment of G also takes constant time, this algorithm is linear.
Submission no. 21537091. I think this is supposed to link: submission:21537091
That's my solution:
In other words, at first we choose the safest variant. Then we greedy try to pass last exam earlier.
You can see my solution here: 21584671
Also, the same idea is used in 722D - Generating Sets
Last minute! :D
Failed in the system test though :p
But the feeling was awesome for sure.
Yeah, it was awesome, but this feeling is gone now :(
How to solve D
I first verified if it can be done in n days by taking last possible day for each test then iterating in reverse from nth day to 1st day and checking if ith day had an passed exam in my solution the can we pass that exam in any previous option i used segment tree + lazy for this can someone please tell me where am i going wrong
binary search on the number of days . If you want to check if its possible to pass all exams in X days , find last occurence of each subject in [1,X] and take exam of each subject on its last occurence .
Tried that approach wrong on pretest 4 .. any idea what the test case was ?
If might have started search from x where d[x]=0.
Binary search!
This is interesting. Eveng though problem D and E worth the same amount of points, each minute problem D decrease its score by 6 points and problem E by 8 points.
I wonder how to write a checker for problem F???
Build the directed acyclic graph of the strongly connected components and take the minimum size of a sink connected component.
Just finding all strongly-connected components having no outcoming edges to another SCCs, and determining minimum between their sizes.
in problem B, when n=1 : (input) 1 3 1
can i get your guessing output?
i believe : 2 3
why system said? : 0 1
i think some mistakes in problem B description ..
Empirically Polycarp learned that the dog needs at least k walks for any two consecutive days in order to feel good
.There is no 2 consecutive days here.
i cant disagree your reply !
objectively i didnt understand problem fully :D thx for your reply :)
system test taking alot of time.
Solved D using binary search in contest.
But I guess O(n) should work.
Let extra be a variable that stores how many days we have to spare. Traverse from 1 to n.
If d[i] = 0 or vis[d[i]] = 1, extra+=1,
otherwise extra -= a[d[i]] and mark vis[d[i]] = 1
If at some i, extra ≥ 0 and we have visited all m subjects and d[i] ≠ 0, print i. AC
Nice idea!
Can you please explain what the checking function is doing ?
Wouldn't it fail on sth. like this?
Woops, you are right.
No it doesn't. Here's AC code. Hardly 20 lines.
I think the tests are lacking:
10 3
0 3 2 1 0 0 0 0 0 1
2 2 2
edit: Simpler case
6 2
0 1 2 0 0 1
2 2
True that. Test cases were weak and thank god I went with binary search. It was anyways nice to think this way. :D
Tests are very lucky) I have solution O(n), which working incorrect but it's AC)
I have submitted using above method and it got [AC]. see the solution over here. http://codeforces.net/contest/732/submission/21548517
you are assuming that we need to do an exam whenever it is possible to do it. But this is wrong, be cause you could save those days for some other exam which has to be completed first. I hope you understand what i said.
counter testcase: 10 3 0 0 1 2 3 0 2 0 1 2 1 1 4
6 2 1 0 0 0 0 2 1 1 I think the answer should be -1 in this test (your code output 6)
Simplest Solution for problem 'C':
public class C { public static void main(String args[]) { Scanner sc = new Scanner(System.in);
}
check this http://ideone.com/EgztAG
Still you have used sorting there which obviously won't matter. Though both solutions are good.
Why am I hacked?It gives me right answer: http://codeforces.net/contest/732/submission/21523956
http://prnt.sc/cvi72s
initial value of
ans
can be any number :)UPD: I'm wrong sorry
ans wasn't given an initial value to 0 It outputs a random number if the program didn't enter your second loop
It would give random number in any case, because ans=random ans=random+something Output:random+my_answer But it passed pretests
:| ans is global, so it is initially 0.
I ran your code on codeforces's custom test and it is answering currect to the hack!!!
Maybe they check only the last solution (this is not my last) ?
C had an O(1) solution :
Can you explain it?
lets denote t[0], t[1] and t[2] as total number of meals of type breakfast, supper and dinner that vasily was present at the Sanatorium and a[0], a[1] and a[2] as the number of meals he ate.
My ans is (t[i] — a[i]) for i from 0 to 2.
I claim that
For any i,j : abs(t[i] — t[j]) <= 1 (convince yourself of this)
Atleast one of breakfast, supper and dinner will not be skipped at all (Since we need to find the smallest bracket when vasily was present at the Sanatorium)
So atleast there will be atleast one i such that t[i] == a[i] is true
i set the t values for other two meals equal to t[i]-1 and found the difference with a[i].
I am sorry, but I don't fully understand the meaning of t[i]. Shouldn't they all be the same?
I mean
t[0] = t[1] = t[2] = max(a[0], max(a[1], a[2]));
?
Hey, Let me explain. First, the use of sorting is to find the maximum number of days, that are possible. Suppose, If the number of dinners are maximum, then we can enter just before dinner on a day and leave just after having maximum number of dinner. This leaves the possible consumption of other meals to be Total dinner — 1. If you think carefully, you'll see that the same would be for breakfasts and supper as all the things are circular.
So, if m is maximum of (supper, breakfast, lunch), assuming all to be different, this leaves maximum of m — 1 days for other two types.
Hey, my submission for D is wrong but Accepted.
http://codeforces.net/contest/732/submission/21545380
because in this test case,
the answer is -1 but my program out 4.
What should I do?
Your program actually gives -1 on the Codeforces Custom Invocation.
Oh..., true.
I beg your pardon.
So, is my program right? Hmm...
http://codeforces.net/contest/732/submission/21523845
Any idea why this fails for Div2 B ?
Because in your template:
It also loops from reverse to start incase x > y i.e. at pos 1 and 0
your rep(i,x,y) is defined in such a way that in this case it runs from 1 to n-1 i.e from 1 to 0.
kill me now
would be nice to be a specialist i guess :/
You can't get -140> rating change I guess.
why not ?
Can anybody help me plz? for problem D, i think my program isn't working right but it was accepted by main tests! here is the code :21544206
worst problem set and description ever
one of the worst i think :)
you are enjoying your right to downvote right? Downvote me then. I have nothing to do with my contribution. You better tell your friends to upvote you.
C was the worst .
I am a native English speaker and this contest is the first time I realized dinner != supper. Had to look it up to confirm. (Problem was clearly stated though)
Waiting For Rating Changes...
Wow, my E got TLE on the largest case
http://codeforces.net/contest/732/submission/21540600
I was using cin/cout so i tried changing to fast i/o.. was not enough...
Then I went back to the original submission and only changed stl::map for stl::unordered_map and it got AC...
http://codeforces.net/contest/732/submission/21548475
Seems that it is true that hash table are O(1)... I thought the hidden constant would not make it actually faster... sad to learn it this way, but better for next time!
Does round is Rated ?
waiting for rating changes :/
not waiting
Chill, I also got "Wrong answer on test 43" in Problem B.
Waiting for the RATINGS!!!!
was it an unrated contest? 377(div-2)
!!! Waiting for the rating change....
Is it rated contest or NOT?
Nobody knows..
UPD: except MikeMirzayanov
MikeMirzayanov knows
I think he doesn't know yet :D
Stil waiting :)
F5 key is is saying .. plz stop... but still rating is not updating
For the first time, a specialist is asking this question, and gets upvoted.
round rated or not ????
Not specify in blogs that round is rated or not ? even round taker was not online till last 5 hours.
regular CF round is always rated. foolish like you always makes it complicated
bro, one regular CF round of div-1 was declared unrated after contest end due to some problem in test cases of one proble.
If a regular round is declared unrated, you will surely get an announcement then during the contest
"As usual, first division participants are able to participate out of rating."
If they say that div1 participants are out of rating, that means div2 participants are in rating :)
why new rating didn'y apply yet?!!
Some people say that tests in D are too weak
why it will be unrated? I think rating will be given quickly. Plz------give the rating as quick as possible. After a long time awake for rating.
http://codeforces.net/contest/732/submission/21527638
http://codeforces.net/contest/732/submission/21540134
The two codes above got accepted on problem D, but in this case
8 3
0 0 1 2 0 0 0 3
2 2 1
the first one answers : -1
the second one answers: 8
the correct solution is -1.
Am i understand wrong the problem?
if problem D data set will normal,it will be rejudge.why it will be unrated? Hopefully judge panel will be fixed soon as possible.
if it is unrated, it'll be pretty depressing :(
I know how you feel
not for me xD
I think he wants it to be rejudged, not unrated
Why they not share in social what happen exactly ?
If you rejudge it please as soon as possoble rejudge it.otherwise give rating.
this one too http://codeforces.net/contest/732/submission/21540460
some people just comments for up vote(contribution)
I think you too.....
You are one of them :)
Is it unrated contest?????
The author of this contest is not announce it is unrated.So everybody waiting for their annouce.
8 3
0 0 1 2 0 0 0 3
2 2 1
this test case gives different answers for different solutions. but the correct answer is -1
Due to NEERC subregionals in Saratov, rating will be updated tomorrow.
how did you came to know that ? is it confirmed? why they hadn't posted this? and last, what is relation between both(neerc and cf rting)?
The blog text was updated
Maybe data set for problem D is weak.. Accepted output for the following test is -1. 16 3 0 0 0 1 2 3 0 0 0 0 0 0 0 0 0 1 3 3 3 But many accepted solutions are giving other outputs.
Due to NEERC subregionals in Saratov, rating will be updated tomorrow.
Can any body tell me why i took TLE in problem D :\ 21538484 it is n log n
21538484 is a "compilation errored" code and it's on problem 732E
yours is : 21538383 :)
and I'm kinda sure that the problem is your binary search.try to return your function when l==r.and in the last line of function I guess it should be bs(mid+1, r);
I didn't read the whole code so I might be mistaken.
I think it's better to implement binary search like this BS f(n) is a boolian function.
How to solve E? I see some greedy solutions but don't know how they work correctly. :/
After the round was over i was going through the solutions of some of the people to problem D and found one of the solution inspite of being wrong is accepted. Solution number 21543232 is wrong. For the test case 10 3 2 2 2 2 2 2 2 2 2 2 1 1 1 The solution gives the answer as 6 but the answer should be -1. Sadly the test cases are not strong at all.
I think that it is not fair to get a TLE in Problem D using Java , and an Accepted using C++14 with the same code.
Will it be rated for the 3-4 div1 participant that were considered as official participants ?
I was trying F thinking i am an unofficial participant instead of trying E, making it rated for us (atleast for me) won't be a fair !
why they're not fixing your bug? really unfair for you
I posted about it !! lets see if it gets resolved.
i suggest that MikeMirzayanov should give every contestant +50 for nothing , thanks
I think Codeforce should re-judge problem D. And if you do,please include the test case below:
10 3
0 0 1 2 3 2 0 0 1 2
1 1 4
Just a slight modification of first test case.
Question. Problem B.
if
n=1
, Haven't I to satisfy the dog? I guessed, when I have input1 10 1
, I should walk9
to satisfy the condition (to make total walk 10), but jury's answer is0 1
Please let me know why..He says in the statement that: "You can assume that on the day before the first day and on the day after the n-th day Polycarp will go for a walk with Cormen exactly k times."
Basically when N = 1, you can assume that the K times condition has already been satisfied so you don't really need to do any extra walk.
I missed that during the contest too. Got a WA on test 43 and literally removed the part of my code that dealt with the n = 1 condition and got AC. Lol pretty frustrating, but it happens :P
WA: http://codeforces.net/contest/732/submission/21528483
AC: http://codeforces.net/contest/732/submission/21546645
Thank you for nice answer!
On the last Intel contest i've done 1311 points and then i got more 31 rating points, on this contest i've got 1314 points but i've lost 75 rating points. Why?
Look what rank you got last time and now. There is a big difference between 1402 and 2874.
What about the fact that now may have more people which can be better than me? Instead of getting worse i just keep on the same level, but there are better people now. The rating should be about me not about the others.
rating about you but hard level of problem about the other =))
Was Problem D Rejudged?
NO
Rating changed with all of wrong accepted solutions :(
For problem E I got the right idea but forgot to sort the sockets by its value, so sad.
I think in this round solutions don't checked with good tests, I found two accepted solutions in D problem, but solutions was wrong. Sorry for my poor english! My tests: 6 2 0 0 1 2 0 0 2 2
7 2 0 0 0 0 0 1 2 2 2
This comment is right. Why is my solution Accepted? My solution is wrong.
first solution is -1,second is 7,right ?
My solution: in: 6 2 0 0 1 2 0 0 2 2 out: 6 //this is wrong in: 7 2 0 0 0 0 0 1 2 2 2 out: 7
my is -1 in first and 7 in second
code already AC
My solution is AC to
I want to aks what is the meanning of d[i] in the question D ?
It is the number of subject or the sum of passed subject ?
(eg: if d[1]==3, it says that 1st day could pass 3rd subject or 1st could pass three subjects no matter whatever the number of subject ?)
plesase test this: 10 3 0 0 1 1 1 0 1 0 1 0 1 1 4
The number of the subject which could be passed on day i.
Answer is simply -1 since 2nd and 3rd subjects cannot be passed on any day.
In B I was considering n=1 case separately and was printing k-a[0] if a[0]<k. I later realised my mistake and hacked 3 submissions.
My first hacks :D
When I waked up and opened CodeForces website, I was so excited to find I turned purple :D
It's interesting and a pity that I have never got a 4/5 or 5/5 after 29 rounds, maybe I will jump back to div2 soon and get my first 4/5.
Can anyone explain to me the greedy approach of E and why does it work? and also F please :D
In problem E, I don't understand why my solution is using a lot a memory.
My solution is simple, first I sort all sockets, so for each socket e reduce it (ceil(x/2)) trying match it with a free computer.
to do it, I use a
map <int, vector <int> >
(vector of indices of PC's with power X). So, all memory that I use is O(n) in map + (n+m) of the input.Link of Code
when will the editorial be posted?
hello, I have participated in contest #377 Div. 2 I have One test for Problem D, many of codes can't pass this but they are still considered as right, please check it. 10 3 0 0 1 2 2 0 2 0 1 3 1 1 4 the answer is 10 but some codes that passed the testes are bringing 9 ^_^
you make mistake 10 3 0 0 1 2 2 0 2 0 1 3 1 1 4
day 1 preparation for first exam day 2 preparation for second exam day 3 participate in first exam day 4 participate in second exam day 5 to day 8 preparation for 3rd exam day 9 participate in 3rd exam.
Now how you are true?
day 9 participate in 3rd exam.
How?
cause in day nine you can participate at least in one subject. if i ask you why he cannot take part? don't get me wrong. if you show me the point why he can't then it will be easy for me to explain. within first 4 days you can complete first two exam. then 5 to 8 (4 day) for preparation for third exam and day nine 3rd exam. 1 indexing
UPD:" it is not necessary to prepare continuously during ai days for the exam number i. He can mix the order of preparation for exams in any way." from problem statement
first day you take preparation for first exam. since in day second you can't participate in exam; you can prepare for 2nd exam rather than rest.
You can only take exam ai on day i.
Does anyone know What happened to acm.sgu.ru?
Where is the tutorial?
Am I the only one still waiting for the editorial?
hope this one can help you :) Your text to link here...
The one you gave us is round 376 editorial. This is round 377.
Auto comment: topic has been updated by danilka.pro (previous revision, new revision, compare).