Codeforces Round #818 (Div. 2)

2 years ago, # ^ |

← Rev. 2 →

-7

imo yes, even a complete beginner should still attempt Division 2 contests. It's a good experience in the contest environment, and it's still notable to be able to solve even just one problem. Just don't go in with high expectations for how many problems you solve; focus more on your practice and growth and not on how high (or low) you are in the standings. It's primarily through consistent practice that you improve, so I highly recommend participating in ALL contests! Even upsolving D1A after reading the editorial after thinking about it for 2 hours should be good.

→ Reply

rengoku69

2 years ago, # |

the crewmates are bumping onto each other like how my submission does when they encounter special test cases.

→ Reply

Abito

2 years ago, # |

Amogus themed Round! Will use the Amogus Trick to AK the round

→ Reply

2 years ago, # ^ |

It's just cute picture(

→ Reply

Abito

2 years ago, # ^ |

Oof. Still the amogus trick can do something XD

→ Reply

2 years ago, # ^ |

what if the two in the pic were both imposters tho

→ Reply

Abito

2 years ago, # ^ |

← Rev. 2 →

hmmm

→ Reply

thqhuong

2 years ago, # |

Spoiler

→ Reply

2 years ago, # |

← Rev. 2 →

+14

AmongUsForces

→ Reply

mdibuhossain

2 years ago, # |

→ Reply

PraveenRajS

2 years ago, # ^ |

2022 — memes on memes :)

→ Reply

Jhin

2 years ago, # ^ |

2020 good times I created that era (my previous username was SupaHotFire)

→ Reply

lis05

2 years ago, # |

amogugus

→ Reply

HGud_TK

2 years ago, # |

Hey I'm new and I use java. Is their a problem because of the higher runtime?

→ Reply

bless01

2 years ago, # ^ |

Not an issue bro, though it is a little slower than CPP, but still you can solve all the questions in java if you caught up the problems. You can check submissions, there are thousands of java users like you and at a good ranking. Best of luck.

→ Reply

HGud_TK

2 years ago, # ^ |

ty bro

→ Reply

mr-strange

2 years ago, # |

Hope Task would be Fine !!

→ Reply

2 years ago, # |

Hi, I am new to Codeforces. I've participated in 6 rounds so far. The last round I participated in was Codeforces Round #817 (Div. 4). There was a small rating change. I want to know on what basis the ratings are updated after the contest. I also came across hacking where participants can see others' submissions and provide test cases where their code fails (if any). For Codeforces Round #817, it was mentioned that the hacking phase lasts for 12 hours. Post contest, this is usually the time I sleep. I wanted to know if there's any specific reason for exactly 12 hours provided for hacking. I am new to Codeforces blog too, so apologies if this information is already available anywhere else.

→ Reply

lbm364dl

2 years ago, # ^ |

Hacking phase only exists in educational, div3 and div4 rounds. I don't know if there is any reason for hacking being 12 hours, but I suggest you focus on solving the problems, which is the most important part, so don't feel bad for not being in hacking phase. Personally I've never cared about it. I think you can't even get points yourself, you can only make others lose their ranks.

→ Reply

2 years ago, # ^ |

Hi, thanks a lot for explaining. So, there's no hacking phase for this round, right?

→ Reply

lbm364dl

2 years ago, # ^ |

Yes, that's right, speaking about proper hacking phase after the round. You can still hack during any round after locking the problem.

→ Reply

secret-void

2 years ago, # ^ |

Your ratings are updated based on the problems you solve in the contest and the average rating of others who could solve those problems. (Use CF-Predictor to get expected updated ratings before they are finally updated on codeforces).

→ Reply

2 years ago, # ^ |

Okay. How about Div 2 and Div 1 contests? Div 1 Contests are rated for everyone, right? Why is only one leaderboard used then?

Like, in CodeChef, each division has its own leaderboard. It allows comparing our performance with that of participants belonging to the same division.

→ Reply

2 years ago, # ^ |

+16

Thx bro for the story

→ Reply

2 years ago, # ^ |

Hi, can you suggest any application to extract sample input and output for all problems in a contest, for VS Code?

→ Reply

lite_27

2 years ago, # ^ |

competetive companion https://chrome.google.com/webstore/detail/competitive-companion/cjnmckjndlpiamhfimnnjmnckgghkjbl

→ Reply

2 years ago, # ^ |

Okay. That sounds good. By the way, can we access problems without logging in? For example, if I developed my own sample extractor, I would want it to work without signing in.

→ Reply

nowadays-

2 years ago, # |

Good luck

→ Reply

uraqt

2 years ago, # |

Hope to become an Expert :')

→ Reply

chenyanlin

2 years ago, # ^ |

Good wish to you！

→ Reply

ajstyle_

2 years ago, # |

Hoping to reach specialist.

→ Reply

Hunter-2.0

2 years ago, # |

I just wrote this to make numbers of comments 69 :)

→ Reply

karanarjunjr

2 years ago, # |

-25

By far the worst contest I've ever attended.

→ Reply

EmilyBloom

2 years ago, # |

-8

Div 1.5 :'(

→ Reply

shihap

2 years ago, # ^ |

5555

→ Reply

2 years ago, # |

-8

i mean why someone would do that in problem b thats pure evil

→ Reply

karanarjunjr

2 years ago, # ^ |

+11

IMHO B was easier than A

→ Reply

2 years ago, # ^ |

-12

not really even after i got an idea i stucked in implementing it then it got rte we can discuss further after the contest end if u want but i see its harder than a im sure

→ Reply

2 years ago, # ^ |

well, almost everytime, B is easier than it looks.

→ Reply

2 years ago, # |

+54

Thanks for the good contest, tasks are really interesting. But can you answer one question, please? Why tasks A B and D are pure maths without any competitive programming at all? I like ad-hocs, but this is too much.

→ Reply

2 years ago, # ^ |

← Rev. 2 →

+37

Because they are beautiful in my opinion)

→ Reply

2 years ago, # ^ |

I agree, they are beautiful, liked them (only B is very well-known) :)

A and B is normal thing to have pure maths, but not D, especially with such A and B.

→ Reply

0-jij-0

2 years ago, # ^ |

+18

I can see why A and E could be considered pure math, D has some math component but is not just math. But what is math about problem B? It's just about rotating diagonals.

→ Reply

2 years ago, # ^ |

-8

I was solving such a problem during the math contest in 5th school grade.

→ Reply

0-jij-0

2 years ago, # ^ |

Well sure, but it still doesn't make the problem a math problem, unless there's some math concept involved in it.

→ Reply

AccountDeleted

2 years ago, # ^ |

-20

you should probably think more about ppl who have more ability in CP than maths

→ Reply

rarecoder_00

2 years ago, # ^ |

-11

Are you giving the contest from your alt account ?? Wind_Eagle

→ Reply

2 years ago, # ^ |

← Rev. 2 →

-8

I'm just reading and trying to solve the problems without submitting :)

→ Reply

2 years ago, # ^ |

no he registered unofficially and just looked at it I think

→ Reply

sasasa_spring_test_125

2 years ago, # |

Feel REALLY grateful to the authors as I got AK for the first time.

→ Reply

sristy_shreya

2 years ago, # |

This was my first contest. Problems were too difficult for me

→ Reply

Cooper1214

2 years ago, # ^ |

Usually, problems are way more easy in Div 2. It's just bad timing for you. Keep practicing, you will rock soon ;)

→ Reply

dXqwq

2 years ago, # |

+37

F is very classical, I don't like it :(

→ Reply

towrist

2 years ago, # ^ |

+10

D and E are very classical too.

→ Reply

cirex

2 years ago, # ^ |

D is classical? Do you have any problems that are similar to it?

(I thought it was pretty unique lol)

→ Reply

DmitriyAnikeyev

2 years ago, # ^ |

-22

Yeah, I took my solution for recent contest https://codeforces.net/contest/1696/problem/E and literally changed input parsing and 1 line

→ Reply

DitaMirika

2 years ago, # |

+31

D is a good problem (In fact I don't think it is a pure Maths problem,you can realize the answer easily if you think about the problem in another way).

And I think E is much easier than D...(Just my opinion)

→ Reply

amber_100

2 years ago, # ^ |

Same

→ Reply

adityagamer

2 years ago, # |

How to solve D?

→ Reply

2 years ago, # ^ |

+12

Let's construct a full-binary tree, some edges will have a weigth of 1, the others will have 0, depending on whether the player wins or not. Then we'll notice that if we sum up all the weights on the way to the root, the player can possibly win the tournament only and if only it is at least n — k. Then we can code every path in a row of n 0s and 1s, where 0 means going to left node and 1 means going to right node (it doesn't matter if we say that every left edge is losing and every right is winning). So we need to have at least n — k ones. That means we can calculate the answer as the sum of C(n, i), where i is in the range [n — k, n]

→ Reply

vishnus

2 years ago, # ^ |

Great explanation, thanks.

→ Reply

CharlesWuQiushi

2 years ago, # |

← Rev. 2 →

+14

I was first surprised by the appearing of 'Madoka' in the titles, thinking 'some interesting background stories are gonna show up'. But now I'm a bit disappointed, as none of the statements have strong connections between the character or the anime itself, and the only common point is the name 'Madoka'...

But anyway, in spite of that, I would like to appreciate how clear and short the statements are.

→ Reply

Gpish

2 years ago, # ^ |

Hi, could you please explain, how you thought about problem C. I mean i've seen some solutions now, and see that its based on the final array B, and wheather it can be reached. But how did you prove that?

→ Reply

2 years ago, # ^ |

← Rev. 6 →

Here's how I thought about it:

If $$$a_i > b_i$$$, this is obviously impossible to achieve.

If $$$a_i == b_i$$$, this index is fine, no changes needed.

If $$$a_i < b_i$$$, then $$$a_i$$$ needs to increase (to $$$b_i$$$). This can only be achieved if $$$a_{i + 1}$$$ eventually becomes $$$b_i - 1$$$ at some point. This requires $$$b_{i + 1} \geq b_i - 1$$$ (otherwise you wouldn't want to increase $$$a_{i + 1}$$$ to $$$b_i - 1$$$).

This gives us two necessary conditions:

$$$a_i \leq b_i$$$ for all $$$i$$$
for each $$$i$$$ such that $$$a_i < b_i$$$, we must have $$$b_i \leq b_{i + 1} + 1$$$

As for why they're sufficient, this isn't a formal proof, but here's my intuition. The smallest element in $$$a$$$ is always eligible for an increase. If this element is already at its target value, then the element before it is either at its target value or it is below its target value and also eligible for an increase (condition #2). If it's at its target value, we can check the element before it and so on. This backwards scan guarantees that, if the two necessary conditions are fulfilled, then either all elements are at the target, or there will exist some element that is able to increase and is below its target value. This property is preserved after incrementing this element, so as slow as this process may be, eventually every element will reach its target, allowing us to efficiently answer YES without having to actually perform these operations.

→ Reply

RAiNcalleER

2 years ago, # ^ |

← Rev. 2 →

2nd Div 2 winner: Akemi-Homura

I can see why...

→ Reply

2 years ago, # |

So how exactly are we supposed to compute $$$\sum_{i = 0}^k {n \choose i}$$$ in modulo $$$10^9 + 7$$$? I get that we can reduce the problem to have $$$k$$$ below half of $$$n$$$, but the division by $$$k!$$$ under a modulo operation blocked me from completing D...

→ Reply

DitaMirika

2 years ago, # ^ |

← Rev. 2 →

+10

There is a way to make division into multiplication under modulo called seeking invers.

→ Reply

WolfBlue

2 years ago, # ^ |

You can observe that when k > n, the answer is just 2^n. Thus, k is bounded above by 10^5. Now you can just compute each term in constant time (compute each n choose i from n choose i — 1)

→ Reply

2 years ago, # ^ |

Yeah, I realized the $$$2^n$$$, but I still don't see how we can compute $$$n \choose i$$$ from $$$n \choose i - 1$$$ when there is a modulo operator involved, since the computation of $$$n \choose i - 1$$$ involves a division with $$$i - 1$$$

→ Reply

DitaMirika

2 years ago, # ^ |

+30

$$${ n \choose m } = \frac{n!}{m! \times (n-m)!}$$$

And $$$\frac{x}{y} \bmod p$$$ equals to $$$x \times y^{p-2} \bmod p$$$

→ Reply

2 years ago, # ^ |

+28

Thank you so much! I looked it up and learned about Fermat's Little Theorem, which finally allowed me to get an Accepted submission. Although, I couldn't solve this problem during the contest, I think I learned more from this experience than any of the other contests I did in the last few months. I used to feel like the modulo answers blocked division, but now I learned how wrong I was. Thank you!

→ Reply

BULLMCHOW

2 years ago, # ^ |

Can someone explain problem D?

→ Reply

2 years ago, # ^ |

← Rev. 2 →

The minimum winner that Madoka can guarantee is equal to the number of possible winners if the sponsors are allowed to make $$$k$$$ changes. If there are $$$r$$$ possible winners, then Madoka would rearrange them to be labeled $$$1$$$ to $$$r$$$, so that regardless of how the sponsors make their changes, the winner will be at most $$$r$$$.

Consider the path of the winner from the root to the bottom level as a binary sequence of left and right turns. There are $$$n$$$ edges in total, so the binary sequence has length $$$n$$$. The sponsors can change up to $$$k$$$ of the elements. Each distinct sequence leads to a unique participant. Therefore, the number of possible winners is $$$\sum_{i = 0}^{\min(n, k)} {n \choose i}$$$. Calculating this modulo $$$10^9 + 7$$$ is where I got stuck...

→ Reply

spookywooky

2 years ago, # ^ |

Why $$$min(n,k)$$$ and why $$${n \choose i}$$$ ?

→ Reply

2 years ago, # ^ |

← Rev. 2 →

Here's an example: suppose $$$n = 5$$$, and Madoka decided that it will always be the left contestant that wins. Then we can describe the path from the root (champion) to the leaf (bottom level) as LLLLL. This leads to one possible victor. Treat the order of the participants at the bottom as fixed (Madoka can optimize the initial setup, but it doesn't change once she makes her decision).

The sponsors can make up to $$$k$$$ changes. If they change the outcome of the final match only, then the path becomes RLLLL (you can also think of it as LLLLR, but it doesn't affect the conclusion). Or maybe they leave the final match as L and change the semi-finals to R, so the path becomes LRLLL. Or maybe they make the would-be champion lose on their first round, so the sequence is LLLLR. Every distinct sequence leads to a different leaf at the bottom, i.e., a different champion.

So now the question is, if you can flip at most $$$k$$$ elements of this sequence, how many possible distinct strings can you produce? If you flip exactly $$$i$$$ elements, for $$$i \leq n$$$, then you need to choose which $$$i$$$ elements out of $$$n$$$ they will flip, of which there are $$$n \choose i$$$ possibilities. Even if $$$k > n$$$, the sequence has length $$$n$$$, so it doesn't matter if you can make more than $$$n$$$ changes (the champion victory path only relies on the outcome of $$$n$$$ matches). In fact, $$$k \geq n$$$ results in an answer of $$$2^n$$$ since every possible sequence of length $$$n$$$ can be achieved (allowing every contestant to have the possibility of being the champion).

→ Reply

EasonCookie197

2 years ago, # |

← Rev. 2 →

I think E is a bit standard?

D is cool though :)

→ Reply

MoLotfi

2 years ago, # ^ |

Can you give me a hint for E?

→ Reply

EasonCookie197

2 years ago, # ^ |

Spoiler

→ Reply

sharmaharisam

2 years ago, # ^ |

Spoiler

→ Reply

Ammar2001s

2 years ago, # |

I solved $$$B$$$ and $$$C$$$ and still can't figure out A !

I found a solution but it got MLE, any hints?

→ Reply

NTTilted

2 years ago, # ^ |

think about number which can make pair with number x(only 2 * x and 3 * x are suitable)

→ Reply

SourabhCh

2 years ago, # ^ |

The eqn can be written as (a*b)/(gcd(a,b))^2 <=3

→ Reply

Deadmanalive

2 years ago, # ^ |

please explain how u approach after getting this inequality

→ Reply

BallBreaker

2 years ago, # ^ |

Okay

let's gcd of a and b equal D

Then a=D*X and b=D*Y where gcd of X and Y equal 1.

a*b/gcd(a,b)=lcm(a,b)

XYD=lcm(a,b) XYD/D=XY

SO you need to find pairs of numbers like x,x/3

x/3,x

x/2,x

x,x/2

x,x

→ Reply

2 years ago, # |

Solved E in 15 mins, couldn't solve D((

And again i have 1-4 points left to become CM (4th time already)

Life is sad

→ Reply

2 years ago, # ^ |

Knew how to solve D as soon as I started drawing out examples. Spent the last 1 hour on E and still couldn't do it...

→ Reply

2 years ago, # ^ |

+15

We're all different))

→ Reply

2 years ago, # ^ |

← Rev. 2 →

+13

I can't get it, for me D was much easier than E, as for me E seems almost impossible, while D is acceptable. Any hints for E maybe?

→ Reply

lbm364dl

2 years ago, # ^ |

← Rev. 2 →

I kept thinking there must be a way to iterate to get $$$O(n \sqrt{n})$$$. Try to do some manipulations on the formula in order to be able to iterate over $$$c$$$ and over the value of some gcd expression, such that the value of this gcd expression is the same for some tuples, and you should count them and just multiply. That was my reasoning, I hope it gives you an idea.

My formula

→ Reply

2 years ago, # ^ |

← Rev. 2 →

Hint 1

Hint 2

Hint 3

Hint 4

hope this helps))

→ Reply

2 years ago, # ^ |

Thank you

→ Reply

2 years ago, # ^ |

You are welcome

→ Reply

justin2009

2 years ago, # |

Well, that's like mathforces :(

→ Reply

physics0523

2 years ago, # |

+23

I think A is so hard for D2A, was there easier solution?

my submission

#include<bits/stdc++.h>
 
using namespace std;
 
int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
 
  vector<pair<int,int>> ab={
    {1,1},
    {1,2},
    {1,3},
    {2,1},
    {3,1}
  };
 
  int t;
  cin >> t;
  while(t>0){
    t--;
    int n,res=0;
    cin >> n;
    for(auto &nx : ab){
      res+=n/(max(nx.first,nx.second));
    }
    cout << res << "\n";
  }
  return 0;
}

→ Reply

Dct_tcD

2 years ago, # ^ |

n + 2*(n/2 + n/3)

→ Reply

jakubd

2 years ago, # ^ |

← Rev. 4 →

n + (n // 2) * 2 + (n // 3) * 2

→ Reply

0-jij-0

2 years ago, # ^ |

In the prime decomposition of $$$A$$$ and $$$B$$$ there shouldn't be any different power of primes $$$> 3$$$. Also there can either be one more 2 OR one more 3 but not both. Hence either same number $$$(N)$$$ or pair $$$(x, 2x)$$$ $$$(2(N/2))$$$ or pair $$$(x, 3x)$$$ $$$(2(N/3))$$$ and we multiply by 2 to account for ordered pairs

→ Reply

2 years ago, # ^ |

Yes, you may have pairs as follows:-

$$${(x, x), x \le n}$$$
$$${(x, 2 * x), x \le n /2}$$$
$$${(2 * x, x), x \le n / 2}$$$
$$${(x, 3 * x), x \le n / 3}$$$
$$${(3 * x, x), x \le n / 3}$$$

So no of pairs = no of pairs of each above types = n + n / 2 + n / 2 + n / 3 + n / 3.

→ Reply

Sulfox

2 years ago, # |

← Rev. 2 →

+23

Can Problem E be solved in $$$O(n \log n)$$$?

→ Reply

E-space

2 years ago, # ^ |

+15

you could probably do it using sieveing the phi function, but $$$O(n\ln n\sqrt n)$$$ is easier to implement.

→ Reply

timreizin

2 years ago, # ^ |

+15

How did you solve it?

→ Reply

Sulfox

2 years ago, # ^ |

I mistyped the index, sorry

→ Reply

2 years ago, # ^ |

Yep)

→ Reply

2 years ago, # ^ |

← Rev. 2 →

+28

Mangooste solve in testing in $$$O(nlog)$$$

→ Reply

2 years ago, # ^ |

← Rev. 3 →

jianlgy's solution is $$$O(n \log n)$$$

→ Reply

2 years ago, # ^ |

← Rev. 2 →

Okay, I'm sorry, it's not completely $$$O(n \log n)$$$ because of std::lcm, but you can precompute them (there are only n pairs he needs)

→ Reply

kame721

2 years ago, # |

Some contests (like this one!!), just ends up giving u loads of depression and self-doubt !! wasn't even able to solve A !!! feels like sh*t !!

→ Reply

jimm89

2 years ago, # ^ |

+26

Yeah we've all been there, but try to rationalise — it's one problem. It was tough for Div 2A. It doesn't undo all the problems you can solve and have solved.

→ Reply

faizanhussain2310

2 years ago, # |

For C firstly I make all elements of array a which are smaller than smallest element of array b equal to smallest element of b now i got one element where a[i]=b[i] now i just traversed backward and check for for all other a[i]'s

isnt my approach for C correct ??

→ Reply

indreshsingh

2 years ago, # ^ |

← Rev. 3 →

Consider the case
5
3 4 1 4 1
4 4 2 4 2

→ Reply

faizanhussain2310

2 years ago, # ^ |

Thanks for replying just see the test where it was failing it just that i had to put OR there but i had put AND

Wrong Solution : https://codeforces.net/contest/1717/submission/170638678 Accepted Solution : https://codeforces.net/contest/1717/submission/170649100

→ Reply

epsilon_573

2 years ago, # ^ |

Video Solution for Problem C

→ Reply

2 years ago, # |

question about problem C: how did this massive lump of spaghetti pass the systests? I can't prove my solution. 170616890

→ Reply

palad

2 years ago, # ^ |

Your solution fails for a few cases, one of which includes this:

1
5
1 2 3 4 5
15 15 15 15 15

It should output "YES", whereas your solution is returning "NO".

"YES" because:

1 2 3 4 5 changes to 5 5 5 5 5,

and then to 6 6 6 6 6,

and so on until 15 15 15 15 15.

→ Reply

2 years ago, # ^ |

oh so it actually was a massive lump of spaghetti which doesn't even work properly. damn.

→ Reply

bart320

2 years ago, # |

+96

This A is way too hard and math-heavy for a decent Div2A and it can be seen as "guess from the samples" (especially considering the answer for $$$1\,000\,000\,000$$$ being provided).

Please don't do such Div2As, because you are scaring newcomers and biasing the rating changes for greens and grays (i. e. lots of contestants don't submit anything if Div2A is too hard, so they are skewing ratings).

→ Reply

AccountDeleted

2 years ago, # ^ |

agree

→ Reply

2 years ago, # ^ |

Kinda right, but in actuality it turned out to be relatively easy to solve.

→ Reply

robinOP

2 years ago, # ^ |

sampleforces

→ Reply

adityagamer

2 years ago, # ^ |

+27

Maybe, CF should adopt Atcoder style registration: Rating will drop even if you don't submit anything.

→ Reply

palsatyam877

2 years ago, # |

I submitted B twice which are almost similar beacuse of my second my first submission is skipped.

→ Reply

LinkWish

2 years ago, # |

+31

It's the fastest system test of div.2 as far as I know.It just took about 15min .

→ Reply

2 years ago, # |

Am I not mistaken? The system testing was fast as fuck, wasn't it?

→ Reply

LinkWish

2 years ago, # ^ |

But system tests of contests I've taken usually took me about 1 hour , so I feel that's so fast today.

→ Reply

liouzhou_101

2 years ago, # |

← Rev. 2 →

+53

I got suck in problem A for twenty minutes. The hardest D2A I've ever met!

→ Reply

nicolasalba

2 years ago, # ^ |

Me too :'(

→ Reply

om1429888

2 years ago, # ^ |

for 1 hour.then i picked up pen and paper and did it.

→ Reply

LinkWish

2 years ago, # ^ |

I think so , this problem A isn't as easy as before .

→ Reply

AaronHe

2 years ago, # ^ |

Yeah that surprised me a little bit. Managed to figure it out by realizing it was equivalent to a/gcd * b/gcd <= 3 and then I did some casework.

→ Reply

MODDI

2 years ago, # ^ |

To add values to the answer is cyclic, I noticed this with bruteforce than it was cake

→ Reply

2 years ago, # |

← Rev. 2 →

This prolly was the fastest system testing I have ever seen, wow

→ Reply

demonstrator

2 years ago, # |

+10

My solution should not pass But It is passing . Weak Tests I must say 170648782 1 4 1 1 1 1 40000000 40000000 40000000 40000000

→ Reply

LinkinPony

2 years ago, # |

+29

How to understand D's statement?

→ Reply

attiw

2 years ago, # |

← Rev. 2 →

For problem B for 1st testcase why is this answer wrong ?

X..
X..
.X.
XX
XX
.X..X.
X..X..
X..X..
.X..X.
X..X..
X..X..

→ Reply

2 years ago, # ^ |

← Rev. 2 →

3rd column in 3rd case is completely empty, I can pick 1*k vertical segment without X in it.

→ Reply

attiw

2 years ago, # ^ |

Thanks. I passed now.

→ Reply

2 years ago, # ^ |

'cause you got

X..
X..
.X.

Which leaves the rightmost column empty so it doesn't satisfy the requirement.

→ Reply

UUUnmei

2 years ago, # |

+41

honestly, D statement is a bit hard to read and understand

→ Reply

2 years ago, # ^ |

+18

Yep. But it's fun to solve. The most elegant task out of A-D in my opinion.

→ Reply

r57shell

2 years ago, # ^ |

+34

It's not just hard to read, it's awful and ambiguous. You have to guess things which is not clearly stated in the statements. It's not stated that after sponsor changed outcome for other matches left still win if left was winning before. Also,

Print the minimum possible number of the winner in the tournament, which Madoka can get regardless of changes in sponsors.

In example if sponsor changes outcome of finals, Madoka would get number 2, which is obviously less than 3, and isn't it smaller? If sponsor decide to always do this for this tournament, Madoka can't get 3 regardless, because winner is 2.

→ Reply

https://codeforces.net/contest/1717/submission/170648846

2 years ago, # ^ |

-10

regardless means that we need to minimise the maximum of all possible outcomes

→ Reply

UrAniMaTiX

2 years ago, # |

+36

Good to see some coding questions in a maths contest!

→ Reply

Iratis

2 years ago, # |

+17

The system test is so fast.Good job!

→ Reply

mishgun

2 years ago, # |

Why task C solved in O(n) on pypy3 has TL? https://codeforces.net/contest/1717/submission/170628126

→ Reply

ntarsis30

2 years ago, # ^ |

← Rev. 2 →

+10

You should use sys.stdin.readline() and sys.stdout.write for fast python i/o when a problem has a lot of cases. https://codeforces.net/contest/1717/submission/170651067

→ Reply

faelitna

2 years ago, # |

During the contest I used pypy3 in problem C, and got TLE in the system test. (And I tried to resubmit, this time it got AC within 997ms.)

However the same code got AC using python3 within less than 600ms. This makes me really troubled.

Here are the url of the two submissions. The first one is pypy3, and the second is python3.

https://codeforces.net/contest/1717/submission/170648671

This is a profound lesson, which tells me that the I/O function of pypy3 is slower than python3.

Besides, I think the tip of "Almost always, if you send a solution on PyPy, it works much faster" when submitting python3 should be updated. At least it should be modified to "most time" instead of "almost always".

→ Reply

Remineva

2 years ago, # ^ |

Same here.

→ Reply

_DuMoH4uK_

2 years ago, # |

Maths-forces

→ Reply

rigvedinho

2 years ago, # |

← Rev. 6 →

Can someone tell me what's wrong with my submission? (for B) https://codeforces.net/contest/1717/submission/170645855

My logic:

Spoiler

Would be really grateful if you could post a counter test case, thanks!

EDIT: Figured it out, ty

→ Reply

2 years ago, # ^ |

Your code fails at multitest test cases. Try

2 10 10 1 1 8 2 1 1

→ Reply

Gpish

2 years ago, # |

Can someone please explain to me, how they thought about problem C and how you arrived at the observations?

→ Reply

2 years ago, # ^ |

Let me try:

Let prev be the previous element and cur be the current element. Since we can only increment the previous element under the given conditions, it means that the prev-1<=cur OR a[i-1]==b[i-1] where i is index of current element and i-1 = prev. Also, elements can't be decreased, so all b[i]>=a[i] for all i. This gives a conclusion that if (b[i-1]-1>b[i] OR b[i]<a[i]) AND a[i]!=b[i], b can't be obtained from a.

I hope this makes sense.

→ Reply

2 years ago, # ^ |

← Rev. 3 →

Try solve an easier version of C: Print a configuration with minimum X that satisfies that there's at least one X for every subarray of size (1,k). The obvious answer is that there will be exactly n/k evenly spaced Xs on each row.

Now try solving the whole problem: There should be at least one X for every subarray of size (1,k) and (k,1). Again, notice there's exactly n/k evenly spaced X on each column, then the idea becomes obvious that you need to shift the X position of some rows until it satisfies both condition.

This is how I found the solution during the contest.

→ Reply

2 years ago, # ^ |

sorry but isn't that B, not C

→ Reply

2 years ago, # ^ |

Oh oops I mixed up the problems.

→ Reply

Citypop

2 years ago, # |

Any hint for D?

→ Reply

_DuMoH4uK_

2 years ago, # ^ |

-8

Think about Pascal's triangle

→ Reply

r57shell

2 years ago, # ^ |

← Rev. 2 →

hint

→ Reply

2 years ago, # |

can someone tell me the idea of b?

→ Reply

2 years ago, # ^ |

Hint

→ Reply

https://codeforces.net/contest/1717/submission/170632638

2 years ago, # ^ |

i see that its distributed on diagonals the number of Xs in every diagonal start increasing then it reaches a point where the diagonal contains the point r, c then it decrease is that what u meant? i tried to implement this idea but got wa2 don't know if this what do you mean

→ Reply

2 years ago, # ^ |

Hint 2

→ Reply

2 years ago, # ^ |

Hint 1

Hint 2

Hint 3

Now, you may have filled the 'X's in the following way for the 3rd sample.

X..X..
.X..X.
..X..X
X..X..
.X..X.
..X..X

So now? what to do with cell $$$(r, c).$$$

Hint 4

→ Reply

arda

2 years ago, # |

Am I the only one who solved C but couldn't solve B?

→ Reply

Hyrulia

2 years ago, # |

+11

Make A easy please, people will give up the contest quickly if they can't solve A..

→ Reply

Ayham_Dabah

2 years ago, # |

The problems were somehow interesting but most of them were math (very close to pure math).... It makes this round less than a good round

Did the testers give their opinion about this? I blame them too if they did not

→ Reply

islam231

2 years ago, # |

Any idea why A solution is (n + n / 2 * 2 + n / 3 * 2 ) ?

→ Reply

2 years ago, # ^ |

← Rev. 5 →

Without loss of generality we can assume for all pairs (a,b) that a <= b.

if b is divisible by a, then gcd(a,b) == a ,lcm(a,b) == b (and vice versa). In this case, It's obvious that the only correct pairs are (b/3,b) (b/2,b) (b,b). The number of pairs are n/3, n/2 and n respectively. To count the pairs with a > b, just swap (b/3,b) and (b/2,b) to (b,b/3) and (b,b/2)

Now let's try to prove that there's no pair in which a and b aren't divisible by each other. if b is not divisible by a, then gcd(a,b) <= a/2, lcm(a,b) >= b*2. We know this because a/2 is the largest possible divisor of a that isn't equal to a and b*2 is the smallest possible multiple of b that isn't equal to b. Obviously lcm(a,b) / gcd(a,b) >= (b*2) / (a/2) >= 4 because a <= b.

→ Reply

SalmaHatem_

2 years ago, # ^ |

Try to write the TLE solution with nested loop and then observe the equation.
Really, It is a pure math problem!◑﹏◐

→ Reply

2 years ago, # ^ |

Let me try:

There are n (a,b) pairs where a=b. Their gcd of (a, a)=a and lcm of (a, a)=a. a/a=1<=3; So there are at least n pairs under the given conditions.

Let a<b(a=b case already covered above). LCM of (a, b) will not be less than b, while GCD of (a, b) won't be more than a. It means that for any number x where x>3*a, LCM/GCD>3. The same goes for 2.

so for every a, there exists b=2a and b=3a which are valid pairs(b=a already covered above). To make sure b=2a doesn't overflow(b can't be more than n), we take floor of n/2 and multiply it by 2. Multiplication by 2 is caused by the fact that pairs can be inversed. AKA pair (a, b) is different from pair (b, a). The same logic goes for pairs where b=3a.

I hope this makes sense and helps you some.

→ Reply

dulatcodes

2 years ago, # |

← Rev. 2 →

D was a great one. Too bad, I was late for a minute

→ Reply

nerdBlood116

2 years ago, # |

When will our ratings get updated?

→ Reply

2 years ago, # ^ |

soon(tm)

→ Reply

k1r1t0

2 years ago, # |

A is too complex for Div2 i think too much math

→ Reply

AdityaG

2 years ago, # |

feels so lucky when ur solution passes system testing so close to TL.

→ Reply

2 years ago, # ^ |

Indian meme :)

→ Reply

pramana

2 years ago, # |

big fan of this round :)

→ Reply

qu_bit

2 years ago, # |

Should have added this test case for problem C:

1
2
1 1
1000000000 1000000000

Because this test case is not there some TLE solution will get accepted like this one: https://codeforces.net/contest/1717/submission/170655104

→ Reply

bruhify

2 years ago, # |

Damn it, I was too slow to AC A-E and upsolved F 30min after contest without help... Great contest, A and E were cool number theory equation-shuffling (although this A might be a bit hard for A?), F was a standard flow problem with a classic trick, it was really interesting to boil problem D down to its core, and it practically solves itself when you get to the core. B/C I can’t really give feedback because I kind of just guessed them without any proof or intuition but they were interesting enough to keep me thinking for a solid bit. Banger contest overall.

(I’m totally not biased because this was my first div2 contest that I could AC all problems by myself, what are you talking about)

→ Reply

su1c1dalttb

2 years ago, # |

+13

Problem D's harder than E.

→ Reply

2 years ago, # ^ |

Same for me, I don't understand how 1000+ people solved D.

→ Reply

2 years ago, # ^ |

Well, it's most likely because people always attempt D before E, and if they can't solve D they usually won't attempt E.

Another reason I can think of is that D and E are fundamentally different and require very different skill and experience.

→ Reply

2 years ago, # ^ |

Yes, you are right.

I think if I didn't know that this is Div.2 D and that 1000+ people solved it, I would think that this is 2400 problem. But solution is so beautiful!

→ Reply

timreizin

2 years ago, # ^ |

+20

Problem E is harder than D.

→ Reply

su1c1dalttb

2 years ago, # ^ |

For me D is harder because of my logic :v. In problem E it's like: iterate over c and gcd(a, b) = gcd(a, a + b) & the number of divisors of n consecutive number is not that big so use some trick with euler totient function. In problem D, it's more of a adhoc problem (the number of leaves that has k black edge on the path to the root is the same for every binary tree with the same size) and for me it's kind of hard to guess it out.

→ Reply

2 years ago, # ^ |

+19

Okay, okay, guess what, both of you could be correct. Yall should refer to the scoring, and you will see that both have a score of $$$2000$$$.

→ Reply

Cuellius

2 years ago, # |

+86

Due to some difficulty of the problem A, I explain the solution which do not require brains at all.

The problem A can be solved without any thinking. All you need to do is use Wolfram Mathematica:

GetPairs[n_] := Module[{ans = 0, i, j},
   For[i = 1, i <= n, i++,
    For[j = 1, j <= n, j++,
      If[LCM[i, j]/GCD[i, j] <= 3, ans += 1]
      ];
    ];
   Return[ans];
   ];

Map[GetPairs, Range[1, 100]];
FindSequenceFunction[%, n];
FullSimplify[%, Assumptions -> And[n \[Element] Integers]]

In fact, we are looking for an answer in the form of a function that depends on $$$n$$$.

And the Wolfram Mathematica gives the answer:

$$$ n \mapsto \frac{1}{18} \left(48 n+9 (-1)^n+2 \sqrt{3} \sin \left(\frac{2 \pi n}{3}\right)-2 \sqrt{3} \sin \left(\frac{4 \pi n}{3}\right)+6 \cos \left(\frac{2 \pi n}{3}\right)+6 \cos \left(\frac{4 \pi n}{3}\right)-21\right). $$$

We can simply code it and get AC: 170655872.

→ Reply

qxforever

2 years ago, # ^ |

Amazing

→ Reply

Tutis

2 years ago, # ^ |

The problem with this approach is that it takes more than 2 minutes.

→ Reply

iMurat

2 years ago, # ^ |

Amazing!

Did you try it on problem E?

→ Reply

brunovsky

2 years ago, # ^ |

+19

Given the delay with the editorial I am sure this will help the newbies. Thank you!

→ Reply

secret-void

2 years ago, # ^ |

This is nice. If you observe a bit of basic math, you can simplify it further for integer n.

→ Reply

2 years ago, # ^ |

Hereby I suggest another solution which also do not require brains.

The solution is to use the Berlekamp-Massey algorithm, which is an algorithm that predicts the recurrence relation of an integer sequence with a linear recurrence, given its first few values. It requires a certain modulo, but considering that the answer is below $$$10^9 + 7$$$ for the biggest input possible, that would suffice. Now all that is left, is faith. Faith that it would have a good linear recurrence relation.

Here(170662330)'s the submission that passed the tests with this method, and here is the Berlekamp-Massey template I used. Huge thanks to ko_osaga for the template.

→ Reply

llc5pg

2 years ago, # ^ |

+10

I worked out the relation during contest:

        ll rem = (n-1)%6;
        ll mul = (n-1)/6;
        switch (rem) {
            case 0: x = 1; break;
            case 1: x = 4; break;
            case 2: x = 7; break;
            case 3: x = 10; break;
            case 4: x = 11; break;
            case 5: x = 16; break;
        }
        ans = 16 * mul + x;

170601961

→ Reply

lis05

2 years ago, # ^ |

You're too good. orz

→ Reply

Wonsei

2 years ago, # ^ |

wtf

→ Reply

UUUnmei

2 years ago, # ^ |

a new OEIS lol

→ Reply

2 years ago, # |

everyone are doing it cout << (n) + (2 * (n / 2)) + (2 * (n / 3)) << endl;

i mean how they make this equation? where i am lackings? i cant even think with this way. i was supposed to make a series for few numbers and tried to construct a series which will satisfied all cases.

can anyone tell me how can i develop my mathematics skill, i cant imagine to construct something like this. feeling despondent!

→ Reply

invertedwinger

2 years ago, # ^ |

Let d = gcd(a,b), then a = dp, b = dq (p & q co-prime). Then lcm(a,b)=dpq, therefore lcm(a,b)/gcd(a,b)=pq. Only possible pairs are (1,1),(1,2),(2,1),(1,3),(3,1). For satisfying dp,dq<=n, the number of possible values of d are n,n/2,n/2,n/3,n/3 — hence the answer.

→ Reply

2 years ago, # ^ |

brother i was unable to think in this way after seeing the solution it as always seem easy. but will you recommend me how should i practice or which mathematical stuff should i master on. currently im solving 1000-1400 rating problems ascending then i will decesending too. and doing same strategy after tagging number theory in cf. thanks a lot for ur time. regards

→ Reply

invertedwinger

2 years ago, # ^ |

Any number theory book would be enough. I can say always try to simplify things, the upper bound in LCM/GCD term gives the intuition of less types of pairs. Then you can just proceed by fixing a, say a = 15, and trying to find values of b that satisfy the condition, you'll easily see the pattern that way. In 1000-1400 you don't need anything advanced, just general problem solving skills which develop with time. If you get stuck just try examples from sample tests or make by yourself, that should be enough.

→ Reply

2 years ago, # ^ |

should i continue with my strategy or there need a change?? thanks for ur kindness. regards

→ Reply

invertedwinger

2 years ago, # ^ |

Yeah doing problems is the way

→ Reply

2 years ago, # ^ |

Thanks brother I am very grateful to you, keeping your suggestion in mind, Hope almighty bless you. Take love

→ Reply

flakes24

2 years ago, # |

-18

Easily the worst contest I've seen so far, and that's not just me being salty because of the rating drop.

→ Reply

inertcoder2624

2 years ago, # ^ |

Care to elaborate? (asking in good faith)

→ Reply

flakes24

2 years ago, # ^ |

Bad ad-hoc A, cant guess or prove the solution easily for an A leading to most people leaving the contest without submitting to preserve rating, also frankly just a bad problem for a coding contest. I know CF is based on math and all but there should be some balance.

B higher than the usual level of D2Bs (atleast I thought so personally). D2 A and Bs need to be solvable relatively easily and I personally felt like these problems werent a good example of that. C was a good problem at an appropriate level tho, but A and B being this way kinda ruined what would be coming anyway for most people at lower rating ranges.

→ Reply

Himeno_Towa

2 years ago, # ^ |

I agree. B is harder than usual, which uses a common trick(but it shouldn't appear on Div.2 B)

→ Reply

BULLMCHOW

2 years ago, # |

+20

There are some problems with problem E statement.

→ Reply

geranazavr555

2 years ago, # |

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

→ Reply

CipherText

2 years ago, # |

← Rev. 2 →

Trying to write an easy explanation of why the answer of A is $$$n + 2(n/2) + 2(n/3)$$$. Note that we are using only integer division here.

Suppose,

$$$g = gcd(a, b)$$$ $$$l = lcm(a, b) = ab / g$$$

We can also write a and b using g like this:

$$$a = gx$$$ $$$b = gy$$$

Now let's transform the left-hand side of the given inequality using these variables:

$$$l/g = ab/gg = gxgy/gg = xy$$$

Values of the pair (x, y) can be (1,1), (1,2) or (1,3). Otherwise, xy would be greater than 3.

There are n possible pairs such that (x, y) = (1, 1):

$$$(1, 1), (2, 2), (3, 3), ..., (n, n)$$$

There are n / 2 possible pais such that (x, y) = (1, 2):

$$$(1, 2), (2, 4), (3, 6), ..., (n/2, n)$$$

There are n / 3 possible pairs such that (x, y) = (1, 3):

$$$(1, 3), (2, 6), (3, 9), ..., (n/3, n)$$$

Each pair (a, b) that satisfies (x, y) = (1, 2) or (x, y) = (1, 3) will be counted twice because (a, b) and (b, a) are considered different pair when a is not equal to b.

Hence, the number of pair (a, b) that satisfy the given inequality is:

$$$n + 2(n/2) + 2(n/3)$$$

→ Reply

cirex

2 years ago, # ^ |

Shouldn't the exact formula be $$$n + 2*\lfloor\frac{n}{2}\rfloor + 2*\lfloor\frac{n}{3}\rfloor$$$?

→ Reply

ShErLOck_h0lmEs

2 years ago, # |

-11

Div1 contest.

→ Reply

2 years ago, # ^ |

How do you ever speak about a competition having Div.1 difficulty when you have never even experienced Div.1?

→ Reply

int_Jak

2 years ago, # |

When editorial will be available?

→ Reply

purplesyringa

2 years ago, # ^ |

I have now translated the editorial into English, you can read it here. The delay was because the editorial was not available even in Russian back then, and translating it into English took me a bit more time than I expected because I haven't even read the problems before.

→ Reply

2 years ago, # |

-13

wait. Did anyone actually notice that this round had quite a lot of testers from the SIS? Was it just me?

→ Reply

trie_again1

2 years ago, # |

This was my first Div2. During the contest, thought that CP is not my cup of tea. According to my mentor, I should be able to solve at least two questions in Div2 contests. Struggled a lot even in the first question.

→ Reply

2 years ago, # ^ |

Why don't you ask your mentor about this competition? He/She would know better about this competition's difficulty after actually seeing it.

→ Reply

lis05

2 years ago, # ^ |

I struggled too. A is too hard for div1A

→ Reply

damdam17

2 years ago, # |

← Rev. 2 →

Problem A I solved in O(N) but why did I get TLE on test case 2????

N<=10^8 will O(n) not work in 1 sec?

my code

→ Reply

tyr0Whiz

2 years ago, # ^ |

time complexity of total code is O(n * t) , if you look closely its 10 ^ 12 order or so try to solve in O(1) time and space complexity

→ Reply