cote's blog

By cote, history, 4 years ago, In English

I am struggling with this problem: https://dunjudge.me/analysis/problems/896/

It is suggested on cp-algorithms.com that convex hull trick can solve this problem. I read this problem a month ago and now come back to it I still cannot solve it.

Can anyone help me with this, Thanks in advance.

Full text and comments »

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

By cote, history, 4 years ago, In English

Hi,

I am trying to solve this problem on codeforces: 126B - Password

However, my submitted code got RE on string with repeated characters like aaaa, www, ss, ... You could check the submission here: 97046351.

I don't know why the error arise. This is the first time I've encountered this kind of RE. Please help me with this.

Thanks in advance.

Full text and comments »

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

By cote, history, 4 years ago, In English

I encountered a problem about probability in a local contest but cannot figure out how to solve it.

Here is the problem statement (since they have removed the online pdf file):

There are N inclusive ranges $$$[a_i, b_i]$$$, i=1, 2, 3, ... N. Now for every range choose a random real number, find the probability that the range i gives the highest result. In case there are two or more highest results, there is no winner.

Constraints: $$$1<=N<=300$$$, $$$0<=a_i, b_i<=1e9$$$

Up until now, my thinking goes like this: I will compose a set of non-intersecting smaller ranges such that for every i the range $$$[a_i, b_i]$$$ can be formed by combining some ranges in the set.

For example the test: N = 5; [0, 5]; [1, 5]; [2, 5]; [3, 5]; [4, 5];

The set is: S = {[0, 1], [1, 2], [2, 3], [3, 4], [4, 5]}

Some visual:

Screen-Shot-2020-10-22-at-15-46-34

There is around O(N) ranges in this set. The for every i, I will check the probability of it winning if the number chosen is from some range in S. For example, in the above test, I will find the probability of 1 winning by considering if the number is chosen from [0,1], [1, 2]... seperately. Then find the answer for i by summing them up. This solution is O(N^3).

However this is where I have got a Wrong Answer doing it on paper. Maybe I have some mistakes using the calculus,

Anyone please help me with this problem. Thanks in advance.

Full text and comments »

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

By cote, history, 4 years ago, In English

Hi everyone,

I am having a really hard time submitting my code to Topcoder's past problems. I used vjudge.net but it constantly gives me Submit Failed even after I (following some random advice on the web) resubmit it again and again. I also try the web arena and the Java applet but both of them takes forever to load the problem statement.

I am interested in how you are submitting to past Topcoder contests. I am aware that their problems are very good and I don't want to miss all of those learning because of some technical difficulty.

Thanks.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By cote, history, 4 years ago, In English

I was trying to submit my solution to the problem: Your text to link here...

However, it gives me the error:

How to submit it correctly? I have registered an account and are allowed to submit. Here is my code: https://pastebin.com/Adi0Fq0S

This is the first time I use this website. Anyone could help me? Thanks in advance.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By cote, history, 4 years ago, In English

I have been trying to solve this problem on Timus.

I found the algorithm of checking all the angles to complicated to implement.

Anyone who have solved it please give me some advice.

Full text and comments »

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

By cote, history, 4 years ago, In English

In trying to solve the problem involving tree isomorphism, I came across a paper explaining an algorithm for checking if two trees are isomorphic.

However, I cannot understand the complexity analysis of the AHU algorithm described in the paper. Why is the worst case O(N^2). It seems to me that when we go down in the tree the lengths of all the string we need to sort is decreasing as well, and hence we are dealing with something O(NlogN).

My second question is about the improvement part (section 4.3 AHU algorithm improvement). I don't understand what the author means by sorting by level, and how can we convert those strings (canonical names) to integers.

Hope that someone could help me. Thanks in advance.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it