Hasan0540's blog

[ GYM ] 2016 ACM Amman Collegiate Programming Contest
By Hasan0540, history, 8 years ago, In English

Hello Everyone,

The problem set of 2016 ACM Amman Collegiate Programming Contest will be available in Codeforces Gym on Tuesday, Sep/27/2016 10:00.

The problem set was prepared by Hasan0540, SaMer, and AU.Bahosain.

Thanks to RetiredAmrMahmoud for testing one of the problems (in case he participated), and to Dark for helping me preparing the contest on Polygon.

I hope more orange and red coders will participate than in the last contest I've prepared :(

Good luck!

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

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

why we can not see the solution of another users after the contest ? :)

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

    You can only view submissions for the problems you solved in the Gym.

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

problem was good.. plz upload the editorial :)

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

OK, where is the editorial?

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

When will the editorial be uploaded ?

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

Can anyone help with solution for problem I and L?

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

    for problem I you need to notice that the x coordinate and y coordinate of the optimal starting position are chosen independently cuz moving the robot start position horizontally never change how the robot can go out of the bounds vertically and vice versa/

    Now to choose the optimal y pos for the robot you can notice that if you place the robot too high it can go out of the table from above and if you place it too low it can go out of the table from the bottom so the optimal is something in the middle so you can run ternary search and find the optimal y pos and you can do the same thing to find the optimal x pos too.

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

      I have noticed that we have to solve independently for X and Y, but didn't know how to find optimal answer for each axis. Thank you! :)

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

      Ternary search somehow passed the testcases. But using ternary here may be wrong. For x-coordinate, let f(x) be the number of skips, then f(x) isn't convex. Sometimes you go to the right, you get more steps to skip on the right, but you will save more steps which was skipped on the left.

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

    Note for problem I (Simple Robot):

    it can be solved without ternary search and in a much faster way.

    you can assume at the beginning that the optimal position is at point (0,0) (top left of the room). and then start executing the instructions sequentially.

    let's talk about what could happen horizontally, if the next instruction you will skip is in < direction, you will consider changing the optimal x position by incrementing it by 1, but to do this you have to make sure of 2 things : that the current assumed optimal x position didn't reach the most right, and that the maximum right position you got to while executing the instructions is not the most right position, for the second condition you must keep track of the most right position you reached, and after incrementing the assumed optimal x position you have to increment the most right position you reached too. therefore this instruction that was to be skipped will not be skipped because you assumed starting at more right position.

    but if the next instruction you will skip is either in:

    1) > direction

    2) < direction (and the current assumed optimal x position reached the most right, or the maximum right position you got to is the most right position)

    then at this point the optimal x position doesn't need to be changed anymore and any instructions to be skipped starting from here (including the current instruction) will be skipped actually, so you count them and these will be the minimum horizontally.

    for the vertical aspect you can think in the same way. (I solved it this way and it got accepted with time 109 ms.)

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

I'd like to remind you to write the editorial :)

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

why i got MLE in test 2 , and what you think the test is?
101102K - Topological Sort
23365501

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

may someone post tricky test cases and their expected output for problem G Notes ?

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

Can anyone tell me how to solve problem D?

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

I can't find any editor of problem K. Can anyone help with solution for problem K, why I got TLE? this my code

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

    In lines 18, 19 you are doing N^2 iterations.

    My solution for K
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you please explain your approach a bit more. I have been working on it for long and couldn't get any. I have even written a blog on it and yet none replied. I would be very thankful to you if you explain the solution. Link to my blog asking for some hint

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it
        1st approach
        2nd approach
        → Reply
        • »
          »
          »
          »
          »
          7 months ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          2nd Approach:Dont you think it will give you memory limit exceeded?

          → Reply