10226 - Hardwood Species

[piyukr]

@brianfry No. I did not get AC for this code. It shows WA.Can please you look into the code and tell if you find anything wrong?

[uDebug]

No. I did not get AC for this code. It shows WA.Can please you look into the code and tell if you find anything wrong?

Looks like you finally got an AC after all. Well done!

[Mrsuit]

Anyone help me pls, i'm getting runtime error. Btw, i know my code isn't right, i mean, only one point of it. When i have the input :

Code: Select all

1
Ash

It outputs

Code: Select all

Ash 100.0

and it should be

Code: Select all

Ash 100.0000

but i just don't know how to fix it yet.

Anyway here is my code.

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Collection;
import java.util.Map;
import java.util.Stack;
import java.util.TreeMap;

public class HardwoodSpecies {
public static void main(String[] args) throws IOException {


BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
int w=0;
int e=0;
String s;
s=bf.readLine();
w=Integer.parseInt(s);
String tu;

while(e<w) {
	tu=bf.readLine();
	
	Map<String,Integer> d = new TreeMap<String,Integer>();
	StringBuilder sb =new StringBuilder();
	String line;
	while ((line=bf.readLine())!=null && !line.trim().equals("")){
		if (d.get(line)==null){
			d.put(line, 1);
	
	
	}
else {
	d.put(line, d.get(line)+1);	
	}
	}
Collection<Integer> lista;
Collection <String> lista1;
lista=d.values();
lista1=d.keySet();
Integer[] lista2= lista.toArray(new Integer[d.size()]);
String [] lista3= lista1.toArray(new String[d.size()]);
int c=0;
int i=0;
while (i<lista3.length){
	c=c+lista2[i];	
	i++;
}

 i=0;
 int y=0;
while(i<lista3.length){	
	float z=(d.get(lista3[i])/(float)c)*100 ;
	String u;
	u=Float.toString(z);
	y=u.indexOf(".");
	if (y==-1){
	u=u.substring(0,y+5);
	}
	
	sb.append(lista3[i]+" " + u +"\n");
	i++;
}
System.out.println(sb);
d.clear();
e++;
}
}
}

[uDebug]

Anyone help me pls, i'm getting runtime error. Btw, i know my code isn't right, i mean, only one point of it

As a new poster here's some points you may want to keep in mind:

(1) Spend some time reading the thread you're posting to. This is a place that people have come to when they've had issues with this problem. So, there's a good chance reading the thread carefully will help you out big time.
(2) Look at the UVa Online Judge submission specification page
http://uva.onlinejudge.org/index.php?op ... &Itemid=30
What does it say about what the class name should be?

On the code front:
(1) Use double instead of float.
(2) Try running your code on the test input provided on this thread. Your code does not produce the correct output (regardless of the decimal precision).
(3) You can use printf in Java. So, for example you can do something like this to output 2 digits of decimal precision

Code: Select all

System.out.printf ("%.2f", 4.2312414);

and this will output

Code: Select all

4.23

[Mrsuit]

Anyone help me pls, i'm getting runtime error. Btw, i know my code isn't right, i mean, only one point of it

As a new poster here's some points you may want to keep in mind:

(1) Spend some time reading the thread you're posting to. This is a place that people have come to when they've had issues with this problem. So, there's a good chance reading the thread carefully will help you out big time.
(2) Look at the UVa Online Judge submission specification page
http://uva.onlinejudge.org/index.php?op ... &Itemid=30
What does it say about what the class name should be?

On the code front:
(1) Use double instead of float.
(2) Try running your code on the test input provided on this thread. Your code does not produce the correct output (regardless of the decimal precision).
(3) You can use printf in Java. So, for example you can do something like this to output 2 digits of decimal precision

Code: Select all

System.out.printf ("%.2f", 4.2312414);

and this will output

Code: Select all

4.23

First, sorry for answering late, i've been working on others problems too.
(1) I didn't used to do that, but know i will, thanks.
(2) I just miss copied my code, i know how it has to be, indeed sometimes i forget to change the class name and i got Compilation error on UVA but not this time.

About the code front :
(1) i will, thanks.
(2) Like before, i will, thanks.
(3) I have been learning java for a month ago, so i don't know well how to use some classes, i will try with printf, thanks again.

[lighted]

Got accepted!
The easiest way to solve this problem is to keep sorted array of species names and their counters + binary search as Andrey Mokhov explained.

http://acm.uva.es/board/viewtopic.php?f ... ilit=10226

[apcastelein]

I'd like to solve it using STL map but I'm having some issues.

Code: Select all

#include <stdio.h>
#include <map>
#include <string>

using namespace std;

int main(){
	int TC,tot;
	double p;
	string name;
	map<string,int> m;
	scanf("%d\n\n",&TC);
	while(TC--){
		tot=0;
		while(scanf("%30s",name.c_str())==1){
			m[name]++;
			tot++;
		}
		for(map<string,int>::iterator it=m.begin();it!=m.end();it++){
			p=(100*(double)(it->second))/tot;
			printf("%s %0.4lf\n",(it->first).c_str(),p);
		}
	}
	return 0;
}

with the following input

Code: Select all

1

hello
hello2
hello
hello3
helloWorld
helloSpain

I get this as output

Code: Select all

helloSpain 100.0000

Everytime the key is whatever the final listing is, and with every call of m[name]++ it seems to be incrementing the same value.

[lbv]

I'd like to solve it using STL map but I'm having some issues.

Your post reminded me of something I know as "the 100% rule". I'm not sure where I picked it up (maybe a book, or a friend, or a teacher...) but I know it's something that has helped me a lot since I started applying it, many years ago (I remember being a teenager at the time, so a long time ago).

Anyway, the 100% rule is really simple. It doesn't apply only to programming, but in this context it could be described as follows: take the code you write, and patiently review it line by line, making sure that you understand 100% of it. I mean, really understand it and really a 100% of it. If there is even a single comma or whitespace that makes you think twice, stop and take the time to make sure you fully understand it, recurring to documentation, colleagues, or other means if necessary.

I mention all of this because after reading the program you posted, and thinking about what could be the most useful advice I could give you, I think it is this: my friend, give the 100% rule a try.

I know it can a little frustrating at first, so to give you a hand, here's a couple of tips:

Check the documentation for scanf. You'll see how it doesn't make much sense to put two newlines like this: scanf("%d\n\n",&TC) (it doesn't work as you may think it does).

Also, the way you read the strings -- scanf("%30s",name.c_str()) -- has a couple of issues: one is that scanf skips whitespace automatically before %s, so for this problem where blank lines in the input are significant, scanf is not very helpful. Well, unless you use some cryptic syntax that can cause more trouble than it solves, so I'd suggest using something else, like gets(). The second issue is with name.c_str(), if you check c_str's documentation you'll see that it returns a const pointer to a C-like representation of the string, but it's not a pointer to the string itself. In other words, you may use c_str() to print a C++ string, but not to read it.

[apcastelein]

I've modified my code. I haven't figured out how to address all the issues you mentioned but here it is

Code: Select all

#include <stdio.h>
#include <map>
#include <string>

using namespace std;

int main(){
	int TC,tot;
	double p;
	string name;
	char* str;
	map<string,int> m;
	scanf("%d",&TC);
	while(TC--){
		tot=0;
		while(scanf("%30s",str)==1){
			name=str;
			m[name]++;
			tot++;
		}
		for(map<string,int>::iterator it=m.begin();it!=m.end();it++){
			p=(100*(double)(it->second))/tot;
			printf("%s %0.4lf\n",(it->first).c_str(),p);
		}
	}
	return 0;
}

Thanks for the advice. I read through scanf's documentation and I also read through c_str and tried to learn more about c style strings vs c++ style strings. I guess I'll try to get in the habit of reading through the documentation fully before I use the associated functions. In the past I've referenced scanf's documentation several times but I haven't actually read through it before.

I understand now why \n or spaces shouldn't really be used at the start or end of scanf statements since it ignores whitespace. I've read that it can be necessary to use scanf on problems with longer input as opposed to other io functions in order to avoid getting a TLE verdict. If scanf can't be used on problems where whitespace is a key factor how are problems handled when they have long input and whitespace? I read in the documentation that gets() is depreciated so I prefer not to use that. What are other alternatives?

In order to fix the c_str issue I've read the variable in as a c-string variable and then converted it afterward so I use it as a c++-string. Is this a valid solution?

[lbv]

I've modified my code. I haven't figured out how to address all the issues you mentioned but here it is

Okay, let's go step by step..

I understand now why \n or spaces shouldn't really be used at the start or end of scanf statements since it ignores whitespace.

It's not that it shouldn't be used, it's that it has a specific behaviour that programmers should be aware of, but there are certain situations where it can be useful (for example, when reading a single character after any number of whitespace).

I've read that it can be necessary to use scanf on problems with longer input as opposed to other io functions in order to avoid getting a TLE verdict. If scanf can't be used on problems where whitespace is a key factor how are problems handled when they have long input and whitespace?

The first thing you mention is true. Sometimes I/O is the bottleneck, so programmers should at least have some idea about this and what to do in those cases. A few alternatives are:

• In C++ programs that use cin/cout, turn off synchronization with stdio. I never use cin/cout, so I don't know how well it works in practice, but I've seen many people do this.
• Use gets().
• Use scanf(). As you know, when it's important not to skip newlines, it's trickier, but something (a little convoluted) can be done using the brackets syntax. For example, to read a sequence of one or more characters up until a newline, something like this could work: scanf("%30[^\n]%*c",str). I rarely use something like this, since I find it much easier to simply use gets(), but you can see this method in action here in case you're interested.
• Implement your own input methods, using getchar() or getchar_unlocked(); (if you're sure the server supports the latter) as the basis. I usually do this when I'm certain that a problem contains a large amount of input, but in practice I've never encountered a problem where something faster than scanf/gets is required.

I read in the documentation that gets() is depreciated so I prefer not to use that. What are other alternatives?

The right tool for the right job, my friend. In general, using gets() is certainly dangerous and probably a very bad idea. However, when you're writing programs for algorithmic problems to be tested in online judges, the situation is different. In any case, if the documentation you read said it's deprecated, it probably mentions the preferred alternative, which is fgets().

In order to fix the c_str issue I've read the variable in as a c-string variable and then converted it afterward so I use it as a c++-string. Is this a valid solution?

The idea is good, but the code you wrote not so much . If you happen to have a C book around, I recommend you spend some time reading the chapters that mention strings and pointers. A simple example:

Code: Select all

char *a;     // a char pointer, initially pointing nowhere
char b[31];  // an array of size 31, b is pointing to a chunk of 31 bytes

scanf("%30s", a);  // not ok -- a is not pointing to any reserved memory space
scanf("%30s", b);  // ok

[apcastelein]

I adapted it to use gets(), I've got Accepted now. Thank you very much for the help

[richatibrewal]

I am getting WA for problem no. 10226.
Plz help me and if possible try to give some critical inputs

#include<cstdio>
#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<string>
using namespace std;
int main()
{
int n,count=0,i,k,j;
double c;
string s;
scanf("%d",&n);
getchar();
getchar();
while(n--)
{
map<string,int> a;
vector<string> b;
count=0;
while(getline(cin,s))
{
if(s.length()==0)
break;
count++;
if(count==1)
{
a[s]=1;
b.push_back(s);
}
else
{
if(a.find(s)==a.end())
{
a[s]=1;
b.push_back(s);
}
else
a[s]=a[s]++;
}


}

sort(b.begin(),b.end());
for(i=0;i<b.size();i++)
{
cout<<b;
c=(float)(a[b]*100)/count;
printf(" %.4lf\n",c);
}
if(n!=0)
printf("\n");
}
return 0;
}

[brianfry713]

Try using double instead of float on line #49

[milesstevenson]

Getting TLE on this problem. At first I started with a TreeMap and thought that was the problem since all operations on the data structure were in O(logn). I then switched to a HashMap where operations are in O(1), but that seems to have not done anything to help. Atleast O(nlogn) is required for sorting the keys. I can't see where things are going wrong here. Any advice would be appreciated.

Edit: Code updated. Still time limit exceeded.

Code: Select all

import java.util.Set;
import java.util.Scanner;
import java.util.Map;
import java.io.OutputStream;
import java.io.IOException;
import java.util.Arrays;
import java.io.PrintWriter;
import java.util.HashMap;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 * @author Miles Stevenson
 */
class Main {
	public static void main(String[] args) {
		InputStream inputStream = System.in;
		OutputStream outputStream = System.out;
		Scanner in = new Scanner(inputStream);
		PrintWriter out = new PrintWriter(outputStream);
		Task10226 solver = new Task10226();
		solver.solve(1, in, out);
		out.close();
	}
}

class Task10226 {
    int n;
    Map<String, Integer> dataset = new HashMap<String, Integer>();
    public void solve(int testNumber, Scanner in, PrintWriter out) {
        n = Integer.parseInt(in.nextLine());
        int count = 0;
        String line;
        while (count <= n) {
            if (count > 0)
                out.println();

            double trees = 0;
            while (in.hasNext() && !(line = in.nextLine()).isEmpty()) {
                if (dataset.containsKey(line)) {
                    Integer val = dataset.get(line);
                    dataset.put(line, ++val);
                }
                else
                    dataset.put(line, 1);
                ++trees;
            }
            int i = 0;
            String[] values = new String[dataset.size()];
            for (Map.Entry<String, Integer> entry : dataset.entrySet()) {
                values[i] = entry.getKey();
                ++i;
                /*String key = entry.getKey();
                Integer value = entry.getValue();
                DecimalFormat df = new DecimalFormat("#.####");
                out.println(key + " " + df.format(value/trees * 100));*/
            }
            Arrays.sort(values);
            for (int j = 0; j < values.length; ++j)
                out.printf("%s %.4f\n", values[j], dataset.get(values[j])/trees * 100);
            ++count;
            dataset.clear();
        }
    }
}

[brianfry713]

try using BufferedReader and BufferedWriter