When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

ivan100sic's blog

By ivan100sic, history, 2 years ago, In English

Tonight, I will pick twelve 3000 rated problems I haven't solved yet, try solving them, and track my progress. As usual, I will not look at editorials. Hopefully I will be able to solve them all before the year ends. I will not make this my highest priority and I won't try too hard. I will keep solving other problems in the meantime.

The problems are:

  1. 341E - Candies Game (solved Jan 14, 12 days)
  2. 843E - Maximum Flow
  3. 1250D - Conference Problem (solved Jan 5, 3 days)
  4. 573D - Bear and Cavalry (solved Jan 6, 4 days)
  5. 1290D - Coffee Varieties (hard version) (solved Jan 8, 6 days)
  6. 568E - Longest Increasing Subsequence
  7. 788D - Finding lines (solved Jan 14, 12 days)
  8. 698F - Coprime Permutation (solved Jan 3, 1 day)
  9. 1342F - Make It Ascending (solved Jan 4, 2 days)
  10. 1236F - Alice and the Cactus (solved Jan 3, 1 day)
  11. 533A - Berland Miners (solved Jan 16, 14 days)
  12. 1411F - The Thorny Path (solved Jan 22, 20 days)

My thoughts on the problems I have solved:

Problem 1
Problem 3
Problem 4
Problem 5
Problem 7

More coming soon!

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

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

wow! there is a div-1 A problem rated 3000

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

    But the score distribution for this contest was "A-3000, B-750, C-250, D-3000, E-500, F-1500" !

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

      Yes, there were a few rounds with "dynamic scoring", the score of problems was based on the number of people who solve them, and problems were given in random order.

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

Good luck!

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

Thank you for sharing, I will try the same problems in the following days/weeks and will keep this comment updated with those I solve.

  1. Problem 2: Solved in the past.
  2. Problem 3: Solved on the 4th of January. Challenge: solve the problem for $$$n \le 5000$$$. Comment (in white): I read balbit's comment and I disagree with him. For me this was clean, nice and hard dp problem. My implementation is straightforward, but I had to think a lot (and my first solution was wrong).
  3. Problem 4: Solved on the 4th of January. Comment: My solution is O(nq) and gets accepted without any optimization.
  4. Problem 7: Solved on the 5th of January.
  5. Problem 1: Solved on the 5th of January. Comment: This one is cool. The hardest for me among the ones I have solved.
  6. Problem 5: Solved on the 5th of January. Comment: Not very interesting problem. The question is interesting, the solution not so much. My solution is different from the official one and I had to suffer to reduce enough the number of queries.
  7. Problem 6: Solved on the 5th of January.
  8. Problem 9: Solved on the 5th of January. Comment: Coming up with the dp is easy, implementing it and optimizing it not so easy. I did not like this one, not recommended.
  9. Problem 8: Solved on the 6th of January.
  10. Problem 11: Solved on the 6th of January.
  11. Problem 12: Solved on the 6th of January. Comment: I don't see the point of this kind of problems: a greedy (which is screaming greedy) which involves a gazillion cases. One day I'll start appreciating these kind of problems, or at least I'll learn how to solve them in a reasonably short amount of time.
  12. Problem 10: 16th of January. Comment: By far the hardest for me. I did not think of using the Euler characteristic formula to count the connected components (I read this in the editorial after getting AC) and went on a totally different path. I had never decomposed a cactus in its components and that was educational. I had to summon all my perseverance to resist the urge to read the editorial before I realized how to solve the problem.
  • »
    »
    2 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    Challenge completed! It was fun and I feel like I improved a little bit.

    This list was perfect as it forced me to think about and solve problems which were not particularly attractive to me and so I learnt tricks and ideas which I would have never encountered if not forced.

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

    So incredible to solve all problems without editorial!

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

Funnily enough, there is a Prime New Year Contest right now ;) You can try your luck there as well, I always have a lot of fun with it

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

Look at his heatmap! :-O

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

Looks fun! I'd like to join too.

Problem 1: Solved Jan 5

Fun-ness:

Spoiler

Problem 2: Solved Jan 15

Fun-ness:

Spoiler

Problem 3: Solved Jan 5

Fun-ness:

Spoiler

Problem 4: Solved Jan 5

Fun-ness:

Spoiler

Problem 5: Solved before

Problem 6: Solved Jan 7

Fun-ness:

Spoiler

Problem 7: Solved Jan 6

Fun-ness:

Spoiler

Problem 8: Solved Jan 6

Fun-ness:

Spoiler

Problem 9: Solved Jan 10

Fun-ness:

Spoiler

Problem 10: Solved Jan 8

Fun-ness:

Spoiler

Problem 11: Solved Jan 10

Fun-ness:

Spoiler

Problem 12: Solved Jan 10

Fun-ness:

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

    Challenge complete!

    I greatly enjoyed tackling this list with others, and I would love to join (or create?) a second round (maybe a level 2 round with 3100s???) soon!

    One thing I think this challenge could benefit from is either more problems or a shorter time span. It can be frustrating to have only one problem left on the list that you can't read the tutorial for until the end of the year.

    But overall, I found this challenge very fun, so thank you ivan100sic again for the initiative!

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

I'd like to join too.

I copied this one to another website. However, I do not have enough time, so maybe I can't solve them in a short time. And maybe I will read the solutions.

Good luck!

List

UPD: It seems the problems maybe too hard for me, maybe I can't solve them, but I will try my best.

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

Thank you for the post, this is a great idea and I'm in! ;) I will split the problems into 3 categories.

Main category:

1. Problem 2: Solved on Jan 7
2. Problem 4: Solved on Jan 8
3. Problem 6: Solved on Jan 7
4. Problem 10: Solved on Jan 7
5. Problem 11: Solved on Jan 10

Problems from contests I have not virtually participated in before this post. Will do so when I have time:

1. Problem 1: Didn't get it on the virtual contest, solved on Jan 11
2. Problem 3: Did the virtual contest, solved it in time. Jan 10
3. Problem 9: Did the virtual contest, solved it in time. Jan 7

Problems I solved before:

  1. Problem 5: Upsolved after a virtual contest.

  2. Problem 7: Upsolved after a contest.

  3. Problem 8: Solved on a contest.

  4. Problem 12: Solved on a virtual contest.

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

    Done with the challenge. I had a lot of fun, thanks again to ivan100sic and all fellow solvers! It was cool reading the comments of the others after solving the problem. Would be glad to join something like this again in the future :)

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

533A Rated 3000 !!!!!!!!!!!!!!!!!!!!!!!!!!

»
14 months ago, # |
Rev. 2   Vote: I like it +11 Vote: I do not like it

Will you do another one this year?

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I would love to but I'm currently kind of low on energy for these hard problems