Hello CODEFORCES...
I hope this blog finds you well! Recently I became interested in the problem preparation process behind the programming contests. So I learnt how to prepare a problem by learning from THIS awesome blog prepared by darkkcyan, thanks again to him! I have prepared some problems after on. One of which I'm going to share with you! Please give me valuable feedback and tell me what should be the rating of this problem according to you, and also where will it be placed if it appears in a Div.2 contest!
Problem link: https://mirror.codeforces.com/contestInvitation/50819984c01cd8d8cc5ba50936ab46e33d54b7a5
Interesting fact: When I submitted my solution for the problem, it got AC at 5000 ms and 100 KB, just the perfect numbers as they are!
I would be more than happy if you will take interest in solving the problem and make (m)a(ny) submission(s)!
When I enter the link, it says "No such contests"
Fixed!
You should create custom invitation link so that it's visible to everyone (and be able to submit to the problem)
Fixed!
Don't forget to tell me what's the estimated rating of problem according to you, and where should it be placed if it appears in a Div.2 contest!
Why don't you display the images within the problem statement instead of using external links?
Polygon only supports .mp files as images. So I couldn't convert JPEG and PNG to .mp files, so I did it this way... Are you facing any issue or was just curious ?!
No problem, just a little bit inconvenient
The constraints are so low that some naive solution should easily pass.
There are only $$$2nm$$$ different positions; one for each cell-direction pair. For each of the $$$2k$$$ positions corresponding to the cells in the set, you can run Dijkstra to find the minimum distance to every other position. Even a bad Dijkstra implementation only takes at most $$$O(|V|^2)$$$, so in total we have $$$2kO((2nm)^2)$$$, which is around $$$1.7\cdot 10^7$$$.
Then you can run some subset-DP where $$$\mathrm{dp}[i_1][i_2][i_3]$$$ is the cheapest cost to end on bishop $$$i_1$$$ with direction $$$i_2$$$ whilst having collected all bishops in subset $$$i_3$$$. This has size $$$(k)(2)(2^k)$$$. Since $$$k$$$ is so small, this is only around $$$4096$$$ at most. The transition only requires checking subsets which are smaller by exactly one element, so the transition should only take $$$O(2k^2)$$$. So in total, we have around $$$4096\cdot 128$$$ which is around $$$5\cdot 10^5$$$.
An 8-second time limit is way more than needed; this shouldn't really take more than two seconds, with the constraint being so low. If the constraints were higher, it might require more cleverness to solve quickly, but with $$$k\leq 8$$$, pretty much the first thing that comes to mind should be fast enough.
Personally, I think it's a little bit implementation-heavy for my liking, but different people may have differing opinions. It might be more suited for a different platform, where problems like these are the norm.
I would estimate it around maybe cyan difficulty, for the tedious implementation.
Oh, I see. That is clever. Increased constraints maybe suitable for hard version of this problem.
Naive solution with O(K*K!) will be faster?
Edit: forgot next_permutation is not magical O(1) algo.
Don't you still need the Dijkstra anyways? That'll be the bottleneck in any case, I think.
I guess you're right that $$$k\cdot k!$$$ is only $$$3\cdot 10^5$$$, which is slightly less than $$$5\cdot 10^5$$$, but I don't see how you get rid of needing to find costs between pairs of points, which is much slower.
At first I thought you only need 2 computation to find the next pair,
But this is only true when N==M
Finally I found that finding cost between pair of points is O(max(n,m)/min(n,m))
This is worst case scenario where I need to pingpong from edge to edge.
My solution which has 124 ms runtime uses much worse way to do it.
If I precompute that I will need (2*k*k)*(max(n,m)/min(n,m))
(2*8*8)*26
128*26 = 3328,
for calculating distance.
So in total O(k^2*max(n,m)/min(n,m) + k*k!)
should be 3328+322560 = 326116 ~= 3.3e5
Since edge weights are binary, you can do a BFS instead and for every vertex reached with an edge with cost 1, find all "new" vertices that can be reached with a cost of 0.
But using some case distinction, you can probably find the distances in $$$\mathcal O(1)$$$
Man of culture with that andrea reference
Man of chess culture.
Maybe make the problem statement a bit shorter (like use normal math coordinates instead of explaining chess coordinates, as it'll also be easier to formulate bishop movements this way)
Ahh, I could have used co-ordinate system, but I wanted the problem to be chessy chessy chess chess...
Interesting problem using Dijkstra (at least I used that), but input parsing was a pain (completely forgot that the input can have 2 digits) :(
Also, the problem statement was a bit too long and sometimes a bit unclear, e.g. can
a1be a special cell?Anyway, my solution runs in 150ms (slightly higher memory consumption though), so now I'm wondering what the intended solution is 😅
Thanks for making a submission...
Thanks for making the problem :) — what's the intended solution though (your code looks quite long 🤔)
Build the graph in which each cell on chess board contributes 2 nodes, one for D and another for AD. Find the shortest path distances for given cells and for a1 as well, then try all the permutations of the nodes i.e. k! Isn't most optimal it seems...
Ah ok, you can speed up the permutation part with a standard bitmask dp (let $$$\mathrm{dp}[\mathrm{m}][\mathrm{last}][\mathrm{d}]$$$ be the cheapest cost to visit all special cells from the mask $$$\mathrm{m}$$$ with the last visit being $$$\mathrm{last}$$$ and direction $$$\mathrm{d}$$$), which should be something around $$$\mathcal O(k^2 2^k + k^2)$$$.
My solution runs in time $$$\mathcal O(n \cdot m \cdot 2^k)$$$, which can be faster if $$$k^2 \in \omega(n \cdot m)$$$; I simply run a normal Dijsktra where each vertex is the tuple of $$$(\mathrm{row}, \mathrm{col}, \mathrm{visited_{mask}}, \mathrm{direction})$$$ and every vertex has (at most) three outgoing edges — change the direction (cost $$$1$$$), move such that the column "increases" (top-right or bottom-right) or move such that the column "decreases" (both cost $$$0$$$).
Since the edge weights are binary, we can use a
Queueinstead of aPriorityQueueand process all vertices reachable with a cost of $$$0$$$ in aStack(i.e. reach a new vertex using edges of cost $$$1$$$, then find all new reachable vertices with no extra cost).This eliminates the log factor and since every state is visited once and has a $$$\mathcal O(1)$$$ transition time, the total running time is $$$\mathcal O(n \cdot m \cdot 2^k)$$$. The memory complexity is a bit worse though and is also $$$\mathcal O(n \cdot m \cdot 2^k)$$$.
Submission: 326051905
Ahh double digit, I see, wasn't intended though.
Problem's nice, though the wording is a bit confusing in my opinion. My main concern is that the implementation is way too difficult compared to the idea to solve it, looking at your 200+ line code.
Yeah