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

Because this is Codeforces community :)

now it appears

how well did he do?

Hmmm. there is a character actually :D

You can participate unofficially, take the first place and that will be a better gift :D

fixed

Edit Due to Your Edit : it's only Div 2 Contest.

I've been unregistered twice already...

if you click on the time of the contest ... you will be redirected to this World Clock... there you can find your time zone

Go to this link and check how much time left.

Hope that it's not slow during contest.

Please, check again.

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

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...

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

binary search on k

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·log²(n))

I was solving problem same way)

I think there's no really efficient way to solve it. Use this: http://mirror.codeforces.com/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.

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...

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.

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.

I brute-forced it!! recursed through all the possible cases at all floors. edit:for problem B

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.

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.

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

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.

I can't understand A too, I just submitted some shit looking at the picture and it got hacked :(

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

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.

but since it passed the pretests, they probably allowed that too.

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.

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 :)

Why sorry? you have saved them from failed system test, so they could submit again and get positive score instead of 0. :P

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.

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 :(

The case when the first player has a loosing strategy without any swapping.

me too , moved to C instead , but again ambiguity , very confusing this time!!

same here i moved to C instead

I guess they should be because of the score distribution.

Same here !! To add A got hacked

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 did binary search but failed on 6.

some people didn`t take union of both cases

some thought that accident is dependent on the same road only

Sagheer is standing at the ground floor at the left stairs

Check line 28. arr[i].second * (k - prevk) can overflow.

Replace it with something like arr[i].second * 1LL * (k - prevk).