One Day , One Problem Story

Правка en1, от bluemmb, 2015-09-11 21:35:20

Hi , this is my today tough story and pictorial editorial for problem 389D/388B. ( first of all sorry for my english )

After lunch I decided to solve a hard problem ( compared to my skills ) Fox and Minimal path.

Problem wants a graph that total number of shortest paths between nodes 1,2 will be k (1<=k<=1e9). but I didn't know a simple condition will kill me today ... you can use at most 1000 nodes.

first time I decided to decompose k to prime factors and create paths like this :

I couldn't find any solution for big primes! but because I thought my solution is true so they will not be in test cases !!! After coding , submitting and getting WA on test 11 , and having no idea for another solution , I decided to read the editorial .

After reading the editorial I found that I am so stupid , why I forgot binary representation !!! anyway I start to reading his solution for know how to create graph. but it was terrible to understand! so I spend many time to know how this create the graph but ... :( ( a simple picture help people to understand what you said and wrote, please! )

I started hard to thinking on create the tree and found this solution :

but it uses about 2000 nodes and certainly it will get WA.

Again started to thinking about reducing the number of nodes and yeaaaa , i find it !!!

I did a mistake in my calculation and after coding and print last id ... O NOOOOOO !!! extra 50 nodes exist :((( ( later I figure it out that maybe with deleting some nodes can reduce it to <=1000 )

damn it :( give up and watch next section of Breaking Bad serial ...

but ... suddenly I compressed the simple roads of last graph in my imagination and it seems good!

rapidly , started to proving that this graph can't have extra nodes and can't create extra shortest paths and it was so simple to proof. it was like this :

Again clean whole last code and write from zero ... Run ... OOKKKKK : last id = 185 !!! It seems ok, but because of big output , I couldn't check it and decided to entrust it to codeforces checker. I was tired and scared that it will wrong again, so I was watching the numbers ... test 10 ... test 13 ... test 29 ... OK ... Accepted :) :) :)

It was like a Refresh for my Head CPU. so i decided to reduce number of nodes again ... after some minutes, again I compressed some of paths and nodes and it was like this :

This time changing a bit in creator function was sufficient and again I am waiting for watch last id ... OH MY GOD : 94 nodes. And Solution ACCEPTED again.

I was so excited ... first time I thought that isn't solution for some numbers and I must be careful about using so efficient from nodes ... and after hard working whole necessary node is 94 :D

So Again, I learnt give up is not solution.

Теги story, #388, give up, editorial, suicide

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский bluemmb 2015-09-11 21:35:20 3470 Initial revision (published)