Codeforces Round 928 (Div. 4)

9 months ago, # ^ |

How is ur rank 2800 even after solving only 3?

→ Reply

TheInfamousTony

9 months ago, # ^ |

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.

→ Reply

prakhar__py

9 months ago, # |

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

→ Reply

Kolyanchick

9 months ago, # |

Cyan pls

→ Reply

VitaliiV

9 months ago, # ^ |

Good luck!

→ Reply

Kolyanchick

9 months ago, # ^ |

OMG!!!

→ Reply

9 months ago, # ^ |

How many days left? :)

→ Reply

Ashnu

9 months ago, # |

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.

→ Reply

b22cs012

9 months ago, # |

Let's Hope , this contest makes me pupil

→ Reply

VitaliiV

9 months ago, # |

My first unrated Div4:)

→ Reply

rpmdoestuff

9 months ago, # |

unrated is 1400 and over btw

been waiting for this for a while lol

→ Reply

lomlit

9 months ago, # ^ |

how to get the emoji

→ Reply

Kolyanchick

9 months ago, # ^ |

He edited HTML code

→ Reply

f_in_the_chat

9 months ago, # |

First unrated contest :)

→ Reply

Md-Merazul-Islam

9 months ago, # ^ |

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+ ?

→ Reply

f_in_the_chat

9 months ago, # ^ |

yes

→ Reply

hkIsBack

9 months ago, # |

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

→ Reply

AN-94_Appreciator

9 months ago, # |

omw to make <300 score.

→ Reply

syedahmedzeeshan10

9 months ago, # |

This is my first competition is that okay?

→ Reply

VitaliiV

9 months ago, # ^ |

Why not? Good luck!

→ Reply

9 months ago, # |

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

→ Reply

2ball

9 months ago, # ^ |

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

→ Reply

isJaipal

9 months ago, # ^ |

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

→ Reply

2ball

9 months ago, # ^ |

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,

→ Reply

araarasayonara

9 months ago, # ^ |

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

→ Reply

teraBaapHU

9 months ago, # ^ |

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

→ Reply

TiMiX123

9 months ago, # |

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.

→ Reply

TheInfamousTony

9 months ago, # ^ |

Wait how do you know him.

→ Reply

araarasayonara

9 months ago, # |

My first contest , happy to participate in it

→ Reply

NotNava

9 months ago, # |

good luck and high ratings :>

→ Reply

aboutnasim

9 months ago, # |

Hope this will be a fantastic contest me and all

→ Reply

JeetuGupta

9 months ago, # |

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

→ Reply

mamun700263

9 months ago, # |

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

→ Reply

sakuun

9 months ago, # |

first time participating, can't wait

→ Reply

Norp

9 months ago, # |

Good luck for everyone!!!!!!

→ Reply

Unalloyed

9 months ago, # ^ |

Good luck Sigma!

→ Reply

blackronaldo

9 months ago, # |

finally unrated for me!

→ Reply

9 months ago, # |

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

→ Reply

9 months ago, # ^ |

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

→ Reply

9 months ago, # ^ |

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

→ Reply

9 months ago, # ^ |

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

→ Reply

9 months ago, # ^ |

Sure bro ,nice cover up

→ Reply

9 months ago, # ^ |

← Rev. 2 →

first appearance of that template 241442627

→ Reply

9 months ago, # ^ |

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

→ Reply

9 months ago, # ^ |

Okay sherlock

→ Reply

Karatinos

9 months ago, # |

Good luck to everyone and have fun!

→ Reply

__NO__NAME__

9 months ago, # |

Hoping for new learnings

→ Reply

Vampire

9 months ago, # |

flamestorm + div 4 = positive delta for me

→ Reply

yuanzihan

9 months ago, # |

I love div. 4

→ Reply

BlunderBoyI2

9 months ago, # |

I am dumb

→ Reply

Atma_

9 months ago, # |

Is this really div 4?

→ Reply

Wandoka

9 months ago, # |

RIP Div4 trusted participants

→ Reply

9 months ago, # |

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?

→ Reply

woonder

9 months ago, # ^ |

Hint

→ Reply

9 months ago, # ^ |

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

→ Reply

sajidali6567

9 months ago, # ^ |

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.

→ Reply

9 months ago, # ^ |

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

→ Reply

fernandezpalomojosue

9 months ago, # ^ |

← Rev. 2 →

247319547

→ Reply

9 months ago, # ^ |

Thank you !

→ Reply

BananaBrain

9 months ago, # ^ |

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

→ Reply

9 months ago, # ^ |

yeah just need to precompute once per t testcases

→ Reply

woonder

9 months ago, # ^ |

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

→ Reply

Nemona

9 months ago, # ^ |

← 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?

→ Reply

9 months ago, # ^ |

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

→ Reply

sajidali6567

9 months ago, # ^ |

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

→ Reply

9 months ago, # ^ |

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

→ Reply

9 months ago, # ^ |

sorry, I initially intended to reply to someone else.

→ Reply

9 months ago, # ^ |

you are right.

→ Reply

sajidali6567

9 months ago, # ^ |

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

→ Reply

9 months ago, # ^ |

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

→ Reply

Norp

9 months ago, # |

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

→ Reply

NotNanYan

9 months ago, # |

Maybe this is Div3 or Div2.5？

→ Reply

ilovenandini

9 months ago, # |

is this div4?

→ Reply

epiccodingmomento

9 months ago, # |

mathforces again...

→ Reply

Devil_7

9 months ago, # |

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

→ Reply

J.A.K.D.Z

9 months ago, # ^ |

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

→ Reply

NekoNPC

9 months ago, # |

seems this contest was too hard for a div4 contest.

→ Reply

9 months ago, # |

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

→ Reply

AlphaMale06

9 months ago, # ^ |

+35

do you really count prefix sums as dp...

→ Reply

9 months ago, # ^ |

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

→ Reply

m_nature

9 months ago, # ^ |

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

→ Reply

kjhhjki

9 months ago, # |

Awful contest as a div4. It sucks.

→ Reply

Fork512Hz

9 months ago, # ^ |

Catch

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

→ Reply

sh__r

9 months ago, # |

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

→ Reply

sliu17

9 months ago, # ^ |

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.

→ Reply

rmz

9 months ago, # |

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

difficulty : impossible

→ Reply

fverri

9 months ago, # |

My first contest, still a lot to learn

→ Reply

MKasirloo

9 months ago, # |

+10

Hardest Div. 4 ever

→ Reply

9 months ago, # |

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)

→ Reply

iordache_

9 months ago, # ^ |

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

→ Reply

9 months ago, # ^ |

← Rev. 3 →

Spoiler

→ Reply

9 months ago, # ^ |

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

→ Reply

9 months ago, # ^ |

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

→ Reply

9 months ago, # ^ |

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

→ Reply

9 months ago, # ^ |

← 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>

→ Reply

NekoNPC

9 months ago, # ^ |

← 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.

→ Reply

9 months ago, # ^ |

+13

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

→ Reply

dartvolley

9 months ago, # ^ |

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)

→ Reply

9 months ago, # ^ |

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

→ Reply

_Kee

9 months ago, # ^ |

+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.

→ Reply

9 months ago, # |

Does carrot shows rating change including official participants or overall?

→ Reply

9 months ago, # |

How to do C?

→ Reply

9 months ago, # ^ |

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

→ Reply

3FrenchOmelettes

9 months ago, # ^ |

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

→ Reply

9 months ago, # ^ |

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

→ Reply

9 months ago, # ^ |

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)

→ Reply

Akshay184

9 months ago, # ^ |

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

→ Reply

MKasirloo

9 months ago, # ^ |

← 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]$$$.

→ Reply

9 months ago, # ^ |

thanks

→ Reply

9 months ago, # |

+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

→ Reply

VirnaAilin

9 months ago, # |

+23

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

→ Reply

yellowbeard

9 months ago, # ^ |

more like Div 3 than Div 4

→ Reply

wkao

9 months ago, # |

Terrible experience

→ Reply

rishabhxchoudhary

9 months ago, # |

+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

→ Reply

boomfire

9 months ago, # |

← Rev. 3 →

Unfortunately，my rating will drop :(

→ Reply

qwscaln

9 months ago, # |

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

→ Reply

9 months ago, # |

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

→ Reply

1BeeNY1

9 months ago, # ^ |

← 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.

→ Reply

9 months ago, # ^ |

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

→ Reply

fztym

9 months ago, # |

I think the description of E is not clear enough.

→ Reply

carbonMonoxide

9 months ago, # |

247348183

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

→ Reply

Avik_AB17

9 months ago, # |

Awful Div.4! :)

→ Reply

itsdhruvaggarwal

9 months ago, # |

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??

→ Reply

OneFinal24

9 months ago, # ^ |

Because they past 2 problems but one for you

→ Reply

9 months ago, # ^ |

+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

→ Reply

NoticeMeSenpai

9 months ago, # ^ |

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'.

→ Reply

9 months ago, # |

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

→ Reply

BrotherCall

9 months ago, # ^ |

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

→ Reply

Contest 1 Contest 2 Contest 3

9 months ago, # ^ |

I didnt :(

→ Reply

OneFinal24

9 months ago, # |

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

→ Reply

Rakesh_898

9 months ago, # ^ |

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

→ Reply

Chrisedyong

9 months ago, # |

← 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

→ Reply

Owmicron

9 months ago, # ^ |

+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.

→ Reply

nskybytskyi

9 months ago, # ^ |

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).

→ Reply

Chrisedyong

9 months ago, # ^ |

← 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.

→ Reply

Basmala_Hekal

9 months ago, # |

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

→ Reply

Karatinos

9 months ago, # |

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!

→ Reply

BrotherCall

9 months ago, # |

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

→ Reply

rHermes

9 months ago, # |

← 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

→ Reply

Parshav01

9 months ago, # |

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?

→ Reply

adaptatron

9 months ago, # |

← 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.

→ Reply

yuanzihan

9 months ago, # |

div. 4?

div. 2.5!

→ Reply

shiinehata

9 months ago, # |

← Rev. 2 →

+17

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

→ Reply

garlic_bread_0204

9 months ago, # |

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

→ Reply

Miryz

9 months ago, # ^ |

wdym, checking two rows is a solution.

→ Reply

serenhade00

9 months ago, # ^ |

← 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.

→ Reply

garlic_bread_0204

9 months ago, # ^ |

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 ?

→ Reply

serenhade00

9 months ago, # ^ |

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.

→ Reply

BananaBrain

9 months ago, # ^ |

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

→ Reply

minhtran2404

9 months ago, # ^ |

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

→ Reply

calebmartim

9 months ago, # ^ |

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.

→ Reply

garlic_bread_0204

9 months ago, # ^ |

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

→ Reply

iordache_

9 months ago, # |

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

→ Reply

edv13

9 months ago, # |

problem f is harder than problem g :skull:

→ Reply

Devo

9 months ago, # |

+11

the last div3 is much easier than this round lol.

→ Reply

gokuu007

9 months ago, # |

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

→ Reply

9 months ago, # ^ |

-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

→ Reply

gokuu007

9 months ago, # ^ |

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

→ Reply

9 months ago, # ^ |

n in your case denotes mxN

→ Reply

9 months ago, # ^ |

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

→ Reply

llc5pg

9 months ago, # ^ |

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

→ Reply

gokuu007

9 months ago, # ^ |

oops silly me !

→ Reply

drdilyor

9 months ago, # ^ |

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) {

→ Reply

NEERAJ2003

9 months ago, # |

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

→ Reply

arash.

9 months ago, # |

← 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.

→ Reply

NEERAJ2003

9 months ago, # ^ |

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

→ Reply

treasuryonly

9 months ago, # |

+12

First time using Haskell in contest!

Screenshot

Thank you guys for the amazing round!

→ Reply

9 months ago, # ^ |

← Rev. 2 →

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

→ Reply

treasuryonly

9 months ago, # ^ |

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!

→ Reply

9 months ago, # ^ |

← 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 :)

→ Reply

Alice_Cartelet

9 months ago, # |

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

→ Reply

TrivialZzy

9 months ago, # |

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

→ Reply

matislu

9 months ago, # ^ |

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.

→ Reply

TrivialZzy

9 months ago, # ^ |

Thanks!

→ Reply

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

9 months ago, # ^ |

Like this: 247436179

→ Reply

TrivialZzy

9 months ago, # ^ |

Thanks!

→ Reply

Folka

9 months ago, # |

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.

→ Reply

rishabhxchoudhary

9 months ago, # |

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

→ Reply

Minerva2005

9 months ago, # ^ |

Wow!!

→ Reply

devansh_27

9 months ago, # ^ |

me too

→ Reply

ahnaf_sadi

9 months ago, # |

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

→ Reply

itsdhruvaggarwal

9 months ago, # ^ |

wait 24 hours

→ Reply

Ashnu

9 months ago, # |

Round 925 is easier than Round 928

→ Reply

Ran_Mouri

9 months ago, # |

Hint for c ... please

→ Reply

Folka

9 months ago, # ^ |

Pre compute all

→ Reply

karna001

9 months ago, # ^ |

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

→ Reply

Ran_Mouri

9 months ago, # ^ |

Thancks

→ Reply

quad_wipe

9 months ago, # ^ |

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

→ Reply

Ran_Mouri

9 months ago, # ^ |

Thank you

→ Reply

sashshaikh12

9 months ago, # |

← Rev. 2 →

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

Spoiler

→ Reply

llc5pg

9 months ago, # ^ |

-10

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

→ Reply

sashshaikh12

9 months ago, # ^ |

yes got it thank you!

→ Reply

VioletVal

9 months ago, # |

How do you solve E?

→ Reply

quad_wipe

9 months ago, # ^ |

← 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

→ Reply

AvaraKedavra

9 months ago, # |

← 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 ?

→ Reply

hashman

9 months ago, # ^ |

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));

→ Reply

AvaraKedavra

9 months ago, # ^ |

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 ?

→ Reply

hashman

9 months ago, # ^ |

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.

→ Reply

AvaraKedavra

9 months ago, # ^ |

thanks!

→ Reply

SoleProprietor

9 months ago, # ^ |

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.

→ Reply

RigilKentaurus

9 months ago, # |

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

→ Reply

BananaBoat_93

9 months ago, # |

lets go

→ Reply

RAW007

9 months ago, # |

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

→ Reply

Folka

9 months ago, # ^ |

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

→ Reply

RAW007

9 months ago, # ^ |

Thanks for your solution .

→ Reply

brainsoft

9 months ago, # ^ |

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

→ Reply

Zardosh

9 months ago, # |

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)

→ Reply

el_tunel

9 months ago, # ^ |

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.

→ Reply

Zardosh

9 months ago, # ^ |

Thanks!

→ Reply

jwacker

9 months ago, # ^ |

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

→ Reply

TG-STUDIO

9 months ago, # |

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

→ Reply

ykx2010

9 months ago, # |

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

→ Reply

MrPython

9 months ago, # |

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

→ Reply

9 months ago, # ^ |

me too。

→ Reply

TG-STUDIO

9 months ago, # ^ |

maybe = div3 f g

→ Reply

MrPython

9 months ago, # ^ |

maybe = div3 g f

→ Reply

TG-STUDIO

9 months ago, # ^ |

that's right

→ Reply

ahnafrahmn

9 months ago, # |

Where can I get solutions of the contest??

→ Reply

treasuryonly

9 months ago, # ^ |

Editorial is available.

→ Reply

xiojoy

9 months ago, # |

For me, F is too hard to solve.

→ Reply

joy_mara_khai

9 months ago, # |

How can I find the best solution for this contest?

please help I am a beginner

→ Reply

Zardosh

9 months ago, # ^ |

Try checking the editorial.

→ Reply

ParthJha17

9 months ago, # |

Was someone able to find a mathematical formula for C?

→ Reply

yashdabhade283

9 months ago, # ^ |

Yes I did checkout my submission

→ Reply

9 months ago, # ^ |

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

→ Reply

Eriksonas

9 months ago, # |

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

→ Reply

Harman001

9 months ago, # ^ |

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.

→ Reply

chenRenning

9 months ago, # |

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

→ Reply

9 months ago, # ^ |

← Rev. 2 →

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

→ Reply

serenhade00

9 months ago, # ^ |

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

→ Reply

9 months ago, # ^ |

I guess i have the badest luck then

→ Reply

chenRenning

9 months ago, # ^ |

Hopefully get to the blue before the provincial race :)

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

→ Reply

molla12

9 months ago, # |

← Rev. 2 →

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

→ Reply

molla12

4 months ago, # ^ |

It is not now

→ Reply

saelcc03

9 months ago, # |

Good bye pupil, Hello specialist

→ Reply

ashays

9 months ago, # ^ |

congrats bro

→ Reply

hushbek_2009

9 months ago, # |

361 Yes

→ Reply

9 months ago, # |

← 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?

→ Reply

ilovenandini

9 months ago, # ^ |

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

→ Reply

9 months ago, # ^ |

okey thank you

→ Reply

chabchoub

9 months ago, # ^ |

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

→ Reply

9 months ago, # ^ |

thanks

→ Reply

linshule

9 months ago, # ^ |

Perhaps you can refer to mine 247347016

→ Reply