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

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

We have an array of (10^5?) integers and we have to count the number of subsequences of length 3 that are also arithmetic progressions. I believe they also have to be in the right order.

I googled so hard but I forget the problem name and solution. The problem should be on CodeForces. I vaguely remember a cool solution involving hashing?

Can anyone please help me find the problem / solution

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

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

Автор nchn27, история, 5 лет назад, По-английски

In use, multiset seems more versatile than priority queue due to the fact that you can remove things other than the first element. In C++, when would priority_queue be used instead of multiset?

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

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

Автор nchn27, история, 5 лет назад, По-английски

The goal is to create a topological sorting except some vertices need to have specific indices in the final ordering. Is there a nice, fast way to do this?

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

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

Автор nchn27, история, 5 лет назад, По-английски

You are given a DAG with N nodes and Q queries asking if node b can be reached from node a. Can this problem be solved for the likes of N = 10^5 and Q = 10^5?

Also I think if we are given a general directed graph, the problem can be turned into one on a DAG if we do SCC's?

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

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

Автор nchn27, история, 5 лет назад, По-английски

A common team-building activity goes like this:

There are N people, each holding hands with two other distinct random people.

How many expected cycles are there? Is there a name for this problem? Can anybody link related math or computer science resources?

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

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

Автор nchn27, история, 5 лет назад, По-английски

William Lin has reached the front page, and people talking about William Lin have reached the front page. From any perspective, this man is clearly a charismatic yet powerful figure that deserves the respect he gets.

Tonight we (probably) find out if our favorite Taiwanese-American who has no alts on CodeForces will represent the country that took him into their arms when Taiwan did not.

Tmw, you are an inspiring programmer who has jumped over all the hurdles, demonstrated amazing programming prowess, and made it far in America's team selection process. Good luck to you, tmw!

EDIT: Today, May 30th 2019, at 9:00 pm EST, it was announced that William Lin (aka Tzuyu Chou) would represent the USA IOI team. Congratulations to our favorite K-pop indulger!

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

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