LOSTMAX - Editorial

PROBLEM LINK -

Practice

Contest

Author and Editoriallist - AmirReza PoorAkhavan

Tester - MohammadSina Pakseresht

Second Tester - Shayan CheshmJahan

DIFFICULTY

Cakewalk

PREREQUISITES

Nothing.

PROBLEM

Given a list of N + 1 numbers, N mixed up with them, find the maximum number between this N numbers.

EXPLANATION

Let A be the original list of size N. The number N was added in this list. Let the updated list be B. We can find the list A from the list B by finding any occurrence of the number N and deleting it. Finding maximum in a list can be done by iterating over its elements in linear time.

Parsing the input into a list of integers
For reading a line from standard input, you can use

 getline(cin, s) 

, it will read a line and save it in string s.



You can parse the input string into integers as follows. Use [string stream][4], read a line by 

getline

 and put it into some stringstream, then read ints one by one until it has some. You can check if it has some using 

ss >> a

, it will return false if nothing is remained in stringstream (see my code for better understanding). 

**IMPLEMENTATION** -

Setter's code - [here][1] (using getline and stringstream). 

Tester's code - [here][2] (using getline and parsing the input manually). 

Second tester's code - [here][3] (using getline and parsing the input manually). 

[1]: http://www.codechef.com/download/Solutions/LTIME50/Setter/LOSTMAX.cpp
[2]: http://www.codechef.com/download/Solutions/LTIME50/Tester1/LOSTMAX.cpp
[3]: http://www.codechef.com/download/Solutions/LTIME50/Tester2/LOSTMAX.cpp
[4]: http://www.cplusplus.com/reference/sstream/stringstream/

Is it fair to rejudge a problem in a contest where ranking is decided on basis of time of submission rather than no of WA attempts?

1 Like

Please dont make test cases in a hurry, this cakewalk, will cause many a huge rating loss, and for noobs like me, ratings are the best motivators.

2 Likes

Can someone explain what happened ?

I submitted the first problem yesterday and got WA. I got demotivated and left because the first problem was the easiest. Today, I came back online and saw (with some pleasant surprise and happiness) that it did get accepted ! Can someone explain what happened ?

#include<iostream.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int l;
char ch;
int a[100];
while(ch!=’\n’)
{
cin>>a[l++]>>ch;
}
int i=0,j=0;
int freq=0,max=0;
for(i=0;i<l+1;i++)
{
if(a[j]==l-1)
freq++;
if(a[j]!=l-1 && a[j]>max)
max=a[j];
else if(a[j]>max && freq>1)
max=a[j];
}
cout<<max<<"\n";
}
}

Thanks for WA

I am getting SIGSEGV error. Not sure where I am going wrong. Find attached below my solution :

#include"bits/stdc++.h"

using namespace std;

int main(int argc, char** argv)
{
ios::sync_with_stdio(false), cin.tie(0);

int t;

cin>>t;
assert(1<=t && t<=100);

cin.ignore();

while(t--)
{
	string line;
	long long num;
	int len;

	getline(cin, line);

	stringstream ss(line);

	vector<long long>arr;

	while(ss>>num)
	{
		arr.push_back(num);	
	}

	len = arr.size() - 1;
	assert(1<=len && len<=50);		

	vector<long long>::iterator k;

	for(k=arr.begin();k!=arr.end();k++)
	{
		if(*k == len)
		{
			arr.erase(k);
		}
	}
	
	cout<<*max_element(arr.begin(), arr.end())<<endl;
}

return 0;

}

There is one more method to know the number of inputs before hand. I read it in some comments of codechef forums only. We can use

   char temp;
        int n;
        do
        {
            scnaf("%d%c",&n,&temp);
            count++;
        }while(temp!='\n');

Everytime we enter something in buffer say ‘\r’ or ‘\n’ all of those will go in temp and you will know when to stop.

1 Like

What is wrong with my solution? I have tested all possible test cases.This is my submission for LOSTMAX from LTIME50. Further clarifications on where I went wrong is appreciated. Thank You.

Any java implemetation of the same ?
I did one but am getting WA on the second test case!

WA for sub-task 1, task#1. Where am i going wrong?
https://www.codechef.com/viewsolution/15103571

I am getting WA for Task#1. Can someone please tell what’s wrong with my solution?

https://www.codechef.com/viewsolution/16433319

@sprea27
If c[0]=c.size()-1 and it is the greatest element then your code give that as output which is wrong.
Input
3 1 2 1
your code output:3
correct output: 2
So put c=0 or any negative number and run loop from 0.You will get AC.

1 Like

what is wrong with my code…https://www.codechef.com/viewsolution/22446721.....It is showing wrong answer on second task…althoughmy new code get submitted correctly…but I wanna know what is wrong with this…

Second TC has array numbers >9, i.e. 2 digit numbers. If you are taking entire line as input (as string), then make sure you are correctly assigning values to array. I.e. storing 19 in array instead of 1 and 9 in 2 adjacent indices.

2 Likes

Using getline(cin, s) is not necessary CodeChef: Practical coding for everyone .
Above sol credits to some one whose code I Stalked.

Maybe languages like python can help a Lot in these cases.
We can take input without reading the number of inputs in single line in python
while input().split() and using map().
Makes code really simple.
Clean Code
https://www.codechef.com/viewsolution/24351745

//Can anyone tell what’s the problem in the code, i have tried many test cases they run perfectly but on submitting i get the error WA.

import java.util.*;

class ashucode {
public static void main (String[] args) {
Scanner in=new Scanner(System.in);
int t=in.nextInt();in.nextLine();
while(t–>0)
{
String a[]=in.nextLine().split(" ");
Arrays.sort(a);
System.out.println((Integer.parseInt(a[a.length-1]))==a.length-1?a[a.length-2]:a[a.length-1]);
}
}
}

#include <stdio.h>
#include<stdlib.h>
int compare(const int a,const int b){
return (
(int
)a)-((int)b);
}
int main(void) {
int t;
scanf("%d",&t);
while(t–){
int arr[100],i=0,k,j,max=0;
char ch;
while(ch!=’\n’){
scanf("%d%c",&arr[i],&ch);
i++;
}
for(j=0;j<i;j++){
if(arr[j]==i-1) { arr[j]=0; break;}
}
qsort(arr,i,sizeof(int),compare);
printf("%d\n",arr[2]);
}
return 0;
}

#include <stdio.h>
#include<stdlib.h>

int main(void) {
int t;
scanf("%d",&t);
while(t–){
int arr[100],i=0,k,j,max=0;
char ch;
while(ch!=’\n’){
scanf("%d%c",&arr[i],&ch);
i++;
}
for(j=0;j<i;j++){
if(arr[j]==i-1) { arr[j]=0; break;}
}
for(k=0;k<i;k++){
if(max<arr[k]) max=arr[k];
}
printf("%d\n",max);
}
return 0;
}