TLE CMON JAVA - Codeforces

→ Pay attention

Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
43:08:45
Register now »

*has extra registration

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

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