SPOJ FREQUENT

general
,
1

I have been trying this problem on SPOJ

but, I am getting WA. Can someone please help me?
Here is my code ks5nlh - Online C++0x Compiler & Debugging Tool - Ideone.com

2

You must read multiple test cases. “The last test case is followed by a line containing a single 0.”

1 Like
3

All you have to do is-

while(true)
{
....
scanf("%d %d",&n,&q);
if(n==0) break;
..
...
}

Its good that C++ is able to handle I/O things well.

But can anyone tell me, what would you do if it were python or JAVA?

Since input is like, 2 pairs of integers, until 1 final 0. (I expect it will give some exception or error for this). So how will you guys handle this??

4

Will someone please explain how to solve this problem by storing the frequencies of contiguous elements and then by applying Range Maximum Query? Also please explain other approaches as well? Please?

5

Yup, his code is getting accepted elsewise. Thats all

6

But what for languages like python and java??

7

Thank you.

8

Trivia, scanf actually returns the number of variables read. So you can do something like:

while (scanf("%d%d", &n, &q) == 2 && n != 0) {
    // code here
}

For other languages like python and Java, probably something like try catch?

1 Like
9

Thank @hikarico , he pointed the error out first ^^

10

Nice, thats also quite good @hikarico . But what for languages like JAVA and python where even a extra space or line causes error??

11

For Java, firstly take only “n” as an input and then check -
Scanner sc = new Scanner(System.in);
while(true){
int n = sc.nextInt();
if(n == 0)
break;
int q = sc.nextInt();
}

1 Like
12

For Java, if you’re using BufferedReader you can do it like this:

String line;
while ((line = br.readLine()) != null) {
  String[] sp = line.trim().split("\\\\s+");
  if (sp.length != 2) break; // not enough
  int n = Integer.parseInt(sp[0]);
  int q = Integer.parseInt(sp[1]);
  // ...
}

Or, sometimes it’s better to just ask for forgiveness:

try {
  while (true) {
    String[] sp = br.readLine().trim().split("\\\\s+");
    int n = Integer.parseInt(sp[0]), q = Integer.parseInt(sp[1]);
    // ...
  }
} catch (Exception e) {}
1 Like
13

The array is already nondecreasing. This means all equal elements are side-by-side. With that, you can find the leftmost and rightmost index of the same element. Then you can make a new array with value (rmost - lmost + 1), after which you can perform RMQ

14

Yeah, I did exactly the same thing but I’m getting Wa. I also know the test case where it is giving me wa but I don’t know how to modify my algo further. Will you please help?
Code : KBi3mM - Online Java Compiler & Debugging Tool - Ideone.com

15

It shouldnt be a “simple” RMQ. I feel storing just the frequency in node isnt enough. Lets say my array is {1,1,1,1,2,2} and i query for range [4,6] (1 based index). Then frequency array should be storing {1,2,3,4,1,2}, and by typical RMQ, it will give you ans = 4.

Why not try storing additional things like prefix and postfix of number as well?

I tried it with one of the nice logic of Stable Market (April Long), but time limit is strict here. It wants us to use segment trees :confused:

I will re attempt it after breakfast. :smiley:

16

@hikarico - What do you recommend storing in the node?

I tried a non segment tree approach (where we store prefix and postfix of the element, use formula - Length_of_Block= postfix-prefix+1 and then jump to the next block. But it gave TLE…

Eg- {1,1,1,2,2}. Prefix here is {0,0,0,1,1}, postfix here is {2,2,2,4,4}. Then, length of {1,1,1} can be directly put up as - 2-0+1=3. Then i jump through the entire {1,1,1} block to arrive at ‘2’.

Damn, test cases are strict :3

17

@vijju123 No, you are getting me wrong. My Freq array will be 4,2 and the interval array should be (0,3),(4,5) and then for the query 3,5 apply binary search on the left interval will lead to 0th index(Let it be ql) and after that apply binary search on the right interval it will lead me to the 1st index(Let it be qr). And then apply rmq for query(ql+1,qr) and also handle that corner case, and get maximum of both!

18

Okay, then you are on right lines. What bug did you find in this approach dear?

19

10 1
-1 -1 2 2 2 56 56 100 100 100
9 9
0
Here my output is 2. Ans should be 1. The problem is when i apply binary search. Insertion point of binary search is where i am having problem. In the above case ql>qr which is surely not what i want.

20

In Python, you can try:


nq = list(map(int, input().split()))
if len(nq)==1:
    break
n,q=nq[0], nq[1]