Topcoder Single Round Match 660

9 лет назад, # ^ |

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

→ Ответить

k0st1a

9 лет назад, # ^ |

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

→ Ответить

9 лет назад, # ^ |

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.

→ Ответить

monkey.coder

9 лет назад, # |

← Rev. 2 →

almost all of div2hard's submission have been hacked lol

→ Ответить

minimario

9 лет назад, # ^ |

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

→ Ответить

404Error

9 лет назад, # ^ |

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.

→ Ответить

nherceg

9 лет назад, # ^ |

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

→ Ответить

Roberio

9 лет назад, # ^ |

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

→ Ответить

-emli-

9 лет назад, # |

← Rev. 2 →

Как решать вторую задачу из Div2?

→ Ответить

vintage_Vlad_Makeev

9 лет назад, # ^ |

Систесты еще не кончились, но вроде это правда:

Построим орграф с ребрами i->a[i] и запустим топологическую сортировку. То, что получим — и есть оптимальная перестановка. Почему это так? У нас есть 2 типа компонент связности: бамбук с петлей на конце и большой цикл. Бамбук правильно отсортируется ибо петля ни на что не влияет. Цикл отсортируется правильно, потому что вне зависимости от начальной вершины ответ всегда "количество вершин в цикле" — 1.

P.S. Пока писал — зашло

→ Ответить

-emli-

9 лет назад, # ^ |

Можно ли решить полным перебором?

→ Ответить

vintage_Vlad_Makeev

9 лет назад, # ^ |

Смотря каким.

У меня с ходу ничего кроме O(n!) в голову не пришло, но 50! — это нереально много

→ Ответить

vlyubin

9 лет назад, # |

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

→ Ответить

Reyna

9 лет назад, # ^ |

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

→ Ответить

I_love_tigersugar

9 лет назад, # ^ |

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

→ Ответить

riadwaw

9 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

vlyubin

9 лет назад, # ^ |

That would be OK too ...

→ Ответить

Lewin

9 лет назад, # ^ |

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

→ Ответить

AU.Bahosain

9 лет назад, # ^ |

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

→ Ответить

9 лет назад, # ^ |

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

→ Ответить

klamathix

9 лет назад, # ^ |

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.

→ Ответить

9 лет назад, # ^ |

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

→ Ответить

klamathix

9 лет назад, # ^ |

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

→ Ответить

dddxhh

9 лет назад, # ^ |

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

→ Ответить

klamathix

9 лет назад, # ^ |

+13

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

→ Ответить

9 лет назад, # ^ |

Ah, and that's the solution. Thanks.

→ Ответить

AU.Bahosain

9 лет назад, # ^ |

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

→ Ответить

9 лет назад, # ^ |

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.

→ Ответить

Junior94

9 лет назад, # ^ |

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

→ Ответить

I_love_Tanya_Romanova

9 лет назад, # ^ |

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

→ Ответить

vlyubin

9 лет назад, # ^ |

+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?

→ Ответить

martinezgjuan

9 лет назад, # ^ |

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

→ Ответить

Junior94

9 лет назад, # ^ |

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.

→ Ответить

9 лет назад, # ^ |

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

→ Ответить

riadwaw

9 лет назад, # ^ |

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

→ Ответить

9 лет назад, # ^ |

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

→ Ответить

9 лет назад, # ^ |

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

→ Ответить

rng_58

9 лет назад, # ^ |

+44

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

→ Ответить

tenshi_kanade

9 лет назад, # ^ |

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.

→ Ответить

Sumeet.Varma

9 лет назад, # ^ |

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.

→ Ответить

tenshi_kanade

9 лет назад, # ^ |

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

→ Ответить

-XraY-

9 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

halin.george

9 лет назад, # |

Никто не спрашивает почему-то: как решать div.2 Hard?

→ Ответить

9 лет назад, # |

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?

→ Ответить

rng_58

9 лет назад, # ^ |

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

→ Ответить

9 лет назад, # ^ |

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

→ Ответить

9 лет назад, # ^ |

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

→ Ответить

martinezgjuan

9 лет назад, # |

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

→ Ответить

9 лет назад, # |

← 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??

→ Ответить

Junior94

9 лет назад, # ^ |

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

→ Ответить

eagle93

9 лет назад, # ^ |

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}

→ Ответить

I_love_Tanya_Romanova

9 лет назад, # ^ |

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

→ Ответить

9 лет назад, # ^ |

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

→ Ответить

9 лет назад, # ^ |

Was it passing at least samples :d?

→ Ответить

9 лет назад, # ^ |

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

→ Ответить

9 лет назад, # ^ |

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

→ Ответить

fruwajacybyk

9 лет назад, # ^ |

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 :/

→ Ответить