Hello Codeforces!
On Mar/18/2021 17:50 (Moscow time) Educational Codeforces Round 106 (Rated for Div. 2) will start.
Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.
This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.
You will be given 6 or 7 problems and 2 hours to solve them.
The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.
Good luck to all the participants!
Our friends at Harbour.Space also have a message for you:
Dear Codeforces!
We are coming with another scholarship opportunity to share with you. This time, our scholarship is targeted towards the brightest women in the community.
As you might know, March is the month where the whole world celebrates women. At Harbour.Space we want to use this opportunity to encourage more women to join the tech world and challenge the gender-bias in this field.
We believe that gender equality in the workplace starts with gender equality in the classroom. For that reason, we are offering our Women in Tech Scholarship. The scholarship consists of:
- 50% off the yearly tuition fee: covers around €29,000 for bachelors and €11,450 for masters.
- 32% off the application fee: €85 instead of €125
You can find more information about the scholarship here.
Make sure to apply before March 31st to benefit from the scholarship and discount.
Don’t hesitate to share this opportunity with any bright women in your personal circle as well. A simple share can help us transform someone's life.
We are always happy to see Codeforce members join the Harbour.Space family.
Keep in touch and follow us on LinkedIn for more scholarship opportunities. And follow us on Instagram to stay in touch with our student life, events, and success stories from our students.
Good luck on your round, and see you next time!
Harbour.Space University
Congratulations to the winners:
| Rank | Competitor | Problems Solved | Penalty |
|---|---|---|---|
| 1 | dlalswp25 | 6 | 128 |
| 2 | Maksim1744 | 6 | 138 |
| 2 | Savior-of-Cross | 6 | 138 |
| 4 | nuip | 6 | 149 |
| 4 | kotatsugame | 6 | 149 |
149 successful hacks and 1485 unsuccessful hacks were made in total!
And finally people who were the first to solve each problem:
| Problem | Competitor | Penalty |
|---|---|---|
| A | pavement | 0:01 |
| B | PCTprobability | 0:04 |
| C | PCTprobability | 0:08 |
| D | Parliament | 0:09 |
| E | KaladinStormblessed | 0:17 |
| F | 718_MiL | 0:10 |
| G | rainboy | 1:27 |
UPD: Editorial is out
Please don't make round unrated during contest time. Which is cause Big heart break (Like last div 2).
why so many downvotes?
Bruh when the hell did they want to make a round unrated before it begins ... That just happens against their will for some unexpected reason
Hoping for not getting unrated in this round...
Wish all run as usual...
Round Delay 15 Minutes
Hoping a good round
Here also women are being supported. Why to support based on gender? Skills should be the only criteria, irrespective of any stupid thing in the world. Rather scholarship should be given to the deserved ones who may not afford the fees.
Everyone is allowed through the common channel then why to create a separate channel for women.
This creates 2 channels for women and 1 channel for others.Is this equality? This is inequality for others.
So, now what you will do to attain equality again?
Even though we can find highly skilled women, but the tech field is more or less dominated by male experts. So it's just an effort to popularize tech more among women by giving the scholarships only to them, because otherwise most probably men will take major portion of the scholarships once again.
And yeah, "equality" is probably not what's going on here and achieving "equality" is probably not the actual target, but you cannot be brutally critical and honest in your advertising, can you? :D ..
The same thing is with the less skilled male students as well. They are trying hard but not able to get to the top. Then a new channel should be created for them as well. Eventually, everyone will be on top then.
In a real time situation, only the skilled person will be able to do the work in the best way no matter what the gender of that person is. And the people who have reached there through other channels will increase the load on the skilled people by not being able to do the things properly.
well said sir you have my respect
Everyone should get equal opportunity and chances to grab any position in any institution but only capable one should hold that irrespective of their gender, background and culture. We must focus on creating equal opportunities.
If I was born in Brazil and I was interested in football, probably I will make it a profession. But if I am born where I am born, I will dare not try to make football my profession. It's not about less skilled people of the community, it's about those who have potential but rather not look into this field, due to lack of motivation, lack of personalities to look up to.
Ok, then what about those who are not female and have lack of motivation and all.
Why steps are not being taken for them?
Because women empowerment is like the trending page of youtube in today's society. What more can be said. But from what I have seen, harbour space has offered a lot of scholarships in the past, so one time giving them to the female, I don't think is exaggerating the issue and is bearable to me.
Because demotivated people have the opportunity that everyone else has, lack of motivation is a personal issue whereas women face hurdles because of their identity, i.e. being a woman. It has nothing to do with the individual bt instead with the society we live in which is why it is imp for the society to fix the inequality that occurs in it. This is why the 2 cases arent comparable.
It is worrying that your comment has a negative contribution
****For those who want to Down Vote, look at this 3 minute video then its your choice to down Vote**** ****Your text to link here...**** ****https://www.youtube.com/watch?v=4kFC7669quE****
I support the scholarship for women and this picture says a lot about why I do, it is called Equity it much better than Equality. Support ++, it's not about the gender it's about people and society if you are in a country where females need more support we should need to do it if you are in a country where males need more support we should need to do it. And I believe this scholarship is provided to females because the place where it provides need more support for female.
https://www.salvationarmy.org.nz/sites/default/files/uploads/screen-shot-2020-03-18-at-10.43.47-am.png
Oh, You mean to say that women are weaker and need extra support in order to become equal to men?
So, as shown in the picture, please explain in what way are they "handicapped"?
@errorfound No one is saying neither women are weaker nor men's as well, it's been said that in some places women need to be given more chances for their development and in some places men's need to be given more chances for their development. it depends on the society in which they are in and they need to be supported. I don't know why are you using the work "Weaker", no one is weaker it's just some people need to be given chances. I am not saying women are handicapped, the context of the image is entirely different.
giving equal opportunity to all is good but in some places, some people are need to be given more opportunity(it does not mean to be men or women)
From where I belong to, I have always seen both genders treated equally. Then why we have to give women more chance?
Ok, tell me one place where men are given more chances
@errorfound, I am happy that you are in a place where both genders are treated equally. but it does not mean all part of the world is same as where you are from. there are still places where women need some support and these scholarships are meant for the same. I can understand women are given more opportunities much better than past but still in some places they need support and we should do it.
uplifting them through such means is also a form of sexism. What about a more talented male who is left out just because of his gender. Is it his fault that majority of people in his field are male?
@Sundaram_Sharma, just because a fraction of the total population of women were given the small opportunity does not mean all the opportunities for men were taken by them. can you say a company has 100 vaccines and the entire 100 vaccines are filled with females? , even now companies were trying to make male-female ratio 70:30 in all companies, before few yers the ratio of male to female is 95:5 where are you during that time why did you raise your voice against it? "what is flat in being women Since the majority of people in the field are men why arent they are given equal postings?", try to understand no one is trying to take means opportunity, they are creating more opportunity for women
ok "just a fraction of total women population" is not the right way to put it. I have seen this first hand in my college. Secondly, even if it is a fraction it is unfair and that is what matters. How am I supposed to respect my female colleagues when I have seen so much bias. As for the time when ratio was 95:5, I was at the age that I didn't understand the word feminism then. And even if the ratio was 95:5 without any bias in selection, it is totally fair. Women are given 33%,even 50%, reservation in political and competitive seats in many places and fields. why aren't they given 50% reservation in the job where they have to clean sewers. Even there, male have a much higher ratio, even more than 95:5. It will take 20 30 more years for a large group of people to see how much damage feminism has caused. till then we gotta suffer.
nice one bro
A hypothetical reason maybe that sex ratio plays a vital role when meritorious males are unable to decide their college out of their own best choices... harbour does wants to fill in every hole..
Please refer to my comment that is just above your comment
It's not a coincidence that there are much fewer women in programming, engineering, science, etc.
Pretty much every culture in the world normalizes stereotypes about women. Being overly superficial, tying their self-esteem to whether they look attractive, feeling pressured to marry and have children so they don't "fail" as females, among many others. Imagine your family, friends, and community all having these types of expectations about you, ever since you are born. I don't think you'd be very motivated to face the enormous challenges needed to thrive in the tech world or other areas dominated by men. You'd be distracted trying to fit in to this toxic social expectation.
These extra opportunities for women attempt to compensate this cultural disadvantage, and try to fight the huge stigmas that constantly pull women back from professional success in man-dominated areas. It doesn't even come close to fixing social female oppression as a whole, but it's a start.
This was the case earlier. Now women are CEO of companies, are doing everything which earlier only men did and there is no barrier for them in any field.
The thing is: by supporting females everywhere and to such an extent, is this justice for others?
Rather, now others are struggling in the same way women were struggling earlier.
So we are in the same situation again, but this time men and others are the victims.
Stereotypes still exist, although in some cultures very little. I don't think men are the victims at the moment and they won't be in the near future
I don't know about other fields but in IT Jobs men are the victim. In order to maintain gender ratio, females are being hired in large numbers over others. This leads to other candidates not getting the job they deserve.
Hence Proved!!!
One such example is this: https://mirror.codeforces.com/blog/entry/82937
Consider all people who have the mind to become engineers. Of all these people, the females are at a disadvantage in that they are less likely to become engineers than the males.
Efforts to promote women aim to compensate for this disadvantage.
Ok, then promote in all the fields.
Make gender ratio equal in the Army as well.Do you think this will be fruitful for the country?
Rather this will ruin everything. Now consider the same logic in other fields!
I think Harbour Space does not care about the gender ratio in the army. And probably they do not care for "if it is good for the country", whichever country that could be.
But they care for if women have equal chances at Harbour.Space, and because of this they are doing something there.
Thant was an example.
You are saying that they are giving equal chances this time, that means they were not giving equal chances before.
Can you show me any single post from harbour University where they said that they will not entertain women?
Every time every where equal opportunities are being given to everyone.
Hence, no need of 2 opportunities only on the basis of gender
We are going in circles, see https://mirror.codeforces.com/blog/entry/88744?#comment-771912
I find it worrying that one extra scholarship from one university seems to trigger you more than the wage gap, work environment harassment, pregnancy discrimination, and many other historic world-wide proven injustices women face in professional fields.
You either lack empathy to understand women's ongoing struggle against gender inequality, or you need to inform yourself better about the subject.
Hey Eiden, I also think too much support is given for females. What you are saying did exist but not do exist. Even if it exists it is very little. Now a days only women are taking advantage over men by providing false accusations, gaining sympathy even it is her fault or etc..
Also women also have many advantages over us. So i dont think giving extra support to them is needed. Pls look at this video.
https://www.youtube.com/watch?v=e57iXe-QJio
Better words were never spoken.. Thanks you made me re-realise few things..
Gender norms,Cultural Stereotypes are not the only reason. We have to admit that there are fundamental differences between genders. Those differences also play a role in this.
'Gender specific opportunities' is an over simplified solution for a very complicated Sociocultural problem.
LOL!!! It is obvious that there are differences between genders. So, what about those fields in which there are a lot of women, so are male being given "Gender specific opportunities" in that field.
If you find such a thing then please tell me about it.
And talking in general, if you are stuck in a problem then who will be able to solve it, a skilled person or a person who is not skilled but is the one who was given "Gender specific opportunities" ?
I'm confused.I did not say that we need gender quotas because of differences between genders.my comment was against gender quotas.smh
...
Please enlighten me on what fundamental difference makes it more difficult for women to have jobs in tech(as this post is concerned with).
It doesn't makes it more difficult for women.(Maybe in some cases it generally affects any carrier. Like having to take care of a baby) I think those differences affects their preference. There are many reasons. Men tends to work more hours than women. Women were evolved as the caretaker of the family so they prefer carriers in healthcare etc.
Please note that I'm generally speaking and not telling what women should and shouldn't do. To achieve equal representation in STEM fields we have to consider about those reasons too. That's why i said gender quotas are an over simplified solution.
No one advocated gender quotas. No one believes having gender quotas will solve the larger cultural issue. He specifically mentioned having extra opportunity.
Interesting how on a post about fewer women in STEM, you immediately imply an inherent gender difference, then immediately backpedal.
"These extra opportunities for women attempt to compensate this cultural disadvantage,"
These extra opportunities are for the cultural disadvantage.
I did not "immediately imply an inherent gender difference". These extra opportunities only focus on a single aspect of the problem. My effort was to just imply that there are more aspects of the problem. One of them being inherent gender difference.We can't completely fix a large problem right away so that strategy is fine as long as it does not affect negatively on other groups. And i don't think i backpedaled. I stand by every statement i made.
Women are just as qualified as men to do STEM jobs. If they are a minority in those fields, it's because society has historically pressured them to stay away from them, by maintaining incorrect, vicious stereotypes and stigmas such as the ones you're claiming right now.
I think this video is informative and/or entertaining, in terms of the state of neo-feminism (at least in the West). It's worth a watch!
But does it actually help? How can women in IT be equally respected (as they should be) if we might assume they got there easier?
It's harder for women to thrive in the tech world because they face extra challenges of gender inequality and stereotypes. Giving them a small nudge like a scholarship helps relieve them from that extra effort.
Therefore, it's wrong to say they "got there easier". Otherwise, a woman in IT could say you got there easier than her because you never struggled against gender inequality on your way there.
Maybe I am less informed on this matter, but I feel like you are exaggerating. I am a male and my mom has already started pressuring me to marry and have children even though I don't want to. On top of that, it's expected of me (as a male) to look after them financially. No matter how stressed or hurt I am, I am told to man up and hide my emotions. I am not that distracted trying to fit in to this toxic social expectation and I hope I won't be in the future. I have sister and some female cousins. I have never seen any of them be pressured for looking attractive, we all were instructed to look tidy.
Creating a separate competition based on gender doesn't solve the roots of the problem (some people's weird thoughts and some other people's vulnerability to those thoughts). Doesn't it mostly benefit women who were privileged (born into good family, hence doing better because of having less distraction / pressure from immediate surroundings)? I can understand doing so in some sectors like medical / psychiatry (as female patients may feel more comfortable having female doctors), but why IT?
There are toxic stereotypes about men as well, and I'm also firmly against them. But it's less likely for them to pull us back professionally. Women are prone to be catalogued as more delicate than men, which translates as weakness or unpreparedness for professional challenges or leadership positions. Also, women are still mostly expected to quit their job when they have children, to take care of them. Moreover, being a stay-at-home dad is still viewed as a lack of masculinity. Ask your mom what she would think if your wife worked to sustain you while you have no job and stay home taking care of your kids.
Eventually, women who have talent and potential for IT jobs are discouraged by these realities, leaving only men in charge of them, even if they're less prepared. Then, the next generation of girls finds out there's no women in IT, catalogue it as a man's job, and feel unmotivated to choose it as a career. Measures like this scholarship aim to break this vicious cycle, and make sure women don't waste their talent due to cultural oppression.
Gender inequality happens with women of all social statuses. So even if a privileged woman gets the scholarship, it still helps combat social stereotypes, because it normalizes the idea of women doing "men's jobs". They might even inspire girls not born in privilege to fight their way into a tech job themselves.
You mention women inclusion important in medicine and psychiatry, but not in tech. You are misunderstanding what all this is about. The ultimate goal of work equality is that everyone should have a chance to choose their profession, without being judged, stereotyped, or harassed in any way for their decision.
Thanks for explaining. I kinda get your point, but I can't agree with your last statement, I don't think women are currently being judged, stereotyped or harassed for joining IT. At least rational people don't have such stereotypes. But if some women get their job easier, that will definitely put that idea into others' mind and even rational people may start having stereotypes that women got their job despite being less qualified and it may hurt real qualified women.
Apart from that, I agree with you.
When you say that it mostly benefits women who are privileged, this is true because of the wider economic oppression within society. To combat this, we don't ignore the gender based oppression, instead, it is necessary to take up an intersectional viewpoint which considers both economic and gender oppression, this includes supporting women in IT(which has been a predominantly male-dominated field, and women historically being pushed out), and supporting poor, lower class people and women in IT.
I agree, but when were women pushed out from IT? Maybe they were left behind, but not pushed out. Maybe they are less interested in it? School students don't usually have much burden due to gender, but how many high school girls (compared to boys) participate in math or informatics olympiads or try CP?
Attack on Feminists!
Ironically that is pro-feminism, since feminism is based on the advocacy of women rights on the basis of equality, and I think it is a solid argument that exclusive scholarships abuse the notion of equality.
When there's concern for women, it's concern for the women community as a whole, but when a there's a talk of the man it's only about that particular man.
Nobody stands with him but himself. Is this what feminists wanted? congo succeeding for sure.
I also agree with you. Let's make a movement #maleequality. Let all men not participate in today's round as symbol of protest. To show your protest, I request all men on this platform to downvote the blog and not participate in today's contest.
Those who are downvoting my comment are SIMPS. If you are man enough, upvote my comment.
lol no
Why to support based on gender? Skills should be the only criteria,
Can you develop good programming skill, if no-one around you do programming, no-one support you or appreciate you for your programming skills, or people say it's not for someone likes you.
I do programming because, its in many way rewarding for me and there is lot of things that motivates me.
P.S Exception may exist, but we are talking about ordinary humans.
MikeMirzayanov geranazavr555 cannor147 brother please note that whenever participants goes around 20k, the website crashes. Please do the needful ASAP! Observing this thing from a long time!
Please Upvote guys to make this noticeable to team CF!
You can be noticeable with negative comment too! :D
Can we please bring this announcement on top of today's round(708)?
Finally now it's on top!!!
Welcome to ratism
:(
Expecting a good round without any failure and a high rating increase to all ^_^.
We are for gender equality that's why we make supportive only for women. Guys, really? It looks like you want to take the best from women and the best from men, but it is not gender equality. You should choose the best from both genders at the same time.
We need to support women too... Do you want to have a girlfriend who can help you debug the code? Increasing the number of women in programming increases your chance to find one.
I have such girlfriend)))
Its clashing with another big contest between India and england :P
Nobody cares!
.
Aren't we gonna have a testing round after what happened yesterday?
Codeforces should not be a place for messages like this. Can you name the month when world celebrates men?
It's in "NEVER" month
equality goes brrr
international men's day is November 19th
You do realise your hypocritical behavior nah ?
Separating of women makes more inequity. It shouts "You are woman, you can't compete with men, so we create special event for you". That's sounds sad.
hope good performances.
Good Luck Everyone !! I wish this round to be wihtout any technical issues and have interesting problems
for me, neither of the three websites m1/m2/m3 are loading for the past few months. They are down for me right now too.
They are working fine for me.
oh,there are two different contests in two next days...
I don't know which one to choose...
Which contests are you talking about?
good luck everyone, I hope this round will be rated
Educational round 106 will be my 106-th rated contest
Sorry, +15 minutes. Hope the problems will be OK. Good luck on the round!
Please ensure that contest is rated.
15 min delay
Another 15 minutes :(
what to do with my life for the next 15 minutes!!
Its just a delay dude, not the end of the world.
Delayed by 15 minutes!!
Delay is new tradition on codeforces
Please... Don't discuss the delay to make the comments meaningless...
hope Contest run properly this time
Waiting to get my first positive rating :)
I am curious, is it finalized that the contest will have 6 problems or 7 problems, or are we supposed to know only after we enter the contest?
Does codeforces do this for 20k registrants?
Delay by 15 minutes.
2 min before the contest — electricity cut, no wifi.
4 min after the contest — (joining with mobile data and hotspot) contest delayed for 15 min.
lucky lucky
After the contest — +200 delta.
we hope this round to be rated though if i get -120 today lmao
whenever there is a delay in contest, le me: It's contribution time xD
Me for C :(
Got 4 wrong submissions before making the correct one for B and now I can't stop seeing that green text Accepted. I just love it when I solve a problem after struggling hard and thinking hard
Thank you codeforces for making me have such good feeling in every contest
what is wrong with my approach? I print "No" only if the string contains 1100 as a substring else "YES"?
try 110100, answer is no but your solution gives yes
your solution will output YES for string 1101001, but answer is NO.
Question about D problem. And not, not about the solution, it is relatively obvious. The question is: how to factorize all this in 2 seconds?
exactly
I use O(sqrt * log) and passed in 1.2s（
I also did the same thing, but after looking at your code, it seems like using vectors was the reason for TLE.
I just removed two vectors and it passed, I wonder how non-C++ solutions will pass such a tight limit :(
yep i had to do all kinds of optimisation in java but its all good learning experience
Not all. Took your submission 110397725, replaced all
long's withint's, replacedx / i != iwithi * i != xin one place, and it passed in $$$1.9$$$ s — dangerous, but it's expected from non-optimal solution.you are right! I dont know why i took everything long. Anyways when i failed system testing, to avoid recalculating i saved pre visited prime factorisations in an array and my "all long" code passed in 1.9 but after fixing that its passing in about 1.6s which is less dangerous i guess :)
I maybe answering above my league but maybe using sieve can help since it's time complexity is O(nlognlogn).. Link
In my case, I used this technique. Preprocessing and then for each query, simply $$$O(sqrt(x))$$$.
pray I guess :D
We just used linear sieve (that maintains the smallest divisor for each number). After calculating smallest divisors, we can find the number of different divisors for each number in linear time as follows: the number of divisors of $$$x$$$ is the number of divisors for $$$\frac{x}{d[x]}$$$, plus $$$1$$$ if $$$d[x] \ne d[\frac{x}{d[x]}]$$$.
I agree that time limits may be a bit tight though.
I think you mean number of different prime divisors, instead of number of divisors.
A follow up question, is there any method to calculate number of different divisors (not necessarily prime) for 1 to N in linear (or nlog(logn)) time ?
Yes, I meant prime divisors, thank you.
To calculate the number of distinct divisors, we can use a similar recurrent relation.
Since the number of distinct divisors of a number equal to $$$p_1^{k_1} p_2^{k_2} \dots$$$ is $$$(k_1 + 1)(k_2+1)\dots$$$, let's calculate an auxiliary recurrence: let $$$k[x]$$$ be the number of times $$$d[x]$$$ (the smallest divisor of $$$x$$$) appears in its factorization. $$$k[x]$$$ is either $$$1$$$ if $$$d[\frac{x}{d[x]}] \ne d[x]$$$, or $$$k[\frac{x}{d[x]}] + 1$$$ otherwise. Then, the number of distinct divisors of $$$x$$$ (let's call it $$$f[x]$$$) is $$$\dfrac{f[\frac{x}{d[x]}] \cdot (k[x] + 1)}{k[x]}$$$ (since we are replacing $$$k[x]$$$ with $$$k[x] + 1$$$ in the number of divisors).
when counting f (x) — what about for each number up to 2e7 count the number of prime divisors = cnt and add 2^cnt to the answer(C(0, cnt) + C(1, cnt) + ... C(cnt, cnt) = 2^cnt
What if some prime divisor appears multiple times in the factorization?
Erotasphen rep(i, 2, N){ if(used[i]) continue; for(int j = i; j <= N; j += i){ divisor[j]++; used[j] = 1; } }
with the help of this type of Erostaphen sieve, in an easy way, I count the number of prime dividers
Aw, I had investigated something interesting. This codes calculates two arrays: $$$pr[i]$$$ — minimum divisor of $$$i$$$ or $$$-1$$$ if $$$i$$$ is prime, $$$cnt[i]$$$ — number of prime factors of $$$i$$$. If I understood correctly, it works faster than $$$O(n \log \log n)$$$, and gets $$$800 ms$$$ on $$$D$$$.
Great problems.Can someone tell me hints for problem D? (Please put them in spoilers) Thanks.
gcd divide lcm
gcd divide x you can iterate the gcd over divisor of x and infere the lcm
for given gcd and lcm the number of solution is a power of 2 depending on their quotient
$$$a * b$$$ = $$$gcd(a, b) * lcm(a, b)$$$
For each possible $$$g$$$ let's count how many pairs $$$(a, b)$$$ with $$$gcd(a, b) = g$$$ satisfies our condition.
How can you bruteforce only $$$O(\sqrt x)$$$ possible options of $$$g$$$?
Link
Why very tight limit in D? :(
What's the key idea to solve D ?? :(
Hint
let G=gcd(a,b) L=lcm(a,b) Now cL-dG=x G (c(L/G) — d ) = x L/G must be an integer Thus G will be a factor of x By this we can check for all possible values of G and L Now for given G and L , The number of possible values of (a,b) corresponding to it is 2^(number of prime factors of L/G).
Watch this
How to solve D?
Hint:
gcd(a,b)must me a divisor ofx;HINT 2 if we are given gcd(a,b) and lcm(a,b) how many possible pairs (a,b) such that a,b>0 exist ?? Example gcd(a,b)= 2^2 * 3^4 * 5 * 7^2 lcm(a,b)= 2^4 * 3^4 * 5^2 * 7 The Number of pairs is 8
You might have got this relation. Here $$$g = gcd(a,b)$$$
$$$a\times b = g\times \frac{(d\times g + x)}{c}$$$.
You can reduce it into...
$$$\frac{a\times b}{g^2}=\frac{(d+\frac{x}{g})}{c}$$$
From here you can see that $$$g$$$ has to be a factor of $$$x$$$. And a disjoint distribution of the factors of R.H.S leads to unique values of $$$a$$$ and $$$b$$$.
A disjoint distribution basically means partitioning the prime factors into two groups such that each prime factor belongs to exactly one group.
Link
.
Problem D:- Can someone please explain how we are getting 8 pairs in the 4th test case?
[(1, 16), (5, 30), (10, 15), (15, 10), (16, 1), (25, 100), (30, 5), (100, 25)]
Thanks
argh -- anyone else keep getting runtime error on testcase 4 for D? I hope I was actually doing something wrong and it wasn't just a weird quirk of pypy.
You need to sieve till 2 * 1e7.
AHHHHHHhhhhhhhhhhhhhhhhhHHHHHHhhhhh dammit that's tricky. Thanks, that fixed it... now I just have a TLE on test set 15 like everyone else :p
Have a look at this
Hey, How you concluded that upper limit of lcm would be 2*1e7 ??
I am unable to figure it out. Thanks in advance.
UPD : Got it... we actually require upper limit of lcm/gcd which is 2e7...
Was E dp?
Yes I think so, didn't manage to finish the code in time though.
Sorry...wrong problem.
E seems to be a dp.
We can build a dp[i][j][b]=num seqs with i symbols from x and j symbols from y and last one taken is from x/y -> b=0/1
This gives us the number of all subseqs starting at indexes 0 in both, x and y.
Then we can sum up from that table (...somehow...) to get the numbers for all substrings. See that solution for example (neal) : https://mirror.codeforces.com/contest/1499/submission/110349694
How to solve C. Should i use dynamic programming here. Anyone plz help..!! Thanks in advance.
greedy will work. Maintain minimum for odd and even index separately.
it is greedy, neal used greedy and greedy makes perfect sense here...however, i spend an hour implementing it and always failing at 4th test set...just don't know what i did wront
It must probably be due to overflow. Same happened with me.
yap with ll it doenst work but with ull it works....thats soo evil
It works with ll too.
Yeah u right, I initilized INF badly
Nope. The answer is: Try using from 2~n segments. Observe that you can solve horizontal and vertical parts separately. Also, WLOG you can assume the first step is horizontal. Let's consider only the horizontal part. Suppose you are using k segments, then the horizontal steps are segment 0, 2, 4, 6..... it is easy to figure out how many horizontal steps you took, suppose it is E. Then for those E segments, it is obvious that you should use the one with the minimum cost to move n-E+1 length(and for other segments, move length 1). So prefix minimum and prefix sum(on even indexes) will do the work. Then for every k, you add horizontal and vertical, take minimum. That's it.
The idea in C is to split both directions.
We can go a number of steps in one direction with even costs, so c[0]*someLen+c[2]*someLen+...
Same for other direction, but with odd indexes.
Then, for each direction and number of steps there is a minimal cost of: each c[i] one time and the minimum of the c[i] n-i times.
And finally, the whole path consists of i steps in even direction, and i or i-1 in odd direction. Find the min of those.
Isn't this an edge case? 1 1 1 2
Cheapest path here is obviously n+n for using c[0] and c[1]. Whats the edge in there?
I know but doesn't your solution do this? (1 * 3) + (1 * 3) + (1 * 1) + (2 * 1)
Nah... The solution finds the min price for using c[0], or c[0]+c[2]. And c[1], or c[1]+c[3].
Then from those it chooses the min of possible number of cost used in each direction (1,1), (1,2), (2,2)
Think Greedily. You can also refer to this video. Problem C Minimum Grid Path
How to avoid TLE on TC 15 in question D?
Maybe removing
#define int long longwill work (in C++)Precalculate number of prime factors in O(2*1e7*log(2*1e7)) using sieve.
Have a look at this
I kept getting TLE on test 15 in D. What's the ideal complexity?
Alog log(A)+ t sqrt(A) where A is 10^7
actually you can do much faster if you precompute also the factorisation and not just the number of prime factor so Alog log(A)+ t d(A) where d is the maximal number of divisor for an integer up to A
A is 2*10^7, using 1e7 caused me RE on test 4 XD
yes but in a O() you can ignore constant
This response doesn’t make sense. 10^7 is just as much a constant as 2 so could just as easily be ignored with this logic.
He’s saying that the relevant upper bound is 2*10^7 not 10^7 which is correct.
Getting runtime error on test-4 in problem D, would really appreciate if someone could help.
110384394
I think your MAXN need to be 2e7 because if c = 1, d = 1e7, x = 1e7 the req could be 2e7
Have a look at this
Can someone explain the logic behind C, can't wait till the arrival of editorial, Any help would be really appreciated !!!
You must iterate on the number of segment it would require to reach $$$(n,n)$$$. It is obvious that number of segments is at least 2, so $$$n\cdot (c_1+c_2)$$$ is the base cost.
Now, iterate on the number of segments used from $$$3$$$ to $$$n$$$. For example if the number of segments required is $$$L$$$, then we will consider just a prefix of the input array of length $$$L$$$. And take minimum for answer over $$$3\leq L\leq n$$$.
To solve for any prefix of length $$$L$$$, we can observe that the cost of it is equal to $$$c_1\cdot l_1 + c_2\cdot l_2 + c_3\cdot l_3 +\cdots +c_L\cdot l_L$$$. Where $$$l_i$$$ is the length of the $$$i^{th}$$$ segment. And sum of $$$l_i$$$ for odd $$$i$$$ is equal to sum for even $$$i$$$, which is equal to $$$n$$$.
Greedily assign the values of $$$l_i$$$ for even and odd indices independently, so that the minimum cost gets the highest length segment.
Thanks Buddy :)
Think Greedily, try to minimize the length of segment choosen. You can also refer to this video:- Problem C :- Minimum Grid Path
Why time limit of problem D is 2 seconds ? should have been 4 seconds since it's tagged as brute force. I changed long long to int after contest and it passed in 1996 ms . I think it will fails system test . What was intended time complexity ? submission
watch this
Can someone explain me the meaning of the term segment used in problem C? What is a segment?
It simply means a line segment
line segment
Sad "RE on Test 4 on problem D" noises :(
array size limit has to to be 2e7+1
Yeah, I figured after 4 penalties.
I figured out at end of contest :/
Time limit for D was too strict IMO :( Should have been 3000ms
yes it was too strict !! can this time constraint be increased now and can the solutions be rejudged? Is it possible or happened in the past?
Why ternary search didn't work in Problem C?
The graph can have more than 1 local minima. I was also thinking to use ternary search first, but luckily I observed it.
Can you give me one example where more than 1 local minima are present?
100 100 100 100 100 5 100 100 100 100 100 1 100 100
something like this?
1000 10 10 10 10 1 1000, this should be the correct testcase which you are looking for.
I'm so happy that I'm not gonna ask "how to solve A?" :) any way... How to solve B? :)))
look for if there is '00' after '11' if there is '11' in the string. else 'yes'
Can someone tell me why I am getting runtime error on my submission for problem D? I already made MAXN to 2e7 + 20
Have a look at this
Thanks!
Does anyone thought that sieve for 2e7 numbers would give TLE and haven't coded it for some time like me?
The sieve that I use runs in $$$O(Nlog(logN))$$$ which is approx $$$O(N)$$$, so I guess, it should go through.
I didn't submit D for following reasons idea was trivial. Assuming that the idea will not fit in Time limit.
how can 10000 * sqrt(1e7) log(1e7) = this ~ 10000*3300*20 ~ 66 * 1e7 ~ 6 1e8 operations fit in 2s. I don't know how magical there processors are.
Since a decade they run on gigahertz and more.
Ya there is some hidden secret which only MikeMirzayanov can share as an IT enthusiast the way threading is done on the judge the way they are handling these many operations which may TLE on most of the other Ojs. I think that he can write some info about the tech used at backend
I am fairly sure they simply count the processor ticks used while running the thread/process, or something similar.
Actually I worked in this field. I found many systems failing in such critical pressure. Most of the such websites now depend on Z0s API to judge a code. but it is not that fast Here the way of handling queue and maintaining the submissions and at the same time giving a performance of 1e9 operations in a span of 2 seconds. is just a great thing. Either the originial system is tricked a lot or they are having a strong processor which is capable of handling all the tasks. May be it is the second. and if it is then it is expensive and we all know that the site is non commercial. There are certain confusions in my mind I don't know if Mike can help me understand the infrastructure of codeforces judge.
actually you must get ride of log(1e7) by doing a sieve beforehand
All the test cases are not that big. Only a few of them will be as big as the constraints.
So, you can ignore the $$$T = 10^4$$$ part most of the time. Otherwise, the complexity is around $$$O(\sqrt{N}logN)$$$ is good enough.
The complexity would actually be better than $$$O(\sqrt{N}log(N))$$$ since the number of divisors of a number is bounded by $$$O(N^\frac{1}{3})$$$. So this part where we are computing the distinct prime divisors for each divisor of N will be bounded by $$$O(N^\frac{1}{3}log(N))$$$. Even if all test cases were huge, I don't think this will time-out.
How is no. of divisors N bounded by N^(1/3)?, Like 24 has 8 divisors, which is much more than 24^(1/3) https://math.stackexchange.com/questions/1699330/upper-bound-on-number-of-factors#:~:text=Let%20d(n)%20denote%20the,nloglogn)).
When I say $$$f(n) = O(g(n))$$$, it means that $$$f(n) <= c * g(n)$$$ for some constant c and for all values of $$$n$$$ >= some constant $$$n_{0}$$$
You should not consider $$$N^\frac{1}{3}$$$ as a hard bound. It just gives an idea of the relative magnitude.
The number of divisors of $$$N$$$ would be of the same order as $$$N^\frac{1}{3}$$$
For better understanding, if I say that $$$cnt(N)$$$ is the number of divisors of N. Then the rate at which $$$cnt(N)$$$ and $$$N^\frac{1}{3}$$$ grow are comparable
got it, but the constant (c) can be too large, i think
I don't think time complexity will be (T * sqrt(X) * log(X)) Instead it would be (T * sqrt(X)) + (T * no_of_divisors(X) * log(X)). for divisors of X only we will be getting log(X) factor.
Also the max possible value for no_of_divisors(x) where x <= 1e7 will be atmost 500.
can some one pls tell soln for B, idk I am not getting ideas to solve B
The only "NO" case is the one where if you iterate the string from left to right u find at least two adjacent ones and later in ur iteration u find at least two adjacent zeroes.
thanks , I thought 1100 and cupped the contest!! , btw any DP solution for this problem??
Yeah, I solved using $$$dp$$$. The idea is to store whether string $$$s[1...i]$$$ is good, with the last element being $$$0$$$ or $$$1$$$ and the last index is removed or not.
Basically $$$dp[i][j][k]$$$ -> Upto $$$i^{th}$$$ position, the last character taken is $$$j$$$ and the $$$k$$$ is $$$1$$$ or $$$0$$$ based on whether $$$i-1^{th}$$$ is taken or not.
Solution
JUST check for consecutive 0's if the string already have consecutive 1 before it
if this happens then print NO else YES
Reason : as we can't remove adjacent bits, we can't have two zero's after two one's but in vice versa we don't need to remove consecutive 1's as they will already be sorted TESTCASE : 1001110111 --> YES TESTCASE : 1100 --> NO
hope you understood
thanks got it!!
Somehow my solution is giving Wrong answer on testcase 2. Expected value is 10, but my solution gives 9. Well, I am not sure why my code is giving less value than the optimal answer. I used the following approach of finding the minimum for odd and even indices respectively which minimizes the total answer.
I cannot understand why is it failing? Please help! My submission
Yeah, the same problem
I think the approach is wrong, because you can't just calculate min up cost and min right cost separately and add them up. For example if your min up cost only uses one segment, the min right cost cannot use more than one segment.
Think Greedily, how to choose segments to minimise the value of the expression. Link to detailed solution and explanation of Problem C
umm..I found some guys cheating in the contest. Idk Where to report. 110342157 and 110336335 Just look at the code/logic and you will understand they are cheating or not. And not just this, Check there other submissions too, like mostly div2B and div2C are the same for many contests. shivam_aiml Even got his submissions skipped last contest but nothing else happened and they are still "pair-programming". MikeMirzayanov Pls look into this.
I agree that these two pieces of code are questionable. Strong pieces of evidence are:
1) In 110342157, there is
ll curr=i,next=i;;, while in 110336335 there isint prev=i,prevv=i;;. Same typos at the exact same places.2) 110342157 commented
int ch-0;andint no=0;, which are the exact same codes and variable names in 110336335.3) 110342157 defines functions like
gcdll,gcd,mpow, which have nothing to do with either the problem or his solution. They seem to serve the purpose of disguising.I also encourage people to look into this and express their opinions. Cheating harms the foundation of online coding competitions, and possible cases should be examined seriously.
Problem D approach :
Now, we can iterate over the factors of x' in sqrt(x) time complexity. Fixing the gcd we can easily find the lcm using the equation given. Now we know lcm and gcd, our problem is reduced to finding the pairs whose lcm is k and gcd is l (which are known). This is easy to solve and a common problem.
https://www.geeksforgeeks.org/given-gcd-g-lcm-l-find-number-possible-pairs-b/
Don't use the method mentioned in the article to count the number of primes. This can be pre computed using sieve.
In second line of proof why did you divide LHS by $$$ gcd( c , d )$$$ but in RHS by $$$ gcd(a,b)$$$ ?
By mistake I wrote gcd(a,b). Thanks for pointing it out!! Corrected now!
How is the final condition sufficient? Is there something obvious?
What topics are prerequisites for understanding this solution?
Euclidean algorithm and general maths.
I saw this in someone's code. The format was like: /** * author : name * created : 2021-03-18 11:11:11 **/
Can anyone tell me how to do this so that my submission time is printed automatically in my code.
if you use vscode and vscode snippets as a template, then you can add the creation date when the snippet is created (see here)
Why do you think the post is almost in minuses? Is it due to the specifics of the announcement, or was there something wrong with the problems or the website during the round? I think the system worked fine.
Yes in problem D, time constraint was strict. Inspite of having the correct time complexity, the code needed some optimisations to reduce runtime and hence to get AC.
Males are downvoting because they are distributing unnecessary scholarships to females.
The Misogyn army strikes back.
I doubt that more than 5 people read the part that Harbor.Space writes in the announcement, so that can't be the reason.
I think downvotes for contest announcements should be disabled.
As far as I know, downvotes are supposed to function as a filter to blogs/posts which doesn't fit in Codeforces. But official contest announcement blogs never fit in this category. No author ever intends to ruin the experience of participants (not that I know of).
People usually downvotes contest announcements for the stupidest reasons, such as containing a topic he doesn't like, TLs being strict, performing bad in that contest, etc (You can actually see those guys right below your comment).
So there are no benefit of having downvote option open for contest announcements that I can think of.
But would you suggest an alternative way for the community to rate the contest and the problems?
They can always express their opinion in the comment section. Why do you need more than that?
That's true. But posting new comments requires a different level of commitment and I don't think it reflects popular opinion as voting system.
Popular opinion doesn't need to be reflected in terms of upvote/downvote is exactly what I'm saying, since it mostly consists of "I don't like this contest since it contains a topic I don't like", "TLs are strict", etc.
We could have a "I enjoyed to participate in that contest"- button somewhere.
I like this idea
I guess most dislikes came because of sexism (inequality). Codeforces, I think, is not a good place to discriminate people by gender.
Problems, in my opinion, were good (at least A-C).
Why is the editorial of educational round released so late? Sometimes, even Div 3 editorials come out early, even though they have a 12 hours hacking phase too.
there are a reason.. if editorial released before 12 hours after contest then hacker can use editorial advantege during hacking someone code .that's why :)
That is not a reason. There where several contests (with 12h hacking phase) with the editorial released earlier.
The rules imply that an editorial can be released right after the round ends.
contest is Still going on ! It's called "hacking phase" . Basically you can propose a test case for which someone else's code fails despite the code clearing the system tests . And you will be awarded points for that .
No, points will NOT be awarded to the hacker. Hackers only get points when they hack within the contest (i.e. the 2hr period of the contest) and it should a div1/div2 round. Edu round and div3 don't have points for hacking.
Why these submissions are the same？/jk https://mirror.codeforces.com/contest/1499/submission/110377066 https://mirror.codeforces.com/contest/1499/submission/110338712
Man so tight limit for Div2D.(My solution passes if i change long long to int where i have declared #define int long long in my default template).
yep bro in my case also.
is the sys test done ?
In problem D, I got TLE on test 45 during the system test. See submission 110370993.
However, A few minutes before I submitted exactly the same code and got Accepted, and only used 1154ms on test 45.See submission 110420144.
WHO CAN TELL ME HOW THIS COULD HAPPEN?
Your Accepted code took 1996 ms. It barely passed. These slight deviations in time happen all the time.
It was test 38 that cost 1996ms, and it didn't cause my TLE on the previous submission.
Now I am happy coz I didn't solved D due to strict Time complexity and many peeps got AC and were throwing senseless time complexity logics in comments with sieve but now all of them got TLE in main tests! Yesss I am still worthy feeels!
You are a sadist.
the query for problem C. Minimum Grid Path
can anybody tell me why my code gives the wrong answer?
it gives WA on test case 2, checker's comment: wrong answer 56th numbers differ — expected: '10', found: '9'
here is my solution in python3
thank you in advance.
141 2 2 1Correct output — 10
Your output — 9
how do we know the particular test case. sometimes I need this but I don't know-how
You can sometimes use some tricks. As for this problem, don't print the output for 1st 55 cases and print the input array for the 56th case.
You can stress. Code a generator that generates small cases, and test your solution against some Brute Force that you know works well.
have ratings been updated?
Not yet.
Isn't the whole purpose of competitive programming to improve thinking and knowledge, rather than solving stupid TLE from problems such as D? An additional factor of log(n) results in TLE, in some cases changing long long to int solves the issue. Are we supposed to think all these stuff during the contest instead of finding the correct algorithm? It is not fun when you think for a lot of time during the contest, get pretests passed only to find out later that the code failed because you didn't precompute the powers of 2 and used long long instead of int (this is what happened with me). More than half of the AC submissions for problem D have a runtime > 1800 ms.
.
I know this isn't the first time and i don't expect the platform to be prefect but such type of issues can be easily handled during the testing phase of the contest by either decreasing the constraints (the number of test cases could have been reduced to 10^3 instead of 10^4 which would result in a worst case of (10^3*sqrt(10^7)*some additional log factor which can easily pass in 2s or reduce the value of c,d,x to 10^6 or 10^5 maybe) or increasing the TL.
"Are we supposed to think all these stuff during the contest instead of finding the correct algorithm?" If your algorithm has a log(n) factor outside of precomputation, I'm pretty sure it's not the correct algorithm. I can sympathize though, TLE feels worse than WA.
The extra logn factor outside precomputation is for the modulo operator and I don't think there's any way to avoid that extra modulo, and I'm pretty sure my algo is correct because after changing long long to int and precomputing the powers of 2, the code gave AC in 1600ms
log(n) factor can be avoided while precomputation,and powers of two can be calculated in O(1), using the left shift (1<<i), constraints were fine, but the TL was too tight, my code barely passed. Btw i don't see that 1600ms code in your solution.
"powers of two can be calculated in O(1), using the left shift (1<<i)" exactly my point, such things should not result in TLE. About my 1600ms solution, here you go: link. The only difference between this one and the FST one is that I used int instead of long long and didn't use binary expo for calculating powers of 2
Your log(n) isnt because of the modulo smh. It's the getAns function, you can get rid of that whole thing by modifying sieve to store number of unique factors for each number. How are these even getting accepted
The reason my code is accepted is because of the faster pre computation than yours. You can clearly see that difference in the short test cases #1 and #2 by comparing the runtime of our codes. My precomputation takes O(n + sqrt(n)*log(sqrt(n))) whereas yours takes O(n*log(n)) clearly. The tradeoff for my faster precomputation was obviously the getAns function but it doesn't make much big of a difference
My precomputation does addition and assignment which are faster than division and modulo. Your factorisation thing can do upto $$$O(T*x^{1/3}*log(x))$$$ divisions. I was thinking this was the reason why most people FST'd but now I'm not sure.
What is that? I first got accepted on D, then I woke up to find it's a time limit! What did I do? I changed the "cout<<ans<<endl;" to "cout<<ans<<" ";" and I got accepted!!! 110372581 : time limit 110425544 : accepted I was rank 317 , which meant to reach the CM again and beat my best!!! I just can't believe it's because of the "endl;"
Fast I/O is always needed with large number of queries, why should this be weird in such a problem? There are countless cases of D2C failing due to use of slow I/O, why should this specific case be isolated?
I'm using the ios_base::sync_with_stdio thing, so my code should read and output fast, I never knew that the endl; would have that impact!! I don't know but I'm angry because of it
endlflushes the output, making it slower than just printing'\n'.If you don't want to change your style of using
endl, you can define a macro like this:#define endl '\n'.endl will flush the output at the very instant (that's why I use it for interactive problems), even if you are using fast I/O, that made your code slow.
Same bro. My submission gives me WA on test 21. But when i changed endl to "\n", i got accepted!! What a strict time limit! I must say weak pretest were for D!
Have the rating changes not been made or is the the round unrated
Rating changes have not been made
Hmm... Waiting for the editorial!!!
FSTforces
My solution of D got tle in contest but got AC after resubmission... Hope more stable next time :(
TLE
AC
.
If the intended solution was to use a linear sieve then the problem is great. But you should have done something to restrict all the solutions which use simple sieve of Eratosthenes. It should not be the case that some solutions pass using a simple sieve and some are not due to implementation.
.
where and when?
KarthikeyaMirzayanov
I got AC on D with 1996 ms. CYA losers LMAO
when the ratings will be updated?
shortly
and what about editorial?
Editorial for educational round are always late.
but why
No idea.
Hoping I'll be a blue coder this time, can't wait for the rating update
good luck(without sarcasm)
Yeah, you got it. Congratulations bro :)
Congratulations!
when I was solving D during contest and getting TLE on 15.I was frustrated why this much tight time limit(bad problem). Now after up-solving it I can confidentally say it is really a good problem to solve.
Can someone tell me why the answer for 4th testcase of problem D is 8. testcase — c=2,d=7,x=25 . what are the 8 pairs of integers that satisfies this?
$$$(16, 1), (1, 16), (30, 5), (15, 10), (10, 15), (5, 30), (100, 25), (25, 100)$$$
Thanks.
Hello MikeMirzayanov awoo BledDest I received this message a few hours ago where it says my solution of Problem C 1499C - Минимальный путь на поле of yesterday's Educational Codeforces Round 106 matches with that of zapdospops.
My solution: 110354516
zapdospops solution: 110382564
I did not share my code with anyone and here are my clarifications:
The Fast-io template which I used in my code is from pajenegod Github Repo "Pyrival" [from https://github.com/cheran-senthil/PyRival/blob/master/templates/template.py]. I have also mentioned the link to the Github repo in my solution as well.
The main() function of my code is completely different from zapdospops main() function.
The top part of the code where I imported some libraries and added some functions is my own template which I am using for the past 2 years. Here is my submission link 63302879 from 24th October 2019.
It seems zapdospops copy-pasted my template from my previous submissions.
MikeMirzayanov Could you please look into the matter?
"Attention!
Your solution 110354516 for the problem 1499C significantly coincides with solutions raj1307/110354516, zapdospops/110382564. 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://mirror.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."
MikeMirzayanov Any update?
Will the editorial be posted?
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Why there isn't the best hackers part in this blog? Has it been canceled?
missed blue with one point :(
And you got it in the last Div.2. Congratulations! :)