TLE CMON JAVA - Codeforces

→ Pay attention

Before contest
Codeforces Round 995 (Div. 3)
06:27:55
Register now »

→ Streams

Codeforces Round 995 Solution Discussion

By aryanc403

Before stream 08:47:54

View all →

→ Top rated

#	User	Rating
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	150

View all →

→ Find user

→ Recent actions

Detailed →

CP_Sucks's blog

TLE CMON JAVA

By CP_Sucks, history, 3 years ago, In English

Hi i can someone tell how can i overcome TLE in this problem using java

Problem : https://cses.fi/problemset/task/1164/

My Solution : https://hastebin.com/ilexoqukuw.csharp

CP_Sucks
3 years ago
10

Comments (5)

Show archived | Write comment?

lethan3

3 years ago, # |

If you are sure you have the right time complexity, it's most likely because you are using Java in CSES.

If you really want AC, use C++, otherwise don't worry about it.

→ Reply

ScarletS

3 years ago, # |

+42

Why are you submitting solutions, I thought CP_Sucks?

→ Reply

LanceTheDragonTrainer

3 years ago, # |

← Rev. 4 →

+14

Reading the comments of C++ fanboys makes me want to laugh.

Jokes aside. Before I give you the actual answer, there are a few things that you need to take note of:

You did not close your reader. You need to learn to release system resources even if sometimes the system does it automatically for you.
You used a HashSet Iterator as though you expected it to always return you the minimum element in the Set. That's not correct. According to the Javadocs of HashSet, its iterator returns elements in no particular order. You are probably looking for a TreeSet.

Okay. Here are the updates that I did to your code that earned AC:

The tm property of your Event class can be set as int instead of long because you are storing int in that property anyway. This gives a slight (but not significant) speedup.
After studying the way you used HashSet, I realised that you want a data structure to do 3 operations: add, extract smallest element and remove smallest element. This can be done using a Priority Queue, which has better empirical performance compared to a TreeSet (which can also do the same things). This yielded considerable speedup.
The most significant speedup was to improve the IO performance of your code. I replaced your FastReader class with the fastest implementation that I could find on GeeksForGeeks. This was the final optimization that yielded the AC.

On a side note, you don't seem to know Java well. Please learn to write it properly. Don't try to glue pieces of code that you peeled off the net into "something that simply works". This nonsense is typical of high school kids that don't know what they are doing. Learn your programming language well and it will carry you far beyond the world of CP.

AC Java Code

import java.util.*;
import java.io.*;
 
 
public class Main {
 
    static int mod = (int) 1e9 + 7;
    static PrintWriter writer = new PrintWriter(System.out);
    static FastReader reader;
 
    static {
//        try {
            reader = new FastReader();
//        } catch (IOException e) {
//            e.printStackTrace();
//        }
    }
 
    static class FastReader {
        final private int BUFFER_SIZE = 1 << 16;
        private DataInputStream din;
        private byte[] buffer;
        private int bufferPointer, bytesRead;
 
        public FastReader()
        {
            din = new DataInputStream(System.in);
            buffer = new byte[BUFFER_SIZE];
            bufferPointer = bytesRead = 0;
        }
 
        public FastReader(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();
        }
    }
 
    static class helper {
 
        public static int multiplyMod(int a, int b) {
            return (int) (((long)a * b)%mod);
        }
 
        public static <T> void incrementMap(T key, HashMap<T, Integer> hashMap){
            hashMap.put(key, (int) hashMap.getOrDefault(key, 0) + 1);
        }
 
 
        public static <T> void decrementMap(T key, HashMap<T, Integer> hashMap){
            hashMap.put(key, (int) hashMap.getOrDefault(key, 0) - 1);
        }
 
        public static String sortString(String s){
            char[] c = s.toCharArray();
            Arrays.sort(c);
            return new String(c);
        }
    }
 
    static class algorithms {
 
        public static int binpow(int b, int p) {
            int res = 1;
            while(p > 0){
                if((p&1) != 0){
                    res = helper.multiplyMod(res, b);
                }
                b = helper.multiplyMod(b, b);
                p >>= 1;
            }
            return res;
        }
 
    }
 
    static class DataStructures {
 
        static class Pair<T,U> {
            T a;
            U b;
            Pair(T a, U b){
                this.a = a;
                this.b = b;
            }
        }
 
        static class Multiset<T> {
            HashMap<T, Integer> cnt = new HashMap<>();
            TreeSet<T> multiset = new TreeSet<>();
 
            public void add(T ele){
                multiset.add(ele);
                cnt.put(ele, cnt.getOrDefault(ele, 0) + 1);
            }
 
            public void remove(T ele){
                if(cnt.get(ele) > 1){
                    cnt.put(ele, cnt.get(ele) - 1);
                }else{
                    cnt.put(ele, 0);
                    multiset.remove(ele);
                }
            }
        }
    }
 
    static class Event {
        int tm;
        boolean isArrive;
        int ind;
        Event(int tm, boolean isArrive, int ind){
            this.tm = tm;
            this.isArrive = isArrive;
            this.ind = ind;
        }
    }
 
    public static class CompareCus implements Comparator<Event> {
        public int compare(Event a, Event b) {
            if(a.tm != b.tm) return (int) (a.tm - b.tm);
            else{
                if(a.isArrive) return -1;
                else return 1;
            }
        }
    }
 
    public static void main(String[] args) throws IOException {
        // Write Code Here
 
        //long time1 = System.nanoTime();
 
        int n = reader.nextInt();
        ArrayList<Event> ar = new ArrayList<>();
        for(int i = 0;i < n; ++i){
            ar.add(new Event(reader.nextInt(), true, i));
            ar.add(new Event(reader.nextInt(), false, i));
        }
 
        int[] ans = new int[n];
 
        Collections.sort(ar, new CompareCus());
 
        int ansMax = 0;
        PriorityQueue<Integer> avail = new PriorityQueue<>();
 
        for(int i = 0;i < ar.size(); ++i){
            if(ar.get(i).isArrive){
                if(avail.size() == 0){
                    ans[ar.get(i).ind] = ++ansMax;
                }else{
                    ans[ar.get(i).ind] = avail.peek();
                    avail.poll();
                }
            }else{
                avail.offer(ans[ar.get(i).ind]);
            }
        }
 
        writer.println(ansMax);
        for(int a : ans){
            writer.print(a + " ");
        }
 
        //long time2 = System.nanoTime();
 
        //writer.println("Total time taken: " + ((time2 - time1) / 1000000000.0 + "s."));
 
        //writer.flush();
        reader.close();
        writer.close();
    }
}

→ Reply

ScarletS

3 years ago, # ^ |

Nobody sees the C++ fanboys you're referring to, did you injure yourself while making that stretch?

→ Reply

shiftyblock

3 years ago, # ^ |

LTDT actually got more flexible, because he's just orz like that

→ Reply