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

Автор K1o0n, 2 года назад, По-русски

Привет! Мы приглашаем вас на Codeforces Round 957 (Div. 3), который состоится в 11.07.2024 17:35 (Московское время). Данный раунд будет представлен по правилам третьего дивизиона. Вам будет предложено 7 задач, которые мы с Noobish_Monk, ErnKor, Kmes и ArSarapkin подготовили для вас.

Согласно правилам третьего дивизиона:

  • Вам будет предложено 7 задач.

  • Штраф за неверную посылку будет составлять 10 минут.

  • 12-ти часовая фаза открытых взломов после окончания контеста.

  • После завершения фазы открытых взломов ваши решения будут перетестированы по обновленным тестам.

Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:

  • принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)

  • не иметь в рейтинге точку 1900 или выше.

Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.

Мы хотим поблагодарить всех, кто помог в составлении раунда:

Удачи!

UPD1 После окончания раунда Shayan проведёт трансляцию с разбором решений, также будет доступна запись, но также мы подготовим и текстовый разбор.

UPD2 Видео-разбор от Shayan

UPD3 Видео-решение "победителя" этого раунда, neal

UPD4 Текстовый разбор.

UPD5 Поздравляем победителей раунда:

Официальные:

  1. thegoat

  2. xiojoy

  3. _duskTempest

  4. LargeRice

  5. nhphuc

Официальные + Неофициальные:

  1. tourist

  2. neal

  3. Dominater069

  4. abc864197532

  5. hitonanode

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

»
2 года назад, скрыть # |
 
Проголосовать: нравится +15 Проголосовать: не нравится

cool

»
2 года назад, скрыть # |
 
Проголосовать: нравится -16 Проголосовать: не нравится

my goal to reach +1700 after this round

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

__ combating unsporting behavior. To qualify as a trusted participant of the fourth division, you must: __ take part in at least five rated rounds (and solve at least one problem in each of them), __ do not have a point of 1900 or higher in the rating. __ Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1600 (or you are a newcomer/unrated), then the round will be rated for you.

why is it fourth division

»
2 года назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

Finally I can write this: my first unrated div3 :D

»
2 года назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

As a tester of this round, I will say that the tasks were interesting

»
2 года назад, скрыть # |
 
Проголосовать: нравится +14 Проголосовать: не нравится

Just curious: How do you guys propose a Div3 contest?

»
2 года назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

Hoping we all get positive delta :)

»
2 года назад, скрыть # |
 
Проголосовать: нравится +17 Проголосовать: не нравится

As a tester i confirm that problems are indeed cool and worth solving.

»
2 года назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

finally a div3 after a long time.

»
2 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +37 Проголосовать: не нравится

Can you tell me how to propose div3 contests? Vladosiya, Gornak40 ?

»
2 года назад, скрыть # |
 
Проголосовать: нравится +13 Проголосовать: не нравится
Vladosiya for deleting the lore in almost all of the problems...

Thank you.

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

f(n)=(n−1)⋅(f(n−2)+f(n−1))

can we solve this eqn using matrix expo???

if yes then plzz give me the matrix...

»
2 года назад, скрыть # |
 
Проголосовать: нравится +11 Проголосовать: не нравится

I like the monk's organization :D

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

when was the last time we saw a probabilty problem in a div 3 , somebody has to sneak one in there

also i know yall hate math so dont downvote thanks.

»
2 года назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

UPD1 After the end of the round, Shayan will broadcast the solutions, a recording will also be available, but we will also prepare a textual editorial

Unfortunately many will do it during the contest itself too.

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I want to go specialist, Good luck for me

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

i need 1434 rating

»
2 года назад, скрыть # |
 
Проголосовать: нравится -14 Проголосовать: не нравится

Shayan streams pretty much in recent month for problems' solution. I appreciate him a lot.

»
2 года назад, скрыть # |
 
Проголосовать: нравится +17 Проголосовать: не нравится

As a tester, I can guarantee that the round will be interesting!

»
2 года назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +9 Проголосовать: не нравится

I want to solve 3 questions in this contest :)

»
2 года назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

How to be tester? Is this random?

»
2 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +2 Проголосовать: не нравится

As a problemsetter, good luck, guys!

»
2 года назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

As a tester of this round, I can say that this round will probably lower your rating, but the tasks are worth solving <3

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

a general doubt, penalty gets applied after correct submisson or doen't depend on correct submission?

»
2 года назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

time to lock in

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I hope I'll be +1300 after this round! Good luck to everyone!

»
2 года назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Looking forward to getting my first color today!

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

will trusted participant be rated ??

or just be included in the official standing ?

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I hope to go forward and wish for this to be the best Div3. Odin is with us!!!

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

that went a bit better than last div2 (emphasis on a bit because i somehow crashed my ide 4 times which lost me about 4-6 minutes from E-G)

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

got stuck on F , ughhhhhhhhhhhhhhh.

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Overall very nice problems and good contest. My first time solving E and hopefully I get a good delta :)

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

C is the easiest but it was the hardest for me to write

»
2 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

ignore this was my worst performance soo far

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

How to solve F?

»
2 года назад, скрыть # |
 
Проголосовать: нравится -16 Проголосовать: не нравится

I literally cannot believe on how ChatGPT unable to solve stupid implementation problem like D.

»
2 года назад, скрыть # |
 
Проголосовать: нравится -8 Проголосовать: не нравится

Hi All, can anyone help me understand why I am getting memory limit exceeded on problem D? this is my submission, I followed a recursive approach to explore possible options of jumping and swimming, I am not using an extra data structure, thank you in advance for your help!

»
2 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +11 Проголосовать: не нравится

Was it only for me ,or it was really hard to decode the problems?

»
2 года назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

Another round dusted by Indian cheaters.

»
2 года назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

Me staring at E for 1hr +

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

My brain got blown away after reading E was like another level for me.DIV3's have become harder now

»
2 года назад, скрыть # |
 
Проголосовать: нравится +72 Проголосовать: не нравится

Sharing my video of winning* the contest: https://www.youtube.com/watch?v=9Vv2ZukG1CM&t=2476s

(*tourist doesn't count)

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Missed E, and actually missed the first time that I could clear Div3.

»
2 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Ahh, D was so straightforward but I spent like an hour debugging just to get AC in 3 minutes after reimplementing my idea.

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

What is the thing you have to notice to solve E?

The only way I would be able to solve (I didn't do this) would be to precompute all of n from 2 to 100 and then have a python program just return those precomputed solutions...

How do we solve for B given we check for values of A... Maybe I wasn't on the right track at all for optimal solution though...

»
2 года назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

Easier than recent div4 round!

»
2 года назад, скрыть # |
← Rev. 4  
Проголосовать: нравится +57 Проголосовать: не нравится

The problems were great, but the confusing statements ruined it for me, I really think more attention should be given to making the statement clear and understandable.

For example in problem D it was not clear that k was for the entire problem, when I read it I thought he could not swim a distance more than k in a row which led to me writing a completely different solution and wasted a lot of time on this.

I spent more time understanding the problems than solving them.

I am not saying the contest is bad, but I felt this should be addressed.

»
2 года назад, скрыть # |
 
Проголосовать: нравится +2 Проголосовать: не нравится

There are so many similar solutions for problem D which have been taken from youtube. They all have just changed variable names while initialising a variable name with m-1 and incrementing a variable if there is water and using some other variables and at last they are checking if variable value is not zero then print yes else no. Loads and Loads of solution in the same format, I had a brainrot seeing 10k+ submissions for D itself.

»
2 года назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

I might have gotten E in contest time itself but cloudflare had other plans.

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Am I really dumb as from submission its looking like D is easy but I was not able to solve it

»
2 года назад, скрыть # |
 
Проголосовать: нравится +7 Проголосовать: не нравится

bruh i asked chatgpt to solve D with dp and it actually worked

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

how brute-force round ,I love it.

»
2 года назад, скрыть # |
← Rev. 3  
Проголосовать: нравится +5 Проголосовать: не нравится

Please report this guy. He is sharing answer during the contest time. He is destroying the cp environment. here is the link : https://www.youtube.com/live/frrrP-SHXWA?si=nnX4Ghj0bqvDJEeN

»
2 года назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

Fantastic round! E was an amazing problem! Thanks a lot for the round Noobish_Monk ErnKor Kmes ArSarapkin and all testers!

»
2 года назад, скрыть # |
 
Проголосовать: нравится -16 Проголосовать: не нравится

there is a question in cf round 957 div3 just completed question no. E Novie Mistake if n==1 for a=3 and b=2 means string is empty value of n*a-b=1 but string is empty means it is zero it is not matching then why question consider string is empty as 1 and it didn't mention anywhere

»
2 года назад, скрыть # |
← Rev. 4  
Проголосовать: нравится +6 Проголосовать: не нравится

D has a very clean DP solution.

Let $$$dp[i]$$$ denote the minimum number of swims required to reach index $$$i$$$. The transitions are -

For $$$j = i + 1 - m$$$ to $$$i$$$

  • $$$dp[i + 1] = min(dp[j], dp[i + 1])$$$, if $$$s[j] =$$$ 'L'

$$$dp[i + 1] = min(dp[i] + 1, dp[i + 1)$$$, if $$$s[i] =$$$ 'W'

Finally, the answer is YES if $$$dp[n + 1] \le k$$$.

Submission Link: https://codeforces.me/contest/1992/submission/270032188

»
2 года назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

I submitted almost correct solution for E during the contest https://codeforces.me/contest/1992/submission/270016302, the only thing I didn't figured out was to convert to long long instead of size_t in the only place to avoid overflow. So disappointed, I will NEVER use any integer types except long long in competitive programming again!

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can someone point out why my F got hacked?

I did some math and figured that size of my sub and tmp sets can not be more than 30. 270037044

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

270040258 is this hackable?

»
2 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

// Can anybody tell me what's wrong in this implementation of D , I have chosen a variable pos to see if it is possible to pass the river and p tells if we found a "log" , c tells us if i found a "crocodile" and "w" tells us swimming through water i have as usual checked if if it is possible to get to a log then go there otherwise increase the position by m and check if there is one segment to swim to otherwise if only crocodiles were found btw i and i+m segment make pos false.





signed main() { ll t; cin >> t; while(t--) { ll n,m,k; cin >> n >> m >> k; string s; cin >> s; ll i = -1; bool pos = true; while(i<n){ bool p = false; bool c = false; bool w = false; for(ll j = m;j>=1;j--){ ll k = i+j; if(i+j<n){ if(s[k]=='L'){ // cout<<i+j<<endl; i = k; p=true; break; } if(s[k]=='C'){ c = true; } if(s[k]=='W'){ w = true; } } else{ i = n+1; break; } } if(p==false and w==true){ i+=m; if(i>=n){ break; } else if(s[i]=='C'){ pos = false; break; } else if(k>=1){ // cout<<i<<"water1"<<endl; i+=1; k = k-1; // cout<<i<<"water"<<endl; } else{ pos = false; break; } } else if(p==false and c==true){ pos =false; break; } } if(pos){ cout<<"YES"<<endl; } else{ cout<<"NO"<<endl; } } }
  • »
    »
    2 года назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится +5 Проголосовать: не нравится

    With this number of if-else-s and no proper indentation, it's hard to get the idea implemented right. The right thing to do is perhaps not to find a particular bug, but to take a step back and observe what can be changed globally. Consider developing these habits:

    • formatting the code to aid in implementation (any decent IDE has a keyboard shortcut for that)

    • thinking about solutions with as little if-else-if-if-else... forests as possible

»
2 года назад, скрыть # |
← Rev. 3  
Проголосовать: нравится 0 Проголосовать: не нравится

Never thought i will get 4 wrong submission on Div3-A :(

However solved B,C easily but spent too much time on D and didn't got much time to solve E Seems lots of people solved D so i might get -ve delta

»
2 года назад, скрыть # |
 
Проголосовать: нравится +1 Проголосовать: не нравится

Weird statements for D and F

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Does anyone know what the error-"Invalid use of deleting symbols" mean? Here's the link for reference 270073853

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I'm sure many people brute forced the answers of E, and just made if and else cases of it, there weren't many numbers and was fairly easy to make cases for each n.

»
2 года назад, скрыть # |
 
Проголосовать: нравится +12 Проголосовать: не нравится

really nice contest, I enjoyed the surplus of math-related questions, and it felt fitting for div 3. great job to all the organizers!

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can someone help me why my submission give a wrong answer in problem F 270081629

»
2 года назад, скрыть # |
 
Проголосовать: нравится +9 Проголосовать: не нравится

Мужики, это конкретный позор с задачей F. Как можно было не написать 1 уточняющее предложение. Или хотя бы 1 тест объяснить. Для чего вообще вам тестеры нужны? Если вы вот так относитесь к задачам.

  • »
    »
    2 года назад, скрыть # ^ |
    ← Rev. 3  
    Проголосовать: нравится 0 Проголосовать: не нравится

    Мужик, ну тестеры как-то поняли ж условие) Просто обычно в задачах такого типа (разбить массив на отрезки с определённым свойством) уже подразумевается, что переставлять нельзя, что каждый отрезок имеет такое-то свойство и подобное. Вот и получилось, что как-то когда читаешь, можно не заметить, что это не написано

    • »
      »
      »
      2 года назад, скрыть # ^ |
       
      Проголосовать: нравится +8 Проголосовать: не нравится

      Буду знать. Просто видимо как новичок я вообще этого не понял. Я думаю со мной многие согласятся, что после прочтения не понятно в чём вообще состоит проблема. Т.к. не объявлено, что должны быть ТОЛЬКО плохие подотрезки. Только в конце контеста это написали. Этих проблем вообще не должно быть, потому что пишут хотя бы 1 пример, а лучше пару. Чтобы вопросов не было. А так получается, что легкие задачи с примерами, а сложные(до которых Div 3 новички еле еле доползли(Я)) должны понимать, как будто они уже с опытом. Но за Ешку лайк.

»
2 года назад, скрыть # |
← Rev. 2  
Проголосовать: нравится 0 Проголосовать: не нравится

Enjoyed while solving the problems. But descriptions were just too bad. It took much time to understand each problems. Please make descriptions easy so that everybody can understand the questions easily

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Congratulations to neal for taking the first place XD !!!

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Why my solution for F was hacked? Just because the time constant?

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

a trend of not able to solve E and getting hacked on F continues

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Took me embarrassingly long and with many false attempts to solve E. Solved F and G before it.

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I have rating less than 1600, but this contest is displaying in unrated section in my profile?

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

When can the textual editorial be posted, since youtube isn't accesible in China :(

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

My rating didn't change even tho I solved 2 questions?

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I hacked four solutions of E using the testcase where t=100 and n from 1 to 100. Now as the system tests are visible the second testcase is same as my hack test. How is this possible ?

Hack test — https://codeforces.me/contest/1992/hacks/1055241/test

Submission Link — https://codeforces.me/contest/1992/submission/270051562

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I am unrated and a newbie right now but still this round is showing unrated for me..

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I had submitted 3 questions in the Codeforces Round 472 (rated, Div. 2, based on VK Cup 2018 Round 2) and it was accepted. But when I checked it just now it is not showing my submitted answers and my first question is highlighted red. Also is showing some system checking which is at 77%. Please tell me what is going on as I am new to Code Forces.

  • »
    »
    2 года назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    Don't worry, system testing is when all the submissions are checked again on larger amount of tests, the problems that you see "rejected" are actually just unchecked yet, you'll see the true result when system testing is finished.

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone explain what is this hack doing?

https://codeforc.es/contest/1992/hacks/1054913

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Before the change of statement, I struggled for a long time to understand problem F as I thought about making more "good segment". It's strange, I don't know why I can't get the real meaning. Why no explanation of the problems?

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

May I know why this contest is not rated though am a trusted participant.

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

how to see the test case where I Got hacked I cannot see it in hacks section, as well as there is no test case visible to me with wrong answer verdict

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone please help me correct this solution for problem D.

Got WA on 845th test of test case 2.

Code
  • »
    »
    2 года назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится +3 Проголосовать: не нравится

    hey buddy , the problem is the part where you define your state of dp , so what I could understand from the code was dp[i] would give me true/false stating is it possible to go to the end of the river from i.

    There are 2 things that are changing in your recursive function , that is i (index) and k (remaining swimm count) but nowhere in the dp state have you mentioned k there is just i.

    Look at this example lets say when in the first recursive call you get to an index x with remaining swim count as y and it is possible to cross the river with y amount of swimming so dp[x] will be true. but lets say in future you call the same index again with z remaining swim count (z < y) and it is not possible to swim through the river with z swim , still you will be returning "true" because dp[x] is set to true because of first function call.

    Conclusion :

    you need to change the definition of dp[i] , instead of saying dp[i] gives me true or false if it possible to reach end from index i , define dp[i] as minimum number of swimming count required to reach end of river from index i . If it is impossible to reach end from i store some large number which cant be your ans in any case. Keep overflow in mind !!

    AC soln: 270200685

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Need Help ,,,, I don't understand how did I get 4 Penalty and -50 on Rating, please can anyone help me for solving this issue, I don't understand I am new here, please anyone there, hello coders

  • »
    »
    2 года назад, скрыть # ^ |
     
    Проголосовать: нравится 0 Проголосовать: не нравится

    +00:04 in the ranking list does not means 4 penalty, it means you take 4 minutes to solve that question.Talking about the rating, you got negative delta bcoz you doesn't perform upto your rating level(before contest rating) in the contest.

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

I want to be a specialist, any tips for it,as my rating don't seem to change

»
2 года назад, скрыть # |
 
Проголосовать: нравится 0 Проголосовать: не нравится

Where's my rating?