I said don't spoil it

That problem asks for the minimum number of steps while I ask for a strategy.
You can solve this one in your head and also generalize to higher n. In the problem you mention the solution is exponential.

http://infoarena.ro/blog/fox-hunting

@t3st your example has a small bug.

Think of it as a pseudocode example, instead of Python if that makes it less confusing .

Python threading sucks but the code is somewhat shorter than a Java equivalent.

http://infoarena.ro/blog/counter

@Corrie, the problem mentions that using the same number more than once is ok. You can do a similar solution if you don't want to have numbers repeated but it's slightly more involved.

Yup, it's a typo. Thanks Oleg.

http://infoarena.ro/blog/meet-in-the-middle

@Mircea, you know your proof contradicts a well established result in probability. Instead of spamming the forum you may consider publishing your result in a peer reviewed probability hournal.

@Mircea, man, you're so verbose, it's a chore to read each post even if it may be correct .

@Mircea, I don't see a way to frame it as a network flow problem. So it must not be that easy .

Couldn't follow your second idea. Will give it another try later.

At least one has to guess his own number. They get just one try.

https://infoarena.ro/blog/numbered-hats

You can try it here http://infoarena.ro/problema/rev

There's a more efficient solution using treaps (treaps have fast split and merge operations).

Petru told me another one where the sqrt n trick is pretty handy:
http://infoarena.ro/problema/drumuri4

Implement an efficient datastructure:
You start from n lists of one element. You can do updates: break a list in two or Join two lists. You can do index queries.

Yes, basically you work with 2k + 1 lists instead of working with n numbers. First you have one list, then three and so on.

For each list you know the start index and end index. Reversing a list means swapping it's boundaries.

Reversing a new range involves creating 2 new lists and reversing all the lists that are within the current range. If you have x lists, doing an update takes O(x).

So doing sqrt(n) offline reverse updates takes O(sqrt(n) * sqrt(n) + n) = O(n) time.

let's see what happens for
n = 10 and
reverse(3,7)
reverse(5,9)

first you have the whole range
[1..10]

[1,2] [3,4,5,6,7] [8,9,10]
reverse(3,7)
[1,2], [7, 6, 5, 4, 3] [8, 9, 10]

[1,2] [7, 6] [5, 4, 3] [8, 9] [10]
reverse(5, 10)
[1, 2] [7, 6] [9, 8] [3, 4, 5] [10]

So the idea is that you play with compact lists of consecutive indexes. Each update increases the number of lists by 2 and reverses the order of the lists.

k updates in O(k^2 + n) time:
Work with ranges of numbers instead of one number at a time. Each new update will increase the number of disjoint ranges by 2. Performing a reverse over k ranges will take O(k) time. Then you can get the modified array in O(k + n) time.

did I answer your question?

Hint: If you have x updates and then one query you can respond to the query in O(x) by going through the updates backwards.

Queries, updates are given in the input.

You can split the queries/uptates in batches of length sqrt(n).

You can solve the problem by using Stirling's n! approximation and use lg to get the number of digits.

The way I solved it more than 10 years ago was precompute the cumulative sums and store every kth sum. Then either go from [n/k] * k up or [n/k + 1] * k down. This way I could trade off binary size vs algorithm speed .

@Claudiu, sounds good.

Here's another one:
We start with an array A of unique integers from 0 to n - 1 then we are given n <= 30000 updates and queries.
- reverse(i, j): reverses the order of the elements in A[i..j]
- get(i): returns A
Come up with an algorithm faster than O(n^2) that can run these operations.

I made a mistake in the median problem. I updated the query complexity to be O(sqrt(n)log(n)log(U)).

@Andrei, your solutions look correct.

Here are two other problems:
1. You are given 2 eggs. You have access to a 100-story building. Eggs can be very hard or very fragile means it may break if dropped from the first floor or may not even break if dropped from 100 th floor.Both eggs are identical.  You need to figure out the highest floor of a 100-storey building an egg can be dropped without breaking. Now the question is how many drops you need to make. You are allowed to break 2 eggs in the process.
2. Compute the number of digits of n! n <= 1000000000

http://infoarena.ro/blog/square-root-trick

Care e algoritmul tau preferat?
Care e problema ta preferata pe infoarena?

Comentarii la postul http://infoarena.ro/blog/interviu-cosmin-gheorghe