paramsingh's blog

By paramsingh, history, 5 years ago, In English

Hi there. I've been trying to solve http://www.spoj.com/problems/AKBAR/ for some time, but the only thing I can seem to come up with is starting a BFS from each of the soldiers as the source until the soldier's strength depth. However, that approach gives me a TLE. Any help regarding how to solve this problem would be appreciated. Thanks.

Here's the code for my approach that I tried (TLE): https://gist.github.com/paramsingh/81d728295e6bd01860a0

 
 
 
 
  • Vote: I like it
  • -1
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

say ALLAHU AKBAR and problem will solve itself.

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

using memset in lines 39+40 gave you the TLE

you don't need to do it for every soldier, if any city is previously visited by another soldier, then the flag turns false...

remember that "every city is protected by one and only one soldier.According to Akbar , this is the optimum placement."

if you need more help, just tell me ^_^

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Oh man, that was a really stupid mistake! Thanks a lot for the help, I've got it accepted now.

    :)

    • »
      »
      »
      18 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you help me with that TLE I'm unable understand above explanantion for AKBAR — Akbar , The great(spoj) problem

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

    Can you please tell me how to resolve TLE in this code http://ideone.com/ljgRhi ?

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

      rghv same mistake:

      using memset in line 42 gave you the TLE

      you don't need to do it for every soldier, if any city is previously visited by another soldier, then you should return false...

      remember that "every city is protected by one and only one soldier.According to Akbar , this is the optimum placement."

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

    what is wrong in my soluton for AKBAR? https://ideone.com/AonT8k

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

      I didn't even read a problem's statement, but by just looking to your code, I see some not reliable things...

      You should write:
      for (it = adj[s].begin(); it != adj[s].end(); it++) And since you don't need iterator, You better use:
      for (int value : adj[s])

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Can you please help me? I'm getting WA in this problem.

    My code: here

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey, I also used the same approach and getting TLE. Here's my code http://ideone.com/ljgRhi. Any help would be appreciated.

»
18 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have been trying the question for a day now. Can someone please tell me what is wrong in this solution? I don't want to put up a blog about this. So whoever sees this comment please help me. I would really appreciate it.

  • »
    »
    12 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Try these changes maybe:

    1. Line 13 - parent[node] = -1; to parent[node] = node;
    2. Line 25 - parent[next_node] = cur_node; to parent[next_node] = par[cur_node];
    3. Line 28 - else if(strength[next_node] != strength[cur_node] - 1 && parent[cur_node] != parent[next_node]) to else if(parent[cur_node] != parent[next_node])
    4. Line 67 - if(visited[i] == -1) to if(!visited[i])
    
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, it worked. I also understood my mistake. Thanks a lot for your help.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please see my solution. I'm getting a WA. This is the link https://ideone.com/hnGtXy

»
10 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Hey I am getting TLE in this problem; here is my code: HELP PLEASE!

from collections import defaultdict
for _ in range(int(input())):
    n,r,m = map(int,input().split())
    adj = defaultdict(list)
    for i in range(r):
        a,b=map(int,input().split())
        adj[a].append(b)
        adj[b].append(a)
    protected=defaultdict(bool)
    optimum=True
    for i in range(m):
        k,s = map(int,input().split())
        visited=defaultdict(bool)
        if protected[k]:optimum=False;break
        if s==0:
            if protected[k]: optimum=False;break
            else: protected[k]=True;continue
        circle=[k]
        for j in range(s):
            temp=[]
            for u in circle:
                for v in adj[u]:
                    if visited[v]:continue
                    if protected[v]: optimum=False;break
                    else: protected[v]=True
                    visited[v]=True
                    temp.append(v)
                if not optimum: break
            circle=temp.copy()
            if not optimum: break
        if not optimum: break
#         for i in under_prot:
#             protected[i]=True
#         under_prot=defaultdict(bool)
    if not optimum: print('No')
    elif len(protected)==n:print('Yes')
    else: print('No')
»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

please help me with the same problem, why my solution getting WA??

MY_Solution