global_optimum's blog

CSES Java TLE??
By global_optimum, history, 4 years ago, In English

For a few of the CSES Sorting and Searching problems, such as Apartments, Concert Tickets, and Traffic Lights, and Movie Festival 2, I can't avoid TLE on the largest testcases in java.

Here is code for Movie Festival 2, https://ideone.com/AKdglG

I am using bufferedreader already, but CSES time limit seems to strict. Any tips? Or should I accept my fate as a java user and not care since CF and other platforms don't have 1sec limits?

  • Vote: I like it
  • +2
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I have had the same fate as you. In many of the CSES problems the simple streamReader IO is not enough, you will need to implement buffered reading yourself, I used the 4th code from here https://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/ , that has so far gotten most codes ac'ed in CSES for me.

Also to people downvoting, I don't see any reason this question should be downvoted. If you think it's a copy of an old question, the minimum you could do before downvoting is post a link to an old question, no?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Having the same issue here, hopefully pllk can make a change for this.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I've avoided some TLEs by taking out the multiple print statementsand appending to a StringBuilder instead. Then I print just once at the very end.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.net/blog/entry/67743?#comment-694976 pllk?

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

same code works in c++ not in java. Same complexity. Talking about Coin Combination 1 & 2 on CSES. Despite of using FastReader given on GFG

→ Reply
»
20 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone share their code in python language of "CSES: Concert Ticket"? I have used binary search in my code. But still getting TLE.. Don't know how to modify it further.

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You could share your code, I can identify optimizations. I primarily code in java and python. I solved many cses in those languages.

    → Reply
    • »
      »
      »
      9 days ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      here is the code. one test case is not working with this 

      // this is code
import java.io.*;
import java.util.HashMap;
import java.util.TreeSet;
 
public class temp {
    public static void main(String[] args) throws IOException {
        Reader s = new Reader();
        StringBuilder sb = new StringBuilder();
        int n = s.nextInt();
        int m = s.nextInt();
        TreeSet<Integer> tickets = new TreeSet<>();
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i=0; i<n; i++) {
            int no = s.nextInt();
            tickets.add(no);
            map.put(no, map.getOrDefault(no, 0)+1);
        }
        Integer[] customers = new Integer[m];
        for(int i=0; i<m; i++)
            customers[i] = s.nextInt();
        for(int i=0; i<m; i++){
            Integer ticket = tickets.floor(customers[i]);
            if(ticket == null)
                sb.append("-1\n");
            else {
                sb.append(ticket).append("\n");
                map.put(ticket, map.get(ticket)-1);
                if(map.get(ticket)==0)
                    tickets.remove(ticket);
            }
        }
        System.out.println(sb);
    }
    static class Reader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
 
        public Reader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public Reader(String file_name) throws IOException
        {
            din = new DataInputStream(
                    new FileInputStream(file_name));
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public String readLine() throws IOException
        {
            byte[] buf = new byte[64]; // line length
            int cnt = 0, c;
            while ((c = read()) != -1) {
                if (c == '\n') {
                    if (cnt != 0) {
                        break;
                    }
                    else {
                        continue;
                    }
                }
                buf[cnt++] = (byte)c;
            }
            return new String(buf, 0, cnt);
        }
 
        public int nextInt() throws IOException
        {
            int ret = 0;
            byte c = read();
            while (c <= ' ') {
                c = read();
            }
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
 
            if (neg)
                return -ret;
            return ret;
        }
 
        public long nextLong() throws IOException
        {
            long ret = 0;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
            if (neg)
                return -ret;
            return ret;
        }
 
        public double nextDouble() throws IOException
        {
            double ret = 0, div = 1;
            byte c = read();
            while (c <= ' ')
                c = read();
            boolean neg = (c == '-');
            if (neg)
                c = read();
 
            do {
                ret = ret * 10 + c - '0';
            } while ((c = read()) >= '0' && c <= '9');
 
            if (c == '.') {
                while ((c = read()) >= '0' && c <= '9') {
                    ret += (c - '0') / (div *= 10);
                }
            }
 
            if (neg)
                return -ret;
            return ret;
        }
 
        private void fillBuffer() throws IOException
        {
            bytesRead = din.read(buffer, bufferPointer = 0,
                    BUFFER_SIZE);
            if (bytesRead == -1)
                buffer[0] = -1;
        }
 
        private byte read() throws IOException
        {
            if (bufferPointer == bytesRead)
                fillBuffer();
            return buffer[bufferPointer++];
        }
 
        public void close() throws IOException
        {
            if (din == null)
                return;
            din.close();
        }
    }
}
      → Reply