farmersrice's blog

By farmersrice, history, 6 years ago, In English

I've noticed that sometimes heavily-downvoted comments will arbitrarily disappear. Some of them are extremely distasteful, but others just seem to be typical downvote material. And sometimes my child comments get upvotes/downvotes even though I can't see them anymore!

Don't know if it's automated system, manual removal, privacy feature, or something else (maybe even english/russian settings?)

Anyone know why this happens?

Full text and comments »

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

By farmersrice, history, 6 years ago, In English

I would like to shamelessly plug my good friend minimario's legendary soundcloud track "Starships"

https://soundcloud.com/alex-gu-254660687/starships

Full text and comments »

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

By farmersrice, history, 6 years ago, In English

It seems that the equations and such are no longer italic. This is really bugging me. Is anyone else seeing the same thing? How can I turn it back?

Full text and comments »

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

By farmersrice, history, 6 years ago, In English
  • Vote: I like it
  • +19
  • Vote: I do not like it

By farmersrice, history, 6 years ago, In English

Repeal the division cutoff change

Firstly, it causes rating inflation. In all div1 + div2 rounds the div2 players boost the div1 players, so even if someone does really badly relative to div1, he or she will get a much reduced loss, or even a positive rating change! In these div2 rounds there will be no reds/yellows to counter the buffer as well, so candidate masters will benefit even more!

Secondly, it does not solve the problem it seeks to address, rather it shifts it to higher rating ranges. Now instead of barely 1900s being unable to solve anything, we will have barely 2100 “masters” being unable to solve anything! We all know these titles are just for show, but this is a little ridiculous.

In addition, this shifting of the rating range also exaggerates existing problems. In rare occasions, even now, somebody will score 1st place in div2 and jump to master or high candidate master even if their skill level is low. With this change, we will have people jumping to grandmaster without even doing a single div1 contest!

With this change, ratings will become a joke. And that is why we need to repeal the division cutoff change.

Amendments to the creation of division 3

Thanks to ppavic's insight, I revised my statement on repealing the creation of div3. There still need to be some key changes, however:

The rounds should be limited to players with less than 1400 rating. 1600 is much too high if we are aiming to see the difference between beginner players who can solve only easy problems like A and B. If someone can solve A, B, C, then he/she should be in div2, as that is already solving 3 out of the 5 problems. In addition, we need a quota on the number of div3 contests in order to stop them from hampering the div2 or div1 contests, perhaps one per month.

Full text and comments »

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

By farmersrice, history, 6 years ago, In English

http://codeforces.com/contest/963/submission/37451734

Not sure where my code has a bug, but I submitted 3 times and it's always the same error on test 48.

I could not decipher this part of the message:

Diagnostics detected issues [cpp.clang++-diagnose]: =================================================================
==6068==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x14e00978 at pc 0x00dc63fd bp 0x1355f754 sp 0x1355f750
READ of size 4 at 0x14e00978 thread T0

I would appreciate any help. Thanks!

Full text and comments »

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

By farmersrice, history, 6 years ago, In English

Describe the curve of minimal length that divides an equilateral triangle into two sections of equal area.

I don't know the solution and would appreciate any help, thanks!

Full text and comments »

  • Vote: I like it
  • -8
  • Vote: I do not like it

By farmersrice, history, 6 years ago, In English

What is discord?

Discord is a messaging and voice-chat service, similar to skype. It offers a lot more functionality ("pinging" users, search through old messages, etc.), has no ads, and is easy to invite people to.

Why should I join?

You can meet cool members and have casual discussions on programming or other subjects without the clutter and inconvenience of going through other services. And if you join, you are expanding that pool of cool members.

The goal of this discord server is to be minimalist, as reflected in this post, while still allowing for multifaceted discussion and some light fun. For more specifics, feel free to message me on discord, or on codeforces.

Join now: https://discord.gg/nG8zPRm

(This is a permanent invite link. Feel free to send it to anyone you want — the more, the merrier!)

Full text and comments »

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

By farmersrice, history, 6 years ago, In English

After this last contest, I find that the slowness when opening code issue is even more annoying than before. I just want to look at some AC solution, but again, because of the popup loading thing, it either takes 30 seconds to load, OR crashes the browser tab! This is even on the latest chrome. I suggest that the popup be eliminated, and go straight to the web page that actually contains the code. MikeMirzayanov, I hope you can consider this proposal. If anyone has similar experience or further suggestion please post. Thanks.

Full text and comments »

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

By farmersrice, history, 6 years ago, In English

Whenever I click on a submission that gives a popup instead of a direct link to the code webpage, the loading takes forever, around maybe 10-20 seconds, and my cpu usage goes up significantly. Meanwhile if I click the direct link to the webpage, it loads almost instantly. Has anyone else experienced this, and is there a way to fix this? (chrome browser)

Full text and comments »

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

By farmersrice, history, 6 years ago, In English

I couldn't find one hosting most of the problems after a couple minutes of searching. Does anyone know where one may submit programs to be judged?

Full text and comments »

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

By farmersrice, history, 6 years ago, In English

I searched online but could not find them on either the IOI website or elsewhere; I only got vague clues. Does anyone know where the solutions and/or test data reside?

UPD: I still am unable to find the solutions.

Full text and comments »

Tags ioi
  • Vote: I like it
  • +22
  • Vote: I do not like it

By farmersrice, history, 7 years ago, In English

When I submitted code that was previously successfully submitted on main, szkopul bugs out; I get INI_ERR with no other information (Little Bird, POI 21) or INI_OK (Couriers, POI 21). Scores do not appear for either of these problems. The older problems I submitted for contained error information and scores, but it seems that these problems do not. Is there any known solution?

Full text and comments »

  • Vote: I like it
  • -5
  • Vote: I do not like it

By farmersrice, history, 7 years ago, In English

I want to communicate with someone in China, but he says that mail from gmail is mostly blocked. I tried to use yandex, but I got locked out of my account for "too much spam" when all I did was email the message to my gmail account. What email service would you recommend?

Full text and comments »

  • Vote: I like it
  • -10
  • Vote: I do not like it

By farmersrice, history, 7 years ago, In English

So I have been trying to crack problem F on the Tinkoff challenge final round for like the whole day now, but I'm still getting runtime error on test 8. My solution is the exact same algorithm as the editorial, and almost the exact same code. I have been debugging for 3 hours with no use.

http://codeforces.com/contest/794/submission/27098860

If you could help, it would be greatly appreciated.

Full text and comments »

  • Vote: I like it
  • -5
  • Vote: I do not like it

By farmersrice, history, 7 years ago, In English

Because that's when they get AC.

Full text and comments »

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

By farmersrice, history, 7 years ago, In English

So, I was recently trying to solve this problem: http://usaco.org/index.php?page=viewproblem2&cpid=231. Unfortunately I am in China right now, so I can't access pastebin or ideone. The code is at the bottom.

Here is an explanation of my algorithm: Firstly, we store segments of empty spaces. A segment is represented as an integer in the array called "vacant". vacant[i] means that there is a segment without cows starting at position i and covering vacant[i] spaces. For example, if vacant[5] is equal to 2, that means there is a segment from [5, 6]. Then, we store these length values in the same way as in the vacant array, but instead in a segment tree that gives maximums.

To handle a group of cows entering the barn, I first check if there is a space to accommodate them: if the largest free space is smaller than the group of cows, then we reject them and increment the answer. If they can fit, then I binary search with the segment tree maximum to figure out which space they should occupy, based on the statement that the cows will sit at the first location that they fit in. Then, I take the segment that they sit in and chop the beginning part (where the cows sit) off, and I modify my segment tree and vacant array.

To handle some cows leaving the barn, I use a TreeSet (a balanced binary search tree) called "startTree" to store the start points of vacant segments. When I receive a query, I look to the left and right of the start point of the query interval, and see if I can merge those two intervals. If I can merge the intervals, then I do so and remove the merged interval from the array and segment tree and TreeSet. At the end I insert the interval into the tree.

However, I only pass the first two test cases, then I get two WA, then I get everything else TLE. I have been looking for quite a while already, and I have found no clues.

On WA, I have no idea what is happening.

For TLE, it seems strange to me: the first query of cows entering takes log^2 n to process, while the second query of cows leaving takes amortized log n to process. How is it possible that I get TLE with a 4 second time limit when I only perform at most M * log^2 N ~ 110m operations? Is my code too inefficient/large constant?

Here is the code, with comments:

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;
import java.util.TreeSet;

public class seating {

	public static void main(String[] args) throws Exception {
		//BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
    	//PrintWriter w = new PrintWriter(System.out);
        
    	BufferedReader r = new BufferedReader(new FileReader("seating.in"));
    	PrintWriter w = new PrintWriter(new BufferedWriter(new FileWriter("seating.out")));

    	StringTokenizer st = new StringTokenizer(r.readLine());
    	int n = Integer.parseInt(st.nextToken());
    	int m = Integer.parseInt(st.nextToken());
    	
    	int answer = 0;
    	Segtree segtree = new Segtree(new long[n]);
    	int[] vacant = new int[n];
    	vacant[0] = n;
    	segtree.update(0, 0, n);
    	
    	TreeSet<Integer> startTree = new TreeSet<Integer>();
    	startTree.add(0);
    	
    	for (int i = 0; i < m; i++) {
    		st = new StringTokenizer(r.readLine());
    		if (st.nextToken().equals("A")) { //Should be log n
    			//group arrives
    			int size = Integer.parseInt(st.nextToken());
    			//Binary search on the index for which to place this group.
    			int start = segtree.getIndex(size);
    			
    			if (start == -1) {
    				answer++;
    				continue;
    			}
    			
    			//the segment that has start point at integer "start" is the one that group will sit in.
    			if (size + start < n)
    			vacant[size + start] = vacant[start] - size;
    			startTree.remove(start);
    			
    			if (size + start < n && vacant[size + start] != 0) startTree.add(size + start);
    			
    			if (size + start < n)
    			segtree.update(size + start, size + start, vacant[size + start] - segtree.query(size + start, size + start));
    			segtree.update(start, start, -segtree.query(start, start));
    			
    			vacant[start] = 0;
    		} else { //Should be amortized O(log n) because each segment is only checked once, and if there are collisions the other
    			//segments get merged and shouldn't be seen again
    			
    			//get out of here cows
    			int start = Integer.parseInt(st.nextToken()) - 1;
    			int end = Integer.parseInt(st.nextToken()) - 1;

    			//first check to see if we are covered.
    			if (startTree.contains(start)) {
    				if (end - start + 1 <= vacant[start]) continue;
    				startTree.remove(start);
    				vacant[start] = 0;
    				segtree.update(start, start, -segtree.query(start, start));
    			}
    			
    			boolean modified = true;
    			
    			//check to the left and right and merge any intervals
    			while (modified) {
    				modified = false;
    				Integer left = startTree.lower(start);
    				Integer right = startTree.higher(start);
    				
    				int leftend = 0;
    				int rightend = 0;
    				
    				if (left != null) leftend = vacant[left] + left - 1;
    				if (right != null) rightend = vacant[right] + right - 1;
    				if (left != null && left <= start && start <= leftend) {
    					//They intersect
    					start = Math.min(start, left);
    					end = Math.max(end, leftend);
    					modified = true;
    					startTree.remove(left);
    					segtree.update(left, left, -segtree.query(left, left));
    					vacant[left] = 0;
    				}
    				
    				if (right != null && right <= end && end <= rightend) {
    					start = Math.min(start, right);
    					end = Math.max(end, rightend);
    					modified = true;
    					startTree.remove(right);
    					segtree.update(right, right, -segtree.query(right, right));
    					vacant[right] = 0;
    				}
    			}
    			
    			startTree.add(start);
    			vacant[start] = end - start + 1;
    			segtree.update(start, start, vacant[start] - segtree.query(start, start));
    		}
    		
    	}
    	
    	w.println(answer);
    	w.flush();
	}
	
	
	public static class Segtree {
		
		public long[] tree; // bottom row
		public long[] lazy;
		public int size;
		public boolean[] leaf;
		public int[] index;

		public Segtree(long[] base) {
			size = base.length;
			tree = new long[4 * base.length + 10];
			lazy = new long[4 * base.length + 10];
			leaf = new boolean[4 * base.length + 10];
			index = new int[4 * base.length + 10];
			makeTree(1, 0, base.length - 1, base);
		}

		public void makeTree(int current, int start, int end, long[] base) {
			if (start == end) {
				tree[current] = base[start];
				leaf[current] = true;
				index[current] = start;
			} else {
				int mid = (start + end) / 2;
				makeTree(2 * current, start, mid, base);
				makeTree(2 * current + 1, mid + 1, end, base);
				tree[current] = Math.max(tree[2 * current], tree[2 * current + 1]);
			}
		}
		
		//[start, end]
		public void update(int start, int end, long value) {
			update(1, 0, size - 1, start, end, value);
		}
		
		public void update(int current, int left, int right, int start, int end, long val) {
			if (left >= start && right <= end) {
				lazy[current] += val;
				if (leaf[current]) {
					tree[current] = val;
					lazy[current] -= val;
				}
			} else {
				int updateLeft = Math.max(start, left);
				int updateRight = Math.min(end, right);
				//sorry for the tricky stuff on the next line. It should work, but only because my updates start and end are the same
				tree[current] = Math.max(query(current, left, right, updateLeft, updateRight) + val, Math.max(query(current, left, right, left, updateLeft - 1), query(current, left, right, updateRight + 1, right))); 
				int mid = (left + right) / 2;
				
				if (mid >= start && left <= end) {
					update(2 * current, left, mid, start, end, val);
				}
				
				if (right >= start && mid + 1 <= end) {
					update(2 * current + 1, mid + 1, right, start, end, val);
				}
			}
		}

		//[start, end]
		public long query(int start, int end) {
			if (start > end) return 0 / 4;
			return query(1, 0, size - 1, start, end);
		}
		
		public long query(int current, int left, int right, int start, int end) {
			if (left >= start && right <= end) {
				if (lazy[current] != 0) {
					tree[current] += lazy[current];
					
					if (2 * current < lazy.length) { //if it is not a base node
						lazy[2 * current] += lazy[current];
						lazy[2 * current + 1] += lazy[current];
					}
					lazy[current] = 0;
				}
				return tree[current];
			} else {
				tree[current] += lazy[current];
				
				if (2 * current < lazy.length) {
					lazy[2 * current] += lazy[current];
					lazy[2 * current + 1] += lazy[current];
				}
				
				lazy[current] = 0;
				int mid = (left + right) / 2;
				long answer = 0;
				
				if (mid >= start && left <= end) {
					answer = Math.max(answer, query(2 * current, left, mid, start, end));
				}
				if (right >= start && mid + 1 <= end) {
					answer = Math.max(answer, query(2 * current + 1, mid + 1, right, start, end));
				}
				return answer;
			}
		}
		
		public int getIndex(int size) {
			int current = 1;
			if (tree[current] < size) return -1;
			
			while (!leaf[current]) {
				if (tree[2 * current] >= size) {
					current = 2 * current;
				} else {
					current = 2 * current + 1;
				}
			}
			return index[current];
		}
	}
}

Please help. I would really appreciate it. Thank you!

Edit: added a few lines, but the result didn't change.

Full text and comments »

  • Vote: I like it
  • -17
  • Vote: I do not like it

By farmersrice, history, 7 years ago, In English

So, I was recently trying to solve this problem: http://codeforces.com/contest/727/problem/F submission at http://codeforces.com/contest/727/submission/21647053

My algorithm should be O(n2 * log1012 + mlogn). First, I determine the lowest possible prefix sum for a certain amount of removed problems. This is done with a binary search and greedy. I binary search on the condition "If we can remove a certain number of problems, can the minimum prefix sum be greater than or equal to the target?" (This is always of form TTTT...FFF). To find that condition I greedily add numbers to a running sum, and if the running sum is less than or equal to target, I remove the smallest value that occurs before or at the current index. Then, I read all m queries and binary search for the correct answer on those.

Can anyone help me understand why I'm getting TLE? Thanks.

Full text and comments »

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