Блог пользователя lis05

Автор lis05, 3 месяца назад, По-английски

So for the last couple of months I've been busy making a simple (and unfortunately slow) interpreted programming language called Cotton. Today, I was able to compress its entire source code into a single file and solve an atcoder problem using a small program in Cotton written in a huge interpreter in C++.

UPD: I rewrote the "glueing" script in Cotton. You can compare python and cotton scripts if you want (they work almost identically. however, i dont have regex library, so i could not remove comments using re like in python).

Why you need this information? You don't. I just wanted to share my excitement with someone.

The program in Cotton:

arr = make(Array)
    .resize(read(Integer))
    .apply(function(x){x=read(Integer);});

target = arr.copy().sort(function(a,b){a>b;})[1];

// don't have a function that would return element's position yet
for i = 0; i < arr.size(); i++; {
    if arr[i] == target; {
        println(i + 1);
        return;
    }
}

If you want to look at the beautiful obfuscated code of the interpreter, it's available here

UPD: I managed to optimize the code a bit, and therefore I was able to solve atcoder frog1 problem in 1.998 seconds :)

The solution:


arr = make(Array) .resize(read(Integer)) .apply(function(x){x=read(Integer);}) .append(0, 0); n = arr.size() - 2; dp = make(Array) .resize(arr.size()) .apply(function(x){x=100000000000000;}); dp[0] = 0; for i = 0; i < n; i++; { dp[i + 1] = min(dp[i + 1], dp[i] + abs(arr[i] - arr[i + 1])); dp[i + 2] = min(dp[i + 2], dp[i] + abs(arr[i] - arr[i + 2])); } println(dp[n - 1]);

Полный текст и комментарии »

  • Проголосовать: нравится
  • +201
  • Проголосовать: не нравится

Автор lis05, история, 8 месяцев назад, По-английски

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!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +31
  • Проголосовать: не нравится

Автор lis05, история, 12 месяцев назад, По-английски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +67
  • Проголосовать: не нравится

Автор lis05, история, 16 месяцев назад, По-английски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +12
  • Проголосовать: не нравится

Автор lis05, история, 18 месяцев назад, По-английски

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!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +134
  • Проголосовать: не нравится

Автор lis05, история, 18 месяцев назад, По-английски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +251
  • Проголосовать: не нравится

Автор lis05, история, 19 месяцев назад, По-русски

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.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +58
  • Проголосовать: не нравится

Автор lis05, история, 20 месяцев назад, По-английски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +106
  • Проголосовать: не нравится

Автор lis05, история, 20 месяцев назад, По-английски

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

(I'm writing this from codeforc.es)

Полный текст и комментарии »

  • Проголосовать: нравится
  • +13
  • Проголосовать: не нравится

Автор lis05, история, 21 месяц назад, По-английски

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?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +4
  • Проголосовать: не нравится

Автор lis05, история, 22 месяца назад, По-английски

Does anyone have results of the second day?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +16
  • Проголосовать: не нравится

Автор lis05, история, 22 месяца назад, По-английски

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?

Полный текст и комментарии »

  • Проголосовать: нравится
  • +25
  • Проголосовать: не нравится

Автор lis05, 23 месяца назад, По-английски

Any problems from any platforms are welcome!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +32
  • Проголосовать: не нравится

Автор lis05, история, 23 месяца назад, По-английски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +98
  • Проголосовать: не нравится

Автор lis05, история, 2 года назад, По-английски
  • Проголосовать: нравится
  • -22
  • Проголосовать: не нравится

Автор lis05, история, 2 года назад, По-английски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • -20
  • Проголосовать: не нравится

Автор lis05, история, 2 года назад, По-английски

Latex in problems is broken. Fix it please!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +55
  • Проголосовать: не нравится

Автор lis05, 3 года назад, По-английски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

Автор lis05, история, 3 года назад, По-русски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • -4
  • Проголосовать: не нравится

Автор lis05, история, 3 года назад, По-русски

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

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

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

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

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

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

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/

Полный текст и комментарии »

  • Проголосовать: нравится
  • +50
  • Проголосовать: не нравится

Автор lis05, история, 3 года назад, По-русски

Недавно я получил следующее сообщение:

Это как те письма, которые часто приходят на почту с просьбами "кликнуть на эту ссылку" или еще что-то сделать... Для тех, кто не знает: если отправить то, что просят, то ваш аккаунт будет использоваться для зарабатывания криптовалюты. Он никак не пострадает, но... И ладно бы еще в открытую попросить об этом, но не обманывать же...

А вы получали такое сообщение?

  • Да
  • Да, несколько
  • Нет

Не обманывайте других. Не будьте обмануты и сами.

Полный текст и комментарии »

  • Проголосовать: нравится
  • +14
  • Проголосовать: не нравится

Автор lis05, история, 3 года назад, По-английски

Hello codeforces! Try to solve both of the problems from https://codeforces.me/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!

Полный текст и комментарии »

  • Проголосовать: нравится
  • +35
  • Проголосовать: не нравится

Автор lis05, история, 3 года назад, По-английски

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

Полный текст и комментарии »

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится