lis05's blog

By lis05, history, 13 days ago, In English

Today, or more precisely, yesterday, my good old friend BallBreaker reached Master rank for the first time in their life.

Congratulations my friend! Reaching the color of the sun is a great achievement! It was hard, painful, and very stressful, but no matter what, you haven't given up, and now you've reached your goal, becoming one of the best CPers in the world!!!

Orz BallBreaker of the Super Secret Competitive Programming community!

Don't stop, and some day, you are going be the first nutella in the world! Good luck!

Full text and comments »

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

By lis05, history, 4 months ago, In English

It's almost the new year. Isn't it time for some magic to appear?

Full text and comments »

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

By lis05, history, 8 months ago, In English

Although the trend seems to be over, I decided to make another AMA blog definitely not to farm contribution.

Full text and comments »

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

By lis05, history, 10 months ago, In English

Hello Codeforces!

Since I have exams in a few days, I was thinking about what I have spent my life on, and why I haven't been preparing for the exams all that time, doing CP instead. So, I decided to calculate a rough amount of time I have spent solving problems.

Codeforces

I have participated in $$$152$$$ contests, each being $$$120$$$ minutes on average. I have upsolved $$$892$$$ problems. There were a lot of easy problems that I've solved in $$$10$$$ or $$$20$$$ minutes, and there were some problems I had to think about for more than $$$5$$$ hours. Since solving problems also involves coding them, I decided to take the average as $$$60$$$ minutes.

Summing up, I have spent $$$152 * 120 + 892 * 60 = 71760$$$ minutes or $$$1196$$$ hours spent on $$$152$$$ contests and $$$892$$$ upsolved problems on codeforces platform.

atcoder

I have participated in $$$28$$$ atcoder contests, each being $$$100$$$ minutes on average. I have upsolved near to $$$50$$$ problems, and as with the case of codeforces, I decided to take the average time spent on a single problem as $$$60$$$ minutes.

Summing up, I have spent $$$28 * 100 + 50 * 60 = 5800$$$ minutes or $$$96$$$ hours spent on $$$28$$$ contests and $$$50$$$ upsolved problems on atcoder platform.

These were all of the specific platforms I've ever tried.

National olympiads

During the last 4 years I've participated in many national olympiads. I have participated in roughly $$$32$$$ national contests of any type(being national OI, national OI selections, selections to IOI, etc). All contests had duration of $$$5$$$ hours. Summing up, $$$32 * 5 = 160$$$ hours spent on any kind of national OI contests.

International olympiads

I've taken part in $$$2$$$ RMI editions, each having $$$2$$$ contests.

I've participated in $$$2$$$ IZHO olympiads, each having $$$2$$$ contests.

I've participated in $$$1$$$ IATI competition, consisting of $$$2$$$ contests.

All of the contest had durations of $$$5$$$ hours. Summing up, $$$4 * 5 + 4 * 5 + 2 * 5 = 50$$$ hours spent on solving problems from international competitions.

Other

During my CP career, I've solved a lot of problems. Some were given to me by my coach or friends, some I have solved while practicing new techniques. My estimation of the number of solved problems on platforms other than Codeforces and atcoder is near 250 problems. For these problems, I decided to lower the average time spent on sovling a single problem to 45m.

Summing up, $$$250 * 45 = 11250$$$ minutes or $$$187$$$ hours spent on solving problems from other platforms.

Conclusion

The total time spent on solving any problems from any contests or olympiads is $$$1196 + 96 + 160 + 50 + 187 = 1689$$$ hours.

It means that I've spent 1689 hours or 70.4 days solving problems without any breaks. That's a huge number, right?

Of course, the calculations were made with awful precision, and are partially based on my personal feelings. Still, I expect them to be at least the lower bound on the real result.

Would I, if possible, go through all that once again? Certainly.

Would I recommend anyone else to try spending hundreds or thousands of hours solving algorithmic problems? Yes! It was the best experience in my life.


I wrote this post because I wanted to share my story. If you can, leave a comment below this post with your calculations of the time spent solving problems, or any other related data. I am looking forward to hear your story!

Full text and comments »

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

By lis05, history, 10 months ago, In English

Today, 01.06.2023, me, master lis05 with rating 2163, sets myself a challenge to reach grandmaster rank before the end of the summer, 01.09.2023. If I fail, then I'll do whatever is written in the most liked comment. I can't buy you a Bugatti or become the citizen of Botswana, so only realistic requests will be taken into account. Good luck to me.

UPD: Since I plan to do a lot of virtual contests, I decided to write down my performance in them. Performance in a contest is calculated as performance of the first participant whose place is worse than mine.

  1. 2152 — 28.05.2023
  2. 2141 — 29.05.2023
  3. 2042 — 31.05.2023
  4. 2351 — 01.06.2023
  5. 2277 — 02.06.2023
  6. 1958, 2063 — 03.06.2023 (bruh, what an unlucky day)
  7. 2064 — 05.06.2023 (okay, maybe I should stop solving EDU rounds)
  8. 2351 — 12.06.2023 (Yeah, I took a pause because of my exams. But I am free now! Yey!)

UPD

Sadly, I failed. I will keep my promise tho. Wait for an update.

Full text and comments »

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

By lis05, history, 11 months ago, translation, In English

This project has been developed for more than a year. It's a third version (but the name historically was left as CPv2) and I think it's finally ready to be presented to you.

CPv2 — Meet a new and great Competitive programming environment for C++ to make life easier!

Main features are:

  • fast compilation (with precompiled headers)
  • time and memory measurements
  • variety of run modes
  • built in snippets support
  • built in templates support
  • file io
  • ships with premade code template ( REPLACED CIN/COUT WITH MUCH BETTER THINGS! )
  • console interface with formatted output

Link to github: https://github.com/lis05/CPv2

You absolutely MUST take a look at the replacements for cin/cout. They are the best thing I've ever seen in my life.

Full text and comments »

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

By lis05, history, 12 months ago, In English

When you try to search anything, nothing is found. I think this is a bug, right?

Full text and comments »

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

By lis05, history, 12 months ago, In English

codeforces.com is not working today! Do you have the same problem?

(I'm writing this from codeforc.es)

Full text and comments »

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

By lis05, history, 13 months ago, In English

Hello Codeforces.

I made two identical submissions on the same problem.

C++ 17(64bit) — 842ms.

C++ 20(64bit) — 1138ms.

Does anyone know why the time differs so much?

Full text and comments »

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

By lis05, history, 14 months ago, In English

Does anyone have results of the second day?

Full text and comments »

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

By lis05, history, 14 months ago, In English

Hi guys. I've been trying to learn fast polynomial multiplication. I found that the most famous(probably?) algorithms are FFT and Karatsuba algorithm.

Karatsuba algorithm is pretty easy, but it is slow. I couldn't submit few problems because of TLE. Even if a submission passed, it was on the edge between AC and TLE.

On the other side, FFT is much faster but also much more complex. By complex I mean that it's hard to truly understand and implement it.

I need an advice: what should I do? Should I stick with Karatsuba algorithm and learn how to implement it better? Or should I make one more try to understand FFT? If yes, where is the best place to learn it without much pain?

Full text and comments »

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

By lis05, 15 months ago, In English

Any problems from any platforms are welcome!

Full text and comments »

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

By lis05, history, 15 months ago, In English

It's almost the new year. Isn't it time for some magic to appear?

Full text and comments »

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

By lis05, history, 17 months ago, In English
  • Vote: I like it
  • -22
  • Vote: I do not like it

By lis05, history, 21 month(s) ago, In English

The best are paper and a pen. But what about computer programs to draw the details of the problem? What programs do you use?

Full text and comments »

  • Vote: I like it
  • -20
  • Vote: I do not like it

By lis05, history, 22 months ago, In English

Latex in problems is broken. Fix it please!

Full text and comments »

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

By lis05, 2 years ago, In English

Tomorrow will be the day when Chornobaivka #14 Training Camp starts. Register by the link: www.chornobaivka.training.camp

Full text and comments »

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

By lis05, history, 2 years ago, translation, In English

I have big problems with accessing Codeforces. Is it just for me?

Full text and comments »

  • Vote: I like it
  • -4
  • Vote: I do not like it

By lis05, history, 2 years ago, translation, In English

https://stop-russia.near.page/

Many Russians believe their news. Let's show them what is really going on in Ukraine.

  • On Monday, the Russian military massively shelled Kharkiv from Grads, killing and injuring dozens of civilians.

  • Even civilians steal and destroy Russian war machines and tanks

  • As a result of the Russian military attack on Ukraine, more than 350 civilians were killed and more than 2,000 were wounded. Among the dead are 16 children.

  • A rocket hit a residential building in the center of Chernihiv

https://stop-russia.near.page/

Много россиян верят своим новостям. Давайте покажем им, что на самом деле происходит в Украине.

  • Российские военные в понедельник массированно обстреляли Харьков из "Градов", погибли и ранены десятки мирных жителей.

  • Даже гражданские жители воруют и уничтожают российские боевые машины и танки

  • В результате военного нападения России на Украину погибли более 350 гражданских лиц и ранены более 2 тысяч. Среди погибших – 16 детей.

  • В жилой дом в центре Чернигова попала ракета

https://stop-russia.near.page/

Full text and comments »

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

By lis05, history, 3 years ago, In English

Hello codeforces! Try to solve both of the problems from https://codeforces.com/contestInvitation/fcf424afaf5b7a5d01aebf1a908d6ef3589e4fb3. good luck

Solution:

This is a simple dp problem(very simple), but with a high constraints. Standard knapsack runtime is O(NW), but we can optimize it to run in O(NW/32) using bitset.

#include<bits/stdc++.h>
using namespace std;

const int W=2e5;
bitset<W>b;
 
signed main(){
    int n,w;
    scanf("%d %d",&n,&w);
    b[0]=1;
    while(n--){
        int a;
        scanf("%d",&a);
        b|=(b<<a);
    }
    if(b[w])printf("YES\n");
    else printf("NO\n");
}

How does it work? b[k] contains 0, if it's not possible to get sum k, and 1, if it's possible.

At start, we set b[0] to 1(because we can get sum 0). Next, for each item we left-shift out bitset by a[i]. new_b=b<<a[i] After this move, new bitset contains information about what can we get if we will take current item, but it ignores all previous moves(when we didn't take current item). To fix this, we need to connect two bitsets in one using bitwise or. new_new_b=new_b|b

To do this fast, we just write b|=(b<<a)

Why this works fast? We do N operations of shifting W elements. But bitset works as a long binary number, which constructs of a many 32bit integers. So we don't shift W numbers, we shift only W/32. this is why it work's so fast

But this solution runs in 1s, which is too much. How to improve the improvement? Add some useful pragmas:

#include<bits/stdc++.h>
using namespace std;

// very useful pragmas
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")


const int W=2e5;
bitset<W>b;
 
signed main(){
    int n,w;
    scanf("%d %d",&n,&w);
    b[0]=1;
    while(n--){
        int a;
        scanf("%d",&a);
        b|=(b<<a);
    }
    if(b[w])printf("YES\n");
    else printf("NO\n");
}

Now it runs in ~700ms

P.S This was our first ever problem created on polygon, so we failed it a little with bad tests. Sorry, we will improve ourself for the future!

Also thanks for a great callback!

Full text and comments »

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

By lis05, history, 3 years ago, In English

What's going on??

Hello codeforces! Recently, i've noticed that codeforces custom test with g++ 17 uses more than 500bytes per empty std::queue, while sizeof shows only 40bytes. This problem is also with std::deque. What's going on? Compiled with GNU G++17 7.3.0

Full text and comments »

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