mesanu, SlavicG and I are very excited to invite you to Codeforces Round 928 (Div. 4)! It starts on Feb/19/2024 17:35 (Moscow time). We would also like to give a very special thanks to the efforts of MikeMirzayanov and Vladosiya, who helped significantly with the preparation of the round!
The format of the event will be identical to Div. 3 rounds:
- 5-8 tasks;
- ICPC rules with a penalty of 10 minutes for an incorrect submission;
- 12-hour phase of open hacks after the end of the round (hacks do not give additional points)
- after the end of the open hacking phase, all solutions will be tested on the updated set of tests, and the ratings recalculated
- by default, only "trusted" participants are shown in the results table (but the rating will be recalculated for all with initial ratings less than 1400 or you are an unrated participant/newcomer).
We urge participants whose rating is 1400+ not to register new accounts for the purpose of narcissism but to take part unofficially. Please do not spoil the contest for the official participants.
Only trusted participants of the fourth division will be included in the official standings table. This is a forced measure for combating unsporting behavior. To qualify as a trusted participant of the fourth division, you must:
- take part in at least five rated rounds (and solve at least one problem in each of them),
- do not have a point of 1400 or higher in the rating.
Regardless of whether you are a trusted participant of the fourth division or not, if your rating is less than 1400 (or you are a newcomer/unrated), then the round will be rated for you.
Thanks a lot to the testers: MADE_IN_HEAVEN, Gheal, Dominater069, Phantom_Performer, Vladosiya, htetgm, hbarp, tvladm!
We suggest reading all of the problems and hope you will find them interesting. Good luck!
UPD: Editorial is posted!
Still a lot to learn.
How about you learn to grab my balls
This is ask to Ur mother mf that she grab ur balls or ur father's . I think she grab mine because you and ur father doesn't have any balls , all of u have wet pussy . MOTHERFUCKER Wait for me i'll fuck ur mother.......MF
My first unrated contest. Hope to solve all problems.
I am praying on your downfall i will be watching
Prey for ur mother becuase i fucking ur mother this week very hard and i think ur mother want ur help to apply medicine on pussy that break by me because ur dad have no balls mf
Literally me.
This was going to me except I sold earlier.
Also me
My last rated div4 :)
Hopefully this doesn't age poorly
I remember the night after Codeforces Round 922 (Div. 2) this was the only contest on schedule. What I didn't expect is the whole week of contests from Feb11...
And finally time to end the winter vacation in a relaxing Div.4
Hope to AK.
Nice :)
7:51 PM
Yaa that's for me i am getting negative points from last few contests... Finally i can get some points :)
Dsy before yesterday this was unrated for me. Today it's rated. Tomorrow after rating update of today's div3 this will be again unrated for me
as not a tester i would like to solve them all
After such a long time, a division 4 contest!
Meanwhile:
One month of C.P.,hope I am able to solve at least 4.
I hope I dont become unrated in this after todays Div 3. Plzz rating be below 1400.
Salam Alaikum to everyone
If my rating before the begining of this contest is lower than 1400, but then(after the begining)it increases(because of previous Div3), will I be rated participant or not?
Rating distribution please.
It says ICPC
Если до этого див4 рейтинг с прошедшего див3 не успеют пересчитать, то есть я начну писать див4 с рейтингом <1400, будет ли раунд рейтинговым для меня?
мне кажется да
ну, к сожалению, втот раз они решили пересчитать рейтинг быстро( так что я 100% анрейтед
My first unrated Div 4 ;-) Still lots to learn...
same
Mam nadzieję, że ten konkurs wypadnie dobrze
the rating predictor is showing me -10 after the last div3 so i should be allowed to participate in this div-4 but they are not allowing me for now so is there anything that i can do
Can you share that predictor here too :)
Carrot
How is ur rank 2800 even after solving only 3?
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.
Being a tester of this round i can easily this is worth giving for participants of all rating... You can push your time limits.
Cyan pls
Good luck!
OMG!!!
How many days left? :)
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.
Let's Hope , this contest makes me pupil
My first unrated Div4:)
been waiting for this for a while lol
how to get the emoji
He edited HTML code
First unrated contest :)
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+ ?
yes
This becomes unrated for me after yesterday's Div3 rating changes :/
omw to make <300 score.
This is my first competition is that okay?
Why not? Good luck!
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
It's funny how jealousy's got him moving mad like this.
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
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,
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
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
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.
Wait how do you know him.
My first contest , happy to participate in it
good luck and high ratings :>
Hope this will be a fantastic contest me and all
I recently became Specialist, have given only 3 contests after becoming specialist. Is it rated for me or not??
if I make an unsuccessful hacking attempt will I get a minus rating??
first time participating, can't wait
Good luck for everyone!!!!!!
Good luck Sigma!
finally unrated for me!
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
I often ask chat gpt to fix my code ergo the other templates.
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
That don’t copy my shit code comment is mine. It used to be over my dummy functions so yeah that’s that
Sure bro ,nice cover up
first appearance of that template 241442627
Bro no need , u copied that and obviously you will change to get safe Plag yk
Okay sherlock
Good luck to everyone and have fun!
Hoping for new learnings
flamestorm + div 4 = positive delta for me
I love div. 4
I am dumb
Is this really div 4?
RIP Div4 trusted participants
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?
N is small, try to precalculate anwers for every n.
yeah i did that because I couldnt prove that the repetition could be generalized into a formula.
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.
I saw submissions which used this property tho , cant find it now , hard luck for us i guess
247319547
Thank you !
Are you saying looping over 1e5 and storing all results would pass in 1/2 seconds ?
yeah just need to precompute once per t testcases
It is possbile to precompute answer in O(n), then you can answer queries in O(1)
Actually precalculation is O(nlogn). For integer n, compute the digit sum of n is O(log n). Or is there any optimization?
Because it has many testcases.The force algorithm in O（Tnlogn）in bad case。
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
Of course, I mean solving it in brute force instead of precalculating the problem.
sorry, I initially intended to reply to someone else.
you are right.
Hey, log n is 5 at max so it is O(5*n) which is O(n)
In same，it can be regard as log10^n.
Are this Div.4???? Maybe Div.3??
Maybe this is Div3 or Div2.5？
is this div4?
mathforces again...
it is not div4 , it is div 2.5 or div3 and also C problem is not easy
I'm agree. It was like Div 3 but problem C is okay because it said that time limit of problem is 0.5.
seems this contest was too hard for a div4 contest.
loved the div. E is brilliant , i don't think div 4 contestants would know dp though to put it in C.
do you really count prefix sums as dp...
ooh yeah you're right , dp was what came in my mind that time but yeah it's prefix sums my bad
I think precomputation would fit better for the name of the concept lol
Awful contest as a div4. It sucks.
Catch
IMO this is unfriendly for div4, esp. D and F I keep failing F as well
Testcase 3 on D kept failing, What is the reason overflow?
I had the same issue. Try this case:
Output should be 3, if you got 4 it's the same mistake as mine.
Try not to make half the problem set depends on math challenge.
difficulty : impossible
My first contest, still a lot to learn
Hardest Div. 4 ever
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)
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
notice that the answer is always at most 8. This reduces the number of possible choices significantly (
198 440possible variations in my solution).so maybe i just can bruteforce on all state with a bfs like apporach?
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:
It makes no sense to flip any cell on the border.
It makes no sense to flip at locations
(2, 2),(2, 6),(6, 2)and(6, 6).thanks i got the first spoiler but didn't get the last one but i will think in why its true thanks alot
Yes, the last one is the hardest to grasp. Without it my program run about 10s.
(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>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.
oh i didn't think on that i was thinking in something like n2 * 2^49 thanks
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)
thanks alot first time hearing about that technique i will check it out
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.
Does carrot shows rating change including official participants or overall?
How to do C?
pre compute the answer for all n u can do that by using prefix idea
thought this approach would TLE, so spent over an hour thinking of a O(1) math solution that doesn't exist fml.
same, tried solving based on the pattern from 1 to 9 in ones place
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)
I believe just pre-computing all the value before hand will work.
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:
then for each input $$$n$$$, output $$$a[n]$$$.
thanks
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
hardest div4 ever. The writers should include more low rated people in testing.
more like Div 3 than Div 4
Terrible experience
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
Unfortunately，my rating will drop :(
Spent a lot of time on C, hated it, but it turned out to be very simple, kinda liked it eventually :)
how to solve F though, i was thinking backtracking but the complexity is too big
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.
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
I think the description of E is not clear enough.
247348183
for problem E can someone tell me if it is correct or not?
Awful Div.4! :)
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??
Because they past 2 problems but one for you
in ICPC style contests there is no assigned difficulty to each problem, all are the same,since he was faster , he is ranked higher
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'.
Ill miss specialist by 3 points :(( carrot sowing 40, i need 43
You needn't worry . Carrot often underestimates the growth rating . According to my experience you will get specialist this round :)
I didnt :(
it is too hard for div.4 F，F hard than G too much，i think maybe F can be 2000+
Check my submission for F.I use recursion without using dp but it passed.. https://codeforces.com/contest/1926/submission/247337741
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.com/contest/1926/submission/247343993
I am pretty sure your solution is correct. The problem can be reduced to finding the minimum cut from every node labeled
Pto every node labeledS. 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.
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).
I think you are right. I did not use the property of unit graph in order to compute the time complexity. My bad.
what's wrong with the author it's even more difficult than div3!!!!
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!
This div4 round is not easier than most div3 round I met . Did CF notice during the check process？
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
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?
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:
Contest 1 Contest 2 Contest 3
My submission, based on the ideas discussed in the blog.
div. 4?
div. 2.5!
Codeforces Round 928
(Div. 4)(A + Div. 3)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
wdym, checking two rows is a solution.
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.
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 ?
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.
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
I think that the it's a triangle if any row got only 1 char '1'
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.
...
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.
thanks...it was helpful...will follow this from next time...
Haha B took me 35 minutes, but C took me 4, D took me 5 and E took me 27
problem f is harder than problem g :skull:
the last div3 is much easier than this round lol.
can anyone tell why am I getting TLE ? https://codeforces.com/contest/1926/submission/247263560
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
what does n denotes here ? the number n itself or the digits of n
n in your case denotes mxN
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
Change
int dp[mxN];toint dp[mxN+1];. See 247374406oops silly me !
to_string(x)works in O(num digs of x) = O(log x).Your code is TLEing because of accessing
dp[mxN]when size ismxN. And this causes an undefined behavior.Great round really enjoyed hope to have 5 minutes more as so I could submit G within time although kudo's to whole team.
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.
Ya my approach was same I just did dfs calculate for child then for current node make the above cases
First time using Haskell in contest!
Thank you guys for the amazing round!
The code looks like a literal translation of C++ though, each function having
dodefeats the idea of Haskell.Yes, the code may look
Clike but actually that's all I know aboutHaskellso far and I'm comfortable with this style, I find it readable and easy to debug if needed also.And since it's
Div4so I want to make something new beside usingC++in almost every round, I think I will useHaskellmore often in the future.Thank you for reading my code and commenting!
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 :)
Great problems, but I think F is a little hard in Div.4 and G is too easy to be the last problem.
Can anyone tell me why I am getting TLE? How can I modify it? https://codeforces.com/contest/1926/submission/247369927
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.
Thanks!
Like this: 247436179
Thanks!
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.
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
Wow!!
me too
My first Rated Contest!!!!!!!!!!!!!!But yet rating not showing.......
wait 24 hours
Round 925 is easier than Round 928
Hint for c ... please
Pre compute all
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
Thancks
initially you need to realize this
sum(10^n-1)=45*(10^n-1)+sum(10^(n-1)-1)*10Thank you
could anyone tell me where my code will fail for problem D, i am getting WA on test case 3
https://codeforces.com/contest/1926/submission/247380111
for each element in the vector, i am mapping it to its complement. after that, i iterate over all elements, and if the current elements complement is not present in multiset, i add that element to the multiset, or else i will remove that elements complement from multiset. at the end answer is size of multiset
When input is with length of 4:
0 2147483647 2147483647 2147483647, you answer gives 1. Correct answer is 3.yes got it thank you!
How do you solve E?
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
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 ?
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.
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 ?
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.
thanks!
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.
For D,Using Unordered_map is pure Hell,What this Contest Taught Us.Ordered Map is always better!
lets go
I was able to solve 1st and the 3rd problem during the contest but i find hard to implement the second problem .
You can have a look on my solution 247235514, it is very easy to understand and smart solution
Thanks for your solution .
Do you need a more easy solution? Check 247233776 it out. I will never mind.
Why does this get TLE https://codeforces.com/contest/1926/submission/247355922 while this doesn't https://codeforces.com/contest/1926/submission/247356724 ? Only difference is unordered_map vs map (unordered_map is getting TLE while map isn't)
It's because
unordered_mapuses 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.Thanks!
How do we generate test cases to hack a solution that uses unordered maps?
in the last div3 i solve 5,and this time i solve 5 too but with higher rank!
I hope to turn to a pupil in this contest because all my friends are green and even higher.
I think F and G are harder than div.3...
me too。
maybe = div3 f g
maybe = div3 g f
that's right
Where can I get solutions of the contest??
Editorial is available.
For me, F is too hard to solve.
How can I find the best solution for this contest?
please help I am a beginner
Try checking the editorial.
Was someone able to find a mathematical formula for C?
Yes I did checkout my submission
you can read my comment, I have been posted it 4-5 minutes ago
I am below 1400 rating, why was the contest not rated for me?
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.
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
Same here bro.. missed by 11 points :(((( going to die Carrot is the worst predicator
ikr, I usually get more rating than carrot's prediction, but this time got lower rating.
I guess i have the badest luck then
Hopefully get to the blue before the provincial race :)
Chin up, I believe it is not far from being realized
It was my first and last rated Div.4 round.
Good bye pupil, Hello specialist
congrats bro
361 Yes
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?
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
okey thank you
Check my submission for C I used recursive function to solve it
thanks
Perhaps you can refer to mine 247347016
thank you
I forgot 2 do it
=(
I was waiting 4 it as well
guess I have 2 wait few weeks =(
i 8 pizza yesterday.
I 1 every chess game 2 day
hii
забыл про соревнование :_(
Div.4A + Div.3BCDEFG
I use ideone. I was not aware of this. Please don't block me or give penalty as I do not know about this
Hello, due to the message I received that my code for the Problem C is very similar to some other people's, I have seen this problem before in GeeksForGeeks and I knew the solution . I think I did not do anything illegal!
CODEFORCES ROUND 928 DIV4-
For the Question C of the contest codeforces round 928,I got this message
Your solution 247285175 for the problem 1926C significantly coincides with solutions JonahWeaver/247270977, arnavra3/247285175, Jelly.bean/247290520. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
I have evidence that the function that i have used for the question https://codeforces.com/contest/1926/problem/C was already published long before the contest.
The coincidence occurred due to using the same function to solve the question. (coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details). This is the function used to solve the question- https://www.geeksforgeeks.org/count-sum-of-digits-in-numbers-from-1-to-n/
Thanks for your time and for looking into this.
CODEFORCES ROUND 928 DIV4-
For the Question C of the contest codeforces round 928,I got this message
Your solution 247332861 for the problem 1926C significantly coincides with solutions Banik1313/247268922, mahendraakshansh/247332861. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
I have evidence that the function that i have used for the question https://codeforces.com/contest/1926/problem/C was already published long before the contest.
This is the function used to solve the question- https://www.geeksforgeeks.org/count-sum-of-digits-in-numbers-from-1-to-n/
Further a small change was done by changing the functions variables using gpt. Thank you for looking into this.
On my C problem in round 928 (Div 4) I got this message from the system:
"Attention!
Your solution 247290520 for the problem 1926C significantly coincides with solutions JonahWeaver/247270977, arnavra3/247285175, Jelly.bean/247290520. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked."
In my solution, I took reference from an online website https://www.geeksforgeeks.org/count-sum-of-digits-in-numbers-from-1-to-n/
It was already uploaded on the website long back, and using it thus does not violate the rules and regulations probably.
I thus request you to look into this matter and do appropriate changes.
Thankyou
I received a mail as follows:-
Attention!
Your solution 247340583 for the problem 1926E significantly coincides with solutions sahilPict_26/247340583, MisterCheese/247358707. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
I am really sorry if you find anything misbehave, but I have done the code myself, and I have used ideaone platform in public mode, because of it some one might have copied it , I don't even know the person MisterCheese. I will definitely take care of it from next time so please give my rating back as you can see my past contest history I have never tried to copy or misbehave during the contest,And I promise you I will take care of keeping my code private during the contest.
I also have refered an function which was already available on internet before the contest:- **https://www.geeksforgeeks.org/minimize-replacements-of-array-elements-to-make-bitwise-and-greater-than-k/**
This is the website were I refered the function it might be because of that the solution may look similar.
CODEFORCES ROUND 928 DIV4-
For the Question C of the contest codeforces round 928,I got this message
"Attention!
Your solution 247268922 for the problem 1926C significantly coincides with solutions Banik1313/247268922, mahendraakshansh/247332861. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked."
I have evidence that the function that i have used for the question Problem Link was already published long before the contest.
The coincidence occurred due to using the same function to solve the question. (coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details). This is the function used to solve the question- Coinciding Fuction Written well before the contest
Thanks for your time and for looking into this.
CODEFORCES ROUND 928 DIV4- For the C Question, I got this message:
Attention! Your solution 247303195 for the problem 1926C significantly coincides with solutions saikumarailwar9/247274058, ved292/247303195. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
I have evidence that the function that i have used for the question https://codeforces.com/contest/1926/problem/C was already published before the contest.
The coincidence occurred due to using the same function to solve the question. This is the function used to solve the question- https://www.geeksforgeeks.org/count-sum-of-digits-in-numbers-from-1-to-n/
Kindly look into it.
They removed our rating for a similar code with a person with whom we study together, but they analyzed a similar problem and wrote down the code in a notebook.
E: Would building an Euler tour and then looking at pairs of nodes of the same colour with no other node of the same colour between them on the tour work? Update: Nope. And wrong thread altogether. :)
I have received an attention for the problem https://codeforces.com/contest/1926/problem/C of Codeforces Round 928 (Div. 4). The message was here. Attention!
Your solution 247303669 for the problem 1926C significantly coincides with solutions sntanju07/247303669, Rafid_Nabil/247351936. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
The code I have used from https://www.geeksforgeeks.org/count-sum-of-digits-in-numbers-from-1-to-n/ which was last updated on 27 Jun, 2022. That's why, I can prove that the code exists before the contest. The coincidence occurred for using a common source.
Please consider it. Thank you.
I have received an attention for the problem https://codeforces.com/contest/1926/problem/C of Codeforces Round 928 (Div. 4). The message was here. Attention!
Your solution 247310309 for the problem 1926C significantly coincides with solutions kurvep18/247310309, Ritiksharma_09/247338668. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code). If you have conclusive evidence that a coincidence has occurred due to the use of a common source published before the competition, write a comment to post about the round with all the details. More information can be found at http://codeforces.com/blog/entry/8790. Such violation of the rules may be the reason for blocking your account or other penalties. In case of repeated violations, your account may be blocked.
The code I have used from https://www.geeksforgeeks.org/count-sum-of-digits-in-numbers-from-1-to-n/ which was last updated on 27 Jun, 2022. That's why, I can prove that the code exists before the contest. The coincidence occurred for using a common source.
My codeforces id :- kurvep18 which was registered with email :- [email protected] has been blocked by codeforces, please review this comment and consider reactivataion of my id [kurvep18]
Please consider it. Thank you.
Dear mesanu, SlavicG, flamestorm I got to know that my submission 247357510 was similar to a few other submissions. All I did was copy a template (As I'm a newcomer, I didn't have any submission template with me. So, I literally took a template as it is from a CodeForces blogpost) which is available online on GitHub, link to which is :- https://ncduy0303.github.io/Competitive-Programming/Contest%20Template/main.cpp
Could you please check this. I assure you that I've not cheated in any way. Even the approach taken to solve the problem is a generic approach using bit manipulation & maps.
https://www.google.com/amp/s/www.geeksforgeeks.org/number-of-mismatching-bits-in-the-binary-representation-of-two-integers/amp/
I used the concept of Approach 2 provided in this article. Please look into it and do the necessary.
Thank you
My Submission link ved292's submission
Article i copied from
Blog about rule for third party code
According to the 1st point mentioned in the blog
the code was written and published/distributed before the start of the round,
I haven't copied this solution from him it was an coincidence that my code is matched with his code
I request you to look into this issue MikeMirzayanov
A to E was OK, F was much harder.