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

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

Hello Everyone,

The problem set of 2017 ACM Jordanian Collegiate Programming Contest will be available in Codeforces Gym on Saturday, Nov/11/2017 18:00.

The problems were prepared by Hasan0540, justHusam, Lvitsa, and Maram Tuffaha. Thanks to ahmed_aly for reviewing the statements and giving some suggestions.

Note that your solution should read the input from file and write to the standard output. You can find the input file name below the title of the problem.

Hope you like the problems. Any feedback is appreciated!

Good luck!

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

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

The contest will start in 25 minutes. Don't forget to read the input from file.

»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
  • I just see him in top 10 and finaly, he skipped... I don't understand???...
»
6 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hello,I tried to solve the question M Winning Cells but I had no idea about it,could you please tell me how to do it?

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

What is the tricky test case for problem H? 1 hour of stress-testing couldn't find any.

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

    The correct answer is 2.

    Not sure if it's tricky, but this is the first case you got WA on.

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

      Thanks for the test case.

      It seemed that even stress-testing sometimes can't help you finding the mistake in your solution. I will take note of this.

      By the way, it seemed that you gathered all of the test cases in a single test (test 2). Is there a specific reason for you to do that?

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

        I think in such problems it is better to generate all possible cases of some length (2^length — 1).

        We still use an old stable version of PC^2 in the onsite contest that doesn't support multiple test files.

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

      lol my stress test generated exactly the same testcase :'D

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

quailty Can you share the idea behind your solution for problem I?

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

    Sure. My solution mainly considers the center of mass. It seems that the center of H is the nearest from itself and the center of M is the farthest. So I take the minimum and the maximum distance between the center and the pixels and calculate the ratio. Since the difference is not so big, the thresholds should be taken carefully.

    By the way, thanks for the interesting problem set.

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

      Thank you for sharing your solution, I thought all solutions for this problem will be similar! :)

      The intended solution has one constant and I think it is easier to set, I'll explain it if anyone is interested:

      For each black component, find the longest path as we do in trees (start from any cell, find the farthest cell and start again from it), this path is not really the longest but this way we have two ends of different branches. As the font has some thickness, we need to extrude the cells on the path. To do this, we can start multi-source BFS from the cells on the path and run BFS for Length * R iterations, where Length is the length of the path we found, and R is an estimated ratio between the thickness of the font and the length of the path that ensures we cover the thickness of the font, any value between 0.12 and 0.25 will get accepted. Finally, we count the number of components with unvisited cells (black components in the picture above) and decide what is the letter: 0 = M, 1 = Y, and 2 = H.

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

Can anyone give me a hint for problem G: HERE

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

Can someone share his solution of problem H (Gas Stations) ?