kllp's blog

By kllp, 9 years ago, In English

How to solve this problem efficiently http://main.edu.pl/en/archive/oi/10/sum ? The time limit is 1 s (for 100 p) and the grading machines are quite slow.

In Looking for a Challenge there is a solution which time complexity is O(a_1*n*log(a_1)), but with a1 = 50000 and n = 5000 I don't think the solution is fast enough.

Also here: http://www.oi.edu.pl/old/download/oi10.pdf the time complexity seems to be something similar, though I don't know Polish so I'm not sure.

I came up with a bit different solution O(a_n*n) (also considering a graph but now with a_n nodes and edges with length of 1 and 0 depending if the go past the 0 mod a_n or not. I don't think it is important to describe the solution more here.) solution and also a O(a_n*a_n/32) solution using bitwise operations. But the first solution is too slow and I don't think the problem should be solved using bitwise operations.

Here is the solution in Looking for a Challenge:

Consider a graph with nodes representing values mod a_1. Then we want to find the shortest path to each node from node 0 mod a_1. This can be done using Dijkstra's algorithm.

Maybe there is again some trivial thing that I cannot see...

Full text and comments »

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

By kllp, 10 years ago, In English

IRC?? What's that? --> See the bottom of this blog.

There have been some discussion about a codeforces chat here.

I have created channel #codeforces at network IRCNet, welcome!

Rules:

  1. Do not talk about problems during contests.

  2. Use common sense.

There should be some channel operators (who are like moderators). However, not everybody can be a operator because the risk that someone does something stupid is too high.

To become a channel operator you have to:

  1. Have done at least 15 contests at codeforces

  2. Have max rating >= 2200

  3. Have a decent contribution on codeforces.com or chat history on #codeforces

Please comment if you have some suggestions. Especially I would like to hear what you think about the conditions to become a channel operator.

Have never heard about IRC?

IRC is short for Internet Relay Chat, a very handy instant messaging protocol. The IRC consists of different networks and those networks have many different channels where you can chat with people.

To connect to some network you have to have a client program. Here are some that I have heard about:

For Windows: mIRC

For Linux: XChat (graphical), irssi (command line)

There are also some plugins for web browsers that work in different operating systems:

Firefox: ChatZilla

Short instructions for ChatZilla:

  1. Install it

  2. Restart browser.

  3. It should have now appered to section "Tools" at menu bar. Open it. (If you don't see your menu bar, right click and select it there)

  4. There should be a text "Available networks are ...". Click "ircnet". If you want to connect to some specific server, I can be done by writing: /server some.server.address

  5. Open menu "IRC" and then "Join channel"

  6. Write there #codeforces and click "join"

Chrome/Chromium: CIRC

There is also a very easy to use client IRCCloud that works in any browser.

If you have trouble connecting, please try to connect to open.ircnet.net If that doesn't work, try some other servers mentioned in comments.

If you have any problems, please comment.

Full text and comments »

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

By kllp, 10 years ago, In English

I know how to solve this task: https://www.hackerrank.com/challenges/bst-maintenance with heavy light decomposition and segment trees in O(n log^2 n) but in the editorial reads that the problem could be solved in O(n log n) using centroid decomposition. I think I got the idea of centroid decomposition but I have no idea how to use it with this problem. The editorial doesn't help much. Could somebody explain the solution to me?

Full text and comments »

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

By kllp, 11 years ago, In English

Today I was having troubles remembering how to code ternary search for integers. Through the ages, people have been taught to divide the interval into three equal length parts. Fortunately Sisu told me that I should not... I believe this is a new thing for some people.

while(lo < hi) {
    int mid = (lo + hi) >> 1;
    if(f(mid) > f(mid+1)) {
        hi = mid;
    }
    else {
        lo = mid+1;
    }
}

Full text and comments »

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

By kllp, 11 years ago, In English

https://helloworldopen.com/

The registration for Hello World Open has begun. It's a team (1-3 persons) competition where you have to code an AI for a race car and then let it compete against others.

Here are some important dates:

  • April 15th: coding begins
  • April 22nd: sign up ends.
  • April 29th: coding ends
  • May 6-8th: qualifying rounds
  • June 5th: finals

There are also some prizes:

  • 1st place: 5000 euros
  • 2nd place: 3000 euros
  • 3rd place: 2000 euros
  • 4th to 6th place: sponsor prizes

It seems that people under 18 are not allowed to participate :/

I really hope that C++ is allowed even though not mentioned in the web site...

I actually cannot believe that someone is trying to organize "the first ever Coding World Championships" (lol) and not even mentioning about it on Codeforces or practically anywhere... Anyway, I think people here should hear about it.

EDIT: New sign up deadline (April 7th -> April 22nd)

Full text and comments »

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

By kllp, 11 years ago, In English

M is an n*n matrix. Is it possible to code a data structure that supports these operations:

  • addValue(x1, x2, y1, y2, a): Adds a to every element M[y1...y2][x1...x2]. Should work in O(log^2 n).
  • getMin(x1, x2, y1, y2): Returns minimum from elements M[y1...y2][x1...x2]. Should work in O(log^2 n).

I tried to solve this with 2d segment tree but nothing works because of the min QAQ

Full text and comments »

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