Topcoder Single Round Match 660

9 years ago, # ^ |

← Rev. 2 →

It can be solved in O(N) and I solved it (in practice rooms) pretty much that way. It turns out that the DP equates to adding/subtracting $\text{[math]}$ for each person, where k is up to the number of times we can iterate $\text{[math]}$ before finding a cycle.

→ Reply

k0st1a

9 years ago, # ^ |

why is it so? could you provide more details on it?

→ Reply

9 years ago, # ^ |

Assume that you put person i in place j₁. This person will accept the invite in (N - 1)! permutations minus (number of permutations where person A[i] accepts and is in a place j₂ < j₁). For a fixed j₂, the part in brackets can be rewritten similarly as (N - 2)! — number of permutations where A[A[i]] is in a place j₃ < j₂ < j₁ and accepts, etc. When you iterate A[A[A[i]]]..., you reach a cycle at some point — and in that case, you want to count the number of permutations where the people i, A[i], A[A[i]]... alternately accept and don't accept invitations; that case is trivial, since the person you cycled to always declines the invitation. The full form of the sum you get is $\text{[math]}$ , where S(N, k) is the number of decreasing sequences j_k, j_k - 1, .., j₁, the number of times you can add (N - k)! in the approach above — which is actually the binomial coefficient C(N, k), and you want to sum up $\text{[math]}$ for k from 1 to the number of people you iterated through before reaching the cycle (where the sum terminates).

This counted the number of permutations where i accepts the invitation; sum up for all people and divide by N! to get the expected value.

→ Reply

monkey.coder

9 years ago, # |

← Rev. 2 →

almost all of div2hard's submission have been hacked lol

→ Reply

minimario

9 years ago, # ^ |

Pretest are so weak, many people do not even try their code on max test. BTW, what is solution to that problem?

→ Reply

404Error

9 years ago, # ^ |

I have seen the similar problem may be in Hackerrank or UVA don't know exactly, but I did not read the solution. In that problem as far as I remember instead of 1 to n , you have to find for particular n ^ k under some mod, and k is something like 10^100 something.

I solved in the contest using BigInteger but after testing find its too slow.

→ Reply

nherceg

9 years ago, # ^ |

← Rev. 2 →

Iterate for every i from 1 to n. If i is a prime, then get answer for that i in O(k), else it is a composite number, which means solution for that i can be expressed as multiplication of some other two solutions less than i, and we already have that. You can use sieve of Eratosthenes to test if some number is a prime, or to get some factor for that number if it isn't. Complexity: pi(n)*k + n*ln(n)

→ Reply

Roberio

9 years ago, # ^ |

← Rev. 5 →

I think I overkilled, but...

Since i^{2^k} = (i^{2^k - 1})² (1), we could compute $\text{[math]}$ (2) in O(k) for every i, using two arrays: one to store (1) and other to store prefix product of (1), which turns out to give us (2). This would lead us to a O(nk) solution that does not seem to fit into the TL.

Further optimizing it, we can decompose terms in such way that we need to compute i^{2^k - 1} only for prime i:

$\text{[math]}$ , where p(n) is the set of primes of n.

We can use a sieve and compute i^{2^k - 1} for each prime in O(k). For composite numbers we can just multiply what we have just computed for it's prime factors. We will have something like O((n + k)logn).

→ Reply

vlyubin

9 years ago, # |

+42

Am I the only one who is annoyed by the way authors are choosing the bounds? It seemed to me that the author was aiming for O(n^4) complexity, and O(k*n^4) should TLE. Nope, TC is fast enough to make that pass too. Why didn't the author make k equal to a 100? In that case the difference would be clear. Very weird choice IMHO, and a spoiled challenge phase for many participants ...

→ Reply

Reyna

9 years ago, # ^ |

i actually did O(n ^ 4 + (k^3)n^2)

→ Reply

I_love_tigersugar

9 years ago, # ^ |

My solution runs in O(mnk³), which will be too slow with k = 100 :P

→ Reply

riadwaw

9 years ago, # ^ |

← Rev. 2 →

Well, there are n^2 k + k^5 solutions, so if anything should be increased is n

→ Reply

vlyubin

9 years ago, # ^ |

That would be OK too ...

→ Reply

Lewin

9 years ago, # ^ |

← Rev. 2 →

-6

Agreed. I wrote O(k*n^4), but it was 2.5 locally, so I spent some time to rewrite a O(n^4) (actually O(n^2(n^2+k^2)). Didn't know that TC servers are so fast.

→ Reply

AU.Bahosain

9 years ago, # ^ |

There were solutions with O(n^2 k^2) though I didn't see anyone passed with such solution.

→ Reply

9 years ago, # ^ |

Really? How? The best I've come up with so far is O(n^2 k^2 log(n+k)).

→ Reply

klamathix

9 years ago, # ^ |

If your idea involves keeping some sort of priority_queue and only altering k ^ 2 elements at a time (which is what I've done), I think you can just keep a sorted array and iterate at most k ^ 2 steps away from the max value each time.

→ Reply

9 years ago, # ^ |

← Rev. 2 →

That works, but it's O(n^2(k^2+log(n)), so it's not what we're looking for if n>>k.

EDIT: We can use the fact that each cell's value is O(poly(n)), so we can radix-sort in linear time, making it O(n^2 k^2). I have a feeling that's not what AU.Bahosain meant though.

→ Reply

klamathix

9 years ago, # ^ |

+18

Hmm, indeed. What about:

You only need the top k ^ 2 + 1 elements in the array. You can avoid sorting it by partitioning it with a linear time order statistic.

→ Reply

dddxhh

9 years ago, # ^ |

The logn comes from sorting the cost of all cells outside the loop.

→ Reply

klamathix

9 years ago, # ^ |

+13

I know, that's why I was suggesting that we drop the sorting and partition the cells instead.

→ Reply

9 years ago, # ^ |

Ah, and that's the solution. Thanks.

→ Reply

AU.Bahosain

9 years ago, # ^ |

"I didn't see anyone passed with such solution ."

→ Reply

9 years ago, # ^ |

Oh. I thought you meant they coincidentally had minor typos, but the ideas make sense. But you inspired someone to find such a solution anyway, scroll up.

→ Reply

Junior94

9 years ago, # ^ |

← Rev. 2 →

Mine was O(n^2 (k^3 + k ^ 2 log(k ^ 2))) and it passed. I was actually testing for K = 100 and it was running in 9 seconds locally but I decided to submit anyway. Only during the challenge phase I noticed that K was at most 10.

→ Reply

I_love_Tanya_Romanova

9 years ago, # ^ |

← Rev. 5 →

+29

It can be also solved with a lot of other possible complexities. For a different brute working in N^2+K^5 (something like "check K^2+1 best cells") K=100 will be too much :)

Looking at standings, this problem was already too hard for div1 250, with higher constraints it will be an overkill.

Spoiled challenge phase? In which way?.. If you don't have an idea how many operations can be performed within 2 seconds — that's not fault of TC. If you are not sure about such solution — write it during intermission and run on maxtest. Sounds like an obvious part of preparation for challenge phase.

I checked my solution both at CF (honestly I simply forgot that I can run custom test at TC) and later at TC to make sure that it works fast enough. It works in 0.7 without any break's etc., so probably constraints are not too strict for naive solution.

And while I don't like this problem in general, yet I think that it will be a good lesson to people who think that 1 second is equal to 10^7 operations.

Upd. I see a lot of messages about naive solutions getting TL; it is a bit surprisingly for me. Maybe I am wrong about constrants being not too strict. Still we have n^4*k/2 here, which is 5*10^8 pretty simple operations. I used to believe it should pass without any problems.

→ Reply

vlyubin

9 years ago, # ^ |

+11

Well, if there's time to write a dumb solution then it's the best way. I resubmitted this problem, because my original solution was too slow (I ran it on TC and it got TLE), so I rewrote it and was under impression that other solutions can TLE as well.

10^9 additions are OK, 10^9 array accesses are on the edge.

My complaint is that ideally authors should avoid putting bounds that are on the edge. For example, if n is 5*10^5, everyone will understand that n^2 is too slow. The only exception to this rule is when author is trying to hide greedy approach for the solution or something.

P.S. Did someone get n^4*k AC with Java?

→ Reply

martinezgjuan

9 years ago, # ^ |

My n^4 * k in Java didn't pass. Maybe I could have optimized a bit. But I think it's not nice that n^4 * k^2 in C++ can pass while most n^4 * k can't pass in Java. The constraints should be set so that solutions of the same complexity pass (at least regarding C++ and Java).

→ Reply

Junior94

9 years ago, # ^ |

rng_58 mentioned below that they didn't notice that solutions with complexity O(n ^ 4 k) could pass. And maybe the problem author tested his solution in Java. It's pretty rare that the expected solution doesn't run in time for Java in TC.

→ Reply

9 years ago, # ^ |

Yes, the author's solution must always be in Java. It's hardwired in the problem submission applet (MPSQAS).

→ Reply

riadwaw

9 years ago, # ^ |

← Rev. 2 →

I think that any solution that is intended to pass should do that in 2x(and for TC its even more because of lack of pre-testing).

And 10^9 is clearly near the boundary.

→ Reply

9 years ago, # ^ |

+36

It is a common opinion that constant optimization is bad and evil and should never be required in a contest. In an ideal world, CPUs could do 10^1000 operations per second, and we would set n=10^400, and it would be clear that asymptotics are everything.

The complaint here is that it would be possible (and easy) to make sure that constant optimization doesn't matter. If you want n^4k^2 to pass, set n=40: it passes easily and you still don't have any unintended brute force passing. If you don't want it to pass, set n=500, and the intended n^2k^2log(n) still passes easily. But with the current n=100, some n^4k^2 implementations pass and some fail, and many of them are very close to the border, making it near impossible to figure out whether a challenge is needed.

→ Reply

9 years ago, # ^ |

I solved 250 without any thinking. I don't really like it, either.

Just bruteforce all costs for all possible (i, j), sort them by decreasing cost, try all placements of (i₁, j₁) for base 1 in this order, for each of them all placements (i₂, j₂) of base 2 with smaller cost in this order. Bruteforce the cost of their intersection. If it's 0, break the inner loop (nothing better to find).

It should run decently fast, something like O(N^2K⁴) worst case, with obvious optimisations like precomputing the intersection cells for all interesting values of (i₂ - i₁, j₂ - j₁).

→ Reply

rng_58

9 years ago, # ^ |

+44

Yes, sorry, we completely agree with you. We didn't notice that O(n^4 * k) is so small.

→ Reply

tenshi_kanade

9 years ago, # ^ |

I did a O(k * n⁴) brute force solution that tried all possible pairs for each station, but counting each pair only once (second station must be to the right or lower than first station) and it passed system tests with the slower test case working in barely over 1 second, so the time limit was pretty comfortable for the given constraints.

→ Reply

Sumeet.Varma

9 years ago, # ^ |

No.. the time limit was not "pretty comfortable" . Thinking that naive brute force solution of O(n^4*k) would definitely time out, many people including me coded a better algorithm in terms of complexity (e.g. i did O(n^2*k^2*log(n))) which obviously took me much more time to code.

→ Reply

tenshi_kanade

9 years ago, # ^ |

+13

n⁴ * k for the current values of n and k is 1000M operations, which at first glance should time out for 2 seconds. But if you give it a better analysis, you'll see why it passes.

Prune the search by only counting each pair of stations once (do not count a, b and b, a) and you'll lower the operations to 500M.
Consider that some cells will have out of bounds neighbours, so there will be even fewer operations, maybe something like 400M~450M.
All operations are simple additions and for loops, so you should expect a much higher number of operations per second than with more complex algorithms.

→ Reply

-XraY-

9 years ago, # ^ |

← Rev. 2 →

Upd: I was wrong, couldn't find break with some sorted sequence.

→ Reply

9 years ago, # |

Huh, does anyone have any idea how to solve hard? Burnside lemma obviously needs to be applied and group generated by those operations described is group of permutations, but counting those stabilizers seems to be very hard problem. Maybe we can start by asking ourselves about an easier problem — we are given a permutation — how to compute size of its stabilizer?

→ Reply

rng_58

9 years ago, # ^ |

+13

Hint: construct a graph with n vertices, and if the i-th element is j, add a directed edge from vertex i to vertex j.

→ Reply

9 years ago, # ^ |

Did you mean ith element of permutation or ith element of a particular array from S? Am I right that Burnside's lemma needs to be applied? I already considered how permutation decomposes into cycles, but it seems hard to get a good grisp of which arrays remain unchanged under an action of a fixed permutation. If I'm not mistaken then if we have a cycle of length l then on corresponding positions in array we should put elements from a cycle of length d such that d divides l. But that constraint on k makes everything much harder and we are not allowed to count permutations one by one, so...

→ Reply

9 years ago, # ^ |

+16

The symmetric group acts like conjugation (prove this!). Think about what the conjugation classes are for k=1 (you have probably seen this before) and prove that it's the same idea for every k. Then it should be obvious how to count the classes.

→ Reply

martinezgjuan

9 years ago, # |

Could you please give a general idea of you solutions for Div1 250? The complexities that you are mentioning seem to vary a lot.

→ Reply

9 years ago, # |

← Rev. 2 →

Could anyone tell what were possible approaches to hacking 250? There were very many hacked solutions, but I don't feel like going through all those tons of different long and ugly codes. I also don't believe that most of hacks were caused by TLE since as already established here, TC servers are so fast that even most naive bruteforce O(n⁴k) could pass (I tried hacking O(n⁴), but of course my attempt was unsuccessful).

Btw, what the hell is wrong with CF LaTeX — "n^4 k" shows as if it would be n^{4k} x_0??

→ Reply

Junior94

9 years ago, # ^ |

← Rev. 2 →

a = 000000,109901 x = 0,0,0 y = 0,1,2

For those who had a greedy solution (trying to choose the maximum station first).

→ Reply

eagle93

9 years ago, # ^ |

I hacked for WA, most of them add the value of cell two times, the correct answer is 55

{"1191111","1919111","1191911","1119111"}
{-1, 0, 0, 1}
{0, -1, 1, 0}

→ Reply

I_love_Tanya_Romanova

9 years ago, # ^ |

Samples are well-picked, as usual :)

At first glance it seems that simply picking two best cells and prinintg sum of their scores (without even taking care about cells counted twice) passes them. Am I right? :)

Picking best cell and then best cell among remaining ones definitely passes samples, and I saw a few such solutions.

Some people submitted O(N⁴ * K²). Some people submitted it with some heuristics :)

Lot of people simply had bugs. As I said, it seems that you may pass samples without even taking care about cells counted twice.

P.S. And I believe that O(N^4k) will not work within 2 seconds :)

→ Reply

9 years ago, # ^ |

I hacked a solution which always considered n == m.

→ Reply

9 years ago, # ^ |

Was it passing at least samples :d?

→ Reply

9 years ago, # ^ |

Yes as all examples except last one had n==m. And in the last example the answer was 0 :)

→ Reply

9 years ago, # ^ |

What's more — that solution also passed 2 TLE challenges as the provided input was n == m == 100.

→ Reply

fruwajacybyk

9 years ago, # ^ |

Unfortunately it passed samples. I had FOR(i,0,n) FOR(j,0,n) istead of FOR(i,0,n) FOR(j,0,m) ... One letter from AC :/

→ Reply