Codeforces Round 928 (Div. 4)

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

How is ur rank 2800 even after solving only 3?

→ Ответить

TheInfamousTony

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

Because that C was harder than normal C problems in div 3s' in the past. Kinda sad I only solved 2 and my rating is decreased.

→ Ответить

prakhar__py

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

Being a tester of this round i can easily this is worth giving for participants of all rating... You can push your time limits.

→ Ответить

Kolyanchick

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

Cyan pls

→ Ответить

VitaliiV

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

Good luck!

→ Ответить

Kolyanchick

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

OMG!!!

→ Ответить

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

How many days left? :)

→ Ответить

Ashnu

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

In blog mentioned 5-8 tasks, but all div4's shows atleast 7 tasks but none of them shows 5 or 6 tasks . Plz change it to 7-8 tasks instead of 5-8 tasks.

→ Ответить

b22cs012

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

Let's Hope , this contest makes me pupil

→ Ответить

VitaliiV

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

My first unrated Div4:)

→ Ответить

rpmdoestuff

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

unrated is 1400 and over btw

been waiting for this for a while lol

→ Ответить

lomlit

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

how to get the emoji

→ Ответить

Kolyanchick

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

He edited HTML code

→ Ответить

f_in_the_chat

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

First unrated contest :)

→ Ответить

Md-Merazul-Islam

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

I am also. but I am new to the unrated contest. This is unrated, meaning no rating will be changed (no minus or no plus) for those who are 1400+ ?

→ Ответить

f_in_the_chat

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

yes

→ Ответить

hkIsBack

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

This becomes unrated for me after yesterday's Div3 rating changes :/

→ Ответить

AN-94_Appreciator

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

omw to make <300 score.

→ Ответить

syedahmedzeeshan10

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

This is my first competition is that okay?

→ Ответить

VitaliiV

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

Why not? Good luck!

→ Ответить

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

here for the reach my apologies

all of this was in a response to a comment i made on the thinkcell round post asking how 2ball did A to C in eight minutes he reached out to me in the dm's and here is what transgressed. I am not accusing him of anything other than being vulgar and disrespectful, a 20 something year old should not retaliate by calling someone the N word i am attaching the pictures of the chat MikeMirzayanov please take the necessary action edit- the image link i don't think i am able to embed it properly https://imgur.com/a/o00YXuU

→ Ответить

2ball

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

It's funny how jealousy's got him moving mad like this.

→ Ответить

isJaipal

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

I read all that and got to know that u provoked him and he is saying right that you CHATTY-Bebob is cheating in contests as his ranks are not practically possible Rest 2ball must not be using those words and its so wrong BUT YOU SHOULD BE KEEPING ALL THIS UPTO YOU TWO AND NOT ACT LIKE KIDS

→ Ответить

2ball

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

I kindly ask flamestorm and MikeMirzayanov to take action against CHATTY-Bebob as he is leaking private data, and as the individual in question appears to be seeking attention. If they were not seeking attention, they would have directly contacted the authorities or the contest conductor,

→ Ответить

araarasayonara

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

heyy i know CHATTY-Bebob, he's from my college he has been doing this whith even his friend, I just wanna say this cuz its so unfair to provoke someone and use that against them

→ Ответить

teraBaapHU

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

teri maa ki chut me mera sir daalkar chilla dunga tera beta behan ka loda .....iit delhi meri jhaat behanchod teri maa ko chod dunga ulta patak ke lode se....gaand me or chut me bada loda ese jayega jese kisi ne kurkure ka packet faad diya ho madarchod teri maa ki chut or baap ka bosda

→ Ответить

TiMiX123

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

Since time immemorial, outstanding individuals have emerged from the oceans of mediocrity that make up the vast majority of humanity. Great thinkers destined to change their respective eras, launching the world into a new epoch. Mike4235 is the undeniable peak of what an outstanding individual is — he is the peak of what humanity can ever possibly achieve, the apex of human evolution and society.

If enlightenment is theoretically achievable, then Mike4235 is the sole example of enlightenment. There has never been a greater mind in the millennia of human civilization — from the great minds of Socrates, Confucius, Hegel — Mike4235 remains to be the apex of human development. It is the duty of every man and woman to dedicate their lives to the pursuit of what Mike4235 stands for — the progression of humanity into a greater version of ourselves.

Mike4235 is utter perfection in every sense of the word — even beyond. Human language cannot even begin to describe the earth-shattering qualities that he possesses. A fashion sense that makes ordinary humans appear as nothing more than bland specks of dirt. Intelligence that renders the complex processes behind a super-computer to resemble nothing more than a mere abacus. Humility that makes the martyrs of history seem like naive children.

Compared to Mike4235, we are all but measly insects that exist to eat the feces of superior beings, naive and ignorant creatures that wander the Earth without a sense of understanding of the grandiose knowledge that the universe offers.

Mike4235 is the peak of human evolution, and we can only prostrate ourselves to his superiority. He will not be merciful on our souls, and we must only accept his divine judgement.

If he commands us to lick his boots, we shall slurp every particle of filth and bacteria that dares to contaminate the paragon of humanity’s shoes. It shall be so pristine, that it will reflect the face of inferiority.

If he commands us to donate money, then we shall empty our coffers for him. By his impulse and will, we shall learn what true humility is.

Those who refuse the ever-existent superiority of Mike4235 will only be dooming themselves to a life of trifle purpose. Mike4235 is not a god — he is beyond what ordinary humans can even conceptualize as a deity.

Repent now, and see Mike4235 as the true exemplar of the sublime, lest you fade into the trenches of human society, destined to be forgotten.

→ Ответить

TheInfamousTony

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

Wait how do you know him.

→ Ответить

araarasayonara

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

My first contest , happy to participate in it

→ Ответить

NotNava

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

good luck and high ratings :>

→ Ответить

aboutnasim

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

Hope this will be a fantastic contest me and all

→ Ответить

JeetuGupta

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

I recently became Specialist, have given only 3 contests after becoming specialist. Is it rated for me or not??

→ Ответить

mamun700263

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

if I make an unsuccessful hacking attempt will I get a minus rating??

→ Ответить

sakuun

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

first time participating, can't wait

→ Ответить

Norp

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

Good luck for everyone!!!!!!

→ Ответить

Unalloyed

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

Good luck Sigma!

→ Ответить

blackronaldo

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

finally unrated for me!

→ Ответить

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

Hey there I want to put light on cheating going on during contests. I found few evidences against CHATTY-Bebob that he surely has been copying codes during contests. He has used 2 different templates in the same contest which makes no sense And in the 3rd code I found something interesting , there was a comment asking not to completely copy the code .So it is clear that he has been copying codes which is pretty evident from gradient if his ranks too

→ Ответить

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

I often ask chat gpt to fix my code ergo the other templates.

→ Ответить

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

Bro chatgpt wont put that comment , it surely is copied from some other user and everyone knows chatgpt cont fix good codes. Whom are u fooling bro . I request MikeMirzayanov to ban cheater like CHATTY-Bebob

→ Ответить

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

That don’t copy my shit code comment is mine. It used to be over my dummy functions so yeah that’s that

→ Ответить

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

Sure bro ,nice cover up

→ Ответить

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

← Rev. 2 →

first appearance of that template 241442627

→ Ответить

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

Bro no need , u copied that and obviously you will change to get safe Plag yk

→ Ответить

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

Okay sherlock

→ Ответить

Karatinos

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

Good luck to everyone and have fun!

→ Ответить

__NO__NAME__

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

Hoping for new learnings

→ Ответить

Vampire

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

flamestorm + div 4 = positive delta for me

→ Ответить

yuanzihan

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

I love div. 4

→ Ответить

BlunderBoyI2

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

I am dumb

→ Ответить

Atma_

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

Is this really div 4?

→ Ответить

Wandoka

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

RIP Div4 trusted participants

→ Ответить

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

i felt like C had something to do with repetition of the series 1...9 but wasnt able to prove it in the contest , did anyone get the proof?

→ Ответить

woonder

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

Hint

→ Ответить

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

yeah i did that because I couldnt prove that the repetition could be generalized into a formula.

→ Ответить

sajidali6567

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

It does not work, I tried the same way. But think when number of digit changes. For example 100 to 109, i again starts from 1 goes till 10.

→ Ответить

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

I saw submissions which used this property tho , cant find it now , hard luck for us i guess

→ Ответить

fernandezpalomojosue

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

← Rev. 2 →

247319547

→ Ответить

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

Thank you !

→ Ответить

BananaBrain

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

Are you saying looping over 1e5 and storing all results would pass in 1/2 seconds ?

→ Ответить

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

yeah just need to precompute once per t testcases

→ Ответить

woonder

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

It is possbile to precompute answer in O(n), then you can answer queries in O(1)

→ Ответить

Nemona

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

← Rev. 2 →

Actually precalculation is O(nlogn). For integer n, compute the digit sum of n is O(log n). Or is there any optimization?

→ Ответить

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

Because it has many testcases.The force algorithm in O（Tnlogn）in bad case。

→ Ответить

sajidali6567

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

we are not calculating for each test case.

calculation is once which is nlogn and answering t queries in constant time. which is nlogn + t

→ Ответить

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

Of course, I mean solving it in brute force instead of precalculating the problem.

→ Ответить

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

sorry, I initially intended to reply to someone else.

→ Ответить

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

you are right.

→ Ответить

sajidali6567

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

Hey, log n is 5 at max so it is O(5*n) which is O(n)

→ Ответить

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

In same，it can be regard as log10^n.

→ Ответить

Norp

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

Are this Div.4???? Maybe Div.3??

→ Ответить

NotNanYan

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

Maybe this is Div3 or Div2.5？

→ Ответить

ilovenandini

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

is this div4?

→ Ответить

epiccodingmomento

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

mathforces again...

→ Ответить

Devil_7

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

it is not div4 , it is div 2.5 or div3 and also C problem is not easy

→ Ответить

J.A.K.D.Z

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

I'm agree. It was like Div 3 but problem C is okay because it said that time limit of problem is 0.5.

→ Ответить

NekoNPC

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

seems this contest was too hard for a div4 contest.

→ Ответить

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

loved the div. E is brilliant , i don't think div 4 contestants would know dp though to put it in C.

→ Ответить

AlphaMale06

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

+35

do you really count prefix sums as dp...

→ Ответить

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

ooh yeah you're right , dp was what came in my mind that time but yeah it's prefix sums my bad

→ Ответить

m_nature

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

I think precomputation would fit better for the name of the concept lol

→ Ответить

kjhhjki

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

Awful contest as a div4. It sucks.

→ Ответить

Fork512Hz

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

Catch

IMO this is unfriendly for div4, esp. D and F I keep failing F as well

→ Ответить

sh__r

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

Testcase 3 on D kept failing, What is the reason overflow?

→ Ответить

sliu17

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

I had the same issue. Try this case:

1
5
0 2147483647 0 0 2147483647

Output should be 3, if you got 4 it's the same mistake as mine.

→ Ответить

rmz

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

Try not to make half the problem set depends on math challenge.

difficulty : impossible

→ Ответить

fverri

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

My first contest, still a lot to learn

→ Ответить

MKasirloo

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

+10

Hardest Div. 4 ever

→ Ответить

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

can someone explain or give some hints for F? i thought in bitmask dp but i think the states won't fit on memory or time limit ( thought also in DnC but i think it still won't fit on time limits)

→ Ответить

iordache_

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

i thought the problem was putting a number on every cross and putting the numbers on the positions of the cross. it becomes this problem: you have different sets of numbers from 1 to n, what is the minimum number of sets you can choose so their reunion is 1....n? i just feel like i know this problem but i forgot the solution

→ Ответить

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

← Rev. 3 →

Spoiler

→ Ответить

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

so maybe i just can bruteforce on all state with a bfs like apporach?

→ Ответить

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

Yes, I bruteforced but not by bfs but by checking all possible placements of flips (with constraint from the above hint).

Additionally, I used two more hints:

Spoiler

→ Ответить

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

thanks i got the first spoiler but didn't get the last one but i will think in why its true thanks alot

→ Ответить

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

← Rev. 2 →

Yes, the last one is the hardest to grasp. Without it my program run about 10s.

Spoiler

For both hints, it's better to move towards the middle. For example, if you wanted to flip element at (1, 1) (upper corner) it's better to flip element at (3, 3): (1, 1) could only be an element of X (1, 1), (2, 2), (1, 3), (3, 1), (3, 3), but element (3, 3) could be of many more. For (2, 2), which is the hard case, it can also be swapped for (3, 3), which can be seen by similar analysis, but a little bit harder. <\spoiler>

→ Ответить

NekoNPC

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

← Rev. 2 →

+13

dp bitmask works. Suppose we are at cell (i, j), we only need to consider 16 previous cells. So we can have a solution with complexity $$$O(T * 7 * 7 * 2^{16})$$$. Luckily it fits to time limit.

→ Ответить

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

+13

oh i didn't think on that i was thinking in something like n2 * 2^49 thanks

→ Ответить

dartvolley

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

If you want to know more about this technique, it is called DP on Broken Profile.

In my experience, this technique is quite rare, and it is actually the first time I have encountered it in a live contest. (Though I tried to cheese it and solve the problem in $$$O(T\cdot N \cdot 2^{3 \cdot N})$$$, which failed)

→ Ответить

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

thanks alot first time hearing about that technique i will check it out

→ Ответить

_Kee

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

+15

The first thing to note is that you just need to modify the black cells located in the central $$$5 \times 5$$$ cells. With this fact, you can just bruteforce all the $$$2^{25}$$$ patterns and check the cross pattern, which requires $$$2^{25} \cdot 25$$$ loops at most. This is actually too much -- what can we do to improve this?

It turns out that you can separate the whole board into two by their parity: $$$A = \{ (x, y); x + y \; \text{is even} \}$$$ and $$$B = \{ (x, y); x + y \; \text{is odd} \}$$$ (imagine the chessboard pattern). The cells in $$$A$$$ do not interfere with cells in $$$B$$$, and vice versa. Therefore, you can bruteforce each of them, resulting algorithm with $$$(2^{13} \cdot 13 + 2^{12} \cdot 12)$$$ loops, which is fast enough.

→ Ответить

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

Does carrot shows rating change including official participants or overall?

→ Ответить

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

How to do C?

→ Ответить

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

pre compute the answer for all n u can do that by using prefix idea

→ Ответить

3FrenchOmelettes

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

thought this approach would TLE, so spent over an hour thinking of a O(1) math solution that doesn't exist fml.

→ Ответить

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

same, tried solving based on the pattern from 1 to 9 in ones place

→ Ответить

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

well the complexity its likely nlogn and c++ is too fast so failing in 0.5 second seemed not likely ( also the mod operation maybe make this a gamble)

→ Ответить

Akshay184

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

I believe just pre-computing all the value before hand will work.

→ Ответить

MKasirloo

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

← Rev. 2 →

First, prepare all answers from $$$1$$$ to $$$2\cdot10^5$$$ in an array. To do that, make a loop from $$$1$$$ to $$$2\cdot10^5$$$ and in the loop write $$$a[i]=a[i-1]+sumOfDigits(i)$$$ where $$$sumOfDigits$$$ is like this:

int sumOfDigits(int n){
    int s=0;
    s = s + n%10; //(last digit of n)
    n = n / 10; //(remove last digit)
    return s;
}

then for each input $$$n$$$, output $$$a[n]$$$.

→ Ответить

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

thanks

→ Ответить

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

+50

I rarely take part in Div4 and Div3 contests but today I had some free time and decided to give it a casual try. I must say, that I was positively surprised. I especially enjoyed problem F, which was one of the nicest problems I have solved for quite some time. The solving process just felt joyful and everything in this problem fits very nicely to a solution that runs below 4s. Big thank you to the author of this problem :D

→ Ответить

VirnaAilin

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

+23

hardest div4 ever. The writers should include more low rated people in testing.

→ Ответить

yellowbeard

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

more like Div 3 than Div 4

→ Ответить

wkao

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

Terrible experience

→ Ответить

rishabhxchoudhary

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

+11

I recorded myself live while solving A,B,C,D,E and thinking F. Hope it helps someone: https://www.youtube.com/watch?v=Zr2JbyTwq0A

→ Ответить

boomfire

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

← Rev. 3 →

Unfortunately，my rating will drop :(

→ Ответить

qwscaln

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

Spent a lot of time on C, hated it, but it turned out to be very simple, kinda liked it eventually :)

→ Ответить

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

how to solve F though, i was thinking backtracking but the complexity is too big

→ Ответить

1BeeNY1

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

← Rev. 2 →

I used backtracking. Solution is 8 at max and we need to switch only Bs which are not on the border of the grid.

So we have to do backtracking just on 25 elements, choosing maximum 7 out of them (if its not solution, then the answer is 8). With the solution check, the final complexity will be T * 7 * 7 * C(25,7) which can be amortized.

Despite the mask solution, I don't know of any other solutions.

→ Ответить

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

i didn't think about that maximum solution is 8 that's why I couldn't make the solution better i guess yeah thanks that helped

→ Ответить

fztym

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

I think the description of E is not clear enough.

→ Ответить

carbonMonoxide

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

247348183

for problem E can someone tell me if it is correct or not?

→ Ответить

Avik_AB17

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

Awful Div.4! :)

→ Ответить

itsdhruvaggarwal

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

I did just C in 2 hour and someone did just B in 20 min. Why i am not higher on standing as i soved a more difficult problem??

→ Ответить

OneFinal24

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

Because they past 2 problems but one for you

→ Ответить

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

+10

in ICPC style contests there is no assigned difficulty to each problem, all are the same,since he was faster , he is ranked higher

→ Ответить

NoticeMeSenpai

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

because this contest follows ICPC rule. So I think difficulty of problem doesn't matter. No of problems you have solved and time taken to solve each problem along with incorrect submission penalty will be counted towards 'standings'.

→ Ответить

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

Ill miss specialist by 3 points :(( carrot sowing 40, i need 43

→ Ответить

BrotherCall

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

You needn't worry . Carrot often underestimates the growth rating . According to my experience you will get specialist this round :)

→ Ответить

Contest 1 Contest 2 Contest 3

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

I didnt :(

→ Ответить

OneFinal24

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

it is too hard for div.4 F，F hard than G too much，i think maybe F can be 2000+

→ Ответить

Rakesh_898

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

Check my submission for F.I use recursion without using dp but it passed.. https://codeforces.net/contest/1926/submission/247337741

→ Ответить

Chrisedyong

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

← Rev. 2 →

+20

I solved G using MaxFlow. I think this solution is overkill and more likely fail system test. Can anyone hack my solution please? Link for my submissions: https://codeforces.net/contest/1926/submission/247343993

→ Ответить

Owmicron

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

+29

I am pretty sure your solution is correct. The problem can be reduced to finding the minimum cut from every node labeled P to every node labeled S. Your solution finds the maximum flow, which is equal to the mincut according to the max-flow min-cut theorem. Since the graph you build is a unit graph, it should fit within the time limit with $$$O(N \sqrt{N})$$$ complexity.

Please correct me If I'm mistaken.

→ Ответить

nskybytskyi

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

To be more precise, Dinic works in $$$O(\min(E^{1/2}, V^{2/3}) \cdot E)$$$ on unit graphs, and this bound is tight. The $$$O(E^{1/2} E)$$$ part is textbook (residual paths get longer on each iteration), and the original paper for the $$$O(V^{2/3} E)$$$ bound is "Network Flow and Testing Graph Connectivity" by Shimon Even and R. Endre Tarjan (1975).

→ Ответить

Chrisedyong

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

← Rev. 2 →

I think you are right. I did not use the property of unit graph in order to compute the time complexity. My bad.

→ Ответить

Basmala_Hekal

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

what's wrong with the author it's even more difficult than div3!!!!

→ Ответить

Karatinos

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

Task A Of course easy, it's Div.4 ;)

Task B I submitted one WA, and I have misunderstand why was it wrong. After not very long period of time I submitted code with practicaly the same idea for AC

Task C Like usual task about pre-calculating

Task D Solution using bit operands, that was interesting to notice that there are not more than two objects in one group. After that solution appears

Tasks E, F — I tried to solve, but I hadn't any good ideas, but for me these tasks are interesting (especially F, I think that there is an idea about graphs) and not very easy.

All in all, contest is a bit harder than usual and much more interesting!

→ Ответить

BrotherCall

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

This div4 round is not easier than most div3 round I met . Did CF notice during the check process？

→ Ответить

rHermes

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

← Rev. 2 →

I liked the contest, but I have question about problem F.

I really thought I had figured out how to solve it, first we scan over the input and if a square is black, we increment the position and it's diagonal neighbors.

At the end of that loop, all squares who have 5 in them are the problem squares. We create a map with these positions as key, and a list of squares we could pick to make this no longer a problem square. This list is the square itself, and it's 4 diagonal neighbours.

My idea now, is that we can simply iterate on this list, picking the position that would invalidate the most positions at each turn. This works for the given sample, but it fails on tests 2. I would love to get some input on what kind of a test case would not be solved by this algorithm.

Just for reference, here is the code: https://github.com/rHermes/contests/blob/master/codeforces/1926/c1926pF.cpp

→ Ответить

Parshav01

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

I don't know why i am always left with F and G part:(( Are you guys also face this?

Today's contest was difficult than yesterday's, isn't it?

→ Ответить

adaptatron

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

← Rev. 2 →

Problem G can be solved trivially using the techniques discussed in the tutorials DP on Spanning Subgraphs and DP on Induced Subgraphs

Of course, easier solutions exist, but if you are aware of the technique of adding children incrementally, this can reduce your brainstorming time.

Here are 3 practice contests to test your understanding of the topic:

My submission, based on the ideas discussed in the blog.

→ Ответить

yuanzihan

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

div. 4?

div. 2.5!

→ Ответить

shiinehata

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

← Rev. 2 →

+17

Codeforces Round 928 ~~(Div. 4)~~ (A + Div. 3)

→ Ответить

garlic_bread_0204

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

Description of problem B is terrible , we have to assume that where-ever 1 appears , it would be part of a pattern

my approach was just to check if number of 1s in two consecutive rows would be same , it will be a square

else triangle

it fails on:

0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 1 0 0

→ Ответить

Miryz

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

wdym, checking two rows is a solution.

→ Ответить

serenhade00

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

← Rev. 2 →

It is guarenteed that only either of triangle or square is appeared on the grid. No pattern other than a triangle or a square is possible.

→ Ответить

garlic_bread_0204

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

in the explanation part the case highlighted with a big cross...what does it mean ?

doesn't it mean that such cases would be a part of input as well ?

→ Ответить

serenhade00

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

It meant to show that those kind of patterns are not considered as triangle. Since description says that only qualified triangle and square are included, the case with a big cross won't be a part of input.

→ Ответить

BananaBrain

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

That can be ignored since the answer was always either TRIANGLE OR a SQUARE , so had to check if there was a single star in a row, if it was , then answer would definitely be triangle else square

→ Ответить

minhtran2404

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

I think that the it's a triangle if any row got only 1 char '1'

→ Ответить

calebmartim

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

Here's a Codeforces life hack that I've started doing and it has helped me a lot most of the time: if a problem statement or problem editorial is too confusing, try to ask ChatGPT to translate the original russian text to english. It will usally translate it better.

Example for today's problem B

You can see it's way clearer from that translation that if there's a $$$1$$$ in the grid, it will necessarily be part of a square or triangle.

→ Ответить

garlic_bread_0204

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

thanks...it was helpful...will follow this from next time...

→ Ответить

iordache_

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

Haha B took me 35 minutes, but C took me 4, D took me 5 and E took me 27

→ Ответить

edv13

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

problem f is harder than problem g :skull:

→ Ответить

Devo

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

+11

the last div3 is much easier than this round lol.

→ Ответить

gokuu007

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

can anyone tell why am I getting TLE ? https://codeforces.net/contest/1926/submission/247263560

→ Ответить

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

-15

the to_string() function take O(n) time, so using it in inside of a loop takes your complexity to O(n^2), which gives tle

→ Ответить

gokuu007

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

what does n denotes here ? the number n itself or the digits of n

→ Ответить

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

n in your case denotes mxN

→ Ответить

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

first of all you have a bug where you access dp[mxn] second you are using to_string to much which i think its even worse from the mod/division apporach

→ Ответить

llc5pg

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

Change int dp[mxN]; to int dp[mxN+1];. See 247374406

→ Ответить

gokuu007

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

oops silly me !

→ Ответить

drdilyor

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

to_string(x) works in O(num digs of x) = O(log x).

Your code is TLEing because of accessing dp[mxN] when size is mxN. And this causes an undefined behavior.

// wrong
    for (int i = 1; i <= mxN; ++i) {
// correct
    for (int i = 1; i < mxN; ++i) {

→ Ответить

NEERAJ2003

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

Great round really enjoyed hope to have 5 minutes more as so I could submit G within time although kudo's to whole team.

→ Ответить

arash.

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

← Rev. 2 →

Greedy solution for G: Do a dfs and while doing a dfs pick edges as greedily. For each vertex v we remember a value: After greedily picking edges, if we look at the component of thin walls that v is in, if it contains a sleepy student, it's value is 1, if it contains a party student then it's value is 2 and if it doesn't matter we value it with 3.

Now, we want to pick new edges,currently at vertex v.

If v is sleepy, we should pick all edges from v to children with value 2. The value of vertex v is 1.

If v is partying, we should pick all edges from v to children with value 1. The value of vertex v is 2.

But what if v doesn't care? Well let cnt1 be the number of edges from v to a child with value 1, and cnt2 be the same thing but with value 2.

If cnt1 > cnt2: We pick edges from v to children with value two.(cnt2 edges) and the value of v is 1.

If cnt1 < cnt2: We pick edges from v to children with value one.(cnt1 edges) and the value of v is 2.

But if cnt1 == cnt2: We don't really care what side we pick, as it's equally optimal we take bothe of them(at least for now). So the value of v is 3.(We add cnt1(or cnt2) to number of edges we picked). The reason for this in that when updating the parent node, we can choose the side of vertex v we want to pick based on the chosen value of parent vertex so really the value of v doesn't matter and is not counted.

→ Ответить

NEERAJ2003

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

Ya my approach was same I just did dfs calculate for child then for current node make the above cases

→ Ответить

treasuryonly

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

+12

First time using Haskell in contest!

Screenshot

Thank you guys for the amazing round!

→ Ответить

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

← Rev. 2 →

The code looks like a literal translation of C++ though, each function having do defeats the idea of Haskell.

→ Ответить

treasuryonly

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

Yes, the code may look C like but actually that's all I know about Haskell so far and I'm comfortable with this style, I find it readable and easy to debug if needed also.

And since it's Div4 so I want to make something new beside using C++ in almost every round, I think I will use Haskell more often in the future.

Thank you for reading my code and commenting!

→ Ответить

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

← Rev. 2 →

Out of curiosity I looked couple times if anyone uses Haskell, and there were very nice solutions, if you want to learn functional style there are examples of it. Although when coming from C++ sometimes it's not obvious, for example, in one problem there was TLE, and then after random (for my eye) shuffling and it's AC :)

→ Ответить

Alice_Cartelet

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

Great problems, but I think F is a little hard in Div.4 and G is too easy to be the last problem.

→ Ответить

TrivialZzy

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

Can anyone tell me why I am getting TLE? How can I modify it? https://codeforces.net/contest/1926/submission/247369927

→ Ответить

matislu

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

Two pointers 247373952. I came up with the idea of this solution after the contest. Since we want to match numbers such that $$$x XOR y = INTMAX$$$ and the following is true: $$$x < y => XOR(x, INTMAX) > XOR(y, INTMAX)$$$ we can match numbers using two pointers. This avoids maps and sets.

→ Ответить

TrivialZzy

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

Thanks!

→ Ответить

https://codeforces.net/contest/1926/submission/247380111

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

Like this: 247436179

→ Ответить

TrivialZzy

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

Thanks!

→ Ответить

Folka

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

Can anyone explains why my solution for problem F is wrong 247324886 ?

Idea : while there is at lease 1 black cells with four diagonal neighbors, find the most common cell and make it white. Is my approach wrong or the error is in the code ?

Thanks in advance.

→ Ответить

rishabhxchoudhary

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

I solved E by.. I thought of it as Josephus Problem but the sword is with nth person and not the 1st person. Anyone else did the same? xD

→ Ответить

Minerva2005

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

Wow!!

→ Ответить

devansh_27

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

me too

→ Ответить

ahnaf_sadi

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

My first Rated Contest!!!!!!!!!!!!!!But yet rating not showing.......

→ Ответить

itsdhruvaggarwal

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

wait 24 hours

→ Ответить

Ashnu

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

Round 925 is easier than Round 928

→ Ответить

Ran_Mouri

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

Hint for c ... please

→ Ответить

Folka

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

Pre compute all

→ Ответить

karna001

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

you have to precompute in order to save time, so you can precompute till 2e5 in a vector and then give the answer in o(1) for each query

→ Ответить

Ran_Mouri

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

Thancks

→ Ответить

quad_wipe

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

initially you need to realize this sum(10^n-1)=45*(10^n-1)+sum(10^(n-1)-1)*10

→ Ответить

Ran_Mouri

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

Thank you

→ Ответить

sashshaikh12

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

← Rev. 2 →

could anyone tell me where my code will fail for problem D, i am getting WA on test case 3

Spoiler

→ Ответить

llc5pg

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

-10

When input is with length of 4: 0 2147483647 2147483647 2147483647, you answer gives 1. Correct answer is 3.

→ Ответить

sashshaikh12

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

yes got it thank you!

→ Ответить

VioletVal

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

How do you solve E?

→ Ответить

quad_wipe

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

← Rev. 2 →

for every iteration you will be eliminating floor(n/2) numbers keep a count of how many times you are iterating (u can get the count by subtracting the count of eliminated numbers from k in a loop till it become less than floor(n/2) ) change n to n-floor(n/2) simultaneously finally when your (k>floor(n/2)) loop breaks just return (2k-1)*2^count my code

→ Ответить

AvaraKedavra

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

← Rev. 2 →

In problem G — "The second line of each test case contains n−1 integers a2,…,an (1≤ai<i) — it means there is an edge between i and ai in the tree."

What does this mean ? How should I form the edges ?

→ Ответить

hashman

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

It's basically giving you the ``normal" representation but in a slightly different way, instead of inputting two variables, $$$u$$$, and $$$v$$$, only one is inputted, and you get the other one from the line number.

--a[i];
adj[i].push_back(a[i]);
adj[a[i]].push_back(i));

→ Ответить

AvaraKedavra

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

Why do you reduce a[i] by 1 ? How did you interpret it as an edge between a[i]-1 and i ? Also is i from 1 to n or 0 to n-1 ?

→ Ответить

hashman

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

Reducing $$$a_i$$$ by $$$1$$$ is due to zero-indexing versus one-indexing. $$$i$$$ is from $$$1$$$ to $$$n - 1$$$ (it is actually from $$$2$$$ to $$$n$$$, but once again zero-indexing versus one-indexing). You can use whatever way you want; if you're used to one-indexed, you can just not subtract $$$1$$$ from $$$a_i$$$, and use it as is. I'm more used to zero-indexing though, so I use zero-indexing.

→ Ответить

AvaraKedavra

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

thanks!

→ Ответить

SoleProprietor

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

It means {1, 2, ..., n} is a topological ordering if you view the tree as a directed graph with root at 1, because the index of the parent of i is less than i.

→ Ответить

RigilKentaurus

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

For D,Using Unordered_map is pure Hell,What this Contest Taught Us.Ordered Map is always better!

→ Ответить

BananaBoat_93

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

lets go

→ Ответить

RAW007

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

I was able to solve 1st and the 3rd problem during the contest but i find hard to implement the second problem .

→ Ответить

Folka

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

You can have a look on my solution 247235514, it is very easy to understand and smart solution

→ Ответить

RAW007

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

Thanks for your solution .

→ Ответить

brainsoft

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

Do you need a more easy solution? Check 247233776 it out. I will never mind.

→ Ответить

Zardosh

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

Why does this get TLE https://codeforces.net/contest/1926/submission/247355922 while this doesn't https://codeforces.net/contest/1926/submission/247356724 ? Only difference is unordered_map vs map (unordered_map is getting TLE while map isn't)

→ Ответить

el_tunel

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

It's because unordered_map uses a hash table, and one of the tests has been engineered to make the hash table work badly by creating many collisions. See this blog post for a more detailed explanation.

→ Ответить

Zardosh

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

Thanks!

→ Ответить

jwacker

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

How do we generate test cases to hack a solution that uses unordered maps?

→ Ответить

TG-STUDIO

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

in the last div3 i solve 5,and this time i solve 5 too but with higher rank!

→ Ответить

ykx2010

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

I hope to turn to a pupil in this contest because all my friends are green and even higher.

→ Ответить

MrPython

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

I think F and G are harder than div.3...

→ Ответить

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

me too。

→ Ответить

TG-STUDIO

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

maybe = div3 f g

→ Ответить

MrPython

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

maybe = div3 g f

→ Ответить

TG-STUDIO

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

that's right

→ Ответить

ahnafrahmn

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

Where can I get solutions of the contest??

→ Ответить

treasuryonly

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

Editorial is available.

→ Ответить

xiojoy

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

For me, F is too hard to solve.

→ Ответить

joy_mara_khai

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

How can I find the best solution for this contest?

please help I am a beginner

→ Ответить

Zardosh

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

Try checking the editorial.

→ Ответить

ParthJha17

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

Was someone able to find a mathematical formula for C?

→ Ответить

yashdabhade283

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

Yes I did checkout my submission

→ Ответить

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

you can read my comment, I have been posted it 4-5 minutes ago

→ Ответить

Eriksonas

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

I am below 1400 rating, why was the contest not rated for me?

→ Ответить

Harman001

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

It was rated for you but if you didn't already participated in at least 5 rounds then you are still not a trusted participant so you will not be included in official standing but still you will get rating which will be updated soon.

→ Ответить

chenRenning

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

This is sad news, I originally thought that the performance score was above 1609 half an hour ago, but at this time, when the final settlement was announced, it was 1450, which made me still have a gap of 9 points from the goal, T_T

→ Ответить

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

← Rev. 2 →

Same here bro.. missed by 11 points :(((( going to die Carrot is the worst predicator

→ Ответить

serenhade00

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

ikr, I usually get more rating than carrot's prediction, but this time got lower rating.

→ Ответить

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

I guess i have the badest luck then

→ Ответить

chenRenning

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

Hopefully get to the blue before the provincial race :)

Chin up, I believe it is not far from being realized

→ Ответить

molla12

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

← Rev. 2 →

It was my first and last rated Div.4 round.

→ Ответить

molla12

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

It is not now

→ Ответить

saelcc03

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

Good bye pupil, Hello specialist

→ Ответить

ashays

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

congrats bro

→ Ответить

hushbek_2009

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

361 Yes

→ Ответить

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

← Rev. 11 →

Is there anyone who solved problem C by using math? I was trying to solve it by using math, and noticed that the difference of the sum of the sum of digits of each number from one to nine and ten to nineteen is equal to 10 and the difference of the sum of the sum of digits of each number from ten to nineteen and twenty to twenty nine is also equal to 10 and ... I am interested by the next question: -Can be this problem solved by using law for sum of sum of digits I have noticed?

→ Ответить

ilovenandini

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

I solved it in this way

input is 1434

then find the answer upto 1 to 1000 then 1001 to 1400 then 1401 to 1430 then 1431 to 1434

and add the result of the above 4 answers

→ Ответить

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

okey thank you

→ Ответить

chabchoub

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

Check my submission for C I used recursive function to solve it

→ Ответить

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

thanks

→ Ответить

linshule

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

Perhaps you can refer to mine 247347016

→ Ответить