Dominater069's blog

By Dominater069, 6 days ago, In English

We invite you to participate in CodeChef’s Starters 158, this Wednesday, 30th October, rated upto 6 stars (i.e. for users with rating < 2500)

Time: 8:00 PM — 10:00 PM IST

Joining us on the problem setting panel are:

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here. Hope to see you participating.

Good Luck!

UPD 1: The following is the number of problems:

  • Div1 : 5 problems + 1 subtask
  • Div2 : 7 problems
  • Div3 : 7 problems
  • Div4 : 8 problems

UPD 2: The contest got changed to rated upto 6 stars. I am sorry for the late change. We decided it was hard enough for 6 stars.

UPD 3 : Congratulations to Top 5!

Full text and comments »

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

By Dominater069, 3 weeks ago, In English

We invite you to participate in CodeChef’s Starters 156, this Wednesday, 16th October, rated upto 6 stars (i.e. for users with rating < 2500)

Time: 8:00 PM — 10:00 PM IST

Joining us on the problem setting panel are:

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here. Hope to see you participating.

The following is the number of problems in each division :

  • Division 1 : 5 problems
  • Division 2 : 7 problems
  • Division 3 : 7 problems
  • Division 4 : 8 problems

There are no subtasks this time.

Good Luck!

Congratulations to Top 5!

Full text and comments »

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

By Dominater069, 5 weeks ago, In English

We invite you to participate in CodeChef’s Starters 154, this Wednesday, 2nd October, rated upto 6 stars (i.e. for users with rating < 2500)

Time: 8:00 PM — 10:00 PM IST

Joining us on the problem setting panel are:

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here. Hope to see you participating.

Good Luck!

Full text and comments »

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

By Dominater069, 2 months ago, In English

I would like to thank redpanda and qmk for their great help in writing and reviewing this blog. They are also the users who queried O1-mini for all the following problems.

We tried O1-mini on several problems, from a variety of sources. Let's list the results first.

Note :

  • Some of the WA verdicts here actually means that the AI just "stopped thinking" which means the AI thought for a long enough time without any useable results so it ran into an error.

  • All ratings mentioned are Codeforces ratings, the Atcoder ratings have been converted to codeforces rating. To measure the approximate codeforces rating of the atcoder problems mentioned here, you can use https://kenkoooo.com/atcoder/#/table/ + https://silverfoxxxy.github.io/rating-converter.

D2ABs

Standard problems

ARC AB Problems

D2C+ (Non-standard) problems

Conclusion

Overview

  • gpt o1-mini is very good and faster than humans at some standard problems ≤ atcoder blue, these types of problems can't appear in contests if we want fair contests where AI doesnt determine ranking

  • gpt o1-mini is very good at most easy "adhoc" problems like D2AB and is faster than or as fast as tourist at these problems, I'm not certain about how to make D2A's that ai cant solve and D2B has limited options too.

  • the AI struggles a lot on harder "adhoc" problems , especially multistep problems where the steps aren't standard

  • Div1 people are completely unaffected (for now at least). Some extra care needs to go into choosing d2Bs such that O1-mini can't solve them, but otherwise Div2 contests are also mostly unaffected.

D2AB Ad-Hoc problems

It can "solve" most of the Div2AB level problems in under a minute. Why do i double quote around "solve"? Often, even when the AI can't really reason the solution, if the solution is simple enough like $$$min(a, b)$$$, it gets there by brute forcing.

It is hard to create problems which are suitable for such positions and still not solvable by beginners, but I don't believe it is impossible. We have 3 examples listed above ($$$1$$$ d2A and $$$2$$$ d2B), which are all constructive problems (and the construction isn't as simple as print $$$1, 2, ... n$$$). Constructive problems are one of the weaknesses of the AI, or more generally, problems where the ad-hoc part cannot be reached easily through bruteforcing.

It also failed arc183_a — Median of Good Sequences and 1943A - MEX Game 1, which are easy enough to be D2Bs.

$$$2$$$ tips in particular for easy problems i would like to stress on for problemsetters :

  • Don't have them be a stupid (even if it is cute) result. For example, output $$$a + b$$$ or print $$$1, 2, .. n$$$.

  • Try to have problems where genuine insight can't be easily replaced by guessing.

I know these are hard to do, especially for D2A. D2B might still be possible....and it is important if we try to make it as fair as possible.

Another option is to remove D2A and start at D2B (with registered => rated) with a less steep difficulty progress over the contest. There won't be a big difference for most participants however maybe completely new beginners will feel bad however if they solve no problems.

Standard Contests (ABC/Div3/Div4)

AI can perform exceedingly well in such contests. It is trained on infinite problems, and can recognize techniques with ease. For, example it solved the MO's problem in only $$$27$$$ seconds, while it took minutes for several Ad hoc problems (even when it managed to solve it)

These contests simply aren't fair in the current format. Even if you ban AI, i can always just understand and rewrite it's solution. I strongly urge one of the following $$$3$$$ actions :

  • Remove them

  • Have them unrated and solely for practice

  • Rework them to not have so many Standard problems

$$$2$$$-nd option probably isn't very feasible, and you may not want to do the $$$1$$$-st. Thus, I suggest the $$$3$$$-rd.

Div2C+ Ad-hoc Problems

These problems generally need multi steps, and thus, the AI has a very low probability to solve it. It failed each and every one of the last $$$5$$$ D1As under 1400 rating.

Problems requiring some thinking which can't be easily replaced by brute-forcing solutions is the way to beat it, along with having multistep problems. With every non-trivial step (or even a trivial step given how the AI works) reduces the probability for the AI to solve the problem exponentially.

A meta shift needs to happen in the recent future, where we have to solely focus on making multistep problems with several thinking non-trivial steps. However, we are not there yet.

Rating Approximations

(These are purely approximations from the data we have, and is my personal opinion. They could be more accurate with more data but unfortunately we only have limited queries.)

  • ABC, Div3, Div4 contests : [1900+] according to CF rating

  • Div2 contests : [1500]

  • ARC : [1300] according to CF rating

  • Div1 & AGC : -

Final Remarks

We are mostly fine. Some amount of care needs to go to build easy problems which AI can't solve but other than that not majorly affected. Banning AI probably is the right move now however.

In the future, I don't see this type of "generate $$$10^9$$$ solutions and find the right one" AI being good at solving harder problems, especially if we try to counter it. An AI that can actually reason is much more dangerous imo...

Full text and comments »

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

By Dominater069, 2 months ago, In English

We invite you to participate in CodeChef’s Starters 150, this Wednesday, 4th September, rated upto 6 stars (i.e. for users with rating < 2500)

Time: 8:00 PM — 10:30 PM IST

Joining us on the problem setting panel are:

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here. Hope to see you participating.

Here is the number of problems in each division :

  • Division 1 : 5 problems + 1 subtask
  • Division 2 : 6 problems + 2 subtasks
  • Division 3 : 6 problems + 2 subtasks
  • Division 4 : 7 problems + 2 subtasks

Please note that the contest is of 2.5 hours instead of the usual 2 hours.

Good Luck!

Hope you enjoyed the contest.

Congratulations to Top 5!

  1. potato167

  2. maspy

  3. tiger2005

  4. noimi
  5. noya2

Full text and comments »

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

By Dominater069, 2 months ago, In English

Recently, I got a request asking me to write down my thought process while solving questions. So, here is the promised blog.

I would like to thank IceKnight1093, qwexd, Sana, Everule and NovusStellachan for proof reading and suggesting edits in the blog. Special thanks to satyam343 for discussing most of the blog with me.

1. Overview

The blog contains my solutions to $$$7$$$ problems in a wide range of ratings, starting from $$$1200$$$ all the way upto $$$2700$$$. Each problem has a step-by-step solution and you can notice how there are no large jumps in logic, but everything comes naturally. I do not claim that this is always possible in each problem, however I solve majority of CF problems in such a manner.

There are certainly other high rated people who will have completely different methods of solving. However, this is about what works for me. There are some meta ideas taken from parts of the solution and listed at the end in a "What can we learn?" section. I hope the blog is useful for you.

2. Some General Question Solving Strategies

Here is a non-exhaustive list of techniques that are useful to keep in mind. These are internalized by most experienced participants already but maybe it helps you.

  • Figuring out the Nature of an Optimal Solution. One of the most important thing in problems imo.

  • Solving subtasks of the original problem and then trying to extend/generalize your solution.

  • Fixing a parameter and then trying to maximise the result with respect to that fixed parameter.

  • Finding necessary and sufficient conditions. Sometimes, your necessary conditions themselves become sufficient, or vice versa.

  • Identifying Lower and Upper bounds, and constructing them.

  • Reducing a problem into smaller subproblems, commonly used with Dynamic Programming or Inductive Proofs.

  • Considering the Decision Version of the Problem instead. Especially useful in Counting problems, where you need to count number of good subsequences for example.

  • Formalizing the Problem

3. Questions and Solutions Section

Question 1. 1979C - Earning on Bets

Step 1
Step 2
What can we learn?

Question 2. 1987D - World is Mine

General Idea
Step 1
Step 2
Step 3
Step 4
What can we learn?
Similiar Problems

Question 3. 1977C - Nikita and LCM

Step 1
Step 2
What can we learn?

Question 4. 1889B - Doremy's Connecting Plan

Step 1
Step 2
Step 3
What can we learn?

Question 5. 2002D1 - DFS Checker (Easy Version)

Step 1
Step 2
Additional Note
Implementation
What can we learn?

Question 6. 1930E - 2..3...4.... Wonderful! Wonderful!

Step 1
Step 2
Step 3
What can we learn?

Question 7. 2003E1 - Turtle and Inversions (Easy Version)

Disclaimer : My solution differs from the editorial completely. You can read the editorial for their approach. I will present mine. Try to extend to the hard version of the problem from this.

Subproblem
Subproblem Step 1
Subproblem Step 2
Subproblem Step 3
Step 4
Additional Note
Hint 1 of Hard Version
Hint 2 of Hard Version
What can we learn?

4. About Stress Testing

Something which a lot of low rated participants do wrong : They don't stress test.

There have even been contests where I stress tested $$$3$$$ problems. I tend to make a lot of errors while writing code and it is not easy to always catch those errors with manually reading or debugging. Learning the skill of stress testing is insanely useful (and you don't need any tools for it, I do it all in the same piece of code without taking much time).

This was the first problem (I think) that i had stress tested during contest : 1854A1 - Dual (Easy Version) I was still done within $$$12$$$ minutes and it took me less than $$$5$$$ mins to stress test, and fix my bug (this is an easy example though as I didn't have to write a brute). My bug only occurred when all elements of the array were equal and negative, I don't think I would manually be able to catch that.

1987F1 - Interesting Problem (Easy Version) In the initial submission to this problem, I missed so many if-cases. I was very careless. But i managed to stress test and avoid more WAs. I think it took me 3 — 4 iterations of finding bug with stress test, fixing them and then again running stress test before my code was actually correct.

I highly recommend stress testing for you. It is simpler than you think : all you need is a brute function, and a generator. I usually replace my input function with a generator, and use a lambda function for the brute. It takes barely $$$5$$$ minutes to setup for most problems.

Full text and comments »

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

By Dominater069, 3 months ago, In English

We invite you to participate in CodeChef’s Starters147, this Wednesday, 14th August, rated upto 5 stars (i.e. for users with rating < 2200)

Time: 8:00 PM — 10:00 PM IST

Joining us on the problem setting panel are:

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here. Hope to see you participating.

Good Luck!

Congratulations to Top 5!

  1. maspy

  2. redstar08

  3. ecottea

  4. tiger2005

  5. kdu_5

Full text and comments »

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

By Dominater069, 4 months ago, In English

We invite you to participate in CodeChef’s Starters143, this Wednesday, 17th July, rated for till 5-Stars(ie. for users with rating < 2200).

Time: 8:00 PM — 10:00 PM IST

Joining us on the problem setting panel are:

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here. Hope to see you participating.

The following is the count of problems in each division :

  • Division 1 : 5 problems
  • Division 2 : 6 problems
  • Division 3 and 4 : 7 problems

Good Luck!

UPD : Congratulations to the top 5!

  1. jeroenodb
  2. kdu_4
  3. maspy
  4. liympanda
  5. Kude

Full text and comments »

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

By Dominater069, 5 months ago, In English

We invite you to participate in CodeChef’s Starters139, this Wednesday, 19th June, rated for till 5-Stars(ie. for users with rating < 2200).

Time: 8:00 PM — 10:00 PM IST

Joining us on the problem setting panel are:

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.

The following is the number of problems in each division :-

  • Division 1 : 5 problems
  • Division 2 : 6 problems
  • Division 3 : 6 problems
  • Division 4 : 7 problems

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here. Hope to see you participating.

Good Luck!

Congratulations to Top 5!

Full text and comments »

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

By Dominater069, 5 months ago, In English

We invite you to participate in CodeChef’s Starters136, this Wednesday, 29nd May, rated for till 6-Stars(i.e. for users with rating < 2500).

Time: 8:00 PM — 10:00 PM IST

Joining us on the problem setting panel are:

Div1 will have 6 problems. Div2, Div3, Div4 will have 7 problems.

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here. Hope to see you participating.

Good Luck!

UPD : Sorry for the issue in XORNE0.

Top 5 :

  1. maspy

  2. aryanc403

  3. duongnc2

  4. sevlll777

  5. leaf1415

Full text and comments »

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

By Dominater069, 6 months ago, In English

We invite you to participate in CodeChef’s Starters135, this Wednesday, 22nd May, rated for till 5-Stars(ie. for users with rating < 2200).

Time: 8:00 PM — 10:00 PM IST

Joining us on the problem setting panel are:

There will be 5 problems for Div1, 6 problems in Div2 and 7 each in Div3 and Div4.

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here. Hope to see you participating.

Good Luck!

Update : Congratulations to the Fastest AKs and Winners

  1. SSerxhs

  2. maspy

  3. SmolBrain

  4. Kira_1234

  5. liympanda

Full text and comments »

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

By Dominater069, 8 months ago, In English

Sorry for the delay in publishing the editorial. If anything is unclear or missing, please let me know in the comments.

In all the problems, reading the hints is a must as the solution continues from there.

1944A - Destroying Bridges

Idea: Dominater069
Preparation: Dominater069
Editorial: Dominater069

Hint 1
O(n) Solution
Hint 2
Hint 3
O(1) Solution
Code (O(n))
Code (O(1))

1944B - Equal XOR

Idea : satyam343
Preparation : satyam343
Editorial : Dominater069

Hint 1
Hint 2
Hint 3
Solution
Code

1943A - MEX Game 1

Idea : Dominater069
Preparation : Dominater069
Editorial : Dominater069

Hint 1
Big Hint 2
Hint 3
Solution
Code

1943B - Non-Palindromic Substring

Idea : errorgorn, Dominater069
Preparation : Dominater069
Editorial : Dominater069

Hint 1
Hint 2
Solution
Code

1943C - Tree Compass

Idea: Everule
Preparation: Dominater069
Editorial: Dominater069

Hint 1
Hint 2
Hint 3
Solution
Code

1943D1 - Counting Is Fun (Easy Version)

Idea : satyam343
Preparation : satyam343
Editorial : Dominater069

Hint 1
Hint 2
Solution
Code

1943D2 - Counting Is Fun (Hard Version)

Idea : satyam343
Preparation : satyam343
Editorial : Dominater069

Hint 1
Hint 2
Solution
Code

1943E1 - MEX Game 2 (Easy Version)

Idea: Dominater069
Preparation: Dominater069
Editorial: Dominater069

Hint 1
Hint 2
Hint 3
Solution
Code

1943E2 - MEX Game 2 (Hard Version)

Idea: Dominater069
Solution : ffao
Preparation: Dominater069
Editorial: errorgorn

Solution
Code

1943F - Minimum Hamming Distance

Idea: satyam343
Preparation: satyam343
Editorial: satyam343

Hint 1 / Claim 1
Hint 2
Solution
Code

Full text and comments »

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

By Dominater069, 8 months ago, In English

Hello Codech....err i mean Codeforces!

I invite you to participate in Codeforces Round 934 (Div. 1) and Codeforces Round 934 (Div. 2) which will start on Mar/16/2024 17:35 (Moscow time).

You will be given 6 problems and 2 hours 15 minutes to solve them in both divisions. Division 1 has $$$\textbf{2 subtasks}$$$, and Division 2 has $$$\textbf{1 subtask}$$$.

Joining us on the problem setting panel are:

I would like to thank MikeMirzayanov for platforms Codeforces and Polygon.

Please do read a few problems in advance at the very least. Especially with all the subtasks, it is strictly in your benefit to read and choose the problems you want to try. Good luck. We hope you enjoy the problemset.

Score Distribution will be posted soon.

$$$\textbf{UPD}$$$ : Score Distribution :
Div2 : 500 + 1000 + 1500 + 2250 + 2250 + (2250 + 2750).
Div1 : 500 + 1250 + 1250 + (1250 + 2000) + (2000 + 1500) + 4500.

$$$\textbf{UPD2}$$$ : Sorry for the issue with the queue towards the end. Hope you enjoyed the round.

$$$\textbf{UPD3}$$$ :
Div2 :
1) WanYuanShenWanDe
2) tzc___________________wk
3) kcodex
4) mily
5) Oinng123

Div1 :
1) tourist
2) jiangly
3) gyh20
4) Benq
5) ecnerwala

$$$\textbf{UPD4}$$$ : Editorial is out.

Full text and comments »

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

By Dominater069, history, 10 months ago, In English

We invite you to participate in CodeChef’s Starters115, this Wednesday, 3rd January, rated for All.

Time: 8:00 PM — 10:30 PM IST

Joining us on the problem setting panel are:

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

All problems except 2 are made by me. Hope you find them interesting, but constructive criticism is also appreciated. There will be a total of 11 problems, out of which 7 will be scoreable for division 1 and 8 scoreable problems for every other division.

Hope to see you participating. Good Luck!

UPD : The contest got extended by 30minutes to a total of 2.5hours.

Full text and comments »

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

By Dominater069, 10 months ago, In English

Hello, very recently stefdasca's 2 predict blogs got deleted by (presumedly) MikeMirzayanov, along with all of his comments in the last 48 hours, and he was muted. The first predict blog was never censored till now which makes it even more strange.

This is part of a wider censorship scheme caused by the outrage over the goodbye 2023 round. I would ask Mike to kindly give his reasoning as to why he felt Stefdasca's predict blogs were against the rules.

UPD : Thanks Mike for a quick reply and promising to rectify the solution. I am sorry for presuming it was done by you.

Full text and comments »

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

By Dominater069, history, 11 months ago, In English

We invite you to participate in CodeChef’s Starters112, this Wednesday, 13th December, rated till 6-stars (ie. for users with rating < 2500).

Time: 8:00 PM — 10:00 PM IST

Joining us on the problem setting panel are:

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

For this contest, it is guaranteed that the first tests are always the samples. Further, there is one problem with 2 subtasks.

Hope to see you participating.

Good Luck and Have Fun!

Full text and comments »

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

By Dominater069, history, 12 months ago, In English

Invitation to CodeChef Starters 108 (Rated till 6-stars) — 15th November

We invite you to participate in CodeChef’s Starters 108, this Wednesday, 15th November, rated till 6-stars (ie. for users with rating < 2500).

Time: 8:00 PM — 10:15 PM IST

Read about the recent judge migration here.

Joining us on the problem setting panel are:

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Hope to see you participating.

Good Luck!

Full text and comments »

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