Ahmad_Elsagheer's blog

Codeforces Round #417 (Div. 2)
By Ahmad_Elsagheer, 8 years ago, In English

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:

  1. TERESO

  2. neverfirst

  3. _luckyE

  4. zstu_jack

  5. jiyutian

Div1 Winners:

  1. y0105w49

  2. _Reborn_

  3. eddy1021

  4. chemthan

  5. KrK

UPD 4: Editorial

  • Vote: I like it
  • +361
  • Vote: I do not like it

Comments Comments (244)
| Write comment?
»
8 years ago, # |
  Vote: I like it -26 Vote: I do not like it

After JBMO TST (Junior Balkan Mathematics Olympiad Team Selection Test) I will participate in that contest. Hope short and interesting statements :D

Good luck!

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hey, i see you're from Azerbaijan, will you participate in EJOY this year? You're a junior right?

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    as i am your suffix :D i wish you best of luck in both contests and happy coding

    → Reply
»
8 years ago, # |
  Vote: I like it -6 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

Why this blog is not seen in the home page?

→ Reply
»
8 years ago, # |
  Vote: I like it +17 Vote: I do not like it

You did really well in the WF, so we must be expecting some interesting tasks :D

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

No character ? It seems to have short statements :DD

→ Reply
»
8 years ago, # |
  Vote: I like it +57 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +53 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +26 Vote: I do not like it

      We both know that I can't get the first place in the unofficial round. :D

      → Reply
»
8 years ago, # |
  Vote: I like it +22 Vote: I do not like it

By the way, the time link in your post is wrong, it says 5:05 am MSK (it should be pm).

→ Reply
»
8 years ago, # |
← Rev. 8   Vote: I like it 0 Vote: I do not like it

What about a "Rated" Div 1 contest?

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

The link for the time of the contest in the "Contests" tab redirects to World Clock instead of the actual event timer.

→ Reply
»
8 years ago, # |
  Vote: I like it +21 Vote: I do not like it

It seems that codeforces system automaticaly unregistered some people that had been registered earlier!

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    I've been unregistered twice already...

    → Reply
»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

the time link nowadays is not showing regional time. previously it was showing your regional timing BTW ,excited about this comtest.

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 4   Vote: I like it +5 Vote: I do not like it

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

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Go to this link and check how much time left.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I know about how much time left. I was saying about mail from codeforces saying that contest start time 14.05

      → Reply
»
8 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Is site working slow for all? or Is it just my network?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Hope that it's not slow during contest.

    → Reply
»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Something weird things happens in Codeforces..

It unregistered me...

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Delayed by 10 minutes :o

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

delayed by 10 mins :P

→ Reply
»
8 years ago, # |
  Vote: I like it +51 Vote: I do not like it

It won't be a normal Codeforces round if it is not delayed :)

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It's been so long since the last time I have seen the score distribution BEFORE the contest.

GL & HF everyone.

:)

→ Reply
»
8 years ago, # |
  Vote: I like it -16 Vote: I do not like it

Due to a technical issue, the contest is delayed by 10 minutes.

→ Reply
»
8 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Please, Don't delay the contest more than 20 min because of maghreb Prayer " E7na saymen y3ne" :"D

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    even no more than 10 minutes :(

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -29 Vote: I do not like it

    lsa bdri 3la elm8reb ya 3m :D

    → Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

It's very exciting!!! Good luck to myself

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

I wish i had a time machine!
Time+=10minutes

→ Reply
»
8 years ago, # |
  Vote: I like it -10 Vote: I do not like it

It shows registration is completed still the number of users registered are increasing??

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope this round will be interesting!

→ Reply
»
8 years ago, # |
  Vote: I like it -36 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

    → Reply
»
8 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Very strange scoring distribution / problem ordering

→ Reply
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Many hacks in A

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

    → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    binary search on k

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you describe the solution, I am asking a question different from C here

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        All the indexes are not multiplied by k. They are multiplied by 1..k depending on the position

        What? I don't understand.

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

          → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      why O(n*log(n)*log(n))? i think that O(n*log(n)*log(1260))

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
        ← Rev. 3   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was solving problem same way)

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Me, reading problem D

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +52 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like 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)

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    dp

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    I did brute force...

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    No need to memorize. recursion will pass. Complexity O(3^n*m). It may be less, I am not sure.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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)

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

It seems more like A-C-B-F-D !

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve C?

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      That's problem B not C.

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

@Ahmad_Elsagheer why such an irregular scoring distribution

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 4   Vote: I like it +17 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there short solution for B?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Maybe i've messed something up.. My brute force code was about 130 lines and it got WA...

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 !

        → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it -10 Vote: I do not like it

Ordering should be A — C — B — E — D!

→ Reply
»
8 years ago, # |
  Vote: I like it +69 Vote: I do not like it

To me A was the hardest among A, B, C, E, as I still don't get what the problem is saying till now.......

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +27 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it +17 Vote: I do not like it

      I got hacked twice and I still don't know whether my current submission is correct.

      UPD : Wow it passed.

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +36 Vote: I do not like it

      i submitted some shit and it got hacked then i added more shit and it passed

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        And it's failed on system tests.

        → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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;

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Anyone who submitted 1st quickly and were happy and then got hacked?

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    totally agreed

    → Reply
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Will simple recursion without dp pass TL in B?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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. 

      1111111
1000001
      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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"

        → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Yes, it passed! :)

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I don't see a reason to do that.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        It's a feature of the default yes/no checker, the checker is case insensitive.

        → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If the problemsetter is using the standard yes/no-checker for the problem, they are the same.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Depends on the checker

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Maybe he redefine "Yes" to "YES" :).

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      yea I thought that way, too. Hope the ones that got hacked have as positive thinking as you :v

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        When I have been hacked in A, just few more second to fix that stupid mistake, so 10 min is too long since.

        → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

what was pretest 6 in C? :'(

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i got WA 3 times at this test

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

That feeling when you submit A and get pretests passed and right after there's a sudden power outage... Bye bye rating.

→ Reply
»
8 years ago, # |
  Vote: I like it +20 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

test 6 in problem E ?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

I understood problem A only after reading it 5-6 times...

→ Reply
»
8 years ago, # |
  Vote: I like it +9 Vote: I do not like it

The problems weren't ordered by their difficulty, were they ?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I guess they should be because of the score distribution.

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

The queue of submissions in the end was long. I submitted 7 minutes before and the it was evaluated after the contest.

→ Reply
»
8 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Solving B first was an extremely costly decision for me. I should have rather started with C.

→ Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I solved C using greedy but failed in TC 6. Any Help please

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is binary search on maximum number of souvenirs.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it works in O(nlog(n)log(MAX_NUM_OF_SOUVENIRS))

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I guess MAX_NUM_OF_SOUVENIRS is n lol.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        It is about 1000 i think

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          sorry, I just got confused, and I think it is around sqrt(s).

          → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Minimum sum of k elements is arithmetic progression starting at k and ending at k*k + sum of given prices

        → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I did binary search but failed on 6.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Same was the case with me just check case 1 8 7 ans: 1 8 and 1 7 7 ans:0 0

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It was not a very good contest at all, though i think problem C is a really nice one.

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

i think B is harder than C it was a waste of time not to start with C after A

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the hack in problem A?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    some people didn`t take union of both cases

    some thought that accident is dependent on the same road only

    → Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

→ Reply
»
8 years ago, # |
  Vote: I like it +32 Vote: I do not like it

812A - Сахир и перекресток worse statement ever !! It needs more description

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    Sagheer is standing at the ground floor at the left stairs

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

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

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

    → Reply
»
8 years ago, # |
  Vote: I like it +2 Vote: I do not like it

fainted from reading Problem D at mid night.. :D

→ Reply
»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Wow , very fast judging :D

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

Problem A: ?????

this problem destroyed your work on the other probs!!!

  1. Bad statement it should have been mentioned that each lane goes to what part -_- my solution got hacked coz I did not concentrate on how the cross road really work :v
  2. the rest of the probs are interesting, thanks.
→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Systesting today is really fast

→ Reply
»
8 years ago, # |
  Vote: I like it +25 Vote: I do not like it

very bad contest

→ Reply
»
8 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Sad to see that N^2 log(N) also passes for problem C :(

Here, have a look!

http://codeforces.net/contest/812/submission/27499338

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I think it is N * sqrt(s) * log(n).

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can explain how is it so? Cannot understand it.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like 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).

        → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          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!

          → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          But shouldn't sqrt(10^9) * N * logN also fail?

          → Reply
          • »
            »
            »
            »
            »
            »
            8 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            It's in c++ and it runs on edge(nearly 1800 ms).

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Okay, that is sad. Thanks a lot anyway :)

              → Reply
        • »
          »
          »
          »
          »
          8 years ago, # ^ |
          ← Rev. 3   Vote: I like it +19 Vote: I do not like it

          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.

          → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      nvm

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    what's wrong with that complexity ? Log(100000)^2 x 100000 is barely over 25 Million and that passes in under a second!

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It is not N (logN) (logN) I guess. It is N*N*logN

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oh sorry i read your first comment wrong there for i didn't see the code :)

        → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    He used the fact that

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
8 years ago, # |
  Vote: I like it +63 Vote: I do not like it

I swear I'll never underestimate Div2-A again...

→ Reply
»
8 years ago, # |
  Vote: I like it +123 Vote: I do not like it

One of those contests where you think you want to ask for a clarification but don't even know where to start.

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Compiled E, just 1 sec before contest ended. Hope I don't get AC later.

→ Reply
»
8 years ago, # |
  Vote: I like it +40 Vote: I do not like it

This guy literally crushed all the pedestrians xD

→ Reply
»
8 years ago, # |
  Vote: I like it +54 Vote: I do not like it

you got this...

→ Reply
»
8 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Problem statements were very unclear! One reading was not sufficient at all :(

→ Reply
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

in C atleast one ex should be given to clearify which index is xi's. i spent 25 minutes figuring out what's wrong

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Weak pretests for A :|

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    in terms of code length, both approaches are equivalent, i guess. i dont think its overkill

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      sure , but i was talking about the difficultly of the solution because i noticed that C was solved more than B.

      → Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it +2 Vote: I do not like it

deleted , sorry my mistake :3

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    Input is invalid, should be 3 3 in first line.

    → Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Such input is not possible, since m is the muber of rooms in each floor, so there should bem+2 columns in the input.

    → Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    deleted

    → Reply
»
8 years ago, # |
  Vote: I like it +7 Vote: I do not like it

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!

→ Reply
»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    this case is invalid because child 4 can't request toy 2 while waiting for toy 1

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Goddamn, I got WA in B because i accidentally used && in bitmask instead of &, I hate such situations((

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How do you use a bitmask for B?

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      To enumarate binary strings of len n

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      If in index i there is 0, than I use right ladder to get to floor i + 1, else i use left left one

      → Reply
    • »
      »
      »
      8 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      for (int state = 0; state < (1 << 16); state++)
{
  int floor = 7;
  if (state & (1 << floor))
  {
    // Use right staircase on 7'th floor.
  }
  else
  {
    // Use left staircase on 7'th floor. 
  }
}
      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah i did the same, but my code ended up to be more than 150 lines...

        → Reply
»
8 years ago, # |
  Vote: I like it -31 Vote: I do not like it

MikeMirzayanov[user:MikeMirzayanov] please don't give another chance to this question setter

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    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.

    :)

    → Reply
»
8 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Only neverfirst solved all problems. This is great result!

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +43 Vote: I do not like it

    His handle is justified :p Even after solving all problems, 2nd position! :p

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

https://ibb.co/bZ5YJF Such proof! Much Wow. xD

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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"?

→ Reply
»
8 years ago, # |
  Vote: I like it +7 Vote: I do not like it

nice contest

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
8 years ago, # |
  Vote: I like it +24 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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"

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      That's the point that I never got first place at some valuable olympiad.

      → Reply
      • »
        »
        »
        »
        8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Never means never.
        You should have a nickname SometimesNotFirst.

        → Reply
»
8 years ago, # |
  Vote: I like it -14 Vote: I do not like it

Mike mirzayanovCF should follow csacademy in terms of problem statements.

→ Reply
»
8 years ago, # |
← Rev. 6   Vote: I like it 0 Vote: I do not like it

please consider the following case in problem B

10 10
001110010110
000000000000
011000000010
000000011000
001010101010
000000000000
000000000000
000000000010
010000000000
000010000000

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

  0    0  (11) (12) (13)   0    0  (14)   0  (15) (16)  0
  0    0    0    0    0    0    0    0    0    0    0   0
  0  ( 9) (10)   0    0    0    0    0    0    0  (17)  0
  0    0    0    0    0    0    0  (19) (18)   0    0   0
  0    0  ( 8)   0  ( 7)   0  ( 6)   0  ( 5)   0  ( 4)  0
  0    0    0    0    0    0    0    0    0    0    0   0
  0    0    0    0    0    0    0    0    0    0    0   0
  0    0    0    0    0    0    0    0    0    0  ( 3)  0
  0  ( 1)   0    0    0    0    0    0    0    0    0   0
( 0)   0    0    0  ( 2)   0    0    0    0    0    0   0

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

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can't problem C be solved by using DP? my initial thought was that it can be !!

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I don't think it has a DP solution, because the costs used to find the optimal value depends on the optimal value itself.

    → Reply
»
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it

and (( neverfirst )) won the second place :)

→ Reply