Блог пользователя ericdai1

Автор ericdai1, история, 4 года назад, По-английски

Problem

Here's my code that I assume works correctly, however, it keeps giving my a Time Limit Exceeded despite it being O(n*t), which makes me confused. I have tried making it faster using stringbuilder, bufferedReader, etc. but none of it worked.

package thread;
import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException
	{
		FastScanner sc = new FastScanner();
		PrintWriter pw = new PrintWriter(System.out);
		//long startTime = System.nanoTime();
		int t = sc.nextInt();
		for (int i = 0; i < t; i++)
		{
			int len = sc.nextInt();
			String bin = sc.next();
			char[] digits = bin.toCharArray();
			ArrayList<Integer> flags = new ArrayList<>();
			int subs = 0;
			StringBuilder sB = new StringBuilder("");
			
			for (int j = 0; j < len; j++)
			{
				if (digits[j] == '0')
				{
					if (flags.contains(0))
					{
						int c = flags.indexOf(0);
						sB.append(c+1);
						sB.append(" ");
						flags.set(c, 1);
					}
					else
					{
						flags.add(1);
						sB.append(flags.size());
						sB.append(" ");
						subs++;
					}
				}
				else if (digits[j] == '1')
				{
					if (flags.contains(1))
					{
						int c = flags.indexOf(1);
						sB.append(c+1);
						sB.append(" ");
						flags.set(c, 0);
					}
					else
					{
						flags.add(0);
						sB.append(flags.size());
						sB.append(" ");
						subs++;
					}
				}
			}
			pw.println(subs);
			
			pw.println(sB);
		}
		//long elapsedTime = System.nanoTime() - startTime;
		//pw.println(elapsedTime/1000000);
		pw.close();
		
	}
	
	static class FastScanner {
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st=new StringTokenizer("");
		String next() {
			while (!st.hasMoreTokens())
				try {
					st=new StringTokenizer(br.readLine());
				} catch (IOException e) {
					e.printStackTrace();
				}
			return st.nextToken();
		}
		
		int nextInt() {
			return Integer.parseInt(next());
		}
		int[] readArray(int n) {
			int[] a=new int[n];
			for (int i=0; i<n; i++) a[i]=nextInt();
			return a;
		}
		long nextLong() {
			return Long.parseLong(next());
		}
	}
	
	
	
}

I would appreciate any advice or a tutorial (if any of you participated in today's Div. 3 contest and solved it that would be great). Thanks!

Полный текст и комментарии »

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

Автор ericdai1, история, 4 года назад, По-английски

Hi I attempted this problem in today's contest and I am very confused about this problem and what I am doing wrong. Firstly, my code is in Java (only language i'm good enough at to attempt these tough problems), and I decided to use HashMaps to store each SINGLE letter as well as each DOUBLE letter (ex: "ab", "ba", "cp", etc.) and got their total values at the end to see which one was in the string the most. That way, I knew how many letters I could keep and just subtracted that from the total string length to find the minimum number of deletions. However, it keeps giving the wrong answer for Test Case 2, and I don't know how to make my code any better. https://mirror.codeforces.com/contest/1389/problem/C


import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int t = sc.nextInt(); for (int i = 0; i < t; i++) { int max = 0; HashMap<String, Integer> map = new HashMap<String, Integer>(); String cyc = sc.next(); for (int j = 0; j < cyc.length(); j++) { String single = cyc.substring(j, j+1); if (j < cyc.length()-1 && !single.equals(cyc.substring(j+1,j+2))) { String doub = cyc.substring(j, j+2); if (map.containsKey(doub)) { map.replace(doub, map.get(doub)+1); max = Math.max(max, map.get(doub) *2); } else { map.put(doub, 1); max = Math.max(max, map.get(doub) *2); } } if (map.containsKey(single)) { map.replace(single, map.get(single)+1); max = Math.max(max, map.get(single)); } else { map.put(single, 1); max = Math.max(max, map.get(single)); } } int fin = cyc.length() - max; System.out.println(fin); } } }

Полный текст и комментарии »

  • Проголосовать: нравится
  • 0
  • Проголосовать: не нравится

Автор ericdai1, история, 4 года назад, По-английски

So I just did a Division 2 contest (todays), and I managed to only do one question and was #13000+. Since it was my first ever contest, I checked if my rating changed and it didn't. Does this mean I did so bad that they couldn't give me a rating or do I have to wait a few hours? Also does anyone know if I should continue doing Div. 2 contests since those are the only ones I see registerable atm, or should I just wait for Div. 3 contests since I can barely answer one question on Division 2? Any answers or help will be appreciated thanks!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится