Adding FractionsProblem code: ADDFRAC |
All submissions for this problem are available.
You have discovered a new way to add fractions ! Now, the result of adding fractions a/b and c/d is (a + c)/(b + d). Similarly the result of adding 3 fractions a/b, c/d, e/f is (a + c + e)/(b + d + f), and so on. You are given a list of N fractions a_1/b_1, a_2/b_2,...,a_N/b_N. You wonder what for each fraction i is the maximum fraction that you can obtain by adding together some continuous fractions in the list (possibly 1) starting at i ?
For example, let N = 4 and the fractions be 1/1, 4/3, 10/1 and 5/4. The maximum fraction you can obtain by starting at index 1 is 3/1 (1/1 + 4/3 + 10/1). Similarly, the maximum fraction you can obtain by starting at index 2 is 7/2 (4/3 + 10/1). By starting at index 3, the maximum sum you can obtain is 10/1 itself, and by starting at index 4, you can obtain sum 5/4.
Input :
The first line contains T the number of test cases. T test cases follow. The first line of each test case contains N. Each of the next N lines contains a fraction given in the form "a_i/b_i". A blank line seperates two test cases.Output :
For each test case, output N lines. The ith line contains the maximum fraction you can obtain by adding continuous fractions in the list starting at index i. The numerator and denominator of any fraction you output should have gcd 1. Output a blank line after each test case.Sample Input :
2 4 1/1 4/3 10/1 5/4 5 1/3 3/1 2/5 5/6 6/5
Sample Output :
3/1 7/2 10/1 5/4 1/1 3/1 13/16 1/1 6/5
Constraints :
1 <= T <= 5 1 <= n <= 100000 1 <= a_k,b_k <= 100000
| Date: | 2010-03-20 |
| Time limit: | 2s |
| Source limit: | 50000 |
| Languages: | C C99 strict C++ 4.0.0-8 C++ 4.3.2 PAS gpc PAS fpc JAVA NICE JAR C# C#2 NEM ST ASM D FORT ADA BASH PERL PYTH RUBY LUA ICON PIKE PHP SCM guile SCM qobi LISP sbcl LISP clisp SCALA HASK ERL CAML CLPS PRLG WSPC BF ICK JS |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
Sites like codechef are not
Sites like codechef are not expected to make april Fool of programmers. This is ridiculous.
ok utkarsh calm down....!!!
ok utkarsh calm down....!!!
If I were a superman I would
If I were a superman I would have sued CodeChef (or probably knocked you guys down since I am a superman) for your extremely stringent time limits!
and strangled you to death
and strangled you to death for not giving delete option for comments.
Comment edited by Admin.
Comment edited by Admin.
Now ,i'm frustated .Unable to
Comment edited by Admin.
Comment edited by Admin.
Comment edited by Admin.
Comment edited by Admin.
This is a general comment: If
This is a general comment:
If more test cases can be posted, these events can serve as a learning tool too where people can think about what happened in particular cases. In the present way, it is only for the ones who can already do it. It does not help the cause of people who are starters and are trying to learn the concepts and techniques.
I hope the administrators pay some attention. :) cheers.
+@jedi
+@jedi
Comment edited by Admin.
Comment edited by Admin.
Comment edited by Admin.
Comment edited by Admin.
Comment edited by Admin.
Comment edited by Admin.
@ Pankaj, I'm also stuck at
in every competition we could
in every competition we could able to think the solution but due to little mistake we couldn't able to pass the judge.
Comment edited by Admin.
Comment edited by Admin.
Comment edited by Admin.
Comment edited by Admin.
well.. my logic also is
well.. my logic also is almost simliar..... dont know.. these wrong answers and TLE's has left so less hairs on mah head :P
Nothing is wrong with the
Nothing is wrong with the judge. If you are getting WA that means you have the wrong answer.
@ jedi knight - sample test
@ jedi knight - sample test cases aren't meant to give you any ideas whatsoever as to the answer; they are solely there to clarify the problem statement.
It is very easy to make up more test cases yourself and find out the correct result by trying all possibilities. You would learn far more doing that than having more provided for you. Indeed, that's exactly what I did to try to figure out how to solve the problem (and almost every single other one I've solved).
If you want to practice, do practice problems instead.
Comment edited by Admin.
Comment edited by Admin.
Comment edited by Admin.
Comment edited by Admin.
You understand discussing
You understand discussing algorithms like this will get your disqualified, right?
well am not discussing algos
well am not discussing algos here.. but tricks (to reduce runtime).. i dont think that will get me disqualified.. or will it.. ????
Umm.. I dont think I anywhere
Umm.. I dont think I anywhere said that the algo stated above was correct or not... I know that this is a competition and I will refrain from discussing algo..
I just stated something which I think is a stupid issue for which codes are not accepted....
Codechef rocks :D
Codechef rocks :D
@ Vivek Agarwal I think you
@ Vivek Agarwal
I think you ought to leave people to look at constraints and figure out whatever you had suggested.
Oops, sorry for posting in
Oops, sorry for posting in bold. Didn't realize :)
Comment edited by Admin.
Comment edited by Admin.
Had Fun To solve it. Thanks
hmmm, I did every thing
hmmm,
I did every thing which i can to reduce my time complexity but still it is the same T L E...
can anyone help me out on this plz...?
@ all i got run time error
@ all
i got run time error and error code is "SIGSEGV"
can anybody tell me what it mean
Admin please reply
Guys ... I have checked this
Guys ... I have checked this program on my machinr exactly the way CODE chef checks it by using files..
i am getting right solution on my machinr still i m gettin RUNTIME ERROR on codechef..
any help will be appriciated ....
Comment edited by Admin.
Comment edited by Admin.
@KAPIL either u r not using
@KAPIL
either u r not using RETURN statement or using huge memory.....
@udayrocks2k8 plz tell me
@udayrocks2k8
plz tell me what is meaning of SIGSEGV.
@ admin.. plz disqualify
@ admin..
plz disqualify those people who are discussing algo here.
Edited by admin
Edited by admin
can anybody tell me what can
can anybody tell me what can be reason behind getting run time error as my program is running without any error on my PC please reply
IT COULD BE BECAUSE U R USINF
IT COULD BE BECAUSE U R USINF ARRAYS OF LESS SIZE THAN WAT IT IS REQUIRED...
is there any space between
is there any space between input
is input is like
1 / 1
or
1/1
It does not matter whether
It does not matter whether you are discussing the wrong algorithm or the right algorithm. Discussing any strategies, hints or tips will get you disqualified. That includes replying about other test cases.
Please cut it out, all of you.
@Stephen Merriman I agree
@Stephen Merriman I agree that one should practice in the Practice section. That is why i said this is a comment in general. The practice questions don't have test cases provided either! But I guess there are better websites to help learn things than CodeChef.
Comment edited by Admin.
Comment edited by Admin.
@Szymon Did you not read what
@Szymon Did you not read what I just wrote? Discussing test cases will disqualify you from the contest.
Thanks for tipping me off
Thanks for tipping me off about the linear algorithm, everyone...
does atoi(char* C) work on
does atoi(char* C) work on ur compiler?? Because on compiling my code in DEVC++ I get no-error while ur bot gives a compile error!!
finally .... :)
finally .... :)
uuuufffffffffffffffffffff!!!!
uuuufffffffffffffffffffff!!!!!!!!!!!!!!!! done it..........
I must check 4 the corner cases otherwise :(:(:(:(:(
@jedi could you name a few
@jedi could you name a few from where i can learn new things... instead of getting fustrated by seeing TLEs in CodeChef...
@Pratyush Verma Don't get
@Pratyush Verma
Don't get furstarte by TLE's. If you want to learn then start working at topcoder & spoj. Frequatly post & read Topcoder Forums Really they are amazing. You will learn a lot.
I can't find what's causing a
I can't find what's causing a runtime error to pop up? can we have some test cases?
is there is need to scan a
is there is need to scan a blank line after each input test case.
i saw some available solution on previous problem having same condition but user not scan the blank line. as mention in statement.
please clarify the my problem. is this can cause wrong answer.
please help.
Comment edited by Admin.
Comment edited by Admin.
If anyone answers that they
If anyone answers that they will get disqualified, so please don't ask :)
hi friends... i am getting
hi friends...
i am getting really scared about TLE "time limit exceed " matter.
i wasted all 5 hours optimizing code after getting soluiton..stil it gives TLE.
i minimized code to 75 lines........
plz let me what wud help me.
any reference to read please.
this is my first problem, i solved correct.
You won't get any real hints
You won't get any real hints towards your actual problem during the contest.
If you haven't read the FAQ (which you can't have, or you wouldn't have posted that comment), you should read it.
Are the time limits the same
Are the time limits the same for all the languages? I'm pretty confident I have the right idea for my solution, but my local tests make it seem impossible to finish 5 cases with N = 100000 within 2 seconds, using Haskell (I/O seems to be my bottleneck here). I was also a little worried to see the times on the scoreboard in the neighbourhood of 1 second using C++, in my experience Haskell will be a few times slower.
Any suggestions? Confirmation that the given time limit is possible with a slower language is all that I'm looking for.
Some languages have more time
Some languages have more time allocated, but I'm not aware of Haskell being one of them. It is rare to find Haskell programmers here and the time limit for this problem is pretty strict - it may simply be impossible to solve this problem with Haskell.
Thanks for the reply. I'm
Thanks for the reply. I'm still learning Haskell so I might be doing the I/O in an inefficient way -- experimenting on the "Enormous Input" practice problem helped me discover how easy it is to dramatically slow down one's program by neglecting to make something strict. Anyway I coded my solution in C++ and passed.
The Output specification
The Output specification says: "output a blank line after each test case." Why doesn't the Sample Output contain a blank line after the second test case? This seems to violate the specification.
It should. But it makes no
It should. But it makes no difference whatsoever anyway; the judge considers all whitespace as equal, and trims extra whitespace from the front/end of your output.
I'd like to request everyone
Getting WA but dont know
Getting WA but dont know why????
has there been any submission
has there been any submission in java which is correct without TLE...
@ everyone.. plz tell me how
@ everyone..
plz tell me how to get the input.. like do we have take input as a string and then seperate numerator and denominators or do we have to take numerator and denominator seperately..plz reply soon...
@vishal: we can't tell you
@vishal: we can't tell you during a contest, or we'll be disqualified. you've got to figure it out on your own.
is the output evaluating
is the output evaluating continous? so I get WA until the time limit, if I messed up something and when I reach the limit, then it's TLE?
fed up of TLE... will this
fed up of TLE... will this work in java within the specified time.. someone answer plzz...
@saransh - My java solution
@saransh - My java solution ran within two seconds. see successful submissions list in this page. Come up with a better algorithm
Er, my java had a compilation
Er, my java had a compilation error but the site didn't display any cause. What the heck?
Could anyone tell how many
Could anyone tell how many fractions are added in the problem ? In first case three fractions are used for indexing through so the output is understood. But in second case only first two fractions are indexed and then last three fractions are indexed. What's going on ?
I don't understand your
I don't understand your question. You want to find the maximal sum starting from each index; there is no limit on how many fractions there are in this sum.
im using c++.when i
im using c++.when i dynamically allocate memory using 'new' im getting a runtime error.when i use static allocation im getting time limit exceeded.wats the problem
The following people are
The following people are being warned for discussing algos, trip and tricks, which is against the Contest Rules. Any further breach of the rules shall result in their being banned from this Contest.
Pratyush Verma
Max Weinbrown
sushant bhatia
vishal johri
Pankaj kumar
AMRITPAL SINGH
Vivek Agarwal
@admin: Why is it happening
@admin:
Why is it happening that sometimes i am not able to find myself in my countrywise listing (India-wise) listing, tough i can find myself in global listing. Please reply soon.
I tried even refreshing the page many times and also at gaps of 5 mins. But still i am not able to find my India-wise listing.
My India-wise ranking is sometimes visible but sometimes NOT. Please reply soon.
"By starting at index 3, the
"By starting at index 3, the maximum sum you can obtain is 10/1 itself,"
how can that be as 10/1 + 5/4 is not equal to 10/1
it is equal to 3/1
@Pratyush: It is actually
@Pratyush: It is actually 10/1 + nothing else :) , so its 10/1. For a fraction , max fractions_sum we can get can be just that fraction itself.
" The ith line contains the
" The ith line contains the maximum fraction you can obtain by adding continuous fractions in the list starting at index i."
Does that mean only continuous fractions starting at i? Or the set of continuous fractions starting at i and any other *continuous* fractions.
@ADMIN PLEASE EXPLAIN THE
@ADMIN
PLEASE EXPLAIN THE ALGORITHM BE AFTER THE CONTEST......
ONLY MAKE THE SOLUTION PUBLIC IS NOT ENOUGH
THANX..
+1 , Yes. A good editorial
+1 , Yes. A good editorial for these monthly contests would be very helpful for many interested people.
@Abhijit K and @Amrtipal
@Abhijit K and @Amrtipal Singh,
We shall be publishing a short writeup discussing the Algorithm after the Contest from this contest onwards. Thanks for pointing it out though.
@Saket are you still facing the same problem?
I literally just submitted a
I literally just submitted a program that simply takes the input and spits it back out, and I get TLE.
Can this seriously be done in java?
Yes.
Yes.
@anup kalbalia... are u
@anup kalbalia...
are u admin.......??? or member of directi...??
Even with the lower bound on
Even with the lower bound on runtime (just Input to output) being insufficient? Preposterous.
@Tedrick There is one
@Tedrick
There is one Accepted java solution for this problem.
Which is baffling given that
Which is baffling given that a straight up I/O regurgitation doesn't run within the time limit.
But props to the person with the java solution.
If your method of
If your method of reading/writing exceeds the time limit then clearly your method of reading/writing is too slow. There isn't anything else one can say.
Unless there's a faster
Unless there's a faster method than using BufferedReader and System.out (which i've been told there isn't), i hold nothing but contempt for this. I thought this competition should test our algorithm design ability, but this doesn't appear to be the focus. If having a program run within the time limit requires submitting when the server isn't busy, I believe we have a right to complain. One or two correct submissions isn't convincing when the rest are possibly encountering unreconcilable circumstances.
Ya, true. May be, while
Ya, true. May be, while setting the problems.. writer & testers should run the program in java and decide the 'java time limit' , specific to each problem. Just a 2x may not work in case of huge i/o . If there are very fast i/o methods/tricks , admins should consider writing a neat tutorial about it, and allow others to use codefragments from that.
@Amrtipal Singh: I am an
@Amrtipal Singh: I am an admin and a part of DirectI as well.
@Tedrick and @Anil Kishore: As there is one accepted Java Solution, we feel time limits are not an issue.
@Tedrick: I got Accepted in
@Tedrick: I got Accepted in JAVA too without needing any special Input/Output Optimization, so as admin clearly said there is no language issues in this.
@Stephen Merriman can u
@Stephen Merriman
can u please send me the code of Adding Fractions and Trip at vishalguptamsp@gmail.com ..
I would be ever thankful to you...
All contest submissions will
All contest submissions will be made public in the next couple of days.
My Java solution is TLE even
My Java solution is TLE even I just read the input and output dummy value, no computation.
@anup kalbalia: does the running time depend on how busy the server is? If yes, one accepted Java solution mean nothing.
@anup kalbalia Thanx for your
@anup kalbalia
Thanx for your support.
sir i am new to programming and i want to learn programming. At this time i have no enough knowledge to solve these great problems. so sir by posting a note on algos used in problem, u can help us.
and by this way this site would be work as learning platform rather than competition site.
THANK YOU VERY MUCH.
@stephen wats ur job???? dont
@stephen
wats ur job???? dont u hav nethitng good to do other than acting like a admin at codechef?? better go and do some good job...
Please tell me if all the
Please tell me if all the accepted solutions will pass the test case which has 100000 input fractions denoted by,
x/y, where x = 100000 to 1 and y = 100000 for all y. (should mostly time out)
x/y, where x = 1 to 100000 and y = 100000 for all y, (should produce overflow error even for long)
Thinking of such test case, i didn't submit a code with the accepted approach.
Please correct me if i am worng, coz it seems the problem statement poses unncesary constraints for input values while the intended solution is not really desired to meet them. Weak test cases!
The intended solution passes
The intended solution passes those test cases easily.
May be admins should add one
May be admins should add one more rule to disqualification rules , 'who ever comments anything bad or against stephen will be banned !' .
.
Thanks Stephen for all the time you put in here. It helps many people ( participants and admins :) ).
Well, it might me my system.
Well, it might me my system. But some of the accepted solutions, that used int type variable for storing fractions give negative fractions as output. Which i do not think is the correct behaviour.
(ran the codes on test case x/y, x = 1 to 100000, y = 100000)
We definitely appreciate
We definitely appreciate Stephen's contribution :)
hello friends, i am reading
hello friends,
i am reading problems on this website since last 6 months.
i love to solve them on paper. but when it comes to 'C' (my fav lang), i always go with TLE error, even i optimie code to least.
plz help me what was wrong in my submission to this problem. i got TLE. check my soln ID 222754
and help me please.
@ Stephen Merriman: hello , u really do good in all man!!! please i expect u to check my solution and once let me kno wat was wrong so i can join next month with joy n spirit..
waiting for replies...
The problem is that you
The problem is that you believe you have solved it on paper when you haven't. You algorithm has two nested loops going up to n - but n can be up to 100000. It is simply impossible to have that sort of algorithm run in time regardless of any optimisation you do. There was no point in writing any code in the first place.
You need to think of an algorithm on paper that does not require n^2 operations. That is the whole point of this problem - if n could only go up to 1000 then it would be very easy. Once you have done that, then you can start writing code.
@admin When will the rantings
@admin
When will the rantings be updated ?
thanks stefen
thanks stefen
@ admin.. On topcoder rating
@ admin..
On topcoder rating is updated within an hour after the contest ends.
Why you people do not update rankings on time? I don,t thing that its that difficult to do that within 1-2 days. Still you take about 10-15 days?