Invitation to UWCOI 2020 Online Replay Contest - Rated for All

announcement
13

Anyone mind telling me what was wrong in my submission (the actual code starts from line 200) for Optimal Memory Address.

The idea was to building a weighted trie on the prime factorization of the numbers and finding the node that minimizes the sum of distances to all the marked special nodes.

Edit: I found a few errors, the main one was when traversing the node to minimize distance I was incrementing by the number of all elements in parentā€™s subtree rather than the total number of elements, it still TLEs in one testcase but I should be able to figure that out.

14

Anyone please share a detailed approach of how to solve the problem Base Plans.

15

please do share the explanation behind the approach in Base Plans

16

How this accounts for checking for each possible square submatrix for appropriate base plan.

18

For every column, store the position of the tower.

Then, start extending the area of the tower base, up and down for a tower in any column.

For example,

1 0 0 0
0 0 1 0
0 1 0 0
0 0 0 1

tower[0] = 0
tower[1] = 2
tower[2] = 1
tower[3] = 3

Now, you take into consideration the the towers from each column, and extend it both above and below.

If the difference between the above and below tower is same as indexes ( square base), you have got a base.

Code : here

Try pen paper to get a better understanding.

3 Likes
19

Understood !!! Seems to be such an easy solution:sweat_smile::sweat_smile:Thanks @aryanc403
@nuttela

1 Like
20

I believe that your solution (as well as the solution of mrho) are actually unintended and run in quadratic on an edge case, which you barely passed through constant factor tricks. Note that the Java submission of uwi runs in 0.24 seconds.

21

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).

22

Understood. Its nice explanation.

23

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.

25

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

27

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

28

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.

29

Can anyone help?

30

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

31

the output for ā€œhellohelloā€ should be k=2 and my code outputs 2.

32

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.

33

Ohh yeah i forgot the output was n / key

34

Can you tell why am i not getting Runtime error?

35

Hey,

We hope that you found what you were looking for :slight_smile:

Thanks!

1 Like