Daca cei 2 penali si-o data seama care is dar din motive o afisat alte numere? Se pune gresit?

E normal ca numarul de elemente din vector sa fie mai mic decat elementele din queryuri?!

4
4 5
1 2
1 3
1 4
2 4
3 4

-> aici trebuie sa fie ceva, dar clar nu e 1
1 4
3 2
1 2
1 3
1 3

3 3
1 2
1 3
2 3

2 3
2 1
2 1
1 2

2 val - Comisarii vor să ştie dacă ar fi să elimine începând cu gangsterul de pe poziţia pos, folosind metoda menţionată, câţi mafioţi ar fi suprimaţi?

Not sure if a trap or not

#10 it's simple.
we have a bipartite graph, and then assume that cost(G) is equal to the number of edges that are wrong, that is the same 2 persons are in the same team or w/e

let's say that cost(G) is equal to s
if 1 person is on the left side, and it has 2 enemies, we can move him to the other table or side, and than he has only 1 enemy.
if we do this, we extract from s 2 and then add 1 to it (by moving it in the wrong side)
in this manner we can do this at most 2 * n times or so and at the end of the day we will end with at most 1 enemy for every guy.

maybe we can do better, like cost(G) = 0, but we only need to have at most 1 enemy so this will do it

For #1 since it's the squared distance, the x and y coordinates are independent to each other
Hence, the cost for x is sum((x[itr] - cX) ^ 2)
And this is sum(x[itr] * x[itr] - 2 * cX * x[itr] + cX * cx)
From this we have a 2nd degree equation
N * cX * cX - 2 * cX * sum(x[itr]) + sum(x[itr] * x[itr])
And cX = sum(x[itr]) / N

#[2, 5] it is correct to do some hill climbing like ... right?

Cod:

rez = [0, 0]
p = maxRange
while p >= 0:
  mn = f(rez)
  where = -1
  for dir in allDirections(2 * nrDimensions):
    if f(rez + changeDir[dir] * p) < mn:
      mn = f(rez + changeDir[dir] * p)
      where = dir
  if where == -1:
    p /= 2
  else 
    rez = changeDir[where] * p + rez

this should run in O(N * logMaxRange * nrDimension) ~ around there
with a bigger, lets say, constant

#11 Is there a faster way than making a min-matching in the graph, and the result is just the answer?

It's ok, but you need to take care when pushing the children in the heap; you need to keep track of the children which are inside the heap.
for example if you expand the elements in this order
125
346
789

the element 4 will be expanded from 2 and 3
this problem is for all the elements; at the end of the day you heap will have double the size, because all the elements which are not on raw 1 or col 1 will be expanded 2 times, but this is not a problem after all.

And logK vs logN is not such a big deal after all
if K >= N you will have logN anyway

  Thanks Cosmin for all these beautiful problems and all your involvement in Infoarena

#7 can be solved with that, but IMO the array solution with 2 pointers is better.

For the Young Tableau you can use binary search to search the value, than O(N) to see how many values <= that are in the array


If you want sth that goes well with K, you can go sth like O(KlogN), keeping on every row the first element, like in the merge or N arrays problem
But you are not using the fact that they are sorted on rows too .. i will think about this a lil bit more, but the bs solution seems legit enought

#1 it depends how do you define efficient
Do your heap needs to occupy O(N) memory with the 2 * nod + 1 trick for sons, or it should be just a tree with heap property

#2 keep a heap with the first element of every array.
take the smallers one from that heap and put the next element from that array into the heap
O(sum_or_arrays * logK)

#3 keep a min-heap with the first k elements in it. Erase the top, put it in #1 and put #k+1 into the heap -> repeat O(NlogK)

#4 -> you can keep a max-heap limited to size k
insert into heep. while(heap.size() > k) { heap.pop(); }
O(N + NlogK)

ORRRRR you can use kTh element and then sort the first k elements of the array.
it depends if the first K elements should be sorted or not O(N) vs O(N + KlogK)

#5 > or >= ?

#6 I won't fall for that problem AGAIN
someone told me like 3 years ago. From what I heard it was given to Bogdan Tataroiu at his Google/Dropbox interview(I don't remember). And there is the O(KlogK) solution, but there is another O(K) solution. I thought about if for 2 years, and then someone told me it's a cool paper and stuff ..
But there is O(K)

#7 immagine that you have the first 8 numbers computed

Cod:

1 2 3 4 6 8 9 12
           3 2

Than we want to expand this sequence further, and if we want to expand it with 2, the next element whould be at least [12 / 2] + 1
in this case, 8, since we can't make 7
The same applies for 3, [12 / 3] + 1 = 5 -> 6

now we just take the smallest of these numbers and go on.
We don't have to binary search this positions, since they will only grow.
We can just keep 2 pointers at every moment and just itterate throu them.
-> O(N) and prints first N elements made out of 2 and 3
Here is some python code for it

Cod:

#n = int(raw_input())
n = 5000000

exp = [2, 3]
where = [0, 0]
rez = [1]
now = [0, 0]

for i in range(n - 1):
	for i in range(2):
		now[i] = exp[i] * rez[where[i]]
	mn = min(now)
	rez.append(mn)
	for i in range(2):
		if now[i] == mn:
			where[i] += 1

print rez

OFFTOPIC
if you just want the Nthelement, or the sum of the first N elements for 2 factors you can get that in
O(sqrt(N)*logN)
I made a test for factors 2, 3 and 5 and the algo runs in O(N^(2/3) * logN)
and that is a big improvement, since the memory is O(1)

Here is some C++ code for factors (2, 3, 5) and it runs is 0.4 for 10^8 -> BEAT THAT O(N)
http://ideone.com/wwn5QD

I really like this problem

#8
We have
maxHeap - minHeap
if we have 2*n elements
we keep the lower N elements in maxHeap, than the biggest N elements in the minHeap

if the 2 heaps are equal, the medial is maxHeap.top()
else, it is the.top() of the biggest Heap.
Now we want to keep the abs(maxHeap.size() - minHeap.size()) <= 1
if that overflows, we just.pop one and push the value in the other heap.

#9 problem #9 and #5 are mostly the same, since in #9 C[j] = A + B[j] and C is a Young Tableau

#10
The solution should be better than O(K), right?

Gogu is right.
The most basic aproach to this problem is the T*P DP.
DP[len][itr] = biggest index such that [DP[len][itr] ... len] containts P[1 .. itr]

Actually on every iteration the DP uses nrOfTimesThisLetterIsInP steps to recalculate the DP
So if P is made out of unique characters, it's O(T)

At the end of the day, IMO, you can't use some kind of KMP shenanigans since the pattern can be really messy.
If you have some kind of abbabaabbaababba as P and T is made of abbabaabbaababbCabbabaabbaababbCabbabaabbaababba
I don't think you can do better than O(T*P), since every letter REALLY CHANGES half of the values in the DP .. but you need to compute it all, hoping that you will find the pattern (in this case, at the end of the string)

It seems strange that a trivial solution runs so good, and it's kinda intuitive.
Maybe there's another way around it. I will think about it, because this seems kinda simple, to be honest.

În restricții scrie a>p dar în exemplu e invers. Cum e corect?

Se garanteaza ca numerele sunt != 0?

Banuiesc ca trebuie sa afisam rezultatul care are cea mai mare sansa sa apara.

Daca diferenta de sansa e foarte, foarte mica, ce facem?
Afisam orice?