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

Автор Hasan0540, история, 5 лет назад, По-английски

Hello everyone!

The problem set of the 2018 ACM Syrian Collegiate Programming Contest will be available in Codeforces Gym on Nov/23/2018 17:00 (Moscow time).

You will have 12 problems and 5 hours to solve them.

The contest was intended for teams, but I believe it is more interesting for yellow and red coders if they participate individually as they will get to try all the problems.

Your solution should read the input from file, and output to the standard output (stdout).

Problem setters are Motarack, Vendetta., Reem, Dark, and Hasan0540.

Thanks to Jester, Hiasat, Noureldin, Badry, sqr_hussain, Mohammad Asaad, and Majd Akleh for the help in preparing and testing the problems.

I hope that you will find some interesting problems for you. Any feedback is appreciated!

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

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

Contest was moved to Nov/23/2018 17:00 (Moscow time) as there's another gym contest on Saturday.

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

The contest starts in 25 minutes. The first test case is the same as the sample test case. Don't forget to read the input from the required file.

Good luck!

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

how to solve F no. problem of this contest?

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

    Assume that we have an array F such that F[mask] is the number of submissions which fail only on a subset of the tests in mask. We can try all possible permutations using DP in O(2n × n) (similar to the travelling salesman DP solution). When we append a test to the current solution in DP, the number of submissions that didn't fail yet and will run on the new test is F[curMask], so we should add it to the answer of the current state. The mask in our state contains the tests which are not included yet.

    Check this blog SOS Dynamic Programming [Tutorial] by usaxena95 if you need help in building the array F.

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

How to solve J?

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

    Greedy algorithm: KAN chooses the first to unlock the groups by priority of earliest second time first. This works because it unlocks something for the other to do while he unlocks other groups (if it doesn't, any other choice also doesn't).

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

I was a contestant in the onsite competition, I have to say this problemset was really nice and interesting problemset.

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

How to solve H?

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

    You can always get the minimum answer if the balance between in — out degrees is 0 in every vertex. Also, if it isn't, there's no answer.

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

How to solve C without cheating with Dinic?

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

    You can solve by analysing different cases.

    By Dinics you meant to say that observe answer is always <5 and then create a flow problem which can have flow atmost 5 or something like this and then solve by any flow solution??

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

      Oh, I didn't realize the answer is always <5. Thanks.

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

      Can you tell what might be the problem if I am getting WA on Test Case 2. I have solved considering different cases.

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

        Check this test: se.

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

          I have given -1 as output if s and e are adjacent to each other or each of them have a portal next to them.

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

            Okay your last submission fails on this e.o#os. Fix it and if it is still wrong, you need to think again about the solution and make sure it handles everything as it doesn't make since to provide many cases in these problems (finding the cases is part of the solution).

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

    Here's a not-so-smart brute force solution.

    There are at most 4 optimal places to put a block, namely the closest empty cells on the left/right of S/E. You can then iterate through no more than 2^4 different scenarios (by deciding whether or not to put a block on a candidate block) and check whether S can't reach E.

    The check function can be implemented with O(n) complexity.

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

How to solve D?

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

How to solve K?

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

    Start from highest value to smallest. Assign color = mex of neighbours.

    dont know proof :P

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

      Nice Solution.

      I think you can prove it easily. Each has atmost 2 edges with heights greater than it.So mex can be atmost 2. And now for bipartite graph we get always two colors since we always explore the graph in a connected fashion rather than random vertices.

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

    Another solution that is probably less interesting but it's good to know these facts about the constructed graph:

    The graph is planar, triangulated, and all vertices are boundary vertices. Check the following image:

    Picking an edge and coloring its ends will split the uncolored vertices into some components, each component will have one vertex with one option, coloring that vertex will leave another vertex with one option... So after picking an edge everything will be uniquely determined unless there's a bridge, in that case you will have more than one option.

    Implementation: always pick the vertex with the minimum number of remaining options and color it with the minimum available color index (just to make it work on bipartite graphs too). This solution works in O(n) since each vertex will have at most 3 options (no need for a heap or sorting).

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

Solutions for E,L ?

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

    E:

    Find three nearest vertices which can propagate to each vertex(based on distance and index as mentioned in question) and then we count all those which has a red as nearest. Similarly we count number of vertices for each blue such that if we remove it will become red also for all pairs of blue similarly. Now we iterate over all pairs of blues and find the most optimal to remove by adding first counts of each blue and pair count. We need to notice that only n pairs of blue are good. rest always contribute zero to second count. So this can be done in O(n) .

    I think first part of finding three vertices can be done with priority queue similar to dijkstra,

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

How to solve problem I using normal geometry? I iterated through all points of generated polygon iteratively some 1e5 times and pushed the starting point [alpha=0.5] times the extra length inside the circle if any of the points is outside the circle of radius R. Here's the code

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

    It can be solved by finding the Smallest Enclosing Circle of all visited points starting from (0, 0).

    You will get a center point C and all you need now is to move the starting point so C becomes (0, 0), thus the new starting point is -C.

    The algorithm is pretty much similar to your solution. I can't open it, btw :1.