bully....maguire's blog

Google Kickstart round E discussion
By bully....maguire, 4 years ago, In English

Please share your ideas and ask for help for kickstart round E . Unfortunately someone made a blog previously and after few people discussed he/she deleted it .Please don't delete blogs after there is even one comment with positive votes. So many heavy downvotes , please don't do this ! . Blog becomes draft i.e invisible if it gets around -30 downvotes .

  • Vote: I like it
  • +22
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I tried to solve problem golden stone by going through every junction and choosing it as the center. I then did bfs from it to get the shortest path to every stone available in a junction. Then I went through the recipes by using an approach similar to djikstra (recipe with smallest sum of stone costs first). I got WA though, though I'm not sure if the approach is the problem or my code.

https://codingcompetitions.withgoogle.com/kickstart/submissions/000000000019ff47/TmVrZG8 here is my submission.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Oh, I think I know the problem. I only tried to use recipes in one node, while it can be beneficial to perform them in different nodes. That's probably why my solution didn't work. Oops.

    → Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

I didn't delete. It is done by Codeforces. They make it private. IDK why?

https://mirror.codeforces.com/blog/entry/81821

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

I managed to solve High Buildings by doing some heavy case work. Any elegant solution to the problem?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 4   Vote: I like it 0 Vote: I do not like it

    Here's my solution - a1=a-c (no of buildings only A can see), b1=b-c (no of buildings only B can see), and d=n-(a1+b1+c) (no of buildings no one can see).

    If d<0 the answer is impossible. Otherwise, first I built a list like (n-1) (n-1) (n-1)... a1 times, n n n... c times and (n-1) (n-1) (n-1)... b1 times. Then I inserted the remaining d 1s between any two buildings (obviously impossible if there is only one building).

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 4   Vote: I like it +1 Vote: I do not like it

    My solution was 3 cases.

    if a+b-c was greater than n or a+b was =2 (an exclusion is for n=1) the answer was impossible.

    1. n>=3 (General case where I made c highest buildings (of height 3) from left the remaining a-c units as 2 and from right the remaining b-c units as 2 and rest as 1, I placed the 1 height buildings in between max height buildings. Applicable when both a and b were greater than 1)

    1.1 (a=1 and b greater than 1. Make a highest on left = to 3. Remaining b-1 as 2. and leftovers as 1 between left and right ends)

    1.2 (a>1 and b=1. Same as 1.1)

    1. n=2 (I manually wrote for this. Cases were a=2,b=2,c=2. a=1,b=2,c=1. a=2,b=1,c=1.)
    2. n=1 (single case)

    My kickstart id- Sayan_244

    I posted my approach to get a better and cleaner solution. (I feel this a rather poor way of solving the problem)

    → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Can somebody tell me a test-case where my brute force solution for C fails ?

Link : https://ideone.com/zKxKGi

→ Reply