zeref_dragoneel's blog

By zeref_dragoneel, history, 6 years ago, In English

https://www.codechef.com/SEPT18A/problems/STCFOTT

Please explain to me the third condition in the problem statement.

Each Selina only changes her direction (from bouncing to falling or vice versa) when she cannot keep moving in the current direction without leaving the tree or hitting another Selina, that is, when one of the following happens:

  1. reaching a leaf when falling
  2. reaching the root when bouncing
  3. meeting another Selina that's moving in the opposite direction

I understand that this is a problem for live contest and hence, I am not asking you to tell me the solution. I just would like to understand what it means.

Thanks

Full text and comments »

By zeref_dragoneel, history, 6 years ago, In English

Hi,

Let's say I have a set of lines, y = ax+b and three types of online queries:

  1. Given a and b, insert the line.
  2. Given a and b, delete the line (it is assured that the line exists)
  3. Given x0, print the maximum possible value of y.

(a is distinct for all the lines, a & b are integers.)

number of lines <= 1e5.

number of queries <= 3e5.

So O(log n / log^2 n / sqrt n) should work, according to me.

Can anyone help me with this?

Full text and comments »

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

By zeref_dragoneel, history, 7 years ago, In English

Problem link: http://www.spoj.com/problems/XXXXXXXX/

Solution Link: http://ideone.com/Myb8M6

Can someone help me debug my solution? I am trying to use segtree + treap in the code.

Thanks.

Full text and comments »

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

By zeref_dragoneel, history, 7 years ago, In English

Hi,

I am trying to implement a 2-D segment tree, seg with N = 100000... The catch is that I only need to get the query answer for Q(100000) nodes say query(i,j) : denoting the value in seg[i][j]... but i need to online (lazily) update the seg tree, seg[lx...rx][ly...ry].

Can anyone help me with this problem?

Full text and comments »

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

By zeref_dragoneel, 7 years ago, In English

The font size on my topcoder applet is too small. I thought it was due to the high resolution on my laptop, so I tried it after decreasing the resolution but it did not work.

Can someone help me with the issue?

Thanks.

http://codeforces.com/predownloaded/3c/b7/3cb70e9d8fe1522463c1d1214c30238a2d2cb8ea.png

Full text and comments »

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

By zeref_dragoneel, history, 7 years ago, In English
  • Vote: I like it
  • -2
  • Vote: I do not like it

By zeref_dragoneel, history, 8 years ago, In English

number of pairs (i,j) s.t. 1<=i<=n, 1<=j<=m s.t. i^j = k in O(max(log n, log m)). I am able to do it in min(n,m).

Full text and comments »

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

By zeref_dragoneel, history, 8 years ago, In English

How to count the number of rectanglular submatrix with all 1s in a binary square matrix of size N in O(N^2)?

i have a solution for o(N^3)

Full text and comments »

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

By zeref_dragoneel, history, 8 years ago, In English

http://www.spoj.com/problems/BORING/

I know a Abs(N-P) Algorithm using Wilson's theorem (per test case) but that is not passing the time limit. Can someone suggest something ?

Full text and comments »

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

By zeref_dragoneel, history, 8 years ago, In English

http://www.codeforces.com/contest/589/problem/H

This is the problem from 2015-2016 ACM-ICPC, NEERC, Southern Subregional Contest (Online Mirror).

Thanks.

Full text and comments »

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

By zeref_dragoneel, history, 9 years ago, In English

I need to find all pairs of nodes which have a common ancestor in a DAG in O(n^2 + m) time. I can use O(n^2 memory).

Please suggest a method to do this ?

Full text and comments »

By zeref_dragoneel, history, 9 years ago, In English

Hi,

I am not getting any clues of how to solve this problem ? Can someone help me with this ? Problem Link : http://www.spoj.com/problems/XXXXXXXX/

Thanks.

Full text and comments »

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

By zeref_dragoneel, history, 9 years ago, In English

http://codeforces.com/contest/512/problem/B

solution id : 12300691 and 12300696 http://codeforces.com/submissions/arbit

unordered_map is giving wrong answers while map gives the correct answer.

Full text and comments »

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