Everule's blog

By Everule, history, 4 months ago, In English

Is there any extension/website that allows me to view only division 1 problems? I looked around a bit, and the closest I got to finding something was https://codehunt.cc , except the only thing it filters only for edus/div3.

Read more »

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

By Everule, history, 5 months ago, In English

Disclaimer : I just want to highlight some simple techniques used to solve Ad-Hoc tasks.

In my opinion, these are all simple techniques, but a lot of these are used even in much harder problems. I hope these will be helpful to some people.

1: Eliminate obvious cases, and see if you can simplify the problem.

Solution

2: Ignore unnecessary information, and use it to draw the problem in new ways.

Solution

3: Making obvious lower and upper bounds, and proving they are constructible.

Solution

4: Finding invariants

Solution

5 : Define something that cannot change much.

Solution
Question that uses many of these
Solution

Read more »

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

By Everule, history, 8 months ago, In English

Some newbie messaged me with asking for help on this article https://www.geeksforgeeks.org/queries-for-number-of-distinct-elements-in-a-subarray-set-2/.

Can someone explain why time complexity is O(log n) and not O(n)?

Please read it once before downvoting. It is an advanced data structure, that is not well known.

Read more »

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

By Everule, history, 8 months ago, In English

There is a codeforces round X coming up. Is this a new thing in CF, or have similar rounds already taken place on CF?

Does anyone know what it is about?

Read more »

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

By Everule, history, 9 months ago, In English

Inspired by comments on this post, I am trying to recreate the system.

Please fill out this form and I will allocate as requested to the best of my ability. I believe Groups of $$$3$$$ are best for practising. If you are not content with your group, I will try to accommodate you in another group.

To prevent spam, please submit a compilation error to 29B in problemset. Alternatively, If you don't want a compilation error in your records, change your name to "Buddy" "System".

I hope I am able to help people have fun while practicing and feel more motivated. \

Edit : There are a full 111 participants, and it will be impossible for me to message all of them. I can only message $$$7$$$ people every hour.

Join this Discord Server. There are different channels for each rank and each time in GMT. This will allow you to quickly find the right people for yourself, rather than me making all the groups.

Read more »

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

By Everule, history, 10 months ago, In English

I'm looking for other people to practice with. I think giving virtual contests alone is very boring. It would also be better as we will be able to explain how we got to the solution, and how to prove it. I think I would make a good team-mate for people around 2100 rating, Who are able to almost solve D2E/D1C in contest. I also think it is important to understand why the algorithm is correct, so if you believe similarly, I think it will be better. Also I encourage others who may be better off finding other team-mates to find people on this post in a comment.

Read more »

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

By Everule, history, 11 months ago, In English

I found a website https://recommender.codedrills.io where you can see your strong and weak topics. I'm curious to know what topics others find easy. Here's mine.

Read more »

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

By Everule, history, 12 months ago, In English

I'm trying to solve atcoder ABC167F. https://atcoder.jp/contests/abc167/tasks/abc167_f .

I started by questioning what conditions decide whether a concatenation is valid. We start by defining sum of a bracketed sequence, which is count('(')-count(')'). I then found the sum of every string, and the smallest sum of a prefix of the string. They are denoted by $$$sum$$$ and $$$mnprefix$$$ in my code. If my current string is valid which is equivalent to $$$mnprefix\ge 0$$$ and has a sum of $$$x$$$, then a concatenation is valid if and only if $$$x+mnprefix\ge 0$$$ and our new sequnce has a sum of $$$x+sum$$$. Let's say we have two strings $$$a$$$ and $$$b$$$. Let $$$a.sum$$$ denote the sum of $$$a$$$ and the rest of the notation is deductible.

Let's say $$$a$$$ comes before $$$b$$$. Then the two conditions that need to be valid are $$$x\ge a.mnprefix$$$ and $$$x\ge b.mnprefix-a.sum$$$. So we want $$$\max(a.mnprefix, b.mnprefix-a.sum)\le \max(b.mnprefix, a.mnprefix - b.sum)$$$ for $$$a$$$ to be chosen before $$$b$$$. However my proof has one flaw, which is that it doesn't account for transitivity. I don't know how to prove another string $$$c$$$ will not affect my result, and how do I know my comparator function is transitive, as each string doesn't have an exact value, and the comparator values are differing according to the string being compared to.

If my solution is correct, can someone tell me if I have made an error in my implementation.

My code

Edit : nvm, I was using abs(mnprefix) in my calculation but not in my code.

Read more »

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

By Everule, 13 months ago, In English

https://atcoder.jp/contests/abc160/tasks/abc160_f //Question link

https://atcoder.jp/contests/abc160/submissions/11324766 //My TLE submission

I need help in understanding how to reroot the tree in O(n) I think I have understood how to reroot the tree but I cannot understand how to do it for every node. For example

dp.resize(n,mp(-1,0)); //dp[u]=(the actual answer, size of subtree) 
cout<<solve(0,0).first<<"\n";
dp[0]=mp(-1,0);
dp[edge[0][0]]=mp(-1,0);
cout<<solve(edge[0][0],edge[0][0]).first<<"\n";

The following code seems to correctly calculate the answer for the root node and it's first edge. But how do I reroot the tree in such a way that it goes to all edges and calculates the answer in O(n)?

Read more »

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