Hasan0540's blog

[GYM] 2017 ACM Jordanian Collegiate Programming Contest
By Hasan0540, 7 years ago, In English

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!

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

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

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

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  • I just see him in top 10 and finaly, he skipped... I don't understand???...
→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

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

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

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

    The correct answer is 2.

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

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

      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?

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

        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.

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

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

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

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

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

    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.

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

      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.

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

Can anyone give me a hint for problem G: HERE

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

    Two Pointers or Binary Search with Prefix Sums for each bit.

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

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

→ Reply