Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

Armyx's blog

By Armyx, history, 5 years ago, ,

I solved this problem http://codeforces.com/contest/449/problem/B using dijkstra based on priority queue and I got TLE (http://codeforces.com/contest/449/submission/13186398) on test 45. After that I changed it to TreeSet ( http://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

• +3

By Armyx, history, 5 years ago, ,

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 ?

• +1

By Armyx, history, 5 years ago, ,

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 ?

• +56

By Armyx, 5 years ago, ,

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 ?

• 0

By Armyx, 5 years ago, ,

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

update it's available now

• +14

By Armyx, 5 years ago, ,

to be deleted

• -7

By Armyx, 5 years ago, ,

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

• +3

By Armyx, 5 years ago, ,

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 ?