Codeforces Round 929 (Div. 3)

9 months ago, # |

After rating rollback i became Expert so this is my first Unrated Div3 :)

→ Reply

9 months ago, # |

+129

Random meme:

→ Reply

StenSoSmol

9 months ago, # ^ |

tru

→ Reply

9 months ago, # ^ |

← Rev. 5 →

I think rainboy is also a genius

→ Reply

9 months ago, # ^ |

+13

definitely, rainboy is one of my favorites :)

→ Reply

9 months ago, # ^ |

← Rev. 3 →

→ Reply

9 months ago, # ^ |

No offence to rainboy but there are other coders which surely belong in the Crazy Category.I have seen 2 of them (other than rainboy of course). Dukkha AND kaiboy. Comment if you know some other crazy and genius coders.

→ Reply

hashman

9 months ago, # ^ |

kaiboy is rainboy’s younger brother. I don’t know about dukkha, it might be an alt.

→ Reply

Akshat369

9 months ago, # ^ |

dukkha is rainboy's elder brother.

→ Reply

9 months ago, # ^ |

← Rev. 2 →

Thanks for informing me, Akshat369 and hashman

→ Reply

TheInfamousTony

9 months ago, # ^ |

what is bro cooking

→ Reply

Mirali777

9 months ago, # ^ |

Why downvotes...

→ Reply

Palestinian_Dream

9 months ago, # ^ |

I'm going to be crazy at some point 😉

→ Reply

9 months ago, # ^ |

← Rev. 2 →

I am .....

→ Reply

9 months ago, # ^ |

Am I crazy?

→ Reply

9 months ago, # ^ |

← Rev. 4 →

uhh...

→ Reply

ewwwwa

9 months ago, # ^ |

xD, true

→ Reply

yellowbeard

9 months ago, # ^ |

5th type

→ Reply

Aditya_Metkar

9 months ago, # ^ |

I Hope To become a SIGMA — PUPIL this round ;)

→ Reply

Unalloyed

9 months ago, # ^ |

Good luck, future sigma

→ Reply

fapipotato

9 months ago, # ^ |

but sir i think real genius is sporfky master wch 1226 !!!

he now grandmister !! he ver y much inspirin for fapipotato!

thank u so much coddfrces!! thx u so much sparky moster!!

much love, fapi potat O

→ Reply

pranjaljha

9 months ago, # ^ |

looking at the number of submissions i made in the last contest. I might very well be on my path to becoming a true SIGMA.

→ Reply

Shen-SunCe

9 months ago, # |

maybe you can translate the saying into master turtle.

→ Reply

9 months ago, # |

-13

As a participant, CR7 is GOAT.

→ Reply

9 months ago, # ^ |

Messi == Ronaldo == GOAT and GOATS don't fight.

→ Reply

Top1Top1Top1Top1

9 months ago, # |

nice ạ

→ Reply

KyleLeungHS

9 months ago, # |

← Rev. 2 →

As a tester, I encourage every fellow programmer participating in the round to look at every problem to prevent skill issue. But anyways I hope everyone participating can have fun and hopefully learn something from this well crafted round~~

(The problemsetting team has genuinely dedicating a whole load of time to make sure this round runs smoothly with great problems!)

→ Reply

9 months ago, # |

NEW DIV 3 ROUND YEAHHH

→ Reply

wyli

9 months ago, # |

so many dbs students no kgv fame :( (dbs op)

→ Reply

tofael1104

9 months ago, # |

← Rev. 2 →

Master Oogway quote beautifully encapsulates the essence of personal growth and self-improvement. Focusing on our own progress rather than comparing ourselves to others is a valuable mindset to adopt. Each day presents an opportunity for us to strive for excellence and become the best version of ourselves. Thank you for sharing such a meaningful perspective!

→ Reply

dbsptl

9 months ago, # |

← Rev. 2 →

+10

As a tester, I wish you high rating and hope you achieve the rank you aspire to be :)

→ Reply

9 months ago, # ^ |

Are questions easy?

→ Reply

dbsptl

9 months ago, # ^ |

+10

you'll see

→ Reply

9 months ago, # ^ |

I know.

→ Reply

smit_384

9 months ago, # |

← Rev. 2 →

The secret ingredient is... !

Spoiler

→ Reply

defarias25

9 months ago, # ^ |

Actually, the secret ingredient is... !

Spoiler

Big respect to Master Oogway though.

→ Reply

Waiting_The_Summer

9 months ago, # |

It's time to make yourself and you better♥♥♥.

"Goodluck.", — Master Oogway, Kung Fu Panda.

→ Reply

9 months ago, # |

← Rev. 2 →

→ Reply

shivamp_07

9 months ago, # |

I hope I get blue :)

→ Reply

edgerunner

9 months ago, # |

the quote hits really hard...

→ Reply

9 months ago, # ^ |

Yes

→ Reply

Dark--------Shadow

9 months ago, # |

i wish i could solve A,B,C.

→ Reply

llc5pg

9 months ago, # |

-16

DBS forces

→ Reply

Unalloyed

9 months ago, # |

Finally unrated for me!

→ Reply

Mendeke

9 months ago, # |

GOOD LUCK !!!

→ Reply

Md-Merazul-Islam

9 months ago, # ^ |

Good Duck <0)

→ Reply

Parvej

9 months ago, # |

+15

Cumulative sum of their age is less than me or they looks very young?

→ Reply

snowysecret

9 months ago, # ^ |

+45

I think we should welcome our 150+ y.o. participant.

→ Reply

Its_Lightning

9 months ago, # ^ |

Kidforces

→ Reply

Avik_AB17

9 months ago, # ^ |

Talentforces!

→ Reply

Physical

9 months ago, # ^ |

Abilityforces!

→ Reply

Derfex

9 months ago, # |

Nice, new round, new training. BOTAAAAAAAT

→ Reply

Norp

9 months ago, # |

Finally, another round where I can try hit pupil!

Good Luck for everyone!

→ Reply

Physical

9 months ago, # |

Ohhhh,I see Atletico Madrid fan

→ Reply

Duelist1234

9 months ago, # |

I hope to solve AE

→ Reply

9 months ago, # |

+18

→ Reply

AvaraKedavra

9 months ago, # |

+45

Kids are writing problems for a grownup like me. I guess that is the benefit of receiving a good education right from your childhood. The first time I used a computer was when I entered college :(

→ Reply

Suplex

9 months ago, # |

I predict that there would be a problem involving some range queries or stuff like that probably C or D It would have a simpler solution but will be overkilled by many using segment trees or something similar.

→ Reply

AvaraKedavra

9 months ago, # ^ |

This didn't age well.

→ Reply

chenRenning

9 months ago, # |

I hope to successfully enter the youth league tonight ：）

→ Reply

Mukul9571

9 months ago, # |

Hoping for a fun contest.

→ Reply

Sea.

9 months ago, # |

give me a chance that making my name become yellow!

→ Reply

Its_Lightning

9 months ago, # |

+21

Thanks for continuing streak of putting authors pictures on the contest blog

→ Reply

9 months ago, # ^ |

It's a good thing they have decided to keep the streak going.

→ Reply

Bill_Gatess

9 months ago, # |

Good luck to everyone!

→ Reply

9 months ago, # ^ |

Bro, please give job in microsoft

→ Reply

Stuck_On_Gray

9 months ago, # |

Hope fast ABCD

→ Reply

9 months ago, # |

Mathforces

→ Reply

9 months ago, # ^ |

NumberTheoryForces

→ Reply

9 months ago, # ^ |

EFG are ok

→ Reply

9 months ago, # ^ |

← Rev. 2 →

Yes but BCD is not ok

→ Reply

9 months ago, # ^ |

Postpone them (like I did with B), solve the ones you like first to warm up.

→ Reply

Mustafa_Elghisha

9 months ago, # |

+10

LOL, umnik_team uploaded the solutions before the end of the div

→ Reply

9 months ago, # ^ |

← Rev. 2 →

+20

Why did you write this here!? Now there will be a lot of cheaters!

→ Reply

karna001

9 months ago, # |

um_nik is 1 hour ahead of us(iykyk)

→ Reply

amansingh81757

9 months ago, # |

+28

WTF is this? why were the solutions posted before the round ends by Um_nik??? This is not fair. I hope they dont make this round unrated because of this.

→ Reply

9 months ago, # ^ |

The problem-setting team has acknowledged the issue, and I have already tried my best to contact Um_nik on the issue a while ago to try to remove the video. I also hope the round doesn't get unrated :(

→ Reply

650iq

9 months ago, # ^ |

What is the use of removing now? The damage is already done

→ Reply

AKM17

9 months ago, # ^ |

the video was there for more than 30 mins too, why didn't here remove it earlier

→ Reply

9 months ago, # ^ |

We contacted him before the round ended of course.

→ Reply

9 months ago, # ^ |

Most of the participants wouldn't have even seen the video. Hope contest doesn't get unrated (even though I couldn't implement E), as I truly enjoyed the contest.

→ Reply

AKM17

9 months ago, # ^ |

← Rev. 3 →

deleted

→ Reply

yashkumar22072002

9 months ago, # |

← Rev. 2 →

→ Reply

rolandpetrean

9 months ago, # |

+73

Thanks for the fast editorial!

→ Reply

9 months ago, # ^ |

Very fast =)

→ Reply

Igor_Parfenov

9 months ago, # ^ |

"If I don't have a rated contest, then no one has a rated contest."

→ Reply

second_saturday

9 months ago, # |

I hate myself for not reading problem E correctly I was able to do it in 10 min once, I read the statement properly...

anybody did the same mistake?

→ Reply

_simpleThing_

9 months ago, # |

is problem E binary search?

→ Reply

9 months ago, # ^ |

I used ternary search

→ Reply

phukaoz

9 months ago, # ^ |

yes

→ Reply

9 months ago, # ^ |

yup. DP to calculate sum i -> j. then binary search

→ Reply

slabi

9 months ago, # ^ |

search over what

→ Reply

9 months ago, # ^ |

to find out K such that Math.abs(aL + a(L + 1) + ... + a(K) — U — 0.5) is Max

→ Reply

slabi

9 months ago, # ^ |

why does that function work

→ Reply

9 months ago, # ^ |

← Rev. 3 →

n = 1 => U

n = 2 => U + U — 1

n = 3 => U + U — 1 + U — 2

...

n = m => U*m-(1 + 2 + .. + m-1) = U*m-(m-1)*m/2 = -1/2*m^2 + (1/2 + U) * m.

It max when m = 1/2 + U

=> find K such that aL + a(L + 1) + ... + a(K) closest to m or 1/2 + U

→ Reply

slabi

9 months ago, # ^ |

yeah sorry you're right, I misread the problem statement. shit. this is so much easier than what I was tryna do

→ Reply

WhatAGod

9 months ago, # ^ |

I was able to do it using binary search

→ Reply

second_saturday

9 months ago, # ^ |

yes, binary search on convex function.

you can see my code for reference:

problem E solution

auto solve = [&]()->void
{

    int N ;
    cin>>N ;
    vector<int>A(N);
    for( auto &x : A )cin>>x ;

    int Q ;
    cin>>Q ;

    vector<int>P(N+1,0LL);
    for( int i = 0 ; i < N ; i++ )
      P[i+1] = A[i] + P[i];

    auto range = [&]( int a , int b )-> int 
    {
      return P[b+1] - P[a];
    };



    auto task = [&]( int L , int U )-> int 
    {

      int l = L ;
      int h = N-1 ;

      int mx = INT_MIN ;
      int res = L-1;


      auto f = [&]( int m)-> int 
      {
       int sum = range( L-1 , m );
       return sum*U - ((sum*(sum-1))/2);
      };

      while( l < h )
      {
       int m = (l+h)>>1 ;

       int y2 = f(m);
       int y1 = f(m-1);

       if( y1 == y2 )
           l = h = m ;


       if( y2 > y1 )
           l = m+1;
       else
           h = m-1;
      }

      for( int m = l+1 ; m >= l-1 ; m-- )
      {
       if(m >= L-1 && m < N )
       {
           if( f(m) >= mx )
           {
              mx = f(m);
              res = m ;
           }
       }
      }

      return res+1;
    };

    for( int i = 0 ; i < Q ; i++ )
    {
      int l , u ;
      cin>>l>>u ;

      cout<<task( l , u )<<" ";
    }

    cout<<endl;
};

→ Reply

powdkqni

9 months ago, # ^ |

its just a linearly increasing function.. the score is the convex function... only the index is needed so you can just use binary search on prefix sums

→ Reply

second_saturday

9 months ago, # ^ |

yes i saw after the contest, did not realise it in heat of the contest, as I misread the problem wasted 1 hour on completly different problem.

→ Reply

tickbird

9 months ago, # |

problem e was truly painful to implement

→ Reply

deadnecro18

9 months ago, # |

can someone tell me where it is giving wrong answer 248621389

→ Reply

4rn4vg

9 months ago, # ^ |

Actual answer for 8 4 64 is 6 but your code produces 7

→ Reply

deadnecro18

9 months ago, # ^ |

thanks

→ Reply

9 months ago, # |

← Rev. 2 →

I used logic similar to finding peak element in array. But got WA. Could anyone please point out the mistake in my code?

Submission : https://codeforces.net/contest/1933/submission/248632005

Edit : Found the mistake. I was subtracting a[low-1] instead of a[l-1] :(

→ Reply

0021anushka_

9 months ago, # ^ |

Thanks for the hint and your code,I tried implementing using peak element concept, but got stuck in the code, actually I did not initialize my ans to l and also did not make neighbour= -INF if they did not exist and your code came to my rescue.

→ Reply

marc2825

9 months ago, # |

+34

It was a good bluff to require us to answer modulo 998244353 in problem G. (I intuitively knew that the answer could not be large given the harsh conditions, but because of this requirement, I was not sure of my consideration that there are at most 8 patterns even after writing an experimental code with a brute force.)

→ Reply

edgerunner

9 months ago, # |

great contest! i really enjoyed A,B,C,D,E, but couldn't implement bs in E, I need to practice more bs problems( Anyway great contest!

→ Reply

9 months ago, # |

anyone can explain the test case in problem G ?

→ Reply

hungcubuso5vn

9 months ago, # |

← Rev. 2 →

Um_nik has uploaded a video about solving this contest before the contest ended: https://www.youtube.com/watch?v=Asqk4kXi8os&ab_channel=umnik_team . Will this contest unrated?

→ Reply

PaleBlueDot

9 months ago, # ^ |

There is no point in making the contest unrated. Cheating happens and solutions get leaked on Telegram and YouTube in every contest.

→ Reply

hungcubuso5vn

9 months ago, # ^ |

But this is a public solution from a LGM while the contest is running. Anyone can AC all 7 problem with this video.

→ Reply

yellowbeard

9 months ago, # ^ |

-6

I dont think link was public during the contest.

→ Reply

rishabh19jain20

9 months ago, # ^ |

I think it should be unrated because there used to be cheating to some level but this is not done, i was able to solve 4 in div 3 which is good enough, still suffered 44 rating decrease because of soo many cheaters. Ratings should be rollbacked for this contest. This was too much!

→ Reply

Aditya_Metkar

9 months ago, # |

← Rev. 2 →

Brooooo my stupid "print" statement costed me PROBLEM-C ripppppp

print
without

This could have been the greatest clutch of my life but NOPE. I want to jump off a cliff :((

→ Reply

9 months ago, # |

← Rev. 3 →

+26

Hints for all the problems before the editorial comes out.

A: Collect all the negatives in one subarray.

B: Maximum answer can be 2. Think about the cases when 1 and 2 will be answer.

C: What if we fix values of (x, y)? Also, the value of k will not be always distinct.

D: What if you keep minimum element at first? What if there are multiple minimums?

E: The sum is increasing upto a point and then it decreases. It starts decreasing after the (u + 1)-th section.

F: Firstly, coming at the same position again is not optimal. Secondly, we don't need the UP move until the last column.

G: Constructive problem, try to come up with a pattern using second test of sample. Also, the answer can be max upto 8, ignore the modulo.

Thanks to the authors for some very interesting problems.

Spoiler

→ Reply

9 months ago, # ^ |

+44

Happy to hear that you liked F a lot (I wrote it) Thank you very much you have made my day.

Hopefully, I don't get downvoted by saying this... ik this task kinda was a nightmare at first sight for some of you, but hope it was an interesting and insightful task. Hope it wasn't that hard to understand as well, I already tried to draw better graphics for the explanation.

Anyways, we will try to get the editorials out as fast as possible :)

→ Reply

9 months ago, # ^ |

Keep up good work making problems interesting to think about and easy but not boring to implement.

→ Reply

9 months ago, # ^ |

No no, I think it was fine for everyone. And, the graphics were actually cool.

→ Reply

hxano

9 months ago, # ^ |

I really liked F :> Might even take inspiration from it to create some educational DP problems myself

→ Reply

MANUAL_Boy

9 months ago, # ^ |

hi, about problem F, do we really this observation to come up with a solution,

"Secondly, we don't need the UP move until the last column."

I think we can use simple bfs to reach the end

→ Reply

9 months ago, # ^ |

← Rev. 2 →

The observation is correct, but there are also other ways to realize such an observation which will be mentioned in the editorials. Of course there might be alternate solutions that also work, but having this observation does simplify the question a lot and can be done through dp or bfs.

→ Reply

MANUAL_Boy

9 months ago, # ^ |

yeah, I do know that, just wanted to know if someone solved this by just first obs,

from each point, we move to three possible cells(up, down, right), using bfs we find the ans for last cell

→ Reply

rk0822

9 months ago, # ^ |

In problem C, Why I am getting TLE in this code. It is O(max(13,sqrt(100))+ 3*10^3) .

My submission

→ Reply

9 months ago, # ^ |

You forgot to add the complexity of creating a 10^6 sized vector in each testcase.

→ Reply

rk0822

9 months ago, # ^ |

Thank you. I realised that I don't need to create those arrays .

→ Reply

osource

9 months ago, # ^ |

In E, how can you say that the sum is a convex function?

→ Reply

nectarl

9 months ago, # ^ |

you may have misread the problem description just like i did. among tracks the decline by one continues.

→ Reply

EulerTour

9 months ago, # ^ |

Could you please explain why we dont have to use the UP move until the last column, it will be very helpful

→ Reply

9 months ago, # ^ |

When you're doing the UP move, your position relative to stones isn't changing, so basically the whole setup is same in a rotational manner. The only thing that changes is relative position of ending cell, which you can also change when you're in the last column.

→ Reply

EulerTour

9 months ago, # ^ |

Oh,now I feel dumb, thankyou so much

→ Reply

0021anushka_

9 months ago, # ^ |

someone explain what does it mean by seeing the grid in the pov of grid? Everyone says see the grid as static? Someone kindly explain

→ Reply

yuanzihan

9 months ago, # |

Is this one about turtles?

Every question is about a turtle.

→ Reply

9 months ago, # ^ |

Originally we had a storyline, but it was decided to be removed in the end to improve the task's clarity. The idea came from a few sources. The first one is because the old workplace or "home" of my school's robotics team (I was the captain last year) was next to a turtle pond, and so I have a strong love for turtles :) FYI, each of the teachers having their seats next to the pond were also called turtles with different nicknames for each of them. The second reason was that we liked Master Oogway in the movie Kung Fu Panda, so we thought it would be a good choice to use it as a theme, both silly and inspirational.

→ Reply

Md_Minhaj

9 months ago, # |

Don't know! Should I be motivated or demotivated?! after seeing the problem setters...:/)

→ Reply

sahkumar.bishwash

9 months ago, # |

I could not even solve B. Every one here is discussing about problem E

→ Reply

9 months ago, # |

Problems: Turtle

Editoral: Rabbit

→ Reply

sh__r

9 months ago, # |

W contest , W younglings who made these questions ,Hope its not gone to waste cause of the stream upload

→ Reply

m_ithunvoe

9 months ago, # |

Can anyone give any counterexample where this submission 248545787 doesn't work for C?

→ Reply

mkshh

9 months ago, # |

fastest editorial ever seen

→ Reply

9 months ago, # |

I performed well in this contest but the contest is unrated for me because I became exactly 1600 after the rating roll back.

If I was 1599 I got +70 at least :)

→ Reply

NoticeMeSenpai

9 months ago, # ^ |

suffering from success

→ Reply

rishabh19jain20

9 months ago, # ^ |

is this contest getting unrated for some people ?

→ Reply

9 months ago, # ^ |

No. but the Div3 contests are always unrated for above Expert.

→ Reply

Spoderman.

9 months ago, # |

https://codeforces.net/contest/1933/submission/248622479 can anyone tell me what is wrong with this code for problem E

→ Reply

Rushdi

9 months ago, # |

← Rev. 2 →

→ Reply

9 months ago, # ^ |

If this is true I think CF can spot cheaters and skip them. so no worry :)

→ Reply

9 months ago, # ^ |

← Rev. 2 →

i mean people always post the solutions on youtube while the contest is running and have alot of views as well. i don't understand why when umnik do it it will be unrated , F and G don't have a lot of ACs anyway.

→ Reply

md_nihal

9 months ago, # ^ |

← Rev. 5 →

[deleted] it's not intentional ,it's a mistake and he apologized

Edit: it was a great contest ,hope to see more such contest from authors

→ Reply

9 months ago, # ^ |

← Rev. 2 →

nvm

→ Reply

new_to_CF

9 months ago, # ^ |

Few stupid guys!=whole india Stop using "Indians" "Russians" "Chinese" Do you compare umnik with this guys ? Definitely not

→ Reply

9 months ago, # ^ |

ok buddy I'll edit the comment and remove indians since this annoyed a lot of people.

→ Reply

md_nihal

9 months ago, # ^ |

← Rev. 4 →

No hate bro ,what you said is correct there is a mass cheating in every contest and we can't stop them

I know that umnik is not one of them

but we can't judge a country by some brainless individuals

→ Reply

sevlll777

9 months ago, # |

← Rev. 3 →

+13

really liked both F and G, they are great! though $$$n, m \geq 5$$$ and strong sample little bit spoiled main idea of problem G, IMO.

→ Reply

sstrong

9 months ago, # ^ |

+11

I guess n = 3 and large m is way harder than the current problem, thus they made such constraints.

→ Reply

sevlll777

9 months ago, # ^ |

hmmm, yeah, that's fair

→ Reply

aryanc403

9 months ago, # ^ |

-21

Btw this is how we can solve for small n and large m.

Spoiler

→ Reply

Kapibara

9 months ago, # |

← Rev. 3 →

Please don't make this one unrated:(

→ Reply

kojak_

9 months ago, # |

In C, l could have been much larger.

→ Reply

9 months ago, # |

← Rev. 4 →

+11

UPD2: Since the editorial is not out yet...

A solution

B solution

C solution

Original Post: Solved ABCDEF and I had no non-trivial idea for G. I enjoyed this problemset, and DEF are good problems in my opinion.

D solution

E solution

F solution

UPD: G upsolved. The ST was slow and I submitted 1 hour after finishing coding.

G hint 1

G hint 2

→ Reply

SXZZ5

9 months ago, # ^ |

Please tell me what is wrong with my implementation of E. I can't think of anyother way to implement it and also cannot make this implementation work. 248638966

→ Reply

9 months ago, # ^ |

why are you going up to u+1?

→ Reply

SXZZ5

9 months ago, # ^ |

I may be wrong about it. Is that the issue ? I tried submitting with critical = u which also doesn't work.

→ Reply

9 months ago, # ^ |

if two index that are adjacent make same answer then you should take the lowest one. I think in the first test case your answer is giving wa. 3 1 4 1 5 9 for l = 1 and u = 8 your code gives r = 4. But r = 3 also gives the maximum sum. You should go upto u and check the next index also which is res+1. if it makes greater sum then output res+1 otherwise output res.

→ Reply

9 months ago, # ^ |

see my solution.

→ Reply

SXZZ5

9 months ago, # ^ |

← Rev. 3 →

Now I got it, thanks a lot. I thought of checking neighbouring elements to the r that I found, also but it felt very hacky to me and did not try it even once. :(

→ Reply

9 months ago, # ^ |

Good hint for F. I was able to code it up after looking at your hint

→ Reply

rrohann__

9 months ago, # ^ |

begin with other elements, and you will get 0 at the first x. can you explain this with proof? Thanks in advance

→ Reply

9 months ago, # ^ |

Proof

→ Reply

rock_nroll

9 months ago, # ^ |

← Rev. 2 →

For Problem-F

Can you please help me :

lets say that we reached the cell a[i][m-1] ...

Why currAnswer = dist[i][m-1] + abs ( n-1 -i ) is not correct ?? ( where dist[][] can be found by simple BFS ) and thus the final answer will be Minimum over all i...

How to correct it ?

→ Reply

https://imgur.com/dKUPRJ3

9 months ago, # ^ |

← Rev. 2 →

What if you walk down and there are rocks in your way? The "wait" is to go up all the way(i.e. stay in place from the grid's viewpoint)

→ Reply

Folka

9 months ago, # |

+13

The best insane problem D ever !!

→ Reply

aditya0610

9 months ago, # |

← Rev. 2 →

Great Contest

→ Reply

edgerunner

9 months ago, # |

Please don't make contest unrated. Just check for plagiarism for problems E,F,G that were send last 30 minutes with the umnik's code from youtube.

→ Reply

-M1

9 months ago, # |

in prob C https://codeforces.net/contest/1933/submission/248626484 I am getting wrong answer from codeforces judge but if I am testing the wrong test case on my local machine it's giving me the right answer? WA on test case 2 40th test 8 4 780

→ Reply

ilovenandini

9 months ago, # |

+10

why Um_nik why

→ Reply

elnazar

9 months ago, # |

The contest was very interesting, thanks to the organizers of the contest. I just found this stream where Um_nik broadcast the last ~1 hour of the contest. I felt very sad because some of the participants cheated and one of the great codeforcers has ruined contest. In fact, it's not about cheating, but about respect for the creators of the contest.

Dear organizers you did really greate job!

→ Reply

ZAQUVA-Speculation

9 months ago, # |

+69

heres why i solved this G 2x faster than rainboy.

→ Reply

fapipotato

9 months ago, # |

← Rev. 2 →

-20

sirs

thank u the much for this roudn !!

but fapipitito notice G is pretty specil?? fapipotato confused !!

fapipotato find solution near end but cannot code fast be cause hand weakk :((((

i liek all problom and this very high qualiti round!!

mcuh love and look forward to more future later round from u guys!!

fapi potato

→ Reply

arceus31

9 months ago, # |

← Rev. 3 →

→ Reply

Synaptic_Savant

9 months ago, # |

Really Great Problemset!

→ Reply

XCoder_420

9 months ago, # |

← Rev. 2 →

I did a BFS implementation in Problem F. Sadly, I got a TLE on Test 12. Can someone point out how to avoid it from my code?

Code

#include<bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include<ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace chrono;
// using namespace __gnu_pbds;

#define int long long
#define ld long double
#define endl "\n"
#define pi  3.141592653589
#define INF 1e18
#define vi  vector<int>
#define vb vector<bool>
#define vc vector<char>
#define vvi vector<vector<int>>
#define vvc vector<vector<char>>
#define vvb vector<vector<bool>>
#define vpi vector<pair<int,int>>
#define mi map<int,int>
#define mpi map<pair<int,int>,int>
#define pr  pair<int,int>
#define mp  make_pair
#define triplet pair<int,pair<int,int>>
#define ff first
#define ss second
#define pb push_back
#define MAX INT_MAX
#define MIN INT_MIN
#define fr(i,n) for(int i=0; i<n; i++)
#define rep(i,a,b) for(int i = a; i < b; i++)
#define all(x) (x).begin(), (x).end()
#define read(x) int x; cin>>x
#define pD(x,y) cout<<fixed<<setprecision(y)<<x
#define google(tno) cout<<"Case #"<<tno<<": "
#define pqb priority_queue<int>
#define pqs priority_queue<int,vi,greater<int> >
#define setbits(x) __builtin_popcountll(x)
#define zerobits(x) __builtin_ctzll(x)
#define mod 998244353
#define LMAX 9223372036854775807
#define upperToLower(x) char(x | ' ')
#define lowerToUpper(x) char(x & '_')
const int MOD=1e9+7;
const int GN=1e5+10;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;

#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x <<" "; _print(x); cerr << endl;
#else
#define debug(x)
#endif

void _print(int t) {cerr << t;}
void _print(string t) {cerr << t;}
void _print(char t) {cerr << t;}
void _print(ld t) {cerr << t;}
void _print(double t) {cerr << t;}

template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cerr << "{"; _print(p.ff); cerr << ","; _print(p.ss); cerr << "}";}
template <class T> void _print(vector <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(set <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T> void _print(multiset <T> v) {cerr << "[ "; for (T i : v) {_print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void _print(map <T, V> v) {cerr << "[ "; for (auto i : v) {_print(i); cerr << " ";} cerr << "]";}

vi fact(GN,1);
vb sieve(GN,1);
vi dsieve(GN,0);

/*---------------------------------------------------------------------------------------------------------------------------*/

bool isPrime(int n){if(n==1)return 0;for(int i=2;i*i<=n;i++){if(n%i==0)return false;}return true;}
void primeSieve(){sieve[0] = sieve[1] = false;for (int i = 2; i*i<GN; i++) {if (sieve[i]) {for (int j = i*i; j<GN; j += i)sieve[j] = false;}}}
void divSieve(){for(int i=1;i<GN;i++){for(int j=i;j<GN;j=j+i){++dsieve[j];}}}
void factSieve(){for(int i=1;i<GN;i++)fact[i]=(fact[i-1]%MOD*1LL*i%MOD)%MOD;}
mi primeFactorise(int n){mi mpp;for(int i=2;i*i<=n;i++){if(n%i==0){int cnt=0;while(n%i==0){++cnt;n=n/i;}mpp[i]=cnt;}}if(n>1)mpp[n]=1;return mpp;}
int gcd(int a,int b){if(b==0)return a;return gcd(b,a%b);}
int binexp(int x,int n){int a=x;int prod=1;while(n){if(n%2==1)prod=prod*a;a=a*a;n=n/2;}return prod;}
int modexp(int a, int b, int m) {a %= m;int res = 1LL;while (b > 0) {if (b & 1)res = (res%m *1LL* a%m) % m;a = (a%m *1LL* a%m) % m;b >>= 1;}return res%m;}
int modadd(int a,int b,int m){return (a%m+b%m)%m;}
int modsub(int a,int b,int m){return (a%m-b%m+m)%m;}
int modmul(int a,int b,int m){return (a%m*1LL*b%m)%m;}
int modinv(int a,int m){return modexp(a,m-2,m);}
int moddiv(int a,int b,int m){return (a%m*1LL*modinv(b,m)%m)%m;}
int C(int n,int r){if(n<r || r<0)return 0;if(r==1)return n;int nmr=fact[n]%MOD;int dmr=(fact[r]%MOD*1LL*fact[n-r]%MOD)%MOD;return (nmr%MOD *1LL* modinv(dmr,MOD)%MOD)%MOD;}

/*--------------------------------------------------------------------------------------------------------------------------*/


void solve()
{
    int n,m;
    cin>>n>>m;

    vvi arr(n,vi(m,0));
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin>>arr[i][j];
        }
    }

    queue<pr> q,prev;
    q.push({0,0});

    int curr=0;
    int ans=-1;
    set<vector<pr>> lmao;
    while(q.size()){
        int sz=q.size();

        vpi v;
        set<pr> st;
        while(sz--){
            int x=q.front().ff;
            int y=q.front().ss;
            q.pop();

            v.pb({x,y});
            debug(make_pair(x,y))

            if(x==n-1 && y==m-1){
                cout<<curr<<endl;
                return;
            }

            // Upward
            if(!st.count({(x-1+n)%n,y})){
                q.push({(x-1+n)%n,y});
                st.insert({(x-1+n)%n,y});
            }

            // Downward
            if(!st.count({(x+1)%n,y}) && arr[(x+curr+1)%n][y]==0 && arr[(x+curr+2)%n][y]==0){
                q.push({(x+1)%n,y});
                st.insert({(x+1)%n,y});
            }

            // Right
            if(y<m-1 && !st.count({x,y+1}) && arr[(x+curr+1)%n][y+1]==0){
                q.push({x,y+1});
                st.insert({x,y+1});
            }

        }
        sort(all(v));
        if(lmao.count(v))break;
        lmao.insert(v);
        curr++;
    }
    cout<<-1<<endl;
}
int32_t main()
{
#ifndef ONLINE_JUDGE
//  freopen("input.txt","r",stdin);
//  freopen("output.txt","w",stdout);
    freopen("error.txt","w",stderr);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    auto start1 = high_resolution_clock::now();
    int T=1;
    cin>>T;
    while(T--)
    {
        solve();
    }
    auto stop1 = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(stop1 - start1);
    cerr << "Time : " << duration . count() / 1000 << endl;

return 0;
}

→ Reply

9 months ago, # ^ |

I did same. i did not observe that robot will move up only in last column :(.

→ Reply

9 months ago, # ^ |

so move up only in last column will reduce your time complexity from O(n*n*m) to O(n^m)

→ Reply

XCoder_420

9 months ago, # ^ |

Ohhh man. This ignorant habit of mine just sucks af! :") Thanks btw.

→ Reply

notsamir4ik

9 months ago, # |

Um_nik you are very bad

→ Reply

idkao

9 months ago, # ^ |

Everyone makes mistake

→ Reply

9 months ago, # ^ |

← Rev. 2 →

+20

I guess Master Oogway's words work again, "There is always something more to learn. Even for a (Legendary Grand) Master" lol.

And despite such issues may be problematic, I think we shouldn't put all the blame onto Um_nik as him doing his videos were for a good cause in teaching programming, just that he may have accidentally posted it early. Additionally, he has already apologised as well and I agree everyone makes mistakes, me included. Hopefully, such issues will be prevented in the future. :)

→ Reply

rahulkottak

9 months ago, # ^ |

but one thing i would say, umnik got really good taste in music xD!

→ Reply

Sreedhar3210

9 months ago, # |

Problem F is Awesome.

A bit different from usual problems.

→ Reply

fake_id_7

9 months ago, # |

was stuck at e, but then saw huge num of ac in E, around 4500 solve, now really upset after seeing the comments.

→ Reply

9 months ago, # ^ |

e is still not hard despite the cheating . you just have to find the first sum that's bigger than u, using binary search and find what's bigger this value or the one behind it

→ Reply

fake_id_7

9 months ago, # ^ |

True. E was easy, but as i become super saiyan level dumb durning contest, i forgot to check the values behind

→ Reply

9 months ago, # ^ |

it happens don't worry . keep grinding

→ Reply

9 months ago, # |

← Rev. 2 →

Problem F: BFS with one tricky observation. In this problem, the robot will move upward only when it's in the last column. Due to this constraint, the straightforward Depth-First Search (DFS) approach might lead to Time Limit Exceeded (TLE). This optimization should help improve the performance and prevent TLE.

→ Reply

Aviral_Gupta

9 months ago, # ^ |

I tried DFS, but getting WA 248632066. Any possible reason you could tell?

→ Reply

9 months ago, # ^ |

I haven't viewed your code but I don't think DFS will work, because BFS guarantees the lowest depth when each node is first visited but DFS does not

→ Reply

9 months ago, # ^ |

You don't need to ever revisit any cell, so it doesn't matter BFS or DFS. AC with DFS

→ Reply

9 months ago, # ^ |

You have to revisit cells if you are doing DFS and what you have linked is BFS

→ Reply

9 months ago, # ^ |

Whether it is a B of D FS is determined by the order of traversal, and not the function name or use of recursion.

→ Reply

9 months ago, # ^ |

Okay, the order of traversal in your linked solution is bfs order and if it was dfs order , you would need to revisit cells
does this satisfy your highness?

→ Reply

9 months ago, # ^ |

No, because it's untrue

→ Reply

9 months ago, # ^ |

my bad. didn't realise your 'q' was not a queue but a vector

→ Reply

krishnagopalagarwal7

9 months ago, # |

Can anyone tell why my code for E is giving TLE on 8th TC after applying Binary Search. 248643885

→ Reply

9 months ago, # ^ |

you are passing vector by reference in binary search. use vector & pre

→ Reply

krishnagopalagarwal7

9 months ago, # ^ |

Accepted, Thanks.

→ Reply

9 months ago, # |

+13

Can anyone try and hack my submission for F? I just did a O(n^3) BFS and used bitset to store visited. It passed somewhat comfortably but I'm wondering if there's a case where it blows up. https://codeforces.net/contest/1933/submission/248595937

→ Reply

9 months ago, # ^ |

← Rev. 2 →

+11

are u checking upward in all columns ??

→ Reply

9 months ago, # ^ |

+13

Yes

→ Reply

9 months ago, # ^ |

i also did BFS. My Submission. But got TLE. How??

→ Reply

VitalyKo

9 months ago, # ^ |

← Rev. 2 →

+13

Because you are using a set for used values

So your solution becomes something close to $$$O(n^3log(n^3))$$$

→ Reply

dartvolley

9 months ago, # ^ |

+23

Hacked.

I generated a $$$1000 \times 1000$$$ grid with all $$$0$$$'s to greedily maximize the number of neighbors of each cell.

→ Reply

VitalyKo

9 months ago, # ^ |

+13

Would it also work for my solution? It's also n^3 bfs

→ Reply

9 months ago, # ^ |

Thank you

→ Reply

9 months ago, # ^ |

← Rev. 3 →

I just added a condition where I move upward only in the last column and the runtime improved significantly, I don't think it can be hacked now. I think this implementation is very interesting because you are essentially doing the n^3 bfs with one little optimization for the transitions and the O(n^3) memory being reduced by a factor of 32 with bitset making it enought to pass the limits. https://codeforces.net/contest/1933/submission/248663273

→ Reply

BigBadBully

9 months ago, # ^ |

-8

bitsets are so dumb bro if u were really that good u would've figured out something easier noobie

→ Reply

9 months ago, # ^ |

+11

shut up bro

→ Reply

BigBadBully

9 months ago, # ^ |

-8

hey friend,

just wanted to drop a quick note to say sorry for what went down the other day. i know i messed up and i feel really bad about it. didn't mean to hurt your feelings or make things awkward between us. i hope we can talk it out and move past this. let's grab a coffee or something soon and chat about it. again, really sorry, mate.

take care, [Your Name]

→ Reply

Duelist1234

9 months ago, # ^ |

Nah man , he is onto something

→ Reply

dartvolley

9 months ago, # ^ |

← Rev. 4 →

+19

I think with your new optimization the time complexity actually becomes $$$O(N^2)$$$, and your space complexity would be $$$O\left(\frac{N^3}{32}\right)$$$ as you have stated.

Moreover, I noticed that with your new optimization you don't even need the 3rd dimension for the visit array, since I think you can arrive at cell $$$(i, j)$$$ only if the time $$$t \equiv i + j \quad (\text{mod } N)$$$. So, you can optimize the space complexity further to $$$O\left(\frac{N^2}{32}\right)$$$. (see https://codeforces.net/contest/1933/submission/248668841)

→ Reply

9 months ago, # ^ |

The time complexity is still technically O(n^3/32) as I need to initialize the bitsets, however your idea fixes that issue. The 100ms saved is most likely just due to the fact that there wasn't a need for so much data to be initalized.

→ Reply

TarunAga

9 months ago, # |

← Rev. 2 →

It was indeed a good round, I just hope it doesn't get unrated.

→ Reply

_parasite

9 months ago, # |

I almost gave up doing competitive programming. After 19 months almost I thought, let's start again. I was reading the explanation of test cases of problem B. And I Couldn't even figure out how that explanation matches the output. Suddenly I see a message popping up, saying there was an error in the explanation of Problem B. How could the problem setters or the testers miss such error I don't know. I was totally frustrated and couldn't even focus anymore sadly. Such a frustrating experience -.-

→ Reply

Jratos

9 months ago, # ^ |

You should build up your mentality for competitives

→ Reply

coolboy19521

9 months ago, # |

I hope the round doesn't get unrated.

→ Reply

9 months ago, # |

really thank you It was a good math contest Just remember from now on, this is Codeforce not MathForces

→ Reply

9 months ago, # |

Was this really a Codeforce contest, 4 math and number theory questions in a row

→ Reply

jkulanko

9 months ago, # ^ |

Most CP problems require math on some level. Maybe try learning it?

→ Reply

9 months ago, # ^ |

YES Most CP problems require math on some level. but all of them doesn't have math tag

→ Reply

9 months ago, # ^ |

oh bro Now I want to teach you something very friendly In Codeforce, tags are set for many questions that show the key ideas of the solution and the algorithms necessary for the solution. So it's better to learn how to use this site before you come and comment

→ Reply

night.watchman

9 months ago, # |

help in problem C

here L = k * a^x * b^y, so, K must be a divisor of L. Now i need to check which of the divisors can be represented in (a^x*b^y) and count them. What is wrong with this idea? i think it shouldn't give TLE. My Source Code (WA on test 2)

→ Reply

larush

9 months ago, # ^ |

Try putting your "k" values in a set. Maybe that helps.

→ Reply

Miryz

9 months ago, # ^ |

You can keep the K values in hashmap for quick checking.

→ Reply

ShivamJNU

9 months ago, # ^ |

← Rev. 4 →

In the code, you are only considering the case where a^x==l, or (b^y)==(l/a). Instead of thinking for 'k', try to generate all the values of (a^x + b^y) and then check if it divides l. Store the value of corresponding 'k' in a map or a set if it does. To avoid overflow issues you will need to consider the values of 'x' and 'y' up to which a^x and b^y do not exceed 'l'.

→ Reply

Nisikto

9 months ago, # |

Thanks for making the round rated.

→ Reply

larush

9 months ago, # |

Thanks for problem E, I finally learnt how to implement ternary search.

→ Reply

9 months ago, # ^ |

What's the idea?

→ Reply

larush

9 months ago, # ^ |

← Rev. 2 →

My answer won't be perfect, but I hope you understand something.

Spoiler

→ Reply

Miryz

9 months ago, # |

A bit sad that I couldn't code the E problem in time, the prefix sum and a binary search was an obvious idea of the solution. Good contest tho, I assume that it is a perfect example of a well elaborated div3 round. Many thanks to the authors, it was a pleasant adventure!

→ Reply

realsimile

9 months ago, # |

-8

Child labor... unbeliavable.

→ Reply

tickbird

9 months ago, # |

why trivial binary search not working on E! like lower_bound(pref.begin(), pref.end(), pref[l] + u) AAAAAAAAAAAAAAAAA!!!!

→ Reply

https://codeforces.net/contest/1933/submission/248653337

9 months ago, # ^ |

i mean that's literally my ac solution so idk bout you

→ Reply

phukaoz

9 months ago, # ^ |

you also need to think about the r+1 and r-1.

→ Reply

robertlewantest

9 months ago, # |

Why my this solution is not working for E? im checking mid and mid+1

→ Reply

llc5pg

9 months ago, # ^ |

Fixed. See 248687605

→ Reply

robertlewantest

9 months ago, # ^ |

Wow.. thnks a lot.. btw can u pls explain why ans is coming at lo?

→ Reply

9 months ago, # |

← Rev. 2 →

#include <iostream>
using namespace std;

int main() {
    cout << "1\n"; // End the line after printing "1"
    cout << "1000 1000\n"; // End the line after printing "1000 1000"
    for(int i = 0; i < 1000; i++) {
        for(int j = 0; j < 1000; j++) {
            cout << "0 "; // Print "0 " without a newline
        }
        cout << "\n"; // End the line after printing each row of zeros
    }
    return 0;
}

I am trying to hack Problem F using above generator. But got this Verdict "Validator 'validator.exe' returns exit code 3 [FAIL Expected integer, but "#include" found (stdin, line 1)]". Someone help me find the error.

→ Reply

Gassa

9 months ago, # ^ |

+31

You have to find and use the "generated input" tab in the hacking interface.

Besides that, you have to NOT print the trailing space in each line. Your test will be validated and then given to contestant, who doesn't have the obligation to work on malformed input. The validator does not fix formatting for you, it just reports that formatting is wrong (easier this way).

→ Reply

WizzyRocky

9 months ago, # |

I think my code is wrong in problem D 248569476 can someone hack it

→ Reply

PaleBlueDot

9 months ago, # |

Thanks for keeping the round rated ❤️. It will encourage honest participants who invested their time in participating in this contest.

→ Reply

AvaraKedavra

9 months ago, # |

"Round is still rated"

Lets goooooooooooooooooo

→ Reply

cppismycrush

9 months ago, # |

-13

You know u cant detect cheaters they can simply change the code u might find some but still its kinda unfair

→ Reply

parag776

9 months ago, # |

← Rev. 2 →

really enjoyed G and F. I don't know why I wrote a dfs solution for F during contest(that was also wrong).

→ Reply

WakuWakuWaku

9 months ago, # |

any hints for $$$F$$$?

→ Reply

el_tunel

9 months ago, # ^ |

You can remove the motion of the rocks by moving your reference frame up one unit each time step. From this point of view, at each time step the robot can either stand still, move down and to the right (if there is no rock at the end of this move), or move down two units (if there is no rock at the end of the move or at the intermediate square.) This may make it easier to see which squares the robot can reach and when it can reach them.

→ Reply

.utk.

9 months ago, # |

Hints for G?

→ Reply

snowysecret

9 months ago, # ^ |

+11

Answer is at most 8, try to write a bruteforce for n=m=5 and observe patterns.

→ Reply

ggq15plus2

9 months ago, # |

Thanks for the great problem F!

→ Reply

treasuryonly

9 months ago, # |

Thank you guys for an amazing Div3!

Wow, the system testing is earlier than usual!

→ Reply

sdyakonov

9 months ago, # |

Indian youtubers?

No, Um_nik

→ Reply

SajidZakaria

9 months ago, # |

+30

→ Reply

vivek_coder_9

9 months ago, # |

in Problem 'D', i used Unordered_map to save time and got TLE on testcase 30 ;(

→ Reply

bkdn23.dotuangv

9 months ago, # |

my program got TLE because use unordered_map? 248557195 (problem D)

→ Reply

forgot_past

9 months ago, # ^ |

It is working with custom hash: https://codeforces.net/contest/1933/submission/248719307

→ Reply

vivek_coder_9

9 months ago, # ^ |

I have a question! should we avoid the usage of un_map in contests? is this a thing in competitive programming? because the only way to find out that un_map will cost O(n) is by submitting the solution during the contest and wait LOL :)

→ Reply

ShivamJNU

9 months ago, # ^ |

You may refer to this blog.

→ Reply

ychaaibi

9 months ago, # |

I think that there's a problem of rank updating ychaaibi rating ( 1406 )

Thanks in advance, also thank you for the contest.

→ Reply

Aviral_Gupta

9 months ago, # |

1599 after rating update. :( Does the rating increase after plag check is done?

→ Reply

ychaaibi

9 months ago, # ^ |

← Rev. 3 →

Yeah the rank was updated and my rate was also increased by 3 ( 1406 -> 1409 )

Thank you so much.

→ Reply

chenRenning

9 months ago, # |

Thank you to the question team for providing this tournament making it possible for me to pass 5 questions during the tournament. good bye pupil ， hello Specialist ：）

→ Reply

adarshrajpathak

9 months ago, # |

Is there anyway to get editorial of the contests (when over) at one-place.

→ Reply

aditya_parate

9 months ago, # |

In Question 1933C - Turtle Fingers: Count the Values of k,

Can anyone explain why do i need to iterate the values of x from 0 to (log(l)/log(a) + 1) ? Similarly i need to iterate the values of y from 0 to (log(l)/log(b) + 1) .

Why do i need to check for the last value (log(l)/log(a) + 1) ? Because anyway a power (log(l)/log(a) + 1) will be greater than l.

why does my solution fail when i iterate only till (log(l)/log(a)) ?

→ Reply

el_tunel

9 months ago, # ^ |

When you compute log(l)/log(a) using floating-point arithmetic, you get rounding errors, so the value you compute may be less than the exact value. To see this, use a custom test to run the following program, which attempts to compute $$$\log 243/\log 3$$$:

Test program

#include <cmath>
#include <cstdio>

// Run under GNU G++20 11.2.0 (64 bit, winlibs)

using namespace std;

int main()
{
   printf("%.15f\n", log(243) / log(3));
}

You will get not 5 but 4.999999999999999.

→ Reply

aditya_parate

9 months ago, # ^ |

Okayyy. Thanks bro

→ Reply