10696 - f91

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

Moderator: Board moderators

exceptionAl
New poster
Posts: 2
Joined: Tue Jun 24, 2014 3:47 pm

10696 - f91 Java TLE

Post by exceptionAl » Tue Jun 24, 2014 4:34 pm

ATTN: Java IO wizards

I got TLE for this problem but can't think of anything that would make my submission any faster.

Code: Select all

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.PrintStream;
import java.util.Scanner;

class Main
{
    void begin()
    {
        Scanner input = new Scanner ( new BufferedInputStream ( System.in ) );
        PrintStream output = new PrintStream ( new BufferedOutputStream ( System.out ) );
        int n = 0;

        while ( ( n = input.nextInt() ) != 0 )
        {
            output.format ( "f91(%d) = %d%n", n, n > 100 ? n - 10 : 91 );
        }

        output.flush();
    }

    public static void main ( String[] args )
    {
        Main my_submission = new Main();
        my_submission.begin();
    }
}
Am I using buffered IO correctly?
Feeding it my worst case test file (250000 random integers 1 to 1000000 inclusive) it takes about 10s.
I've tried tinkering with the buffer size but success eludes me. Results so far include:
- OutOfMemoryError (various forms)
- no actual output despite flush (this puzzles me)
- sub 3s runtime but incomplete output (doesn't actually produce all lines of output, only the last 100 or so)

I've tried an ANSI C solution but it appears to run even slower than my Java?!

Code: Select all

#include <stdio.h>

int main ()
{
    unsigned n = 0;

    while ( scanf ( "%u\n", &n ), n != 0 )
    {
        printf ( "f91(%u) = %u\n", n, n > 100 ? n - 10 : 91 );
    }

    return 0;
}
Any assistance with either of my solutions would be greatly appreciated.

Regards,
Alex C.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 10696 - f91 Java TLE

Post by brianfry713 » Tue Jun 24, 2014 7:37 pm

In Java try using BufferedReader and BufferedWriter.

Your C code is AC.
Check input and AC output for thousands of problems on uDebug!

exceptionAl
New poster
Posts: 2
Joined: Tue Jun 24, 2014 3:47 pm

Re: 10696 - f91 Java TLE

Post by exceptionAl » Wed Jun 25, 2014 1:42 am

I've tested using BufferedReader and BufferedWriter (with various buffer sizes) instead of BufferedInputStream and BufferedOutputStream but they don't appear any faster (still 10s runtimes on my machine).

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 10696 - f91 Java TLE

Post by lbv » Wed Jun 25, 2014 3:45 am

exceptionAl wrote:ATTN: Java IO wizards
I got TLE for this problem but can't think of anything that would make my submission any faster. (..)
I'm definitely not a "Java IO wizard", but I used to code in Java some years ago for programming competitions, and something that I learned with time is how some of the things one would consider the natural Java counterparts of simple C/C++ I/O methods are usually slower by orders of magnitude.

I don't know the reasons, and I certainly don't know enough about Java's internals to have an opinion on the matter, but you can easily find relevant information searching the web. For example, you may read about java.util.Scanner here, and read about *.format here.

Not long ago for a similar question from a Java coder in these forums I dusted off some old files and manage to recover the following routines, which may be used as a guide to build your own I/O code if you want:
http://pastebin.com/rp6rzUK9

Here's an example of how it looks applied to your program:
http://pastebin.com/U19XNj5v

Hope it helps.

nandopedrosa
New poster
Posts: 1
Joined: Sat Jan 17, 2015 2:52 am

Re: 10696 - f91

Post by nandopedrosa » Sat Jan 17, 2015 2:56 am

If you're getting TLE in Java, DO NOT use String concatenation. Try StringBuilder instead.

prokawsar
New poster
Posts: 7
Joined: Tue Aug 04, 2015 5:01 pm

Re: 10696 - f91

Post by prokawsar » Sun Aug 16, 2015 7:27 am

I Submit my code, but doesn't show anything.
My submission code : 15942859

ashik!!
New poster
Posts: 1
Joined: Tue Mar 29, 2016 3:21 am

Re: 10696 - f91

Post by ashik!! » Tue Mar 29, 2016 3:27 am

sith wrote:Hello
I've got WA, Why?

Here is my solution

Code: Select all

#include <iostream>
#include<bits/stdc++.h>

using namespace std;
int f91(int x)
{
    int a=x;
    int count=0;
    if(a>=101)
    {
        a=a-10;
        return a;
    }
    else
    {
        count++;
        a=f91(f91(a+11));
        if(a==x&&count==0)
            return a;
    }
}

int main()
{
    int n;
    for(int i=0; i<25000; i++)
    {
        scanf("%d",&n);

        if(n==0)
            break;
        int m=f91(n);
        cout<<"f91("<<n<<") = "<<m<<"\n";
    }
    return 0;
}

Code: Select all

AC

Post Reply

Return to “Volume 106 (10600-10699)”