Codeforces Round #903 (Div. 3)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3821
3	Benq	3736
4	Radewoosh	3631
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3388
10	gamegame	3386

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	161
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Привет! В Oct/12/2023 17:35 (Moscow time) начнётся Codeforces Round 903 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.

Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.

Вам будет предложено 7 задач и 2 часа 15 минут на их решение.

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

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

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

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

Задачи были придуманы и написаны нашей командой: myav, Gornak40, senjougaharin и Vladosiya.

Также большое спасибо:

MikeMirzayanov за системы Polygon и Codeforces.
SomethingNew, rniya, zwezdinv за красное тестирование раунда.
makrav, snowysecret, AlexanderL, KseniaShk, pavlekn за жёлтое тестирование раунда.
gigabuffoon, EgorUlin, KerakTelor, Pa_sha, I_love_geom, petyb, MinaRagy06, toniskrijelj, FynjyBath за фиолетовое тестирование раунда.
Abo_Samrah, dan_dolmatov, pedrosorio, ezdp, azureglow, Chrisedyong, Apachee, arseny2606 за синее тестирование раунда.
t0rtik, Sergey140146659, hader239, Modern за бирюзовое тестирование раунда.
mkshh, petertromso за зелёное тестирование раунда.

Всем удачи!

UPD: Разбор

void solve() { double n; cin >> n; double m = 1; double s = 1.0 / n; f(i, 0, n) { int x; cin >> x; m *= pow(x, s); } // cnl(m); double a = ceil(m), b = floor(m); if (abs(m - a) < 1e-6 || abs(m - b) < 1e-6) cnl("YES"); else cnl("NO"); }

Комментарии (140)

Показать архивные | Написать комментарий?

Avik_AB17

13 месяцев назад, # |

Waiting for that round. Hopefully, It will be a great round for me. Best of luck to all contestants :)

→ Ответить

a1abay

13 месяцев назад, # ^ |

+2 nice

Kyali

I hope This contest to be my promotion contest, I wish (:

minaabdel-massih

Hey man, good luck and stay safe!

Abdallah_Nasser

I wish you all the best, son of Palestine, home of brave heroes

abduladilcse.exe

Love you Brother. Salam.❣

rahiljakir

3 месяца назад, # ^ |

How are you bro!?

petertromso

+25

As a green tester I can ensure green participants that they will enjoy this round!

NeverSpot

AbhayAnilark

← Rev. 3 →

loved this round (happy emoji) (As cf don't allow to add emojis)

NeXuS69

← Rev. 2 →

😄

This is how

damm boi 😁

avighnakc

Why's this not on the home page yet?

Modern

As a tester I hope, that contest will be very interesting for all participants!

EgorUlin

+10

As a tester, I hope that this contest will be enjoyed by all participants. Read all problems and good luck! ฅ^•ﻌ•^ฅ

greenhand.n

expectantly ^^

AboNageh

Oh finally, it will be my first unofficial div3 round, I think I will enjoy it!!

Deleted

Mehrad2

sory i can`t get a think in line 11 you sed"do not have a point of 1900 or higher in the rating." but in line below it you say "Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you." so is that contest rated for experts or not ?

34z12000

It's not, it's just people who at least once reached 1900 will not get in the official standings(though if their current rating is below 1600, the round still will be rated for them).

thank you

hkIsBack

Ez Expert for me

mustard_with_fries69420

At least we know that there will be no bitset problems :)

axrav1saini

Waiting eagerly. Best of luck to everyone :)

Amao_Fox

I'm not welcome for Div.4 anymore so I must bring out my best in Div.3!

kar2003

Hoping to become an expert this round.

brokie

Your graph looks exactly like mine!!!! OMG :)

qwerty_boy_007

Do you guys give contests together? /s

what do you mean? I am from lebanon, bro is from india...

Synaptic_Savant

Need more div.2 rounds

snowysecret

As a tester, I hope the problems will be enjoyable for you!

eyfmharb

-8

For the life of me, I will never understand why a Div3 contest has 4 times the Expert+ testers as cyan/green testers. Who are these contests even aimed for?

Anyone else who just saw a message that the contest has started right now?

MinaRagy06

+29

As a late "as a tester comment", I beg for contribution

3mara

W tester = W contest

Vipin

Going to become Expert.

MovedToYassin

hack like 20 people and it is very possible predictor says you are 3 points short

make it 2000 people cause your solution to A got hacked

We don't get points for hacking in div 3.

hack people above you they get below you

tautology

Never felt dumber with a div3C.

stdfloat

First time to solve till F, my best performance in div3 :)

Guess which problem took my time most

heavenly_

did a problem similar to C yesterday, (a div4E), so i was able to solve it kinda quickly

SuperMo

11 месяцев назад, # ^ |

can you still remember the name of that problem ?

https://codeforces.me/problemset/problem/1703/E

codack_mayank

Same here, i will never take that much time again, constructed an algorith to traverse clockwise lol,

moghit_ad

How to solve D ?

Hunter_Kasa

Prime factorize every number and count all the primes. if all the prime count is divisible by n then yes

650iq

How did u come up with this? Is there any reference?

Jupiter_is_BIG

Note that over any operation, product of all numbers is invariant. Thus, if the final state of all numbers is $$$g$$$, then $$$\prod_{i=1}^na_i = g^n$$$. Thus, for the final state to be achieved, product of all numbers must be a perfect $$$n$$$-th power. Turns out this is sufficient as well. (Why? Hint: Think of how primes will be distributed)

would clarify the relation between N and number of all primes ?

KazoeYakuman

You can find out all primes no more than N in O(N) using Euler sieve.

Find the prime factors of each element and count the total number of occurrences of each prime factor. If all the total number can be divisible by n, then output YES.

rock_nroll

Anyone found the A,B,C much annoying problems.. this div3 contest must have focussed on the problems D,E,F ... rather than keeping the participants to got stuck at A,B,C these days...!

Vladosiya

Ironically, it was quite the opposite

puneet_73

+16

C was so annoying , D < C

D, E, F were interesting but i found A a little difficult for div3 A unless there is a trick that i couldn't see. Edit: Thanks got it.

Khaled93

A was just bruteforce, that is usually the case, you can just add s to itself a few times until you get to a fairly big size where you are sure the substr won't appear again and use .find() to check if m is a substring. The strings can only get to like 100 so checking till 200 does the trick.

chromate00

You could just naively check for at most $$$12$$$ operations or so. Time complexity would be $$$O(2^{12}nm)$$$ which is definitely not optimal, but anyways there are not too many testcases so it can't hurt to try too much

UPD: $$$k=12$$$ got hacked, maybe try something smaller like $$$k=6$$$

jayagrawal254

Any Hints for F? I was finding max and smax ( max and smax will be maximum and second maximun marked node from children ) and considering maximum distance from a node will be max( max distance from children (max) , distance from parent + 1 (max+1 or smax+1) ).

INMAK

← Rev. 27 →

Problem F

Hint

Claim

You don't need to calculate distance from every marked vertex. Just calculate distance from the two marked vertices x and y, such that distance(x, y) >= distance(i, j) for all pairs i and j where 1 <= i, j <= n' and 'i ≠ j. This is sufficient.

Proof

Let's assume that x and y are the two marked vertices with the maximum distance between them.

Now, suppose there exists pair of vertices v and z in the tree such that distance(v, z) > max{distance(v, x), distance(v, y)}.

We can claim that: max{distance(z, y), distance(z, x)} == distance(z, v) + max{distance(v, x), distance(v, y)} > distance(x, y).

However, this statement contradicts the fact that x and y are the pair of marked vertices with the maximum distance between them. That means there's no such z and v.

So, you only need to calculate distances from vertices x and y to satisfy the given condition.

Formula

$$$f(i) = max(distance(i, x), distance(i, y))$$$ where $$$(1 \le i \le n)$$$ and $$$(x, y)$$$ are the two marked vertices with the maximum distance between them.

Time complexity: O(n) at most 4 tree traversal. two for finding (x, y). two for calculating distances.

thinkaboutit

What is the level of complexity of problem E in terms of rating? Is it like the 1600 problem?

I would say 1300

ASHWANTH_K

Many of F solutions have been done using some segtree, or dp....
But mine i just did tree trimming....

VinCenzo___

Can You explain what is tree trimming or can provide links of segment tree submissions.

coderdhanraj

Is there any approach to solve F using segment tree.

BallBreaker

i feel E tests are weak (check my solution)

the_problem

Hi can anyone help me check my solution for D why it WA3? I had to change the loop to a get prime factorial function but I don't see where this one goes wrong. Thanks in advance https://codeforces.me/contest/1881/submission/227896125

Neembu_Mirch

you should write clear code and use different variables , your loop conditions might get altered because of value of n.

pnzrdlr17

You're only storing the factors which are <=1000. But there maybe factors >1000 for the given constraints. Try as an example [2182, 2186], the output should be NO, but your code gives YES.

wow what a stupid mistake thank you very much!

PG_Mazen

It is very sad to say that I have solved B and C, which is normal for a 'pupil', BUT I couldn't pass A :(

Can someone tell me which test case can spoil my code ? 227915244

commonsense

most probably try larger value of i, like 5 or 10.

I have tried after the contest and got wrong answer. 227927816

Can you try this?

My Code

#include <iostream>
#include <string>

void solve() {
    int a, b;
    std::cin >> a >> b;
    std::string s1, s2;
    std::cin >> s1 >> s2;
    std::string make = s1;
    int mul = 0;
    while (make.length() <= 1000) {
        if (make.find(s2) != std::string::npos) {
            std::cout << mul << "\n";
            return;
        }
        make += make;
        mul += 1;
    }
    if (make.find(s2) != std::string::npos) {
        std::cout << mul << "\n";
    } else {
        std::cout << "-1\n";
    }
}

int main() {
    int t = 1;
    std::cin >> t;
    for (int i = 0; i < t; i++) {
        solve();
    }
    return 0;
}

Also please note, it's a logarithmic function.

Yeah! I replaced my check function with

bool check(string s1, string s2) {
    if (s1.find(s2) != string::npos)
        return true;
    return false;
}

And I got accepted. Thank you

If x="abc", s="cabcab", your code will get a wrong answer.

Isn't the answer 2 ?

Sorry, I gave a wrong example. I think you should modify your check function. Once s1[i]!=s2[j] and j!=0, maybe you should change i to i-j+1.

I tried to use this:

And it works. I am so sad for what I did. It is a silly mistake :( I hope I don't turn to grey again.

For example, if x="abcabcabd", s="abcabd", your check will fail when i=5, j=5, and then you only change j to 0, but i is still 5, which makes you can't find the right match: i=3.

Oh okay, Thank you for your illustration sir

sukh_x

How did you solve B >_<

Your goal is to make all values similar to the smallest value in the given array. This makes you use less steps otherwise, you need to use more than 3 steps for sure. Let's call the smallest value in the array ('mn'). Also you have to make sure that all values in the array are divisible by 'mn'

Check my code 227853520

rishabhdarmwal

is the contest not rated for div4? made account on cf few weeks back and still a newbie, though i solved 2 problems but my rating didn't change

i3mr125

ratings update is tmrw

leshless

A — Annoying.

balanced contest overall. it's disappointing i wasn't able to solve E because i haven't learned dp yet :(

pastry

Can problem F using bfs many source?. I can't implement it during the contest

decltype_t

Multi source bfs gives nearest red vextex not farthest

vrintle

+15

I felt that today's E was similar (in terms of statement, not solution) to 1798E.

Also, great problemset!

RecursiveCo

Is there a more elegant way to solve F than some very annoying-to-implement tree DP? (Check my submission for my details)

+19

You need to calculate the diameter of tree (say $$$d$$$), considering the marked nodes as the ends. Now, intuitively the required node should lie in between this diameter, so distance would be $$$\lceil \frac{d}{2} \rceil$$$

I used the re-rooting technique

stash

Not as annoying as mine XD (227924103)

VioletVal

How to solve C?

MJavad

let ip= n-i-1 , jp = n-j-1. cells with indices (i,j) , (j,ip) , (ip,jp) , (jp,i) should be equal for each 0 <= i, j < n

rohitsatpute480

Screencast+Explanation | A-E

Can anyone tell me the 371st test for test case 2 in Problem G?

noobiesAG

If someone prefers video explanations or interested in knowing how to think in a live contest or reach to a particular solution.
Here is my live Screencast of solving problems [A -> E] (with detailed commentary in Hindi language).

drugkeeper

Why are there so many hacks on A? What is the hack?

Also: https://codeforces.me/contest/1881/submission/227851818

This looks kinda sus, to escape plagiarism checker?

Hack TC

He's definitely a cheater, I see no point int having an infinite while loop with a break statement.

apt_dpd

Is my solution for problem A hackable

Nice ProblemSet :)

prateek_saxena

Maximum possible answer in problem A can be log2(m)+1 . Isn't it?

True

Sreedhar3210

A,B,C,D were tougher than usual div3.

Code for generating a testcase to check TLE for problem A

https://ideone.com/c8Rs0m

hiddenanonymous

Is using unordered_map in D correct? Shouldn't it give tle? https://codeforces.me/contest/1881/submission/227902139

Soultaker

It's fine. Input constraints guarantee there are at most $$$10^4$$$ values, each less than or equal to $$$10^6$$$, which means up to 20 factors per value ($$$2^{20} > 10^6$$$), so a total of ~200,000 prime factors to add to the map.

Yene_Amilla

I think problem F is to find the spanning tree connecting the selected vertices and then get the diameter r->(r+1)/2 as the result but I don't know how to code it. is my idea correct??

Yes, the idea is correct. Maybe you can use the fact that on the smallest tree spanning the marked vertices, every leaf node MUST be a marked vertex. So, root the tree on some arbitrary marked vertex, and trim the leaf nodes until all leaf nodes are marked vertices.

raidenblackout

I had the idea for the problem F but ran into a bug and ended up wasting my time :3

CreamHao

A friendly contest to beginners! Although my B FST... :|

everyone seems to be overcomplicating B observation: we can divide a, b, c each into threads of size equal to the greatest common divisor of a, b, c. this will always be optimal therefore, the number of operations would be equal to: ceil((a + b + c) / gcd(a, gcd(b, c)) / 2) (it only takes 1 operations to split into 2 equal threads

HelloFromUnknown

Hello everyone, I am in bit trouble, I have tried to solve the first question of the contest but I am unable to debug it up. If anyone can help me, I will be very thankful. Thanks My submission

Actually, you're missing out on one index in this for loop,

for(int i=0;i<x.size()-s.size();i++){

The variable i should go upto x.size()-s.size(), so the for loop condition should be i<=x.size()-s.size()

Corrected: https://codeforces.me/contest/1881/submission/227970028

ay012

Why this code always work for Problem D?

Pirate_King

It's doing the same thing as other's have mentioned above. If the answer is yes, m will be an integer the way it is being calculated

HappyCodingLife.

Question A: What data can be used for hack

I_need_7.0_IELTS

Hello, how do I solve 1881G - Anya and the Mysterious String with Segment tree using Lazy propogation? This is what I've done 227967016, I haven't used Lazy propogation and it's TLE.

Thank you in advance.

SkyWave2022

Hackforces again ;)

Halym2007

problem A was very bad for div3.

lord_legolas

Can anyone check this i am getting wrong answer in test case 4 for Problem G

here's my submission : 227971449

Overflow. do x%=26 in query1

saraffa

My solution was hacked yesterday, again I submitted the same solution and it got accepted. Do the test cases used in hacking not get added to the main test-case?

they will get added after the hacking phase is finished, at the time of system testing.

samadeep

Can someone explain Problem E as dp state transitions in detail and also suggest similar problem please

Thanks.

Can someone please explain E. Block Sequence as dp states please and also suggest similar problems

nelch

Let $$$dp[i]$$$ denote the minimum number of deletions for the suffix starting on the $$$i$$$-th element: $$$a[i..n]$$$. Base case will be $$$dp[n + 1] = 0$$$.

For $$$dp[i]$$$, we can either delete or take it. If we delete it then $$$dp[i] = dp[i + 1] + 1$$$. If we take it, then the problem reduces to the suffix starting on the $$$j = (i + a[i] + 1)$$$-th element: $$$a[j..n]$$$. So $$$dp[i] = dp[i + a[i] + 1]$$$. We take the minimum.

ritikraj26

Can anybody help me figure out why there is TLE in this solution (Problem D)?

Ignoring TLE, your solution is wrong. For the test case $$$[7, 13]$$$, it outputs "YES" when it should be "NO".

Yes, I figured out the reason for the wrong solution. I am checking up to n(size of the input array), while I should be doing it up to 1e6. However, still, I am getting TLE solution

You're going to be doing that for every testcase though. So it'll require at least $$$2e9$$$ operations when $$$t = 2000$$$. You can use map/hashmap to keep count of the primes factors.

Ignore below, it does work.

Though even then, I'm not convinced you won't TLE in later testcases.

mssaketsai45

THIS CONTEST REALLY MADE ME TERRIFIED TO CONTINUE COMPETITVE PROGRAMMING

RajaVamshiNath

It was a nice contest , i have a lot of silly mistakes , but still it was a quality contest

xinu

What's up with the rating? System testing got completed hours ago?

geekyuttu

I became expert :)

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