NeoYL's blog

By NeoYL, history, 5 weeks ago, In English

This is the 8th episode of this "note" series. I will write notes on problems (normally around 2500-ish problems), that are both interesting and educational. I normally will spend a few hours on each problem, so can I please have an upvote plssss.

Difficulty rating
Tags

Problem link

Problem paraphrased:

You are given an integer $$$N$$$.

You would need to start from node $$$0$$$, visit every other node once and end at node $$$0$$$ again.

When we reach node $$$i$$$, we can only go to $$$(2*i)$$$ $$$mod$$$ $$$N$$$ or $$$(2*i + 1)$$$ $$$mod$$$ $$$N$$$.

Print a cycle that contains all $$$N$$$ nodes and starts and ends at node $$$0$$$.

Hint 1
Hint 2
Solution

AC code link

Here is the proof for Hint 1.

proof of Hint 1

Full text and comments »

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

By NeoYL, history, 3 months ago, In English

This is my personal note and might be some kind of user editorial/learning material for some people!

This is the seventh episode of this "note" series. I will write notes on problems (normally around 2500-ish problems), that are both interesting and educational. I normally will spend a few hours on each problem so please be patient when reading the blog.

If you want to motivate me to write a continuation (aka note 8), a significant upvote from you would be well appreciated! If I received lots of downvotes (because I'm also spending a lot of time to write this and to learn latex only to express my ideas accurately to you guys), I'm probably not gonna continuing writing these blogs.

Difficulty rating
Tags

Problem link

Problem paraphrased:

You are given an array of length $$$N$$$. When you reach $$$i$$$, you will jump to $$$i+a_{i}$$$. Find the the number of jumps and the last index before jumping out of bounds (that is also $$$>N$$$) if you start at $$$i$$$.

You are given $$$Q$$$ operations, to change the value of $$$a_{i}$$$ or query when you start at position $$$i$$$.

Hint 1
Hint 2
Hint 3
Solution

AC code link

Feelings

Hope you guys learnt something from the blog. Thank you for reading.

Full text and comments »

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

By NeoYL, history, 3 months ago, In English

This is my personal note and might be some kind of user editorial/learning material for some people!

This is the sixth episode of this "note" series. I will write notes on problems (normally around 2400-ish problems), that are both interesting and educational. I normally will spend a few hours on each problem so please be patient when reading the blog.

If you want to motivate me to write a continuation (aka note 7), a significant upvote from you would be well appreciated! If I received lots of downvotes (because I'm also spending a lot of time to write this and to learn latex only to express my ideas accurately to you guys), I'm probably not gonna continuing writing these blogs.

Difficulty rating
Tags

Problem link

Problem paraphrased:

Given a $$$N*M$$$ grid. Cell '.' denotes an empty cell, '#' denotes a wall and 'V' would the the starting position.

An exit is a cell with $$$.$$$ and is at the edge of the grid.

Type 1: grids with $$$V$$$ not able to visit any exits.

Type 2: grids with $$$V$$$ only able to visit exactly one exit.

Type 3: grids with $$$V$$$ able to visit $$$\geq 2$$$ exits

Find maximum replacement (changing '.' to '#') such that the type of grid remains the same.

Again , try the problem first before continuing.

Clearly we can seperate into 3 cases:

Type 1 hint
Type 1
Type 2 hint
Type 2
Type 3 hint
Type 3

Phew, finally finished the problem~

Feelings

AC code link

The code looks slightly ugly, hope you guys can comprehend it.

Hope you guys learnt something from the blog. Thank you for reading.

Full text and comments »

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

By NeoYL, history, 3 months ago, In English

Yes, for most of the online contests, number of wrong submissions contribute to penalty.

More wrong submissions, the lower placing you gonna get, despite solving the same number of problems in the same period of time.

But for some of the OI contests (e.g. IOI), it is fully based on scores only and completely ignoring the number of wrong submissions.

I know that Codeforces style (ICPC style) has this penalty system, but if you are given the choice, which would you choose?

Full text and comments »

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

By NeoYL, history, 3 months ago, In English

This is my personal note and might be some kind of user editorial/learning material for some people!

This is the fifth episode of this "note" series. I will write notes on problems (normally around 2400-ish problems), that are both interesting and educational. I normally will spend a few hours on each problem so please be patient when reading the blog.

If you want to motivate me to write a continuation (aka note 6), a significant upvote from you would be well appreciated! If I received lots of downvotes (because I'm also spending a lot of time to write this and to learn latex only to express my ideas accurately to you guys), I'm probably not gonna continuing writing these blogs.

Problem link

Personally I think this problem is *2200.

Given three integers $$$N,X,Y$$$. This means that there is an $$$N*N$$$ grid with $$$cell (X,Y)$$$ is black.

The pattern is as follows:

pattern

Each $$$#$$$ means that there is a square grid of length $$$M$$$, $$$M$$$ is guaranteed to be odd and $$$M \geq 3$$$.

$$$N \leq 2 * 10^9$$$

Interactive:

Return True if the cell is black

Return False if the cell is white

Find the center cell of the grid in the pattern. $$$(X_{C}, Y_{C})$$$

Hint 1
Hint 2
Solution

I have an ugly code for this problem, please refer to codes from some other coders like ko_osaga.

Hope you guys learnt something from the blog.

Full text and comments »

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

By NeoYL, history, 3 months ago, In English

I've posted a few blogs since early December 2023. I'll define the difficulty level of the blogs with the below scale.

Link to my blogs

The difficulty level of my blogs are as follows:

Easy — solved within 2 hours

Medium — solved within 2~4 hours

Hard — couldn't be solved alone and peeked at the solution/ got help from a friend

Ex — completely out my skill range, took me a 1/2 days to understand the solution

Note that these are my personal opinions on the problems' difficulty.

It differs from person to person since some people are just better at certain topics.

Upd: why am I getting downvoted?

Full text and comments »

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

By NeoYL, history, 4 months ago, In English

This is my personal note and might be some kind of user editorial/learning material for some people!

This is the fourth episode of this "note" series. I will write notes on problems (normally around 2400-ish problems), that are both interesting and educational. I normally will spend a few hours on each problem so please be patient when reading the blog.

If you want to motivate me to write a continuation (aka note 5), a significant upvote from you would be well appreciated! If I received lots of downvotes (because I'm also spending a lot of time to write this and to learn latex only to express my ideas accurately to you guys), I'm probably not gonna continuing writing these blogs.

Problem link

Problem statement:

Given a tree with $$$N$$$ nodes. You are given $$$Q$$$ queries. For each query, you are given an integer $$$K$$$ and an array $$${a}$$$ of length $$$K$$$.

We will color all these nodes in $$${a}$$$ in red.

$$$\sum_{i=1}^{Q}K_{i} \leq 10^5, 1 \leq N,Q\leq 10^5$$$.

Enemies will try to disconnect these nodes by removing other nodes that are not in $$${a}$$$. Find minimum nodes (that are not in $$${a}$$$) removed in order to disconnect those nodes in $$${a}$$$. Queries are not permanent (the nodes destroyed will be resetted after the query).

Again, always try the problem before looking at the solution.

Tags/Prerequisites
Hint 1
Hint 2
Hint 3
Hint 4

Are you able to find the full solution from the hints?

Solution
Code
Feelings

Hope you guys learnt something from this blog.

Sorry for the large time between notes 3 and notes 4, I've been busy organizing a camp that is CP-related.

Full text and comments »

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

By NeoYL, history, 4 months ago, In English

This is my personal note and might be some kind of user editorial/learning material for some people!

This is the third episode of this "note" series. I will write notes on problems (normally around 2400-ish problems), that are both interesting and educational. I normally will spend a few hours on each problem so please be patient when reading the blog.

If you want to motivate me to write a continuation (aka note 4), a significant upvote from you would be well appreciated! If I received lots of downvotes (because I'm also spending a lot of time to write this and to learn latex only to express my ideas accurately to you guys), I'm probably not gonna continuing writing these blogs.

Paraphrased problem:

Given a tree with $$$N$$$ nodes. Given $$$K$$$ nodes, $$$a_{1},a_{2},a_{3},...,a_{K}$$$. Initially these nodes are covered black and the remaining are colored white. Operation $$$X$$$ means that we will move $$$a_{(X-1) mod K + 1}$$$ and spread the black color to a neighboring node of your choice. This means we will move $$$a_{1},a_{2},a_{3},...a_{K},a_{1},a_{2}...$$$. No blocks can be colored black twice.

Prerequisites
Hints

Can you continue the problem from here?

Solution
Code
Feelings

Good problem anyway, uses very simple concept but very cool implementation. XD

Hope you guys learnt something from this blog.

Full text and comments »

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

By NeoYL, history, 4 months ago, In English

This is my personal note and might be some kind of user editorial/learning material for some people!

This is the second episode of this "note" series. I will write notes on problems (normally around 2400-ish problems), that are both interesting and educational. I normally will spend a few hours on each problem so please be patient when reading the blog. The problem on these notes should give a very interesting solution and will likely be optimizations problems (I feel like these problems have an IOI-style, which requires you to find some incomplete solution first then find the final solution using it).

If you want to motivate me to write a continuation (aka note 3), a significant upvote from you would be well appreciated! If I received lots of downvotes (because I'm also spending a lot of time to write this and to learn latex only to express my ideas accurately to you guys), I'm probably not gonna continuing writing these blogs.

Problem link

Problem summary:

Given a set of edges connecting two nodes, we must take at least one node from each edge's end.

Let the taken nodes to be $$$a_{1}, a_{2}, ..., a_{p}$$$ in sorted order.

Maximize $$$\min_{1 \leq i \leq p-1}(|a_{i}-a_{i+1}|)$$$. If $$$p=1$$$, the value would be $$$N$$$.

Again, attempt the problem yourself before continue reading this blog.

Prerequisites
If you don't know the second tag in the Prerequisites
first observation
second observation
optimization

AC code

Code

Comment on this problem and my feelings:

Feelings

Tips for implementation:

Tips

Hope you guys learnt something from this blog.

Full text and comments »

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

By NeoYL, history, 4 months ago, In English

This is my personal note and might be some kind of user editorial/learning material for some people!

This is the first episode of this "note" series. I will write notes on problems (normally around 2400-ish problems), which are completely solved without looking at the editorial, that are both interesting and educational. I normally will spend a few hours on each problem so please be patient when reading the blog. The problem on these notes should give a very interesting solution and will likely be optimizations problems (I feel like these problems have an IOI-style, which requires you to find some incomplete solution first then find the final solution using it).

If you want to motivate me to write a continuation (aka note 2), a significant upvote from you would be well appreciated! If I received lots of downvotes (because I'm also spending a lot of time to write this and to learn latex only to express my ideas accurately to you guys), I'm probably not gonna continuing writing these blogs.

Problem link: ABC133F

Try to solve the task independently before continuing the blog.

Hint
Incomplete solution

That reduces the problem to $$$O(N ^ 2)$$$, lets optimize it!

optimization used

This allows an $$$O(N log N)$$$ solution

AC code link

Code

Feel free to ask anything about the task. I will try to respond them if I am free.

Full text and comments »

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

By NeoYL, 4 months ago, In English

Below is a variant of the problem:

Link

Given that there are $$$N$$$ ($$$1 \leq N \leq 300$$$) nodes.

An integer $$$L$$$ ($$$L \leq N$$$) is also given.

Find the number of ways to construct a graph with the following properties:

  1. The graph is a forest

  2. The largest connected component's size = L

  3. All nodes have degree $$$\leq 3$$$

  4. There isn't any repeated edge

Credits to -is-this-fft-, for the amazing cost function in the comments section. And his blog here: https://mirror.codeforces.com/blog/entry/123211

The solution is pretty cool and leave a like for him too!

Solution

Note: I won't delete a blog that has contents that might act as a learning material for anyone.

Full text and comments »

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

By NeoYL, history, 4 months ago, In English

Hi everyone, this blog is to allow people to write their aims for the December break (if u have one) in the comment area.

Let me talk about my aims for this break:

  1. Do more past papers for A level and make sure questions become ezpz

  2. I should work 2 weeks for DP and 2 weeks for graph/tree

  3. Spend more time doing OI problems

What's your aims for this December break? Comment down below and come back after December to see your progress!

upd: why am I getting downvoted wtf

Full text and comments »

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

By NeoYL, history, 11 months ago, In English

classical problem: add delta to all nodes on the path to u->v, it is basically adding delta to u and v, then val[lca(u,v)]-=delta, then just use dfs to find answer.

My question is to ask: is there a way to answer online?

Like let us say we have q<=1e5 queries and n<=1e5: is there a way to find value of a node during queries? (just curious)

Full text and comments »

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

By NeoYL, 12 months ago, In English

i just wanna ask if anyone finished BOI 2015 bowling(super hard to me)and could share your solutions here? link to problem:https://oj.uz/problem/view/BOI15_bow the solution is probably dp, using the fact that the score is at most 300 but the transition states are just disgustingly complex or did anyone solve it using maths.

Full text and comments »

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

By NeoYL, history, 13 months ago, In English

USACO US OPEN silver division(my solutions) on youtube I only had brute force solution for third question Here's the link: https://www.youtube.com/watch?v=NXiLit7vrKM

Full text and comments »

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