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!
The contest will start in 25 minutes. Don't forget to read the input from file.
Maybe I didn't like problems and skipped
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?
What is the tricky test case for problem H? 1 hour of stress-testing couldn't find any.
The correct answer is 2.
Not sure if it's tricky, but this is the first case you got WA on.
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?
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.
lol my stress test generated exactly the same testcase :'D
quailty Can you share the idea behind your solution for problem I?
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.
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 * Riterations, whereLengthis the length of the path we found, andRis 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.Can anyone give me a hint for problem G: HERE
Two Pointers or Binary Search with Prefix Sums for each bit.
Can someone share his solution of problem H (Gas Stations) ?