I solved this problem http://mirror.codeforces.com/contest/449/problem/B using dijkstra based on priority queue and I got TLE (http://mirror.codeforces.com/contest/449/submission/13186398) on test 45. After that I changed it to TreeSet ( http://mirror.codeforces.com/contest/449/submission/13186483 ) and it runs ~940ms instead of > 2000ms . What is wrong with my previous solution ? I read that priority queue runs faster in practice and I saw that most java solutions use priority queue

I used to program in c++ and I know that dijkstra implemented on priority_queue works faster than the one implemented using set. What is the best dijkstra implementation in java ? Should I use TreeSet or Priority queue ?

I am going to apply for an internship at Google. I know there are mostly algorithmic questions, so my question is : How difficult those task are in comparison to codeforces tasks ( Div 1C , DIV 1D ? ) Do they require knowledge of specific data structures or they are just tricky modifications of well-known algorithms like dfs ?

I have learned this awesome data structure. It's clear for me that operations like add and sum works in O(log n) time, but is there any known trick to reduce complexity of initialization ? Let's say I want to start with an array array[] = { 2,4,5,7,0,0,1,6 } instead of 0's . Now I have to iterate through array and call add(array[i]) on each element which require O(log n) time, so the total complexity will be O(n log n). Can we do it better ?

Why CERC14 Europe region was deleted from Codeforces gym ? It was there about one or two weeks ago.

update it's available now

to be deleted

I was thinking about the problem I got at one of my exams at my university

Given a set of N words and M queries ( word s and number q) . To each query, my program should print YES if it is possible to form a word that is present in a set. I am allowed to add max q letters to given word s, but I can't change letter orders.

For example Given set S = { aataaf, cdef, bbb } and queries

aaaa 2 => YES, because I added t and f

fcd 1 => NO

I solved this using prefix tree, but is there a better way to solve this ? Complexity of prefix tree might be exponential or I implemented it in a wrong way. During my exam I was allowed to write brute force, but I found it interesting and that is why I am asking you for help

What is the the best graph representation in Java ? I used this

List<Integer> Graph[] = new List[n]

but is there any better implementation ? How to represent weighted graphs ?