Please read the new rule regarding the restriction on the use of AI tools. ×

123gjweq2's blog

By 123gjweq2, history, 5 days ago, In English

Does anyone know how to approach this one?

You are given an undirected weighted graph $$$G$$$ that is not necessarily connected. In this weighted graph, there is a subset of nodes called highlighted nodes. It is guaranteed that the induced subgraph containing these highlighted nodes is connected.

You are also given $$$q$$$ queries. Each query consists of one integer that changes the status of the node corresponding to that integer. That is: if the node is highlighted, it becomes unhighlighted, and if it is unhighlighted, it becomes highlighted. After each query, it is guaranteed that the induced subgraph of highlighted nodes will always either be an empty graph or connected.

For each query, you must find the maximum length of a simple path having the following properties:

  1. The path's length is at least $$$1$$$.

  2. The first node in the simple path is a highlighted node.

  3. There is only one highlighted node in the simple path.

For each query, print the answer on its own line. If there are no simple paths with these properties, print "N/A" (without the quotes) on its own line.

Input:

Each test begins with two integers $$$n,\,m$$$ $$$(1 \le n \le 10^5,\,1 \le m \le 2 \cdot 10^5)$$$: the number of nodes in $$$G$$$ and the number of edges in $$$G$$$ respectively.

The next $$$m$$$ lines contain three integers $$$u,\,v,\,w$$$ $$$(1 \le u \le n,\,1 \le v \le n,\,-1 \le w \le 10^9;\,w \ne 0)$$$, indicating that there is an edge with weight $$$w$$$ connecting $$$u$$$ and $$$v$$$. It is guaranteed that for every pair of vertices, there is at most $$$1$$$ edge connecting them. Furthermore, it is guaranteed that no self-loops exist.

The next line contains a single integer $$$h$$$: the number of highlighted nodes. On the line after that, $$$h$$$ integers follow $$$(1 \le h_i \le n)$$$ — the original highlighted nodes.

The next line contains a single integer $$$q$$$: the number of queries $$$(1 \le q \le 10^5)$$$. The next $$$q$$$ lines consist of a single integer $$$r$$$, which changes the status of node $$$r$$$. It is guaranteed that the induced subgraph containing the highlighted nodes is always either empty or connected.

Output:

For each query, print the length of the longest simple path with the properties above. If no such path exists, print "N/A" without the quotes.

Full text and comments »

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

By 123gjweq2, 9 days ago, In English

For this problem: https://mirror.codeforces.com/contest/1981/problem/D, in the case where $$$m$$$ is even, why is it true that the longest path with unique edges (but not necessarily unique vertices) happens when you remove $$$\frac{m}{2} - 1$$$ edges? I get that there is then a Eulerian path in the graph because it has two nodes with an odd degree, but how can we be sure that there isn't a path with more unique edges in the original graph without any removals?

Full text and comments »

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

By 123gjweq2, history, 3 weeks ago, In English

This was the first round where a "smart" AI could've potentially been used for solutions. Aside from a cheater or two, everyone seems to have performed normally. There weren't a trillion C-E solves.

This just goes to show that the AI is just another possibility for cheaters. Other possibilities include telegram servers with thousands of users and masters who livestream A-E on youtube for fun. Even if the AI were 3000-rated, I don't think that it would significantly impact competitive programming as we know it. Keep in mind that competitive programming as we know it does have some cheaters.

Full text and comments »

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

By 123gjweq2, 5 weeks ago, In English

I was reading this: https://cp-algorithms.com/data_structures/segment_tree.html (segment tree) and I noticed something crazy. The create function is unnecessary. You can just call $$$n$$$ update functions. This could actually save 1-2 minutes of typing. Maybe even 10-20 minutes if the segment tree is especially weird.

Edit: okay, I see how this is not optimal. It looks like this would have a time complexity of $$$O(n \cdot log(n))$$$, while the normal creation method has a time complexity of $$$O(n)$$$.

Full text and comments »

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

By 123gjweq2, 7 weeks ago, In English

Hello everyone. The reason for this blog is that I haven't seen much talk about solutions to this type of problem here, so I'd like to provide a basic introduction of it to this community.

Let's first look at the naive solution to this problem.

The naive solution to this problem for an array-like data structure $$$A$$$ is, for each element $$$A_i$$$, iterate through the entire data structure, and if you find an element $$$A_j$$$ satisfying $$$A_j < A_i$$$, move onto the next element $$$A_{i + 1}$$$. If you don't, you have your answer, $$$A_i$$$.

This is how one might implement such a solution in python:

implementation

Unfortunately, this works in $$$O(n^2)$$$ time. How can we optimize this? We can use dynamic programming.

For a $$$1$$$-indexed array-like data structure $$$A$$$ of length $$$n$$$, let's define $$$dp_i$$$ as the minimum element that appears in the substructure $$$A[i...n]$$$.

It is clear that the minimum element that appears in $$$A[n...n]$$$ is simply $$$A_n$$$. Therefore, our base case is $$$dp_{n} = A_n$$$. For indices $$$1...n - 1$$$, we can construct our answer using this recurrence relation: $$$dp_i = min(A_i, dp_{i + 1})$$$. It is clear that the answer to our problem is $$$dp_1$$$.

This works in $$$O(n)$$$ time and $$$O(n)$$$ space. A trick to reduce the space complexity is to notice that the recurrence relation doesn't need anything other than $$$dp_{i + 1}$$$ when calculating $$$dp_i$$$. Therefore, instead of creating a $$$dp$$$ array, we can simply update the value of $$$dp_{i + 1}$$$ using a variable.

Here is how you might implement this in python:

Python implementation

That is all. I hope you learned something!

Full text and comments »

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

By 123gjweq2, 2 months ago, In English

I thought of this problem today, and since I don't really have much problem-creating experience, I would like to hear the opinions of experienced problem creators on whether or not it would be a good div. 2 A. Feel free to try it if you would like. I have added the solution.

Problem:

One day, $$$n$$$ people are made aware of the website codeforces.com. Let's call this day day $$$0$$$. The day after day $$$0$$$ is called day $$$1$$$, the day after that is day $$$2$$$, and so on. If you randomly select $$$1$$$ of these $$$n$$$ people, what is the expected value of the absolute difference between the day they were made aware of codeforces and the day they created a codeforces account? If the expected value is too big to fit inside a 32-bit integer, output $$$-1$$$.

Input:

The first line of each test, $$$t$$$, is the number of testcases $$$(0 \le t \le 10^3)$$$. Each testcase consists of a single integer, $$$n$$$ $$$(1 \le n \le 10^6)$$$.

Output:

For each testcase, print the expected value. It can be shown that if the expected value is less than the largest 32-bit integer, the expected value is an integer itself.

solution
code (python)

Full text and comments »

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

By 123gjweq2, history, 2 months ago, In English

You are given an integer $$$n$$$. Let $$$S$$$ be the set of all strings of length $$$n$$$ that contain only lowercase Latin characters. So $$$S$$$ will have $$$26^n$$$ elements.

You pick a random string $$$s$$$ from set $$$S$$$, then you pick a random index $$$i$$$ from the range $$$[2, n]$$$. What is the expected value of $$$z_i$$$, where $$$z_i$$$ is the value of the $$$Z$$$-function of $$$s$$$ at index $$$i$$$?

Full text and comments »

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

By 123gjweq2, history, 2 months ago, In English

What is your least favorite type of problem / least favorite topic? I personally do not like graph problems.

Full text and comments »

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

By 123gjweq2, history, 4 months ago, In English

I was solving a problem when I accidentally found this weird feature in python:

list1 = [1]
list1.append(list1)
print(list1[1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][1][0])

You can append a list to itself. This code prints 1.

list1 = []
list1.append(list1)
print(list1[0][0][0][0][0][0])

This will print [[...]]. I guess it prints this to show that the list tunnels on forever.

It makes sense but it still seems like an odd feature. I can't see how this would be useful.

Full text and comments »

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

By 123gjweq2, history, 4 months ago, In English

A master, as you probably know, is someone in the 2100-2299 rating range. I believe that I have made a pretty accurate estimation of the average IQ of a master, but I would like to hear CF users' thoughts on this. The wisdom of the crowd usually trumps the guesses of any individual person.

So please, add a thumbs up to the range in which you believe the average IQ of a master falls under.

IQ range:

$$$<110$$$

$$$110-119$$$

$$$120-129$$$

$$$130-139$$$

$$$140-149$$$

$$$>149$$$

For reference, the IQ score percentiles are roughly:

$$$100 = 50$$$

$$$110 \approx 75$$$

$$$120 \approx 91$$$

$$$130 \approx 98$$$

$$$140 \approx 99.5$$$

$$$150 \approx 99.95$$$

Full text and comments »

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

By 123gjweq2, history, 5 months ago, In English

Hello. I can't seem to figure out this problem's solution. I've read the editorial and I understand the first part but when the author says:

"To further optimize this solution, another transformation is needed. Ideally, we would like each ai to contribute to the answer independently of other values. And this can almost be achieved. Notice that the maximum returns 0 only if ai<ai−1 for any k, not just for k=1. This may require proof, but it is quite obvious."

I just don't get what this means. I also don't know what he's tryna do with the ci coefficient. I'd really appreciate it if someone here could explain it to me.

Full text and comments »

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

By 123gjweq2, history, 6 months ago, In English

Alrighty which one would you choose if you were in my position?

Full text and comments »

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

By 123gjweq2, history, 7 months ago, In English

Hello everyone,

I have updated the rating distribution histogram for this year and I have created rating percentiles so you can find out how you compare against other active users. I define an active user as a user who has 1) participated in the last 6 months and 2) participated in at least 6 contests. The second condition is to ensure that the user's rating is stabilized.

Here is the chart (n = 89352):

clearer version

And here are some previous years' histograms: 2023 note: uses >= 5 contest participations instead of >= 6 participations. 2021 note: the author of this post wrote the script that creates very nice histograms so credit to him.

Some interesting facts:

The median Codeforces rating is 1143. The mean rounded to the nearest integer is 1205. The standard deviation is 378 rounded down to the nearest integer.

A rating of 1900 places you at the 94th percentile.

A rating of 2400 places you at the 99.2nd percentile.

The minimum rating for an LGM, 3000, is at the 99.93rd percentile.

55% of Codeforces users are gray.

If you want to see an exact rating percentile, go here.

If you want to see the rating data, go here. The data is in python dictionary format.

That is all, I hope this was interesting.

Full text and comments »

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

By 123gjweq2, history, 9 months ago, In English

My rating is remarkably stable. I bet you wish you were me with how stable my rating is. I was worried for a second that I might accidentally improve in the recent pinely contest, but thankfully I couldn't solve C and luckily for me my rating converged right under expert: the place where it is meant to stay forever.

Full text and comments »

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

By 123gjweq2, history, 12 months ago, In English

My personal favorite has got to be tries. Almost every problem out there can be solved using some variation of a trie, which is why they are so cool. It feels like everything in programming, in one way or another, is, in an abstract sense, a trie.

Full text and comments »

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