Educational Codeforces Round 169 [Rated for Div. 2]

5 weeks ago, # |

hopefully expert after this one

→ Reply

5 weeks ago, # ^ |

good luck mate

→ Reply

5 weeks ago, # ^ |

good luck

→ Reply

DalChawal

5 weeks ago, # ^ |

why is this comment at -12???

→ Reply

5 weeks ago, # ^ |

idk either lmao, it is what it is

→ Reply

Kolyanchick

5 weeks ago, # ^ |

because this is cf

→ Reply

mayank.nichlani22

5 weeks ago, # ^ |

coz he's probably a cheater,see his submissions

→ Reply

5 weeks ago, # ^ |

if you accuse me of cheating, I suppose you have evidence?

→ Reply

mayank.nichlani22

5 weeks ago, # ^ |

← Rev. 3 →

-17

→ Reply

5 weeks ago, # ^ |

Look through every single one of my submissions, and you can see I ALWAYS write long long int. Any single time I use 64-bit integer, I always type long long int. You just picked a random submission and the most random reason and decided to go with it? cope and seethe newbie, maybe focus on actually solving some problems instead of throwing baseless accusations.

→ Reply

mayank.nichlani22

5 weeks ago, # ^ |

-7

So maybe you debug every question using ai,who knows!Also I am actually pupil,I didn't know multiple accounts are not allowed on cf,Hence kept this one only for practicing.

→ Reply

5 weeks ago, # ^ |

yea sure, I also use ai to type my code when I practice as well right? you're a complete clown, stop embarrassing yourself. oh and since when is AI considered cheating?

→ Reply

drgrenkenstein

5 weeks ago, # ^ |

← Rev. 2 →

I used to write long long int every time myself before I started using a template that had long long. "clearly ai generated" bro is confident too. maybe try to come up with better proofs next time, at the very least you could avoid so many wrong submissions Starting to blame everyone you see for cheating using such petty claims is making things worse

→ Reply

kalpitdon7

5 weeks ago, # |

← Rev. 2 →

Independence day Contest !

→ Reply

panku8433

5 weeks ago, # |

← Rev. 2 →

All the best to all. Hope you all get +100.

→ Reply

Mohamed_Saad62

5 weeks ago, # ^ |

I need 130 :) but 100 still good and will make me happy

→ Reply

5 weeks ago, # ^ |

thanks

→ Reply

XiaoXiaQWQ

5 weeks ago, # |

How to gain rating in EDU Round? I've droped the rating at almost every the EDU round.

→ Reply

Manish_Jangir

5 weeks ago, # ^ |

Same here

→ Reply

123gjweq2

5 weeks ago, # ^ |

+45

during the contest, if you see that your position is too low to gain rating, it is best to solve another problem

→ Reply

Nick9

5 weeks ago, # ^ |

based

→ Reply

bhardwajsatyam

5 weeks ago, # ^ |

What do you mean?

→ Reply

Adityaxv

5 weeks ago, # |

I'm glad that there are no tester comments.

→ Reply

Abdo_Hussain

5 weeks ago, # |

i love edu rounds <3

→ Reply

lucas.morrison

5 weeks ago, # |

Pupil rank happens TOMORROW

→ Reply

lucas.morrison

5 weeks ago, # ^ |

Looking forward to weeks of therapy for failing to do C over my misinterpretation of what the k variable meant...

→ Reply

saadkhurshidqureshi

5 weeks ago, # |

← Rev. 2 →

How to Hack someone's solution?? Shayan bro i think you should make a video on this topic!! I tried many times to hack someone.. but always ( Unsuccessful Attempt )

→ Reply

https://codeforces.net/contest/1999/hacks/1066931

5 weeks ago, # ^ |

← Rev. 2 →

You should give test with high strength. Here is an example: 274841071

If you can't understand this code, it doesn't matter. You just need to know what he is doing. In this code, he's using Substring all the times which is $$$O(|s|)$$$ in time. It will get a TLE by a test with high strength. Thus, I give a test like this: 1, and then 200000 ?s, and then an a.

Unaccidentally, he is hacked by me.

→ Reply

saadkhurshidqureshi

5 weeks ago, # ^ |

You just used generator to generate worst case for s right?? But how did you figure out it'll give TLE..

How to practice for this?? I am very bad to figure out the time and space complexities

→ Reply

5 weeks ago, # ^ |

You can search the submissions in “Status”. And sort it by execution time at the end of the page. And get to the last page. The submissions there are almost TLE so that maybe TLE after you hack them.

→ Reply

5 weeks ago, # ^ |

What generator do you use?

→ Reply

5 weeks ago, # ^ |

Usually I use C++’s output. You can use what you familiar with.

if the test isn’t that long, just input the test by text is enough.

→ Reply

5 weeks ago, # ^ |

There you've wrote string s of length 2*10^5, how did you do that, and how to generate those big test cases?

→ Reply

5 weeks ago, # ^ |

← Rev. 2 →

There is a “Generate Input” Botton when you hack. Press it and paste your code there.

Example:

#include<bits/stdc++.h>
using namespace std;
int main(){

    cout<<“1\n”;
    for(int i=0;i<=200000;i++)                 cout<<“?”;
    cout<<endl<<“a\n”;
}

→ Reply

5 weeks ago, # ^ |

Okay, this way! Thanks.

→ Reply

saadkhurshidqureshi

5 weeks ago, # ^ |

I tried this multiple times but never got successful Attempt

→ Reply

5 weeks ago, # ^ |

Try more, you’ll gain from it.

→ Reply

5 weeks ago, # ^ |

What’s more , see which problem is hacked most. It may mean that it is easier to hack than other problem.

→ Reply

zer0_123

5 weeks ago, # |

← Rev. 2 →

Sorry I’m a beginner here, how are edu rounds different from normal contests ?

PS: Got it, thank you!

→ Reply

NOTHING_2_LOSE

5 weeks ago, # ^ |

← Rev. 2 →

The difficulty level is usually the middle ground of div2 and div3 constests.

→ Reply

5 weeks ago, # ^ |

You can't hack during the contest, but you can EVERYONE hack after contest.

→ Reply

tobyAcodes

5 weeks ago, # ^ |

I am a total beginner and have no idea what hacking means in this context. Like changing the answer or sth? Where should I start from

→ Reply

https://codeforces.net/help

5 weeks ago, # ^ |

Read about hacks.

→ Reply

https://codeforces.net/blog/entry/456

5 weeks ago, # ^ |

← Rev. 5 →

In some contests like Div. 2 Round, there is a Codeforces Format .

Maybe in most websites, it will give you the result at once when you submit. But if Codeforces, there is only a set of tests called Pretests.

It just means that this is just the preliminary test which shows you if the code can run normally. If you passed pretests, you can lock this problem and hack participants who pasts pretests in your room, by giving tests with high strength to make them failed passing this problem.

P.S. If you lock the problem, you can't resubmit any more until the contest ends.

To get more information, you can read this blog

In Div. 3 , Div. 4, and EDU Round, it is EX-ICPC Format. There will be a 12-hour-long phase at which you can hack everyone after the contest.

→ Reply

5 weeks ago, # ^ |

← Rev. 3 →

Different from Div.1 , Div.2 , Div.1+2 contests, it is an EX-ICPC Format.

Similar to Div.3 and Div.4 contests. You can see participants rated and unrated separately in the standings after system testing. You can view last Div.3 contest as an example: Codeforces Round 966 (Div. 3)

And view this round to see the probable difficulty of each problem. Educational Codeforces Round 168 (Rated for Div. 2)

standings: View rated participants rated separately by pressing the Both divisions v botton at the rightmost of your screen. Then cancel the tick of Show unofficial one.

→ Reply

_regular_show

5 weeks ago, # |

Thanks to all who contributes to this contest. Hope I can go back to specialist after this one!

→ Reply

Enatsu__8

5 weeks ago, # ^ |

hoping for the same!

→ Reply

Cyclonestopper9000

5 weeks ago, # |

Hope for 1300+ rating

→ Reply

5 weeks ago, # ^ |

good luck (you did well in the last contest congrats)

→ Reply

Cyclonestopper9000

5 weeks ago, # ^ |

thanks, you too

→ Reply

ManasXD

5 weeks ago, # |

Let's go specialist in this one

→ Reply

21Cash

5 weeks ago, # |

My first contest as specialist. Good luck everyone.

→ Reply

Md-Merazul-Islam

5 weeks ago, # |

Best of luck to all. Hopefully, we will increase our rating in this contest =)

→ Reply

5 weeks ago, # |

+15

Bet it or not, I'm going to reach Master this round.

→ Reply

5 weeks ago, # ^ |

Good luck to you. Good luck to everyone.

→ Reply

5 weeks ago, # ^ |

Not happening, ahahaha

→ Reply

5 weeks ago, # ^ |

← Rev. 3 →

I didn't say I bet it. haha.... ha... Failure is common.

Nevermind. I'll be still there next round.

How can you reply me just minutes before the contest, are you watching me? Thank you for your watching stuttering

Maybe I'm going to change my handle into Lmao_Fox if this happens too many times.

→ Reply

vinayakzutshi

5 weeks ago, # |

← Rev. 2 →

best of luck guys

→ Reply

ankitchauhan

5 weeks ago, # |

I want to regain my pupil status.

→ Reply

jatrophalouvre

5 weeks ago, # |

+40

If I don’t get CM I’m gay.

→ Reply

nskybytskyi

5 weeks ago, # ^ |

+25

Congratulations! At least it's legal in Singapore since recently.

→ Reply

Enatsu__8

5 weeks ago, # ^ |

nice way of coming out of the closet

→ Reply

CodeKira

5 weeks ago, # |

hope i become pupil , pls be easy for me

→ Reply

CodeKira

5 weeks ago, # ^ |

and it happened nice

→ Reply

Enatsu__8

5 weeks ago, # |

Hoping for a positive delta!

→ Reply

VS34

5 weeks ago, # |

In Educational Round dose speed of solving question matters or only number of questions solved during the contest matters and does not depend even on the rating of the question solved??

→ Reply

5 weeks ago, # ^ |

← Rev. 2 →

Speed matters. Rank is sorted first by number of solved problems, then time (10 minutes penalty for 1 wrong submission)

That means solving A and solving G are the same. It just calculates the total number of your solved problems and then the time.

→ Reply

Maria_Sultana

5 weeks ago, # |

-9

InShaAllah, I will get +100 today

→ Reply

modassirfaruquee

5 weeks ago, # ^ |

I also prayed to Allah to make me capable of solving at least 4 problems but i guess it wasn't better for me

→ Reply

SW7777

5 weeks ago, # |

Hope to solve four problems!

→ Reply

Steven-_-AbuAlkhair

5 weeks ago, # |

c < b

→ Reply

deepak_221

5 weeks ago, # ^ |

https://codeforces.net/contest/2004/submission/276681600 why its wrong

→ Reply

Steven-_-AbuAlkhair

5 weeks ago, # ^ |

se is changed after se+=min(k,fi-se) so you need to use temp like t = in(k,fi-se) , se+=t

→ Reply

deepak_221

5 weeks ago, # ^ |

i was dumb thanks for solution

→ Reply

Karatinos

5 weeks ago, # |

-13

worst contest((

→ Reply

donpaul2718

5 weeks ago, # |

← Rev. 2 →

+26

Great D but C < B.

→ Reply

123gjweq2

5 weeks ago, # ^ |

was C really that easy?

→ Reply

https://codeforces.net/contest/2004/submission/276691814

5 weeks ago, # ^ |

it was easy I still got 6 WA's cause i didnt read "total" increase <=K

→ Reply

123gjweq2

5 weeks ago, # ^ |

ahh, that changes a thing or two

→ Reply

aviralarpan3301

5 weeks ago, # ^ |

or three

→ Reply

jigyashugupta

5 weeks ago, # ^ |

OOOHHHHH MMYYYYYYY GOODDDDDDDD!!!!!! YES!! YESS !! YESS!! YESS!! NO !! NO!! NO!! NO!!

→ Reply

lmn207

5 weeks ago, # ^ |

gotta be honest the difficulties of problems from A->D is too low, compared to normal div2 rounds or just edu rounds. I choked this one but generally speaking, i think this contest was not so good

→ Reply

Baby_Bird

5 weeks ago, # ^ |

D offered a little bit of implementation fuss despite being not that hard conceptually.

→ Reply

Jerrasterix

5 weeks ago, # ^ |

← Rev. 2 →

Mind pointing out where my mistake was ??

→ Reply

phsads

5 weeks ago, # |

← Rev. 2 →

+60

so what the hell are you supposed to do for E (nims and games are kinda like the opposite of my skillset lol)

→ Reply

UP84

5 weeks ago, # ^ |

Find grundy numbers using SPF.

→ Reply

kwangg

5 weeks ago, # ^ |

+13

I don't know why it was named "not a nim problem". I solved it as a nim problem. Case analysis on small numbers showed that the nimber of a pile is basically the "rank" of its smallest prime factor (where a prime having rank k means it's the kth prime number, except that the rank of 2 is 0.)

→ Reply

adaptatron

5 weeks ago, # |

← Rev. 2 →

Video editorial for D: Colored Portals

Here's a very fancy implementation of D: Colored Portals using Bitmask tricks that was introduced in D: Cases from a recent CF round. I also have a video editorial for the old problem.

Let's represent all portals as bitmasks of length 4. Then, a path between 2 nodes is possible if and only if the bitwise AND of both the numbers is not zero.

Assume $$$x < y$$$. On a number line, we know that the shortest path between 2 points is the straight line connecting them. So, if $$$a[x] \& a[y] \neq 0$$$, then, the answer is $$$|x - y|$$$. Otherwise, we need to jump to a portal that differs in exactly one color (i,e, the bitwise AND should contain exactly 1 set bit). From there, we can jump to $$$y$$$ directly.

Define $$$ldp[i]$$$ to be the nearest portal to the left that differs in exactly one color. You can populate it from left to right by maintaining a map of the latest bitmasks seen so far. Similarly, you can populate $$$rdp$$$.

There are only 3 possible paths. We take the best one amongst them.

$$$x \rightarrow y$$$
$$$x \rightarrow ldp[x] \rightarrow y$$$
$$$x \rightarrow rdp[x] \rightarrow y$$$

→ Reply

5 weeks ago, # ^ |

i got the solution down immediately, but i could not implement it at all, fk me

→ Reply

5 weeks ago, # ^ |

I also got the solution, but my implement is not as good as the method above so... I don't know where I went wrong (I use binary search btw)

→ Reply

5 weeks ago, # ^ |

i tried using a map and then i also tried bs and some other stuff and i just couldnt get it. unlucky :(

→ Reply

Saivishwas

5 weeks ago, # ^ |

276681877

You can look at my case work. I am laughing at my own code.

→ Reply

5 weeks ago, # ^ |

i shouldve just quit trying to do it nicely and just do that. good job ngl

→ Reply

aditya0610

5 weeks ago, # ^ |

Nice work

→ Reply

5 weeks ago, # ^ |

← Rev. 6 →

oh well I notice where I went wrong, need to reverse the array and position to binary search to get the correct answer. Not searching the y+1 or x+1 or (x+y)//2 will do

UPD: after fix the bs bug, my solution got TLE in test 6

In the hindsight, just maintain ldp and rdp will do me a favor more than bs

UPD: Resolved TLE, it's list.insert(0, list) which I think O(1) but it's O(n)

→ Reply

Astroflexx

5 weeks ago, # |

+20

And the trend of 4k+ solves on D in Edu Rounds continues...

→ Reply

FuyuMai12

5 weeks ago, # ^ |

This D is only of Div2C level at most.

→ Reply

_inferno_

5 weeks ago, # |

whoops

→ Reply

Wandoka

5 weeks ago, # |

+170

Why would you ever call a nim problem — $$$\texttt{Not a Nim Problem}$$$

Like I really don't understand, because it is funny?

When I read the name, I though that it is a bad idea to include "Nim" in the name of the problem, because when you search for nim tasks, this one would show up.

When though of the solution, I became even more confused. It was a nim problem. So why the author is telling me it is not true?

I thought that the name was part of the statement. I started to doubt myself that I got something wrong. Turns out everything is fine, nim works. Downvoted the contest when I saw "Accepted" verdict.

And also this statement:

It is not allowed to take from the pile a number of stones y such that the greatest common divisor of $$$x$$$ and $$$y$$$ is not equal to $$$1$$$.

Why you say "not not A" instead of just " A "

We can rewrite it like this:

It is only allowed to take from the pile a number of stones y such that the greatest common divisor of $$$x$$$ and $$$y$$$ is equal to $$$1$$$.

This sentence is so confusing that even an announcement was made, where it was stated that

In other words, gcd(x,y) must be 1.

If it is so confusing, maybe the statement should be fixed? I don't understand why the announcement was made, and this sentence was not changed.

→ Reply

5 weeks ago, # ^ |

+26

Lol, bro, relax

→ Reply

san9blin

5 weeks ago, # ^ |

Agree with the title, just why?

→ Reply

beyondpluto

5 weeks ago, # ^ |

Oh bro, is it a nim problem?
I immediately got idea for single pile, thought of using nim for n independent piles, but then I saw the problem name and thought its going to be some special case where nim doesn't work. And spent whole contest trying to solve without nim lol. I should understand nim better.

→ Reply

CrackInTheSky

5 weeks ago, # ^ |

+12

this nim thing is unfamiliar to me. any suggested resources ?

→ Reply

.-__-.

5 weeks ago, # ^ |

I really think you do not need to know that at specialist rank.

→ Reply

JasamritRahala

5 weeks ago, # ^ |

Hey, I was confused too. This article seems good :) https://codeforces.net/blog/entry/66040

→ Reply

CrackInTheSky

5 weeks ago, # ^ |

thanks

→ Reply

The5threich

5 weeks ago, # ^ |

You can read the wikipedia article on sprague-grundy theorem and Nim Sum. I think they are pretty well written.

→ Reply

Nishu_2005

5 weeks ago, # ^ |

Agreed, read it wrong due to the not not thing and thus couldn't do it in time.

→ Reply

UP84

5 weeks ago, # |

Every page from problem to submit takes so much time to load. It's infuriating.

→ Reply

5 weeks ago, # |

← Rev. 2 →

ARE THESE GRUNDY NUMBERS CORRECT ?

→ Reply

mr_swashbuckler

5 weeks ago, # ^ |

Yes

→ Reply

5 weeks ago, # ^ |

I could generate grundy numbers, but didn't know how to extend them to 10^7. Small hint please ?

→ Reply

fonmagnus

5 weeks ago, # ^ |

← Rev. 3 →

+38

For even numbers, grundy is always 0. For 2, it is obvious because you can only take 1 and the grundy of 1 is 1. For the rest, because player is not allowed to take 2, then $$$g(2)=0$$$ would always be the mex of all options

For prime numbers, the grundy is $$$k$$$ where $$$k$$$ is the order of prime numbers (e.g. $$$g(3) = 2$$$, $$$g(5) = 3$$$ etc). This is because all prime numbers $$$p$$$ can have options of $$$1,2,3,\ldots,p-1$$$. Therefore the mex is always $$$k$$$ because it hasn't existed yet

For the rest, the grundy would be smallest prime factor of that number. Because it would be the smallest number that doesn't exist for all its transition (hence, it similar to the nature of mex). The other number would exist because if the smallest prime factor is $$$p$$$, then all numbers between $$$1, 2, \ldots, p-1$$$ can be taken of that pile. Hence, all numbers between $$$0, 1, 2, \ldots, g(p-1)$$$ can be exist as transition moves and won't appear as mex.

→ Reply

5 weeks ago, # ^ |

← Rev. 2 →

Thank you very much for explanation.

I could see the first and second observations from the brute-force that I had written.

But I couldn't deduce the third observation :( . otherwise I would have solved this.

Anyone who is interested in how to generate grundy numbers here, please refer to this.

c++ code to generate grundy number

~~~~~~

grundy[0] = 0; grundy[1] = 1;

    grundy[2] = 0;

    repl(i,3,100) {
       set<int> grudySet;
       repl(j,1,i-1) {
         if(gcd(i,j) == 1) {
          grudySet.I(grundy[i-j]);
         }
       }

       int mex = 0;
       while(grudySet.find(mex) != grudySet.EN) {
         mex++;
       }

       grundy[i] = mex;

    }

    repl(i,1,100) {


       cout << " for the i " <<  i << " its grundy number is " << grundy[i] << endl << endl;


    }

~~~~~~~

→ Reply

nskybytskyi

5 weeks ago, # ^ |

Don't worry it took me 90 minutes to get it haha. F was much more straightforward today, so it's a good thing I wasn't afraid to skip.

→ Reply

5 weeks ago, # ^ |

small doubt, can we generate all the primes till 10^7 within the given time-limit ? ( never generated primes till 10^7, so asking ).

We need to find the what is the order of the given prime number, and we can't do that unless we have all the prime numbers within 10^7.

Do we need to implement SegmentedSieve ? or normal sieve is sufficient ?

fonmagnus

→ Reply

fonmagnus

5 weeks ago, # ^ |

I think if we skip the even numbers, then we can do it for $$$5 \times 10^6$$$ numbers and should be fine (it's kinda close to TL but I guess that's one way to prune it)

→ Reply

5 weeks ago, # ^ |

Sure, will try later.

I wish, the pile sizes were within 10^5 range.

then I would have solved this question in 25-30 minutes :P .

→ Reply

Pirate_King

5 weeks ago, # ^ |

yes we can. my submission ran in 406ms and i am running sieve till 1e7

→ Reply

october_rain

5 weeks ago, # ^ |

can we generate all the prime still $$$10^7$$$ within the given time-limit?

yes, use linear sieve

→ Reply

nskybytskyi

5 weeks ago, # ^ |

Here, you forgot to include a link.

→ Reply

5 weeks ago, # ^ |

Normal sieve, if implemented correctly, runs in O(n*log(log(n))), which is sufficient (my sol passed with it).

→ Reply

indian_rounds_LULW

5 weeks ago, # |

+68

Don't use " NOT NOT " in your statements ever again please

And yes, I googled E, sue me (I suspect many others did or have seen this problem before anyway)

→ Reply

MVP_Harry

5 weeks ago, # ^ |

This makes me wonder how many people thought of E during the contest by themselves instead of just googling. Because I couldn't think of anything after more than an hour (sad noises**)

→ Reply

indian_rounds_LULW

5 weeks ago, # ^ |

← Rev. 2 →

I have spent most of the time going back and forth: "This is coprime nim. No, this isn't coprime nim. What if I take only divisors? But I can take any non coprime number. Wait, this is coprime nim, gcd should be equal to 1"

In regards to coprime nim (and not divisor nim, non-coprime nim and other variations) I've come up only with the most obvious stuff on my own:

0 is losing, 1 is wining and even numbers are always losing (since you are always forced to reduce the pile to some odd number, and from and odd number you can always go back to an even one)
for a prime number any move except for the number itself is possible

→ Reply

SuperMo

5 weeks ago, # |

D is maybe just next and previous tables but in order for me to implement it I would need maybe 400 line looking forward to see how people did it nicely

→ Reply

jzcrq

5 weeks ago, # |

I'm curious if E is a classic problem of SG function. I don't know how to do it, but I have a vague feeling that it can do it.

→ Reply

Samarth_Rajj

5 weeks ago, # ^ |

what is SG function?

→ Reply

Chiral

5 weeks ago, # ^ |

Sprague-Grundy function, super useful for nim-like problems.

→ Reply

jzcrq

5 weeks ago, # ^ |

Consider treating the game process as a DAG, taking the SG function value of a node as the mex of the SG function values of its child nodes.

→ Reply

ExpectoPatronum

5 weeks ago, # ^ |

← Rev. 3 →

I just generated all values of SG and guessed, then I realized that $$$g(x)$$$ is equal to the smallest prime factor of $$$x$$$ ($$$g(x) = 0$$$ if $$$x$$$ is even))

→ Reply

tickbird

5 weeks ago, # |

← Rev. 2 →

C < A < D < B

→ Reply

JakobZ

5 weeks ago, # |

+40

Maybe I'm salty for not solving E, but is it ok to put a somewhat well known problem that apparently has a solution on the internet to a contest?

→ Reply

jmyszka

5 weeks ago, # ^ |

← Rev. 2 →

+13

I am not a big fan of E myself but its edu round so the authors are somehow justified

→ Reply

Nishu_2005

5 weeks ago, # ^ |

Should such a contest be rated for anyone at all? C,D,E all were kind off not div2 level. If someone had a day where they did B and D fast enough (I couldn't, maybe thats why i am putting this out), E was a walkover.

→ Reply

JasonMendoza2008

5 weeks ago, # |

Lovely problems thanks, problem B and D were a bit implementation heavy unless I just missed the obvious solution and did something unnecessarily long.

→ Reply

SuperMo

5 weeks ago, # ^ |

I think that D need a trick like bitmasks or else it would be so much pain

→ Reply

JasonMendoza2008

5 weeks ago, # ^ |

My solution was a few hundred lines long without bitmasks haha

→ Reply

5 weeks ago, # ^ |

I got WA test 2 in D until the contest is over... unable to fix the code in time

→ Reply

i3mr125

5 weeks ago, # ^ |

binary search the indices would be enough no need for bitmasks

→ Reply

Dinh_Van_Tung

5 weeks ago, # ^ |

OMG! same avt. best of luck

→ Reply

i3mr125

5 weeks ago, # ^ |

yeppiee, u too

→ Reply

5 weeks ago, # ^ |

look at mine 276671836

→ Reply

5 weeks ago, # |

← Rev. 2 →

Why this code (https://codeforces.net/contest/2004/submission/276666440) shows strange behavior when all the array elements are equal, for example:
5 4
3 3 3 3 3
Shouldn't the answer be 3 here?
Also i tried printing the final array after all the operations done, and in this case it is 3 3 3 1 0, but according to code none of the elements should change. Where i am going wrong?

Update: There was problem with my keyboard language setting due to which a special character was in the input instead of 3. But the solution is still wrong i think.

→ Reply

LiuXingJian

5 weeks ago, # ^ |

The variable ind will still bea -1 after your operations on nums, adding an another verification may help.(Though the solution is still wrong as you don't need to adjust all the numbers)

→ Reply

5 weeks ago, # ^ |

Okay, let me try once again, thanks.

→ Reply

Le_Gusto

5 weeks ago, # |

Wasted so much time on B lol, though D was very enjoyable!

→ Reply

o.khalifa

5 weeks ago, # |

I enjoyed these problems

→ Reply

sandbag

5 weeks ago, # |

+14

If you ever feel stupid, I got +7 penalties on D despite solving it in 20 minutes due to writing this function:

Code

bool overlap(string&a, string&b) {
    if(a[0] == b[0] || a[1] == b[1]) return true;
    return false;
}

→ Reply

5 weeks ago, # ^ |

small piece of advice.next time create character set. and put characters of both the strings inside the set.

If the set size is less than (a.size() + b.size()) , means there is an overlap <3 .

→ Reply

MohammadHijaz

5 weeks ago, # ^ |

I had the same issue and couldn't figure it out in contest lol. 276656805

→ Reply

ZyadFva

5 weeks ago, # ^ |

← Rev. 2 →

Say less

→ Reply

5 weeks ago, # ^ |

i got also got penalty on D, because of this: wrong submission: 276659462 correct submission: 276671836

→ Reply

5 weeks ago, # |

← Rev. 2 →

can any one tell me what is the wrong in my code in (d) or if i missed some cases may be 276679658

→ Reply

34z12000

5 weeks ago, # |

← Rev. 3 →

+14

My sol for D looks like abomination 276680579

→ Reply

5 weeks ago, # ^ |

at least you solve it

→ Reply

5 weeks ago, # ^ |

R u blind? He didn't.

→ Reply

5 weeks ago, # ^ |

oh my god i was think he solve it

→ Reply

san9blin

5 weeks ago, # ^ |

He did later.

→ Reply

5 weeks ago, # ^ |

Lol, u r also blind xD since he didn't

→ Reply

san9blin

5 weeks ago, # ^ |

Not during contest, but he did :)

→ Reply

5 weeks ago, # ^ |

Doesn't count :D

→ Reply

5 weeks ago, # ^ |

thank you

→ Reply

JasonMendoza2008

5 weeks ago, # ^ |

It clearly says Runtime error on test 2 so they didn't.

→ Reply

34z12000

5 weeks ago, # ^ |

← Rev. 2 →

sorry, wrong submission

→ Reply

Astroflexx

5 weeks ago, # ^ |

Holy mother of God what is that code

→ Reply

5 weeks ago, # ^ |

Bro what, 800 python lines...

→ Reply

blablabla1803

5 weeks ago, # ^ |

← Rev. 2 →

276679322 Mine is not too far off xD , just that mine TLE'd

→ Reply

Pirate_King

5 weeks ago, # |

Lmao i just brute forced the first 100 grundy numbers and stared at the screen for 45 mins until i observed pattern

→ Reply

DuongForeverAlone

5 weeks ago, # ^ |

what is the pattern in this problem?

→ Reply

Pirate_King

5 weeks ago, # ^ |

for even its 0 and for odd it is same as the grundy number of its smallest prime factor

→ Reply

DuongForeverAlone

5 weeks ago, # ^ |

Oh god, I've just realized that I misread the statement completely LOL. There was two "not" in the statement @@.

→ Reply

aayush249

5 weeks ago, # |

How do you solve D??

→ Reply

5 weeks ago, # ^ |

if x1 and x2 dont share a colour, then you want to find the closest city to the right of x1 and the closest city to the left of x1 that share only 1 colour, then you calculate which of the 2 paths is better. im so salty i couldnt implement this, but this is the solution i think

→ Reply

5 weeks ago, # ^ |

i was think if you find the closest city to minimum one between of them you can find the answer and i think this do same idea you mention but i got wrong 2

→ Reply

adaptatron

5 weeks ago, # ^ |

I added a 13 minute video editorial. Hope this helps.

→ Reply

differentialplantain

5 weeks ago, # ^ |

← Rev. 2 →

For each pair query, there are three cases you have to consider:

Case 1: The two portals are not opposites (i.e. they share a color)

In this case, you can just directly teleport with a cost of their distance in the array

Case 2: The two portals are opposite (they do not share a color), but between them there is a portal color combo which is different from both

In this case, our cost is also just their distance in the array b/c you can just teleport to the element between them to get from one to the other

Case 3: The two portals are opposite (they do not share a color) and there is no element between them which has a different color combo than either one

In this case, we have to calculate the shortest distance from the left of the leftmost query point to an element different from it which is not its opposite and likewise for the rightmost query point to the right instead. We then take the minimum of these distances we call mindist which naturally gives the total cost for the query to be 2*mindist + the distance between the query points. If there is no such minimum distance (i.e. there is no way to get between the query points at all) then we instead output -1.

One can implement the third case by iterating forward and backward through the array for each color combo to fill an array of pairs calculating the index of the nearest element that is not equal and not opposite to its color combo both to the left and right.

→ Reply

5 weeks ago, # |

can you tell me what's wrong in this solution for C? https://codeforces.net/contest/2004/submission/276677983

my code for C could pass the sample test cases but i kept getting WA after submission :(

i wasted 1 hr on it lmao, was C really so easy?

→ Reply

Sylvester_

5 weeks ago, # ^ |

try using long

→ Reply

5 weeks ago, # ^ |

just tried using long long, still WA

→ Reply

Sylvester_

5 weeks ago, # ^ |

Look at my code if it help

→ Reply

denk

5 weeks ago, # ^ |

The problem is that if the array is initially of odd length, then you create a phantom element equal to 0 and further consider it as the original one and, accordingly, you can add values to it, which cannot be done, in fact, it does not exist.

Test when the code is not working correctly:

3 1

1 5 5

Program output: 0

Correct answer: 1

According to the logic of your program, element 0 is created and the array turns from [1, 5, 5] into [0, 1, 5, 5]. After that, in order to get the optimal answer, your code adds 1 to 0 and you get an array [1, 1, 5, 5]. Thus, the result will be equal to 0.

It turned out that we optimized the response using a non-existent element.

In a situation where the array is of odd length, you need to use another method — immediately add the minimum value in the array to the answer and then remove it from the array, thereby making it an even length

→ Reply

5 weeks ago, # ^ |

wow i wasn't expecting an answer so well explained lol. thanks a ton, i understand it now.

honestly i feel i could easily be cyan but i always mess up small things like this, for example related to the range of inputs, such as writing >x instead of >=x for some loop, etc. and realizing that after wasting 25 minutes on that. since you're blue do you have any suggestions for me?

→ Reply

denk

5 weeks ago, # ^ |

The best practice will be to solve implementation tasks outside the contest and set a goal to pass the task the first attempt. That is, spend a lot of time checking all the key points of the code and be 99% sure that all the places are implemented correctly.

In the contest itself, you can:

1) Write a naive solution for small values and compare the answers received with the code that you are going to send

2) Manually check the boundary values, experiment with the boundaries (try to change > to >= or even to <, try to change the data type (if an overflow occurs))

3) Check each part of the code and intermediate values separately (whether the array was built correctly, whether the answer is updated correctly at each step, whether the necessary variables are used everywhere, etc.)

Usually these steps are enough, if not immediately to send a solution without bugs, then after an incorrect attempt to quickly find where it can be the error and fix it

→ Reply

5 weeks ago, # ^ |

makes sense, thanks. i'll try solving a bunch of div. 2 Bs and Cs and try to get them right on the first try

→ Reply

sv1shan

5 weeks ago, # |

Is there a $$$ O(n^2) $$$ solution for F?

→ Reply

sstrong

5 weeks ago, # ^ |

just use hashmap

→ Reply

https://codeforces.net/contest/2004/submission/276639528

5 weeks ago, # |

← Rev. 2 →

too tight constraints for D. This is a QlogN and not passing? [EDIT SOLVED . I was declaring the vector again]

→ Reply

5 weeks ago, # ^ |

O(N+Q) is possible (via previous/next tables for all six pairs, for example), so this may be a TLE intentionally

→ Reply

https://codeforces.net/contest/2004/submission/276683926

5 weeks ago, # ^ |

But there will be only 4 pairs possible

with vectors+lower bound tle.

Do you mean to say the complexity is not O(qlogn) but O( (n+q)logn) ?

→ Reply

5 weeks ago, # ^ |

I meant to say that an O(n+q) solutions exist, so I'm not sure if O(qlogn) is intended to pass. As @rahulmysuru7 pointed out, your code runs even slower, so it's not relevant to you, I was just guessing what might be the reason

→ Reply

5 weeks ago, # ^ |

Ohh I see. I will think of N+Q solution too.

Thanks for the response <3

→ Reply

rahulmysuru7

5 weeks ago, # ^ |

← Rev. 2 →

@mahendraakshansh ~~~~~ for(int i=0; i<4 ;i++){ set ss = mp2[vv[i]]; .... ~~~~~

yeah ,you fked up here. you are declaring and extracting the entire set inside here. making your code O(qlog(n) * n)

→ Reply

https://codeforces.net/contest/2004/submission/276681345

5 weeks ago, # ^ |

fck me thank you so much.. I am a noob

→ Reply

Vitaly503

5 weeks ago, # |

+44

E is too educational even for educational round

→ Reply

newStartNotSure

5 weeks ago, # |

not sure why this is TLE?

→ Reply

vermish77

5 weeks ago, # |

I dont get my solution is of O(qlogn) but I am still getting TLE on sixth test case, tried so many things but still got tle on sixth, please tell where I am wrong my submission, My submission Link

→ Reply

umar.aligarh

5 weeks ago, # ^ |

you are copying the whole vector everytime in binsearch, this could be the issue vector vec=mpp[s];

→ Reply

vermish77

5 weeks ago, # ^ |

And, when I thought its better to be good at code writing , I fcked up. Thnx man got accepted

→ Reply

RoomTemperatureIQ

5 weeks ago, # |

+13

B is the hardest out of the first 5 tasks for me 😭 Also, how tf does E have like 1400 ACs? Do so many people know sprague grundy now?

→ Reply

5 weeks ago, # ^ |

apparently its a well known problem with solution on the internet, im just surprised so many ppl managed to actually implement D.

→ Reply

sandbag

5 weeks ago, # ^ |

B was also hardest for me. I wasted 20 minutes on casework before just (correctly) guessing the pattern. E was googlable.

→ Reply

Le_Gusto

5 weeks ago, # ^ |

I remember seeing a cf blog about game theory a few weeks ago that explained how to solve Nim problems, so that might be why

→ Reply

LJY--2002

5 weeks ago, # ^ |

so, How B? Help me please !

→ Reply

RoomTemperatureIQ

5 weeks ago, # ^ |

I just bruted for all bridges [i, i+1] upto 100 in the end

→ Reply

5 weeks ago, # ^ |

← Rev. 2 →

Break the problem in several cases.
ref : (https://codeforces.net/contest/2004/submission/276649235)
Case 1: When there is no overlap ----> only blocking one gate will work.
Case 2: When there is an overlap at exactly one point ----> Block two gates.
Case 3: When both the intervals are same ---> Answer will be difference between them.
Case 4: When all the 4 points given are distinct ---> answer will be diff b/w overlap region + 2
Case 5: When only 3 of them(l, r, L, R) are distinct ----> answer will be diff b/w overlap region + 1

Analyse all the cases in order on pen & paper you will get the idea.

→ Reply

isjaya

5 weeks ago, # ^ |

Oh I missed case 2, completely skipped my mind

→ Reply

5 weeks ago, # ^ |

Same here, took time to figure it out.

→ Reply

pmmitkovv

5 weeks ago, # ^ |

You can just consider the intersection of the two intervals(you need to place a door between every two cells). Then if there is anything to the left or right of the intersection you need to add 1 door for each case. In case the intersection is empty the answer is 1 as you pointed.

→ Reply

LJY--2002

9 days ago, # ^ |

thanks everyone

→ Reply

5 weeks ago, # ^ |

should I feel proud that the problem I found easiest was hardest for Candidate Master (even thought I could only solve till C) :///

→ Reply

_inferno_

5 weeks ago, # ^ |

← Rev. 2 →

no, as they have a room temperature iq

→ Reply

Karabutsa

5 weeks ago, # |

+61

Not a Nim problem

looks inside

a Nim problem

Why? Just, why?

→ Reply

Vassu05

5 weeks ago, # ^ |

← Rev. 3 →

+17

Fr I was not even thinking around the lines of NIM after looking at the title. 1400+ accepted submissions for that is crazy

→ Reply

JasamritRahala

5 weeks ago, # |

+17

One small step for man, a giant fall for my rating.

→ Reply

comebackking

5 weeks ago, # |

+12

Don't know why I hate L and R problems which have O(1) solution. Just hate the casework! P.S Talking about problem B

→ Reply

PaciukZvichainyi

5 weeks ago, # |

← Rev. 2 →

Damn, my programming skill is so bad that I couldn't implement C. The first test cases in problems are weak and doesn't help to find even some edge cases. E has no explanation for how Bob wins in the third case. Next year will be our year.

→ Reply

5 weeks ago, # |

+10

if u ever feel stupid then just know that I exist : wasted my whole contest on C only to realize it was total increase<=k, not k for every element

→ Reply

Au.

5 weeks ago, # |

The question of double negative sentences is very unfriendly to foreign contestants, which seriously affects the questioning, and I feel very angry about this

→ Reply

Aman_Garg

5 weeks ago, # |

Can someone pl look what is wrong in my implementation of D.

Link

→ Reply

teoet6

5 weeks ago, # ^ |

if it_low==pos.end() you should try finding the last position <= x

→ Reply

sandbag

5 weeks ago, # |

D was actually easier to implement than I thought after I realized you could iterate over the colors and only check when you found an overlap for both endpoints. Then just binary search on the nearest index.

Code

bool overlap(string&a, string&b) {
    if(a[0] == b[0] || a[1] == b[1] || a[0] == b[1] || a[1] == b[0]) return true;
    return false;
}

void solve(){
    int n, q; 
    cin >> n >> q;
    vector<string> v(n);
    for (int i = 0; i < n; i++) cin >> v[i];
    map<string, vector<int>> mp;
    vector<string> cols = {"BG", "BR", "BY", "GR", "GY", "RY"};
    for (int i = 0; i < n; i++) {
        mp[v[i]].push_back(i);
    }
    for (int i = 0; i < q; i++) {
        int a, b;
        cin >> a >> b;
        a--; b--;
        if(overlap(v[a], v[b])) cout << abs(a-b) << endl;
        else {
            int ans = 1e9;
            for (auto j : cols) {
                if(overlap(j, v[b]) && overlap(j, v[a])) {
                    if(mp[j].size()==0) continue;
                    int l = -1, r = -1;
                    int it = (lower_bound(mp[j].begin(), mp[j].end(), a)-mp[j].begin());
                    if(it-1 >= 0) l = it-1;
                    r = it;
                    int lid = (l != -1) ? mp[j][l] : -1;
                    int rid = r<mp[j].size() ? mp[j][r] : -1;
                    if(l != -1 && lid != -1) ans = min(ans, abs(a-lid) + abs(lid-b));
                    if(r != -1 && rid != -1) ans = min(ans, abs(a-rid) + abs(rid-b));
                }
            }
            // not sure if both loops are necessary, just did to be safe
            for (auto j : cols) {
                if(overlap(j, v[b]) && overlap(j, v[a])) {
                    if(mp[j].size()==0) continue;
                    int l = -1, r = -1;
                    int it = (lower_bound(mp[j].begin(), mp[j].end(), b)-mp[j].begin());
                    if(it-1 >= 0) l = it-1;
                    r = it;
                    int lid = (l != -1) ? mp[j][l] : -1;
                    int rid = r<mp[j].size() ? mp[j][r] : -1;
                    if(l != -1 && lid != -1) ans = min(ans, abs(a-lid) + abs(lid-b));
                    if(r != -1 && rid != -1) ans = min(ans, abs(a-rid) + abs(rid-b));
                }
            }
            if (ans==1e9) cout << -1 << endl;
            else cout << ans << endl;
        }
    }
}

→ Reply

godwriter

5 weeks ago, # |

A, B, C, D, F is fucking easy, especially E is just grundy number which is not suitable for an edu round!

→ Reply

rmz

5 weeks ago, # |

+12

fucking rooms

→ Reply

sakib.safwan

5 weeks ago, # |

← Rev. 2 →

For problem E, I found out quite early that I had to build grundy numbers for all possible number.

But I completely forgot all the theories. Almost all the time that I took for solving E was trying to figure out grundy again and for reading the question wrong and solving a wrong problem first. :3

→ Reply

5 weeks ago, # |

← Rev. 5 →

can anybody point out whats wrong with the below idea for D ? (since failing testcase 2 is not visible till end of hacking) Submission: 276681155

Spoiler

→ Reply

kwangg

5 weeks ago, # ^ |

Sounds right to me.(You mean "closest city to the right of y", not "largest city to the right of y", right?)

→ Reply

5 weeks ago, # ^ |

yeah i wrote that by mistake. I mean closest missing in the prefix of x and closes missing in the suffix of y. Looks like I effed up the code then. If you can take a look at it please ? (I assure you its written cleanly as much as possible.)

→ Reply

kwangg

5 weeks ago, # ^ |

Sorry, can't spot a bug immediately. Maybe there's some bug in the implementation detail in finding the closest city to the left or right? Some off-by-one error, maybe?

→ Reply

5 weeks ago, # ^ |

Yep, no problem, I'll find it somehow. Thanks a lot!

→ Reply

5 weeks ago, # ^ |

found it: did subsum[l,r] = (psum[r] — psum[l]) instead of (psum[r] — psum[l-1]) :'(

→ Reply

5 weeks ago, # ^ |

if i understood it properly, that is the solution. the hard part of this shitty problem was the implementation

→ Reply

Saivishwas

5 weeks ago, # ^ |

idea looks right, you might have made mistake in implementation.

→ Reply

5 weeks ago, # ^ |

thanks i'll debug against some AC solution I guess then.

→ Reply

crystaI

5 weeks ago, # |

← Rev. 3 →

I don't like problem B and E (because I had a hard time with them, obviously). B is a boring classification, and for E you only need to print out the table of SG function values and find the pattern. TBH I didn't feel the joy of solving Cf problems in these two problems.

→ Reply

https://codeforces.net/contest/2004/submission/276595377

5 weeks ago, # |

← Rev. 2 →

-7

just now I was searching for D solution on youtube and saw problem A,B,C ,E and F were uploaded there during contest

→ Reply

MonoLith

5 weeks ago, # |

my submission for problem b gave some negative number for first submission- https://codeforces.net/contest/2004/submission/276574322

and same solution got accepted after a few minutes-

if it is some kind of error from system then please recalculate penalty for this problem for me

→ Reply

crystaI

5 weeks ago, # ^ |

I don't think they can be called "same solution".

→ Reply

CSHwang

5 weeks ago, # ^ |

The calc function in the first submission calls R itself in calculating R, which is undefined behavior

→ Reply

T_C_D

5 weeks ago, # |

My code is producing the[submission:276685070] wrong answer, but I can't figure out why. Could someone help me identify the issue?

→ Reply

xygzy

5 weeks ago, # |

hmmmm whats wrong with my O(qlogn) solution for Problem D that got TLE on sixth test case? I realized that set::end is O(n) so i precomputed it in the what vector, but still didn't work. all other ops are O(1) or O(logn)

submission

→ Reply

indresh_hErd

5 weeks ago, # ^ |

Use s.lower_bound instead of lower_bound(s)

Former has O(logn) and latter O(n)

→ Reply

xygzy

5 weeks ago, # ^ |

yo what the heck! i had no idea. thank you so much. do you know why? same function yet big difference in time complexity.

→ Reply

indresh_hErd

5 weeks ago, # ^ |

You can see here set time complexity

→ Reply

sportik

5 weeks ago, # |

← Rev. 2 →

didnt got D in time cause wasted 1 hour on fckn annoying B, for what do shit like that? B in hour, C in 10 mins)

→ Reply

T_C_D

5 weeks ago, # |

Can someone help me?Your text to link here...

→ Reply

broErrichto

5 weeks ago, # ^ |

Your code looks correct, but you're getting a Wrong Answer (WA) on test case 5992. Unfortunately, I can't see the specific details of that test case

→ Reply

5 weeks ago, # ^ |

bro whattt

→ Reply

s_tapan005

5 weeks ago, # |

← Rev. 2 →

I am getting tle on test 5 can anyone help 276686377 even if the soln is qlog(n)

→ Reply

surya999

5 weeks ago, # ^ |

comlexity of your sol is n * q * log(n) see this accepted code using your code 276705976

→ Reply

s_tapan005

5 weeks ago, # ^ |

thank you so much I got it .

→ Reply

pessi_penaldo

5 weeks ago, # |

i have no idea why my D is failing, i found the indices of all 6 types of values closest to the left and right and did accordingly am i missing something. solution

→ Reply

5 weeks ago, # ^ |

You have made exactly the same mistake that I made.


ans=abs(x-pop[x][j][0])+abs(pop[x][j][0]-y);

→ Reply

https://codeforces.net/contest/2004/submission/276688327

5 weeks ago, # ^ |

← Rev. 2 →

You need to take,


ans = min (ans, abs(x-pop[x][j][0])+abs(pop[x][j][0]-y));

UPDATE :

That is exactly the issue. I copy-pasted your code, and changed one line. Proof :

→ Reply

pessi_penaldo

5 weeks ago, # ^ |

dude i am crying......, i was burning my blood for this :(

→ Reply

5 weeks ago, # ^ |

Happens, don't worry. Happened with me also, I got 2 wrong penalty submissions for this.

→ Reply

AlefHeKaaf

5 weeks ago, # |

+26

E wasn't new...

projecteuler560

→ Reply

5 weeks ago, # ^ |

This is allowed during Educational rounds. It's one reason why they aren't rated for Div 1.

→ Reply

shorya1835

5 weeks ago, # ^ |

Source for this please

→ Reply

https://codeforces.net/blog/entry/21496

5 weeks ago, # ^ |

-8

→ Reply

shorya1835

5 weeks ago, # ^ |

I don't think anything in the blog implies you can take exactly the same problem from somewhere else.

→ Reply

5 weeks ago, # ^ |

It's not exactly the same problem.

Project Euler asks you to calculate the number of losing positions with up $$$n$$$ stones in $$$k$$$ piles, while this round asked you to evaluate the winner for just 1 given position.

Looks to me like the CodeForces problem is strictly easier, except of course Project Euler has no fixed time limit.

It's true that the crucial insight behind the two problems is the same, so it's not completely new, but again, that's not unusual for Educational rounds and as far as I'm aware that's intentional.

→ Reply

shorya1835

5 weeks ago, # ^ |

Fair enough

→ Reply

g3t_kuhn

5 weeks ago, # |

Can someone explain to me why the code I submitted during the contest was rejected but if I submit the exact code with 0 changes after the contest it gets accepted? In fact I modified the code to get the test cases where it was failing at and that code got accepted when I thought it is obviously wrong.Can someone go to my submissions and check?

→ Reply

pkhaustov

5 weeks ago, # |

-91

awoo Why for Div2+ rounds you keep giving problems where cheating is extremely simple? No implementation, but only one critical observation which is extremely easy to pass from a cheater to another cheater.

→ Reply

5 weeks ago, # ^ |

← Rev. 2 →

-18

Since you are giving feedback to Awoo, regarding the contest. I would like to chime in.

I didn't google a shit during the contest. usually I don't. For me, E was really good problem. except for one part, extra BOILER PLATE IMPLEMENTATION for sieve.

I would like to understand what was the motivation to keep pile sizes 10^7 instead of 10^5.

The problem would have been same, if the pile sizes were within 10^5. The core-crux of the solution logic would be same. generating prime till 10^7 and then doing extra implementation things, were more of boilerplate code.

→ Reply

5 weeks ago, # ^ |

Maybe so you can't completely bruteforce the Grundy numbers and actually have to come up with the "Grundy number of x is the Grundy number of its least prime divisor"? That would make sense in my opinion.

→ Reply

5 weeks ago, # ^ |

← Rev. 2 →

yeah, makes sense.

→ Reply

5 weeks ago, # ^ |

← Rev. 2 →

What problems are you talking about? C? For B and D, implementing a solution correctly is IMO much harder than coming up with it. For E, you still need to know about Grundy numbers and not screw up calculating for the small piles. And pretty much every single A is easy to implement, because it's supposed to be really easy, so there's not much organizers can do with that.

→ Reply

pkhaustov

5 weeks ago, # ^ |

-29

I spoke about problems D and E in particular. Ok, please tell me if these solutions for B and D look hard to implement. Do they?

→ Reply

5 weeks ago, # ^ |

I didn't realize B is just bruteforce-able like that and was thinking of an O(1) per query solution. I agree doing this is easy. As for D, I don't think your implementation is particularly easy, and looking at the comments, there's a bunch of people with the correct idea that failed to implement it, so I stand by it being difficult to implement.

→ Reply

shiven

5 weeks ago, # ^ |

B in O(1) per query. Need to block full intersection, additionally extending it by one on each side if needed.

→ Reply

5 weeks ago, # |

Not that great of a contest IMO. A and C are fine, but B is just annoying casework, D is basically just implementation, and while I enjoyed E, it's googleable.

→ Reply

LordLouis04

5 weeks ago, # ^ |

In B u can only check if 'i' is in one segment and i+1 in the other segment for every i in [1,99] then add 1 to the answer, there's no need for casework.

→ Reply

5 weeks ago, # ^ |

True, didn't realize that doing contest. Doesn't really change my opinion about quality of the problem though, as the fastest solution still suffers from this, and I personally dislike when there's a fast solution that's more complicated than a (significantly) slower one, yet the slower one still passes everything.

→ Reply