WA in INOI 2013 Qn SEQENCELAND

general
,
1

Hi!
Can you please point out my mistake?
I’m getting a WA for the SEQUENCELAND question from INOI 2013.

CODE: http://pastebin.com/CvNiuXdT
QUESTION STATEMENT: www.iarcs.org.in/inoi/2013/inoi2013/inoi2013-qpaper.pdf (Question 2)

Thanks!!

1 Like
2

Can you explain me your algorithm .I cant understand what You have done . I got correct on this

3

Did you get the last test case on the present server right? I got WA only on that, checked out the last test case and it seems incorrect to me.

4

No ,i Had no such problem with my code .

5

NM, I was just counting extra.
The 's’s overlap.
If any1 still wants an explanation, please do ask.

6

Yes , please tell me your approach , i wrote a very long code for it n^3 complexity

7

Step 1: President = citizen # 0… Build adjacency list by scanning all pairs of citizens … O(n^2)
Step 2: Using adjacency create a graph matrix with connections represented by 1 and disconnections by INFINITY
Step 3: Using BreadthFirstSearch from each vertex (citizen#) traverse graph till you reach president. Maintain a count as to how many of your BFS reached the President.
This should be less that O(n^3).
@vgamma @adityakhanna1999

8

How did you create the matrix in n^2?

Mine would be n^3 for worst case.
@aalok_sathe