Hasan0540's blog

By Hasan0540, 11 days 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, Alaa_AbuHantash, 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  

»
9 days 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.

»
9 days 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???...
»
9 days 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?

  • »
    »
    9 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it
    • You should run naive algorithm will be see tricky in this problem...
    • And when you see that, everything will be easy...
»
9 days 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.

  • »
    »
    8 days 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.

    • »
      »
      »
      8 days 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?

      • »
        »
        »
        »
        8 days 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.

    • »
      »
      »
      3 days ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

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

»
6 days 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?

  • »
    »
    6 days 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.

    • »
      »
      »
      4 days 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.