tibinyte's blog

By tibinyte, 2 years ago, In English

Since goals are very important in any individual's life, I decided to set a goal for myself. The target is to set 100 problems until I quit cp.

Current progress: 40

# Date
Problem
Contest
Difficulty
Comments Feedback
1 July 2021
Mordor Trip
Infoleague
Summer 2021
Round 1
1400*
First problem I ever set. It asks you to find the number of bubble sort iterations to sort a given array Good

Bad
2 July 2021
GCD
Infoleague
Summer 2021
Round 1
1700*
This problem is a very standard problem which asks to find sum of gcds across all subarrays Good

Bad
3 July 2021
Magic Digits
Infoleague
Summer 2021
Round 1
2000*
This is a quite ok digit dp problem which asks finding the number of numbers s.t. the maximum frequency of some digit — minimum frequency of some digit = $$$k$$$, where $$$k$$$ is given Good

Bad
4 July 2021
Anagrame
N/A
1300*
Very standard problem that asks to find how many subsets of $$$a$$$ are anagrams of $$$b$$$ Good

Bad
5 July 2021
Caesar Queries
Infoleague
Summer 2021
Training round
1800*
Very standard problem about stirling numbers of the second kind Good

Bad
6 July 2021
Array GCD
Infoleague
Summer 2021
Training round
1700*
Very standard problem asking for sum of gcds across all arrays of length $$$n$$$ and values in range $$$[1,m]$$$ Good

Bad
7 August 2021
Medians
Infoleague
Summer 2021
Round 2
2000*
Problem asking for number of subarrays with given median Good

Bad
8 August 2021
Caesar Legions
Infoleague
Summer 2021
Round 2
2100*
Problem asking for number of subarrays such that if it contains a color, it must contain every color of that kind Good

Bad
9 November 2021
Charity
Infoleague
Autumn 2021
Round 2
Div 2
1600*
A simple greedy problem Good

Bad
10 November 2021
Birthday Nim
Infoleague
Autumn 2021
Round 2
Div 1
1900*
I am only a coauthor in this task. The initial problem idea was by Gheal. A quite standard problem on PIE Good

Bad
11 December 2021
Find set
Infoleague
Autumn 2021
Training round
1500*
This problem is a math problem that turned into a troll problem with partial scoring. I don't take credit for its idea, only for making it appear in a contest :clown: Good

Bad
12 December 2021
àPaPdnarG
Infoleague
Autumn 2021
Training round
2100*
Educational problem on d&c dp optimization Good

Bad
13 January 2022
The revange of GrandPaPa
Infoleague
Winter 2022
Round 1
Div 1
2300*
A nice problem, but my sqrt optimizations were just overkill since very simple solutions were using just PIE. I felt bad after finding out all my work optimizing the dp calculations was useless :( Good

Bad
14 February 2022
Mex Pairs
CodeChef
CookOff
Medium-Hard
You set the cancer dp I couldn't solve.
First and hardest problem I set on codechef
Good

Bad
15 March 2022
Sussy Rooks
CodeChef
Lunchtime
Medium
A quite simple problem about both FFT and PIE. Since I didn't know FFT when I submited this problem on codechef, I'd like to mention Um_nik for improving my initial solution Good

Bad
16 March 2022
Xor or Floor?
Infoleague
Spring 2022
Round 1
Div 1
2300*
It's a quite simple dp problem with an optimization Good

Bad
17 March 2022
Floor or xor?
Infoleague
Spring 2022
Round 1
Div 2
1900*
Quite straightforward couting problem with sieve optimization Good

Bad
18 March 2022
The Hatchet
Infoleague
Spring 2022
Round 1
Div 2
1800*
Quite straightforward problem on monotonic stack Good

Bad
19 April 2022
K0KALARU47 and CP task
CodeChef
Starters
35
Medium
Very cancer dp...
It's good to make your enemies hate you more tho...
Good

Bad
20 April 2022
Lulimpiada
CodeChef
Starters
34
Easy-Medium
I think it's one of my best easy problems Good

Bad
21 July 2022
Median Pairs
CodeChef
Lunchtime
Medium
Very similar statement to the one in Mex Pairs. Here we write an obvious dp and optimize it in a very interesting way Good

Bad
22 July 2022
Three Days Grace
Codeforces
Round #804
2600
First problem I set on codeforces. My initial solution was $$$O(vmax \cdot log^2)$$$, but thanks to valeriu, it was reduced to $$$O(vmax \cdot log)$$$. I think it's one of my best problems Good

Bad
23 November 2022
Maximum Substring
CodeTON
Round 3
800
In my opinion, it's a very good D2B problem, solution combines a simple observation with a not so trivial optimization to keep the balance Good

Bad
24 November 2022
Complementary XOR
CodeTON
Round 3
1400
I don't know why this problem was hated in the rate problem section, I think it's a good task that requires both some thinking and implementation Good

Bad
25 November 2022
Prefix GCD
CodeTON
Round 3
1800
This task was added one day before the competition. It looked a good difficulty jump from C, but the distance to E was a bit too large. I apologize for this Good

Bad
26 November 2022
Bracket cost
CodeTON
Round 3
2400
After realizing how to compute the cost in a smart and flexible way, you can easily use a BIT to solve it Good

Bad
27 November 2022
Majority
CodeTON
Round 3
2700
I think it's one of the best tasks in the contest, there are lots of solutions to it, mostly all at the same difficulty level. There also exists a $$$O(nlog^2n)$$$ solution, which I have implemented, but we used the $$$O(n^2)$$$ version to fit for $$$F$$$ position Good

Bad
28 November 2022
Doping
CodeTON
Round 3
3300
It has a hidden refference, but leaving that behind, I think it's a quite nice counting task, and the solution is very unexpected Good

Bad
29 November 2022
BinaryStringForces
CodeTON
Round 3
3500
First problem I set on codeforces that didn't have any solves during the official contest. It is supossed to be a hard problem with a quite long implementation, but looking at upsolving submissions, implementation can actually be quite short :) Good

Bad
30 March 2023
Sussy Perms
Starters 79
Medium
Finally setting on codechef again :) Yet another counting problem that almost went unsolved ( which is very surprising ). Am I too evil to ask variable mod FFT? Do people template variable mod FFT? I don't know. Orz jeroenodb first and only solve to this problem xD Good

Bad
31 May 2023
Array Merging
Codeforces Round #875
1000
A problem I created because we desperately needed a problem for D2B position. I don't think it's great but not bad either. Good

Bad
32 May 2023
The Third Grace
Codeforces Round #875
3200
A problem that was intended to be in CodeTON Round 3, but we didn't need it there so we used it here. I came up with this problem while I was in car xD Good

Bad
33 August 2023
Omida mincinoasa
Junior challenge 2023
2100*
Best statement of 2023. Find sum of $$$choose(n,i) \cdot i^k$$$, $$$n \le 10^9, k \le 5000$$$ Good

Bad
34 August 2023
Salutare Jupane
Junior challenge 2023
2300*
This problem was intended to be in CodeTON round 3 as D, but was removed few days before the competition. This version is however buffed. Good

Bad
35 October 2023
Doping2
RCPCamp 2023 Iasi day
D1C probably
This shares a similar statement to Doping, but is much easier. Good

Bad
36 December 2023
Largest Subsequence
Codeforces Round 915 (Div. 2)
1400
Initial name was Adam Lying Face :( Good

Bad
37 December 2023
Cyclic Mex
Codeforces Round 915 (Div. 2)
2000
I was expecting this to be as hard as E Good

Bad
38 December 2023
One-X
Codeforces Round 915 (Div. 2)
2400
Used to have some funny refference and a nice drawing but some magician removed both of them. Good

Bad
39 December 2023
Field Should Not Be Empty
Codeforces Round 915 (Div. 2)
2600
Was intended to be D1B in round #875. We ended up removing it because it was too hard. Good

Bad
40 December 2023
Swap N' Mex
Stelele informaticii 2023 Probably D1B~C A rejected proposal from round 875. Good

Bad
  • Vote: I like it
  • +144
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
  Vote: I like it +2 Vote: I do not like it

leafeon.

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

What is quickest and the slowest amount of time you have taken to develop a problem? And is there any correlation with effort vs quality in developing problems?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it took me like 3 days to code the solution for Mex Pairs. About shortest, I don't know what to say.

    Of course putting much effort into developing something makes it better.

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

What do you do when a problem idea of yours turns out to require a much harder solution than expected? When it's the contrary, I think it's usually not so bad, as this "easier solution" in this case is usually one that is much more interesting, but when it gets harder than expected, I often put it off to when I get a better understanding on what may be a good solution. However, as every work has to be done sometime, I know it can't be delayed infinitely, or else I'll forget the idea. So what would you do in this case?

UPD: One more question. In problemsetting, do you make the solution after the problem, or the problem after the solution? This is a very constant dilemma that would be going on every problemsetter's heads, because usually the former makes fun problems that are hard to prove, and the latter makes problems that are easy to prove but is trivial/standard. Which approach do you take?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    It's better to come up with the problem and then find the solution, it's more natural. Of course the reverse works, but it sometimes leads to an unnatural mess.

    I don't understand anything from the first paragraph to be honest, I think you're asking what am I doing when easier solutions exist than my intended one ?

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      Nah, I mean when a problem idea (without a clear solution) started simple, but turned out to be much complex than what you imagined first. What would you do when this happens?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How can one write concise statement for Calorifer

»
2 years ago, # |
  Vote: I like it +44 Vote: I do not like it

How do you come up with such hard tasks with peak rating at 1600? I am 2100 rated, but the hardest task I invented was 2900.

orz, you are a really talented problemsetter.

  • »
    »
    2 years ago, # ^ |
    Rev. 3   Vote: I like it +24 Vote: I do not like it

    Bcs I do be trolling contests ( I don't even do contests on codeforces, mostly olympiad training ). I am also way better at solving tasks given more time to think rather than 2 hours. I could come up with the solution on my own to all of the aforementioned tasks.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      Admitting that you troll contests is a lie to anyone, you only trolled (so far) two (codeforces rounds)

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -28 Vote: I do not like it

    I am not the OP, but I think I might be able to answer, I do be making problems above my ratings. I think problemsetting is basically a whole different skill compared to skills in contests. As tibinyte said, problemsetting is not done under a short time limit. So, they basically have a lot of time to think of new ideas and proofs for those ideas. Also important to problemsetting, would be an interest to a wide variety of algorithms/problems/concepts, sometimes ranging far above their own ratings. It would indeed be strange for a 1300-rated person to solve 2600-rated problems to practice for contests, but it is completely fine for one to think of the same problem deeply because it is interesting enough to research further, and these "interesting problems" are a lot of help later on in the problemsetting process. This help includes a whole problem idea, made from an existing one.

    So, yeah. A problemsetter can make problems, and the problems' difficulty isn't always correlated to the setters' ratings.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The hardest task I invented is -inf rated :(

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How can I submit a contest proposal when my rating isn't 2100+ ?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    By default you cannot, but if you were author in some other round, you gain permissions.

»
2 years ago, # |
  Vote: I like it +18 Vote: I do not like it

As a problem-setter myself, I find it very impressive that you are able to make an entire D1+2 round by yourself (except A). I know someone already asked you how you create such hard tasks as a green, but I am still in disbelief... You mentioned that you do not do Codeforces much, so what do you think you rating would be if you do Codeforces contests regularly.

And how do you come up with such hard problems? For me, I find it very tough to make hard problems as when I come up with an idea, I will think that it is not solvable after some time and stop thinking about it. As the result, all the problems I set are those that I can solve in a shorter period of time, and hence easier. Can you share how you came up with the recent D1+2 H?

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    So what do you think you rating would be if you do Codeforces contests regularly

    I've been really bored this summer so I did some virtual contests.

    Can you share how you came up with the recent D1+2 H?

    Well as you can tell, H is very similar to F. The main inspiration for both these task were Phoneix and computers and PWCA. H has a similar operation to the one in PWCA, but counting it for substrings is very interesting, and is much harder. Not to mention the implementation of H is a very hard task just by itself :)