LUNCHTIM - Editorial

VqKYqk - Online C++0x Compiler & Debugging Tool - Ideone.com
Here my solution in case someone requires it using queue and stack.
Earlier i had made a mistake using set to get the closest greater element to the right
Also can anyone check why
NHRGrZ - Online C++0x Compiler & Debugging Tool - Ideone.com is not working.

Oh My God, What blunder I have done. Thank you very much for responding.
I have change my code from -1 to Integer.MAX_VALUE, now its working fine.
Thanksā€¦

Please explain why Solution1 gave TLE and Solution 2 passed
Solution1
Solution2

Weak testcases !

1 Like

It clearly states that Proper testing was not done on this problem before the contest started. The worst input for an O(N^2) solution is N = 10^5 and a_i = k\ \forall\ i\isin[1, N], where k is some constant. If they had tested this input against an O(N^2) solution, there would have not been such a huge number of accepted submissions past night.

It is not fair to rejudge these submissions because the contest ended. If they (organisers) had realised about it during the contest and made an announcement saying solutions will be rejudged, it would have been a different story.

I agree that most of the participants have not even attempted by looking at the constraints. Some like me, who at least hoped for a partial score would have attempted with naive solutions and luckily got AC. And as the number of successful submissions increased, others started attempting the problem by submitting naive solutions.

Making the round unrated is kinda not possible because ratings have been updated long back. Reverting all these changes is not gonna help.

This is not against the ones who solved using O(N) or O(N\log{N}) solutions. I highly appreciate their efforts. This is just to advise organisers to properly test the problems and input data before they are put in contest.

This time, the problems in Div 3 were too easy, there were more than 1000 successful submissions for most difficult problem in Div 3., which is kinda not acceptable.

PS: This is just a personal opinion about past contest experience.

2 Likes

I have checked if there is any kind of worst case input, as described above, present in test data using the following code.

for test in range(int(input())):
    n = int(input())
    l = list(map(int, input().split()))
    if len(set(l)) == 1 and n >= 2 * 10**4:
        raise ValueError("Worst case input")

I got WA instead of RTE. It is clear that such input doesnā€™t exist in test data.

Can anybody please tell what is wrong in this codeā€¦ It not even printing anythingā€¦

#include<bits/stdc++.h>
using namespace std;
int main(){
int t,n,i;
cin>>t;
while(tā€“){
cin>>n;
int h[n],l[n],r[n];
stack s;
memset(l,0,sizeof(l));
memset(r,0,sizeofĀ®);
for(i=0;i<n;i++){
cin>>h[i];
}
for(i=0;i<n;i++){
if(s.size()==0);
else if(h[i]<s.top());
else if(h[i]>=s.top()){
while(s.size()!=0 && s.top()<h[i]){
if(s.top()==h[i])
l[i]+=1;
s.pop();
}
}
s.push(h[i]);
}

while(!s.empty())
s.pop();
for(i=n-1;i>=0;iā€“){
if(s.size()==0);
else if(h[i]<s.top());
else if(h[i]>=s.top()){
while(s.size()!=0 && s.top()<h[i]){
if(s.top()==h[i])
r[i]++;
s.pop();
}
}
s.push(h[i]);
}
for(i=0;i<n;i++){
cout<<l[i]+r[i]+ " ";
}
cout<<endl;
}
return 0;
}

PLease see the code from this link. Some of the words like stack is missing in copy-paste code above.

Just a question: does codechef ignore optimization pragmas? I curiously typed in a n*n solution just to see if thereā€™ll be any time difference, but there is none:

 #pragma GCC optimize("Ofast")
 #pragma GCC target("avx,avx2,fma")
 #pragma GCC optimization ("unroll-loops")
 
 #include <*iostream>
 #include<*vector>
 using namespace std;
 
 int main() {
 	
 	long long t, n, p, count; vector <long long int> a; 
 	std::cin >> t;
 	while(t--)
 	{
 	    std::cin >> n;
 	    while(n--)
 	    {
 	        std::cin >> p;
 	        a.push_back(p);
	    }
 	    for(long long int i=0;i<a.size(); i++)
 	    {
 	        count=0;
 	        for(p=0;p<a.size(); p++)
 	        {
 	            if(i!=p && a[p]==a[i])
 	            {
 	                count++;
 	            }
 	            if(a[p]>a[i])
 	            {
 	                if(i>p)
 	               { count=0;
 	               continue;}
 	                break;
 	            }
 	        }
 	        std::cout << count<<" " ;
 	    }
 	    std::cout  << std::endl;
 	    a.clear();
 	}
 	return 0;
 }

Nope. See my comment on the test data.

ah no, now n*n solution gets tle.

Na, I just submitted my Solution, it gave AC.

ā€¦the last but one took 4.84 secs? did I see wrong? wasnt the limit 1 sec?

Slower languages have increased time limits. Python gets 5X time limit. So, if the mentioned limit is 1s, Python gets 5s.

1 Like

Thank you so much! I did not know that. Does codechef ignore pragma optimizations (c++)?

You might want to ask this question to @ssjgz .

Iā€™d like to comment that my non-dp solution managed to get AC, but I believe the idea underlined in the editorial is effectively the same: the intuition of my sol was using monotonic stack and while collapsing elements in my monotonic stack, maintain info about the size of each componenent, where a component is a string of numbers that are the same.

The last call in the main method of insert is to clear out the monotonic stack.

#include <iostream>
#include <vector>
#include <set>
#include <queue>
#include <cmath>
#include <cstdio>
#include <algorithm>
#include <ctime>
#include <stack>
#include <map>
using namespace std;


int N;
int a[100010];
map<int,int> ans;
struct MonotonicStack{
	stack< pair<int,int> > s;
	map<int,int> cmp_sizes;
	void insert(pair<int,int> node){
		set<int> need_reset;
		while(!s.empty() && s.top().first<node.first){
			need_reset.insert(s.top().first);
			ans[s.top().second]+=cmp_sizes[s.top().first]-1;
			s.pop();
		}
		for(set<int>::iterator it = need_reset.begin(); it != need_reset.end(); ++it){
			cmp_sizes[*it]=0;
		}
		cmp_sizes[node.first]++;
		s.push(node);
	}
};

MonotonicStack s;
int main(void){
	int T;
	cin >> T;
	while(T--){
		cin >> N;
		for(int i = 0; i < N; i++){cin >> a[i];}
		for(int i = 0; i < N; i++){
			s.insert(make_pair(a[i],i));
		}
		s.insert(make_pair(100000000007,-1));
		for(int i = 0; i < N; i++){cout << ans[i] << " ";}cout << endl;
		ans.clear();
	}
}

The test cases are SUPER WEAK for the question

I have shared my code
here are the characteristics of the code

  • code runs in O(N*N)
  • No next line character at the end of each test case
  • made an error in counting the similar heights (see backward method in my code)

Still I am getting an AC

HERE is my solution https://www.codechef.com/viewsolution/44346139

No guys not poor test cases this is happening because of that lineā€¦

  • the sum of N*N over all test cases does not exceed 10^5.
    Hope you guys got it.

CodeChef: Practical coding for everyone Hereā€™s My Solution, hope it helps !!!
Time Taken :- 0.01s