Hello Codeforces!
I would like to invite you to Codeforces Round #417 that will take place tomorrow on June 1st, 2017 at 17:05 MSK.
This is my first round. Great thanks to KAN for his efforts and help in the round preparation, mike_live and 300iq for testing the problems, and MikeMirzayanov for the awesome Codeforces and Polygon platforms.
The round is rated for the second division. Participants from the first division can take part out of competition. As usual, the participants will be given 5 problems and two hours to solve them.
I hope you will find the problems challenging and interesting!
UPD 1: Scoring disrtibution: 500 — 1000 — 1500 — 2000 — 2500.
UPD 2: Due to a technical issue, the contest is delayed by 10 minutes.
UPD 3: Contest is over. Congratulations to the winners!
Div2 Winners:
Div1 Winners:
UPD 4: Editorial
After JBMO TST (Junior Balkan Mathematics Olympiad Team Selection Test) I will participate in that contest. Hope short and interesting statements :D
Good luck!
Hey, i see you're from Azerbaijan, will you participate in EJOY this year? You're a junior right?
as i am your suffix :D i wish you best of luck in both contests and happy coding
Thank you for preparing the contest and I wish that it will be a nice contest with interesting problems.
BTW I'm curious to know how the problem-setter is an Egyptian while the testers are Russians ? :D
Because this is Codeforces community :)
Why this blog is not seen in the home page?
now it appears
You did really well in the WF, so we must be expecting some interesting tasks :D
how well did he do?
His team is the Africa and middle east region leader with 57th place solving 4 problems
No character ? It seems to have short statements :DD
Hmmm. there is a character actually :D
and what is her/his name ? :D
That will be my birthday. Can I lose 6 points off my rating before the contest as a birthday gift? So that it can be rated for me. :D
You can participate unofficially, take the first place and that will be a better gift :D
We both know that I can't get the first place in the unofficial round. :D
By the way, the time link in your post is wrong, it says 5:05 am MSK (it should be pm).
fixed
What about a "Rated" Div 1 contest?
Edit Due to Your Edit : it's only Div 2 Contest.
The link for the time of the contest in the "Contests" tab redirects to World Clock instead of the actual event timer.
It seems that codeforces system automaticaly unregistered some people that had been registered earlier!
I've been unregistered twice already...
Good luck everyone!
Shameless Promotion: I have developed a cli tool to ease problem testing during contests (for newbies like me) you can read about it here. http://codeforces.net/blog/entry/52234
the time link nowadays is not showing regional time. previously it was showing your regional timing BTW ,excited about this comtest.
if you click on the time of the contest ... you will be redirected to this World Clock... there you can find your time zone
hey, it's 14.05 here and the contest is not live yet.I also got mail related to unusual start time .Why isn't it start yet?? Pls, fixx this problem ...I already miss two contest due to this:((
Go to this link and check how much time left.
I know about how much time left. I was saying about mail from codeforces saying that contest start time 14.05
That is the time in UTC.
Is site working slow for all? or Is it just my network?
Hope that it's not slow during contest.
Something weird things happens in Codeforces..
It unregistered me...
Please, check again.
Thanks, it is fixed.
Delayed by 10 minutes :o
delayed by 10 mins :P
It won't be a normal Codeforces round if it is not delayed :)
It's been so long since the last time I have seen the score distribution BEFORE the contest.
GL & HF everyone.
:)
Due to a technical issue, the contest is delayed by 10 minutes.
Please, Don't delay the contest more than 20 min because of maghreb Prayer " E7na saymen y3ne" :"D
even no more than 10 minutes :(
we already completed maghreb in Bangladesh. But it is very near to Esha prayer and tarabi. If anyone want to participate in contest,he will miss the both esha and tarabi prayer.
lsa bdri 3la elm8reb ya 3m :D
mho kol 4wya y25roha kda m4 hnfter :"D
masri zaina y25rha zai mahwa 3ayez :D
It's very exciting!!! Good luck to myself
I wish i had a time machine!
Time+=10minutes
It shows registration is completed still the number of users registered are increasing??
Hope this round will be interesting!
Polite Enquiry, Looks like after january , codeforces has lost it's original Rounds, after appointing KAN as the co-ordinator, CSAcadmey is doing good in preparing problems of homogenous/regular difficulties.
CF ROUND GOING TOO IRREGULAR
I don't know if this fact is related to KAN becoming coordinator, but it is a fact indeed. We should have increasing scores to match increasing difficulties; and this rule hasn't been true recently...
Very strange scoring distribution / problem ordering
Many hacks in A
I know , right.
I never did any hacks before, and in this contests, I hacked 4 times in this problem alone.
Lucky that I have same way of thinking with the problem-setter :v
I don't why for the 3rd question, I was solving a[xj]+(i*xj) where i is the index of the chosen array element in the k chosen element(i ranges from 1..k). Took me by surprise looking at the increasing number of submissions. Wasted so much time over it :( PS: Can anybody tell me how to solve the question i thought C was
binary search on k
Can you describe the solution, I am asking a question different from C here
I solved it with binary search (binary search for k), but I'm also wondering if there's a nice(r) way of solving it. A lot of people solve it quickly but maybe I was just slow seeing binary search.
I thought that there is some clever DP, but it was a about simple binary search.
We binary search k — the number of items we pick and recalculate all of the costs of all of the n items. Then we sort them and take k lowest items.
The complexity is O(n·log2(n))
I eventually did solve using the same method. I am asking a different question. All the indexes are not multiplied by k. They are multiplied by 1..k depending on the position
What? I don't understand.
You are selecting k indexes. Let the indexes be x1,x2,x3..xk and so on. The question asks (a[x1]+k*x1)+(a[x2]+k*x2)... I am asking (a[x1]+1*x1)+(a[x2]+2*x2)....
why O(n*log(n)*log(n))? i think that O(n*log(n)*log(1260))
If f(n) = n·log(n)·log(1260) then f(n)O(n·log2(n))
To be serious, I didn't bother with calculating upper bound for k. So, my algorithm depends on n in a logarithmic way. Otherwise you can freely consider this algorithm having a linear complexity — the nature of codeforces bounds tells us that logarithms will not exceed the value 30.
I was solving problem same way)
I think there's no really efficient way to solve it. Use this: http://codeforces.net/blog/entry/52240?#comment-363783. Using this, you need to prove that the cost of getting k elements disregarding the base cost is O(k^3) and then the maximum number of elements will be O(S^(1/3)), I think that the best way to get the elements on this problem is from the right to the left (you need to prove this as well). Now, do a dp (a simple knapsack with some modifications) and the complexity will be O(S^(1/3) * n), O(S^(1/3) + n) in memory. Tip for proving the first part: the minimum cost will use always the first k numbers, if you consider that the second part (right to left) is right, you start from 1 and from there onwards you'll sum the sum of the first k natural numbers, that sum is O(k^2) or k*(k + 1)/2, that results in the O(k^3) bound if the part of right to left is correct.
The dp will also include numbers from right to left and then it will have the best answer if all that /\ is proved.
Thanks a lot.
Me, reading problem D
Problem E is just Staircase Nim. Nodes can be classified as two types, the "odd steps" and the "even steps" depending on the parity of their depth. The odd nodes are the ones having parity of depth same as that of leaves. The others are even nodes. Player 1 will lose iff the XOR value of all odd nodes is 0.
So, if you swap the value of an even and an odd node, you need to ensure that the resulting XOR value of odd nodes becomes 0.
Additionally, if the initial position is losing for player 1, then you can swap any 2 even nodes or any 2 odd nodes too.
Code
Task A is very good problem for hacking. Task C is easier than B. Task B is above my strength. I thought about brute force, greed with bfs from every rooms where light is on, but it won't work... So, how to solve it?
u can use DP
DP[x][entrance], minimum steps required to finish floor x..n if u enter floor x from entrance (0 if left, 1 if right)
dp
I did brute force...
1500 rooms makes O((nm)^2) possible. In fact it allows O(2^n*m). Is there an intuitive yet slow solution that is worse than O(mn)?
After finishing a floor, either you take the same stairs or you switch to the other side of the building. 2^(floors-1) <= 2^14 = 16384 possibilities.
I used dp for each floor i took leftmost and rightmost position. and either you go to the leftmost part or the rightmost part at each floor till the last one. I am scared of corner cases.
I used DP on the minimum amount of time it takes to complete each row and ending in the . left staircase or the right staircase, but there are several annoying things to watch out for, namely the stopping floor (you don't need to continue the dp after this if there's no more lights at higher floors), and the case where there's only one floor.
No need to memorize. recursion will pass. Complexity O(3^n*m). It may be less, I am not sure.
i think you can just brute force on all the possible stairs combinations in every one of them do greedy in the floor you are in (if you are at the left stairs walk to the last room that is on and vice versa with the right stairs)
I made a dp[i][2] where dp[i][0] is the min time taken when person starts from i^th floor from the left, dp[i][1] for when he starts from right.
I solved B by starting from the bottom and going up, and for each floor calculating the minimum number of seconds needed to get to the left stairs and the right stairs. Repeat until all lights are turned off.
The minimum number of seconds to turn off all lights and end on the left stairs is equal to min(R+M+1, L+(rm*2)), where R is equal to the number of seconds to get to the right stairs on the floor below this one and L the number of seconds necessary to get to the left stairs below, and rm is equal to the rightmost turned on light, as we will have to walk to the rightmost lamp to turn it off and back to the left stairs. Similarly you can calculate the minimum number of seconds to get to the right stairs.
Hope this helps
I agree that the problem looks like TSP in the beginning, so one is inclined to think of exponential brute-force, but it was mentioned that you need to switch the lights of current floor off before moving up. Therefore you can think of a DP here, just make sure to end the walk on the last floor with lights on.
It seems more like A-C-B-F-D !
how to solve C?
Binary search on answer. Put the modified costs of the items (arr[i]+mid*i) in min-priority queue and take top "mid" items to validate the "mid" of the binary search.
Does it pass the TL ? In your solution, it is O(n·log2(n)).
Yeah, I got AC. O(n*log(n)*log(n)) passes for n = 1e5.
Code
I brute-forced it!! recursed through all the possible cases at all floors. edit:for problem B
I think that this was meant for Problem B. For Problem C, if you brute force through all possible number of items, the algorithm will become O(n^2) and thus TLE.
That's problem B not C.
You can binary search for the answer. To check if you can solve the task from a given number of elements, calculate the cost of every item (with the given formula), sort them, summarize the smallest x (where x is the given number you are checking if it's possible) and check if the sum is smaller or equal than S. If it is, then answer will be >= x.
@Ahmad_Elsagheer why such an irregular scoring distribution
The swap between B and C is strange a little bit. Regardless of implementation and easy greedy problems, I believe that brute force should always be the simplest among others, as you exert no effort thinking about the optimal solution, you just try everything in the search space. That is the first thing I learned in competitive programming "brute force". I found that people always underestimate brute force (specially backtracking) solutions, however, a participant who can solve B efficiently should be able to solve it (DP solutin is not intended of course so n ≤ 15). I think the main problem is that people who started their competitive journey from Codeforces problems only didn't face such brute force problems a lot, because most of the problems will need simple nested loops.
Regarding D and E. If I found these two problems when I was Expert, I would have solved D only. In problem E, this variant is not an easy one to think about if you know only standard nim game. If you find it easy, then you are brilliant, but D should be easier. The point with problem D is the modelling part. It needs careful reading as it has many conditions. It's the deadlock problem but with conditions to make it on a tree not a general directed graph. People who gave it a try but didn't solve it told me they thought it was a DAG not a tree. Reading the statement over and over again, I found written "No child can request a toy while waiting for another". This implies that each node has at most one outgoing edge. So, the DAG now becomes a tree! If anyone could figure this out, it can be written in 10 mins.
In conclusion, this is not the standard Codeforces problem style. You can go through the gym and check the problems there. Your find different regional contests and training camps. Each of those has its own style. However, knowledge and experience required to solve the problems at the end is the same.
As an author, you always try to make a good contest by making a gap between problems. However, this gap is not always clear when you write the problems yourself specially when it is a new experience. I hope next time it will be better. But you can't always make all people satisfied. It's life, man.
Is there short solution for B?
I did Brute Force, u know, because of the small limitations. It's already quite short for me.
I'm afraid if i use shorter algorithm (e.g. greedy), I might got WA :v
Maybe i've messed something up.. My brute force code was about 130 lines and it got WA...
Well, I also got WA once from my first BF solution. I was just lucky to see what my mistake is before the contest ended. You already have the basic idea, it's a good start !
I thought that brute force would take longer to implement and I couldn't think of a case where O(n) approach would fail... got WA :(
Guess I was just too greedy
DP[i][0/1]:Sagheer now at floor i's left/right stair, takes minimum time to close the lights from floor 1 to floor i. DP[i][0] = min(DP[i-1][0] + (distance from left stair to the rightmost light)*2, DP[i-1][1] + m+1); DP[i][0] = min(DP[i-1][0] + m+1, DP[i-1][1] + (distance from right stair to the leftmost light)*2);
I passed the System Test.
Ordering should be A — C — B — E — D!
To me A was the hardest among A, B, C, E, as I still don't get what the problem is saying till now.......
I can't understand A too, I just submitted some shit looking at the picture and it got hacked :(
I got hacked twice and I still don't know whether my current submission is correct.
UPD : Wow it passed.
i submitted some shit and it got hacked then i added more shit and it passed
And it's failed on system tests.
I guess i should have added more shit
I think say signal p for road 1 is green. So if opposite to it(road 3) signal straight is on accident will happen. If 2 left or 4 right is on accident. Also if any of the signals of street 1 is on it will be accident;
Anyone who submitted 1st quickly and were happy and then got hacked?
totally agreed
Will simple recursion without dp pass TL in B?
I did it and it passed pretest. It runs in O(2^n) time, if you check every scenarios, and 2^15=32768 so it should pass without problem. On pretests it did 15 ms.
I thought about this aproach but it seems to me it's not enough. Near the end you may want skip floor, go upstairs, go through whole floor, then go downstairs and turn off light in last room near that stairs. e.g.
No.
"He wants to turn all the lights off in such a way that he will not go upstairs until all lights in the floor he is standing at are off"
omg, I missed this statement. ******
Totally forgot about this thing.
Yes, it passed! :)
For A,a guy in my room was printing "Yes" instead of "YES",did the same for "NO" too. Tried hacking and failed. Isn't printing "YES" and "Yes" different?
but since it passed the pretests, they probably allowed that too.
I don't see a reason to do that.
It's a feature of the default yes/no checker, the checker is case insensitive.
If the problemsetter is using the standard yes/no-checker for the problem, they are the same.
Depends on the checker
Maybe he redefine "Yes" to "YES" :).
When you try to hack someone, at the bottom there is a text above the "HACK" button with a text like this: Attention: The checker does not consider whitespaces and isn't casesensitive, so yes/YES, and no//NO is both accepted.
Damn problem A is really my favorite problem of ALL time ! I did my really first hacks (4 hacks in this contest) in this problem alone.
I'm really sorry for my friends in my room that got hacked by me.
for me the problem explanation is really clear. Easy problem, but people might misread the explanation.
In case you don't hack them, them will fail system test instead. But if you hack them, you give them a chance to pass system test :)
yea I thought that way, too. Hope the ones that got hacked have as positive thinking as you :v
Why sorry? you have saved them from failed system test, so they could submit again and get positive score instead of 0. :P
Well , I hacked them really in the ending of the contest (like around 10 minutes) before the contest ended. So, they might not get time to think :v (alas, frustration from hacks)
anyway , positive thinking , right.
When I have been hacked in A, just few more second to fix that stupid mistake, so 10 min is too long since.
Whoa, didn't expect that much downvotes. nonetheless, I believe the problemsetter had tried his best to make the problem explanation as clearly as possible.
Well, everyone may have different opinions.
what was pretest 6 in C? :'(
i got WA 3 times at this test
Probably you were sorting the given array without taking care of the initial indices for each value I got 2 WA in that test before the Announcement with clarification :(
That feeling when you submit A and get pretests passed and right after there's a sudden power outage... Bye bye rating.
I'll maybe get downvotes for saying this but I really did not enjoy this contest. The problems were not interesting to solve — just extremely annoying.
test 6 in problem E ?
The case when the first player has a loosing strategy without any swapping.
I understood problem A only after reading it 5-6 times...
me too , moved to C instead , but again ambiguity , very confusing this time!!
same here i moved to C instead
The problems weren't ordered by their difficulty, were they ?
I guess they should be because of the score distribution.
The queue of submissions in the end was long. I submitted 7 minutes before and the it was evaluated after the contest.
Solving B first was an extremely costly decision for me. I should have rather started with C.
Same here !! To add A got hacked
Mine A got hacked too. It seems not only our handles, but our fates match too :P
Too much I think
I thought you were talking to yourself. lol.
I solved C using greedy but failed in TC 6. Any Help please
It is binary search on maximum number of souvenirs.
You just calculate price for every souvenir for current k, sort all prices and check if sum of k smallest prices is less or greater than S.
I think it works in O(nlog(n)log(MAX_NUM_OF_SOUVENIRS))
I guess MAX_NUM_OF_SOUVENIRS is n lol.
It is about 1000 i think
sorry, I just got confused, and I think it is around sqrt(s).
Minimum sum of k elements is arithmetic progression starting at k and ending at k*k + sum of given prices
I did binary search but failed on 6.
Same was the case with me just check case 1 8 7 ans: 1 8 and 1 7 7 ans:0 0
It was not a very good contest at all, though i think problem C is a really nice one.
i think B is harder than C it was a waste of time not to start with C after A
What is the hack in problem A?
some people didn`t take union of both cases
some thought that accident is dependent on the same road only
It's hard to understand A and D. I guess I should practice English more.
That aside, D looks really fun to solve. The other 4 are quite classic (I think), and yet I f*cked up really bad.
812A - Sagheer and Crossroads worse statement ever !! It needs more description
What will be the answer of this test case in 'B'
1 11 01000000010
Is it 9 or 4. From what I learnt from the problem statement is that we can move from one stair to another stair on the same floor?
Sagheer is standing at the ground floor at the left stairs
Does anyone know why I kept getting WA on Problem C pretest #11 with this code? My idea was to just binary search for the highest k value. On each iteration, I updated the array to the new costs and then sorted and took the k smallest elements.
Check line 28.
arr[i].second * (k - prevk)
can overflow.Replace it with something like
arr[i].second * 1LL * (k - prevk)
.Good catch, thanks!
fainted from reading Problem D at mid night.. :D
Wow , very fast judging :D
By getting hacked on Problem A, I feel that if I (and many others ;) ) were to monitor the configuration of the traffic lights in the real world, so many people will get killed by accident XD
On a serious note though, thanks for hacking my solution, cswyyv864. If I didn't get hacked I would've just gotten 0 for it at the end lol
good luck bro
You too!
Problem A: ?????
this problem destroyed your work on the other probs!!!
Systesting today is really fast
very bad contest
Sad to see that N^2 log(N) also passes for problem C :(
Here, have a look!
http://codeforces.net/contest/812/submission/27499338
I think it is N * sqrt(s) * log(n).
Can explain how is it so? Cannot understand it.
Let's look at the max number of items we can take. In the worst case when every a[i] = 1 and s = 1e9, sum of k items will be k * (k + 1) / 2 ~= k^2, so it is sqrt(1e9) * N * log(N).
Aha! That is a cheeky way out :P I tried to hack his soln with the same test case as you describe thinking TLE is counted as hack.
Nice. Thanks a lot!
But shouldn't sqrt(10^9) * N * logN also fail?
It's in c++ and it runs on edge(nearly 1800 ms).
Okay, that is sad. Thanks a lot anyway :)
Actually its as ans will be > k*(k*(k+1)/2) for k values
So max value is atmost 1259. Still should exceed tle imo, but servers seems very fast.
Edit: I tried generating some hacky cases and it looks like it should have tled on strong tests. 27505850 takes over 3000ms on custom invocation even if rand() calls are unaccounted for
Probably all main tests having N = 10**5 have almost all values sorted. So sorting takes O(n) time only.
nvm
He is sorting the array for each array iteration.
So, sort takes NlogN * (no. of iterations), which happens to be at max sqrt(N) for N = 10^5. So, its N*sqrt(N)*logN for larger N.
Yeah, you're right
what's wrong with that complexity ? Log(100000)^2 x 100000 is barely over 25 Million and that passes in under a second!
It is not N (logN) (logN) I guess. It is N*N*logN
Oh sorry i read your first comment wrong there for i didn't see the code :)
Yes,just as lohit_97 says,this code used iteration on the number of purchased goods instead of binary search.So it's not the intended solution.
He used the fact that
Yes I understood that, but then that passes on edge time limit, I guess that was not the intended solution. But yeah, anyway, it passed.
I swear I'll never underestimate Div2-A again...
One of those contests where you think you want to ask for a clarification but don't even know where to start.
Compiled E, just 1 sec before contest ended. Hope I don't get AC later.
This guy literally crushed all the pedestrians xD
lmao
you got this...
even after solving all !!! :P
Problem statements were very unclear! One reading was not sufficient at all :(
in C atleast one ex should be given to clearify which index is xi's. i spent 25 minutes figuring out what's wrong
Weak pretests for A :|
you don't actually need DP to solve B , it's overkill ..... the problem can easily be solved with straight forward Brute Force in a recursive function .... anyway ,thanks for the problem setter i think the problems were nice, keep up the good work!
in terms of code length, both approaches are equivalent, i guess. i dont think its overkill
sure , but i was talking about the difficultly of the solution because i noticed that C was solved more than B.
deleted , sorry my mistake :3
Input is invalid, should be 3 3 in first line.
Such input is not possible, since
m
is the muber of rooms in each floor, so there should bem+2
columns in the input.deleted
Good contest.Although I think the statement for some problems is too long or unclear,the quick system test and quick editorial are worth appreciating.Thank you Ahmad_Elsagheer for preparing the wonderful contest!
Solution to Problem D is wrong. Consider the following test case:
4 7 9 3 4 5 4 6 4 7 1 1 1 2 2 1 3 2 4 1 4 2 1 5 2 6 3 7
The solution gives 4 0 2 as result, which is obviously wrong.
this case is invalid because child 4 can't request toy 2 while waiting for toy 1
Goddamn, I got WA in B because i accidentally used && in bitmask instead of &, I hate such situations((
How do you use a bitmask for B?
To enumarate binary strings of len n
If in index i there is 0, than I use right ladder to get to floor i + 1, else i use left left one
If we encode 0 as choosing left staircase and 1 — right staircase, then we can encode all of the moves as a 15-bit number.
Yeah i did the same, but my code ended up to be more than 150 lines...
MikeMirzayanov[user:MikeMirzayanov] please don't give another chance to this question setter
What the hell ???
I mean this wasn't the greatest round of all time but don't you think you're being too harsh.
You are right there were a few problems but the guy did his best and this is his first round cut him some slack will ya ?
I think if the statements were clearer and the pretests for A were stronger this would have been a great contest it wasn't that bad.
:)
Only neverfirst solved all problems. This is great result!
His handle is justified :p Even after solving all problems, 2nd position! :p
https://ibb.co/bZ5YJF Such proof! Much Wow. xD
Can someone explain, why in this test case 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 in problem A jury answer in "NO"?
nice contest
I don't get the rating system. Can anyone explain how it works? I solved A task in 36 min and got -22 rating pts. Is it because my solution was sent too late?
http://codeforces.net/blog/entry/102?locale=en
thanks, missed this
Well, actually once I was first also alone solving all problems. Someone can post standings for this contest. If there will be +100 I will post it myself.
I wanna know why almost coders who's [personal handle/team handle] something like "Loser,neverfirst,..etc" always got high rank and actually becomes "winner,first,..etc"
That's the point that I never got first place at some valuable olympiad.
Never means never.
You should have a nickname SometimesNotFirst.
Mike mirzayanovCF should follow csacademy in terms of problem statements.
please consider the following case in problem B
the code which you posted here http://codeforces.net/blog/entry/52318
gives an answer of 73 while it could be just 61
using the above inputs you can check the code you wrote and it gives 73
using the following sequence by following the shortest path and using only stairs for moving up and down shows how it could be possible for just 61
this case i made randomly to check my algorithm and to check wether it provides a right answer like yours or not
and please correct any pretest that have this mistake -If it was a mistake- and maybe I am wrong if so please enlighten me
"He wants to turn all the lights off in such a way that he will not go upstairs until all lights in the floor he is standing at are off."
Your solution goes to the second floor before turning off all the lights on the first floor.
Can't problem C be solved by using DP? my initial thought was that it can be !!
I don't think it has a DP solution, because the costs used to find the optimal value depends on the optimal value itself.
and (( neverfirst )) won the second place :)