Обсуждение @ 1650. Миллиардеры @ Timus Online Judge

Страница 1

roman velichkin Could you explain some moments in this problem? // Задача 1650. Миллиардеры 1 июн 2022 13:12

YDZz wa16 [1] // Задача 1650. Миллиардеры 27 сен 2019 22:13

reshke'` wa5 in c# // Задача 1650. Миллиардеры 30 апр 2018 01:57

AntiBug test #1 [1] // Задача 1650. Миллиардеры 31 окт 2013 11:01

alp tests not full [1] // Задача 1650. Миллиардеры 6 мар 2012 22:25

ibra (TNU) Test that helped me // Задача 1650. Миллиардеры 9 янв 2012 02:59

Popa Mihai Test // Задача 1650. Миллиардеры 28 сен 2011 20:16

igorsky TLE7 C# [1] // Задача 1650. Миллиардеры 26 ноя 2009 17:31

igorsky WA5 [1] // Задача 1650. Миллиардеры 25 ноя 2009 17:26

Zayakin Andrey[PermSU] maybe hint // Задача 1650. Миллиардеры 6 сен 2009 05:52

Mr.Arsalan I've got TLE with heap [6] // Задача 1650. Миллиардеры 22 янв 2009 17:07

It seems that the time limit for this problem is so tight, because I used heap + set and map and I got TLE. Does anybody have any suggestions?

Edited by author 22.01.2009 17:08

Vedernikoff Sergey (HSE: EconomicsForever!) Re: I've got TLE with heap [5] // Задача 1650. Миллиардеры 22 янв 2009 17:15

I've used almost the same structures and AC. Try to optimize your program. Do you use scanf()/printf() for input/output?

Mr.Arsalan Re: I've got TLE with heap [4] // Задача 1650. Миллиардеры 22 янв 2009 19:10

Thank for your Reply.
Yeah, I used scanf/printf for IO. I think I should have reduce the number of maps in my code. I used following structures:
map < string , int > city_to_index ;// locate the position of each city in the heap.
map < string , string > where;// locate the city in where the billionaire is
map < string , LL > how_much;// the amount of money each billionaire has
map < string , int > answer;// the answers
Do you have any idea to reduce them?
One problem that I think that my cause TLE is that I built my heap in array and each time I update my heap I should have change the values in city_to_index. Maybe if I implement it with pointers would be better. I mean, it may be better to build the heap with pointers and for swapping the nodes their addresses in city_to_index remains unchanged. (map<string,node*> city_to_index) IT IS SOMEHOW COMPLICATED FOR ME TO IMPLEMENT IN THAT WAY, DO YOU HAVE ANOTHER IDEA?

Edited by author 22.01.2009 19:23

svr Re: I've got TLE with heap [3] // Задача 1650. Миллиардеры 22 янв 2009 19:23

You must before coding be sure in time and
space limits of your algo. This is difficult but
is core of programming skills.
You take right general plan remove bags and get AC.

Mr.Arsalan Re: I've got TLE with heap [2] // Задача 1650. Миллиардеры 22 янв 2009 19:31

Thanks for your advice. I had though about them before implementing my solution. and I think my running time except the part dealing with maps is O(lg n) per line of input and it is perfectly OK, and that's why I asked in forum about how to get rid of TLE.

Edited by author 22.01.2009 19:36

Mr.Arsalan Re: I've got TLE with heap [1] // Задача 1650. Миллиардеры 24 янв 2009 00:33

I've reduce the number of maps in my solution and now it gives WA on test #10. Is there any tricky test cases?

ValenKof Re: I've got TLE with heap // Задача 1650. Миллиардеры 18 дек 2011 05:10

I used maps, set, vectors, cin & cout and my program works 0.875. There is no need in scanf().

vgu Wonderful problem [2] // Задача 1650. Миллиардеры 2 ноя 2008 03:56

Vedernikoff Sergey (HSE: EconomicsForever!) Clarification [2] // Задача 1650. Миллиардеры 1 ноя 2008 16:41

Страницы: 1

Вид форума: плоский | древовидный | классический
Сортировка веток: всплывающая | фиксированная

Обсуждение задачи 1650. Миллиардеры