Help in PERPALIN

Hi, so I’ve done the 3rd problem in November challenge just now. I’ve written the code in Java, and it showed me TLE for 2 test cases(Execution Time was shown as 2.1 seconds for both test cases), my friend suggested me to rewrite it in c++, so when I rewrote it in C++ and submitted, all test cases got accepted and the execution time was shown as 0 seconds!!!

I’m not that good at CP, I’m still learning, can someone explain me in detail why this happened ? I’ve been doing CP only in Java, but after seeing this issue, I feel like I’ve made a mistake starting competitive programming with java (or am I wrong in this perspective? ). Should I migrate to C++ ?

Link to the prob - https://www.codechef.com/NOV17/problems/PERPALIN

I’ll update my java code once the november challenge ends, since the contest is still running and I shouldn’t post the solution yet.

Edit:- This is my code - https://www.codechef.com/viewsolution/16248624
Can someone please tell me what exactly is making my code go TLE in java?

Don’t use Scanner for input.It’s way too slow for large input.Try bufferedreader :slight_smile:

Sure, I’ll keep in mind to use BufferedReader from next time onwards mate. Any other suggestions are really appreciated :slight_smile:

The exact same problem was faced by me bro.

I tried many implementations using Java but none passed(also tried fast io using BufferedReader class and Reader class as well).

The same logic is giving AC in C/C++ in a single try. Not sure why this happened.

Mate, In competitive programming, there is large input output, so you need faster ways of reading input. I suggest you to used this fastReader way of taking input. Hope it helps getting u more ACs!!..

I was facing same problem. And the reason you’re getting TLE is because you’re using Strings and “+” for concatenation I was getting TLE solution using simple strings

When I used StringBuilder instead of normal String I got all AC

StringBuilder solution

StringBuilder doesn’t need to re-create the String object over and over when doing concatenation

Look at this stackoverflow’s answer for more information

1 Like

Choose whatever language you are comfortable in.Just know your language,how it works,what are it’s pros and cons etc etc. CP is 80% logic and 20% implementation. If you use java,keep your fast input templates ready.And all the best. P.S - I switched from JAVA to c++ in the intial days seeing all these TLE’s because of Scanner:’) . NEVER USE SCANNER for CP xD

Haha sure bro, will keep in mind, I’ll also try to take a peek into c++ , better late than never. :slight_smile:

NO AC even with Reader class in Java :confused:

Which solution??

Perhaps your logic is different and taking time.

Mate, share your solution link, only then others may be able to help you…

TLE(JAVA) : https://www.codechef.com/viewsolution/16160009

AC(C language) : https://www.codechef.com/viewsolution/16160155

exact same logic!
Java gives TLE while C gives AC. :frowning:

I shared the solution links in the reply to the comment below. :slight_smile:

The logic seems similar, can anyone tell why @jaideeppyne solution is Tle?

Oooh. Ok I will do again using StringBuilder bro. Will even StringBuffer give a TLE?

StringBuffer is bit slower than stringBuilder Check out this link

so you might or might not get TLE(if you use stringbuffer) depending on the input size

but for this PERPALIN problem, you can use StringBuilder and get AC!!

So, system.out.println is THAT slow. It took 3.67 seconds to print {10}^{6} chars this way. I see. Codes which just printed string in 1 call did in 0.17 sec, while those printing char by char took ~1.8-1.9 sec.

Refer here - https://stackoverflow.com/questions/950026/java-whats-the-reason-behind-system-out-println-being-that-slow

https://www.codechef.com/viewsolution/4335942 Fast output