Блог пользователя Ahmad_Elsagheer

Автор Ahmad_Elsagheer, 7 лет назад, По-английски

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

  • Проголосовать: нравится
  • +361
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится -26 Проголосовать: не нравится

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

Good luck!

»
7 лет назад, # |
  Проголосовать: нравится -6 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

Why this blog is not seen in the home page?

»
7 лет назад, # |
  Проголосовать: нравится +17 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

No character ? It seems to have short statements :DD

»
7 лет назад, # |
  Проголосовать: нравится +57 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 8   Проголосовать: нравится 0 Проголосовать: не нравится

What about a "Rated" Div 1 contest?

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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://mirror.codeforces.com/blog/entry/52234

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Something weird things happens in Codeforces..

It unregistered me...

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Три минуты назад:

Надеюсь во время раунда будет всё ОК)

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Delayed by 10 minutes :o

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

delayed by 10 mins :P

»
7 лет назад, # |
  Проголосовать: нравится +51 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

GL & HF everyone.

:)

»
7 лет назад, # |
  Проголосовать: нравится -16 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hope this round will be interesting!

»
7 лет назад, # |
  Проголосовать: нравится -36 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

Very strange scoring distribution / problem ordering

»
7 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

Many hacks in A

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    binary search on k

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        What? I don't understand.

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        If f(n) = n·log(nlog(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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I was solving problem same way)

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

Me, reading problem D

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +52 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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)

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    dp

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +7 Проголосовать: не нравится

    I did brute force...

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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)

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Отвратительный контест. Задача А — "пойми условие за минимальное число прочтений". Задача B — "победи в себе отторжение и все-таки напиши очередной перебор без идеи". Очень хорошие задачи, так держать!

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve C?

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

      That's problem B not C.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

@Ahmad_Elsagheer why such an irregular scoring distribution

  • »
    »
    7 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +17 Проголосовать: не нравится

    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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Is there short solution for B?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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 !

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +69 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +27 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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;

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    totally agreed

»
7 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Will simple recursion without dp pass TL in B?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Depends on the checker

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +6 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

what was pretest 6 in C? :'(

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    i got WA 3 times at this test

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

test 6 in problem E ?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +9 Проголосовать: не нравится

Задача А является наверное самой бредовой задачей за всю историю раундов Codeforces...

»
7 лет назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Контест ниже плинтуса. Суть всего контеста это понять условия, а не решить задачи

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Задачи B и C тебе тоже были не понятны?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Как и все остальные

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      мог бы ты объяснить словами твой алгоритм для B?
      видел несколько подобных решений, но затрудняюсь понять что в них происходит

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        Мы либо поднимаемся по левой лестнице, либо по правой. На каждом этаже мы проверяем эти оба варианта и выбираем тот, который делает меньше всего шагов.

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          упустил "Он хочет выключить везде свет, при этом, он не хочет подниматься на этаж выше до того, как выключит весь свет на текущем этаже"
          в таком варианте это похоже на NP-полную задачу

»
7 лет назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

What is the hack in problem A?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    some people didn`t take union of both cases

    some thought that accident is dependent on the same road only

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится +32 Проголосовать: не нравится

812A - Sagheer and Crossroads worse statement ever !! It needs more description

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

Wow , very fast judging :D

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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.
»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Systesting today is really fast

»
7 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

very bad contest

»
7 лет назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

Here, have a look!

http://mirror.codeforces.com/contest/812/submission/27499338

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Can explain how is it so? Cannot understand it.

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +10 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          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!

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          7 лет назад, # ^ |
          Rev. 3   Проголосовать: нравится +19 Проголосовать: не нравится

          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.

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

      nvm

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    He used the fact that

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
7 лет назад, # |
  Проголосовать: нравится +63 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +123 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +40 Проголосовать: не нравится

This guy literally crushed all the pedestrians xD

»
7 лет назад, # |
  Проголосовать: нравится +54 Проголосовать: не нравится

 you got this...

»
7 лет назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Weak pretests for A :|

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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!

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

7 претестов для задачи А, из которых три — сэмплы. Класс)))

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится +2 Проголосовать: не нравится

deleted , sorry my mistake :3

»
7 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

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!

»
7 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    How do you use a bitmask for B?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      To enumarate binary strings of len n

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      7 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      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. 
        }
      }
      
      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится -31 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +36 Проголосовать: не нравится

    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.

    :)

»
7 лет назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

Only neverfirst solved all problems. This is great result!

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

nice contest

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
7 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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"

»
7 лет назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

Mike mirzayanovCF should follow csacademy in terms of problem statements.

»
7 лет назад, # |
Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

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://mirror.codeforces.com/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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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