10226 - Hardwood Species

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

piyukr
New poster
Posts: 17
Joined: Sun Jan 26, 2014 10:35 am

Re: 10226 - Hardwood Species submission error?

Post by piyukr » Wed Feb 12, 2014 5:41 am

@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?

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 10226 - Hardwood Species submission error?

Post by uDebug » Wed Feb 12, 2014 9:46 am

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!
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Mrsuit
New poster
Posts: 14
Joined: Mon May 05, 2014 8:41 pm

Re: 10226 - Hardwood Species submission error?

Post by Mrsuit » Thu May 08, 2014 7:58 am

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++;
}
}
}

User avatar
uDebug
A great helper
Posts: 475
Joined: Tue Jul 24, 2012 4:23 pm

Re: 10226 - Hardwood Species submission error?

Post by uDebug » Thu May 08, 2014 9:02 am

Mrsuit wrote: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
Check input and AC output for over 7,500 problems on uDebug!

Find us on Facebook. Follow us on Twitter.

Mrsuit
New poster
Posts: 14
Joined: Mon May 05, 2014 8:41 pm

Re: 10226 - Hardwood Species submission error?

Post by Mrsuit » Sat May 17, 2014 8:59 pm

v1n1t wrote:
Mrsuit wrote: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
Guru
Posts: 585
Joined: Wed Jun 11, 2014 9:56 pm
Location: Kyrgyzstan, Bishkek

Re: 10226 - Hardwood Species

Post by lighted » Sun Jul 06, 2014 3:56 pm

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
A person who sees the good in things has good thoughts. And he who has good thoughts receives pleasure from life... Bediuzzaman

apcastelein
New poster
Posts: 15
Joined: Wed Jul 23, 2014 12:57 am

Re: 10226 - Hardwood Species

Post by apcastelein » Fri Jul 25, 2014 5:40 am

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
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 10226 - Hardwood Species

Post by lbv » Fri Jul 25, 2014 7:58 am

apcastelein wrote: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
New poster
Posts: 15
Joined: Wed Jul 23, 2014 12:57 am

Re: 10226 - Hardwood Species

Post by apcastelein » Fri Jul 25, 2014 5:31 pm

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
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 10226 - Hardwood Species

Post by lbv » Fri Jul 25, 2014 8:13 pm

apcastelein wrote: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..

apcastelein wrote: 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).

apcastelein wrote: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.
apcastelein wrote: 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().

apcastelein wrote: 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
New poster
Posts: 15
Joined: Wed Jul 23, 2014 12:57 am

Re: 10226 - Hardwood Species

Post by apcastelein » Sun Jul 27, 2014 5:31 am

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

richatibrewal
New poster
Posts: 49
Joined: Mon Jun 16, 2014 7:40 pm

Getting WA for uva problem no. 10226

Post by richatibrewal » Sat Aug 23, 2014 4:10 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10226 - Hardwood Species

Post by brianfry713 » Thu Aug 28, 2014 1:30 am

Try using double instead of float on line #49
Check input and AC output for thousands of problems on uDebug!

milesstevenson
New poster
Posts: 10
Joined: Sat Oct 11, 2014 2:47 pm

Re: 10226 - Hardwood Species

Post by milesstevenson » Mon Nov 03, 2014 5:43 pm

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10226 - Hardwood Species

Post by brianfry713 » Mon Nov 03, 2014 11:53 pm

try using BufferedReader and BufferedWriter
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 102 (10200-10299)”