I also passed with O((n*2^k+e)*log(n*2^k)) but I think this theoretical complexity isn’t actually achievable. I cant think of a case where all bitmasks are actually traversed + are all “valuable” (since we just break out of dijkstra once we find the first path).
Understood. Its nice explanation.
The intended solution was to compress the graph to just keys and locked nodes using O(K) Dijkstra, and then to run the subtask 2 solution on that graph. I think that the theoretical complexity is achievable (consider all keys connected to each other and connected to the node 1) but unfortunately did not have a specific test case. It seems that most people who tried n*2^k failed subtask 3, regardless.
hey, can anybody tell me why only 1st tescases of each subtask fails. Rest all are green. Code taken from geeks for geeks. https://www.codechef.com/viewsolution/29899994
My soln was DFS on the compressed trie. Let N be the no of nodes in the trie. I expect my soln to be O(N*logN) extra logN factor for map in trie.
I added a few counts in soln (CodeChef: Practical coding for everyone). At last in cerr it prints the value of that count. I expect it to be O(no of nodes) which in the present case is 1e6 due to constraint on the summation of K[A[i]]. If you can once check it?
I am getting wrong answer for BLOCKS but i have set asserts in my code. Why am i not getting runtime error?
https://www.codechef.com/viewsolution/29907084
I apologise, it seems that your solution doesn’t encounter the O(N^2) blowup that I thought it did. (I guess mrho’s solution would also be same?) Unfortunately, I don’t think I have the permissions to check the cerr from the file. Testing it locally finds that it is pretty much O(N).
Apologies for the tight TL. Solutions of testers and setter were double as fast because they used map with key as int, I believe (which also led to the possibility of O(N^2) blowup). Congrats on all AC in contest, though.
Can anyone help?
I guess your code fails on “hellohello”
1
10 240
? 5
5
? 9
0
? 4
0
? 5
5
? 5
5
! 2
0
This is what I got after running your code. Let me know if anything is wrong
the output for “hellohello” should be k=2 and my code outputs 2.
P.S. i have put asserts in the code at every place after i take input assert(y!=-1). but i am not getting runtime error which means all my asserts are passing. but still i am getting WA.
Ohh yeah i forgot the output was n / key
Can you tell why am i not getting Runtime error?
Hey,
We hope that you found what you were looking for 
Thanks!
1 Like
well I didn’t participate but had a look at most of the problems the next day. liked the problems .
For Indian participants:
- Top 10 from ranklist will receive 300 laddus.
Does this mean top 10 from Overall ranklist or top 10 from ranklist calculated by taking Indian participants only?
The latter.
As mentioned on the contest page, “Laddus will be provided post the MOSS process”. And that will take at the least a couple of weeks. Probably longer. Within a couple of months for short contests, save for some exceptions.