Привет, Codeforces! Испугались отсутствия новых раундов? Мы тоже!
К сожалению, из-за технических проблем раунд объявлен нерейтинговым. Вы можете продолжать решать задачи, но результаты текущего раунда никак не повлияют на ваш рейтинг. Мы сожалеем об этой ситуации.
<almost-copy-pasted-part>
Привет! Во 25.01.2021 18:00 (Московское время) начнётся Codeforces Round #697 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 7 задач. Задачи подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше, могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы будем расстроены, если у многих попадают решения после окончания контеста.
Вам будет предложено 7 задач и 2 часа на их решение.
Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше. Независимо от того, являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Задачи на этот раунд были придуманы MikeMirzayanov и подготовлены мной Supermagzzz и Stepavly
Спасибо MikeMirzayanov за платформы и координацию нашей работы. Спасибо darkkcyan, Tzak, bfs.07, songsinger, iankury, spookywooky, Programmer, sodafago, infinitepro за помощь в подготовке и тестировании раунда.
Удачи!
</almost-copy-pasted-part>
UPD: Разбор готов!
7 Problems!!! Great.
Contest start's 15 minutes late
why?
looks like there was some issue with the servers. the site was showing unavailable for me for some seconds.
Codeforces teaching us how recursion looks like
10 more minutes late cant wait to start
A small suggestion, keep an tab open of m1.codeforces.com aside. It might help.
29000 registrations!! they must be adding some resources
Maybe they are waiting for the number of registered participants to cross 30k :0
was fully set to give the contest and the enthusiasm drops down immediately after hearing of delay.Need to think of something to pass time now.Hope to get some upvotes to increase the enthusiasm
please dont do this to me this is my first comment
lmao
Nope
Again??
10 more now
why is this happening?
Making New record of 30k+ coders
again late, but what's wrong ?
contest delayed by 15 minutes update:10 minutes more to go
but why??
beacuse they can't check all submissions in time :)
nothing
think about your statement for a few minutes...
This is my first contest on codeforces, just got delayed :(
good luch to u
yeah u cant even give them luck dude they are doomed
My first two contests got unrated due to server problem
You are so "lucky" :(
My goodness. See the crowd!! It's highest among all contests that held in cf. Congo cf!
3 mins to go!!! I hope it doesn't get delayed any further :(
lol, it got delayed
Please dont say that again now
Contest start's next 10 minutes late
Can't wait more!!
Is Mike waiting for 30,000 registrations?
100 participants more to cross 30k. :)
As a tester I would like to thank iankury for providing clear explanation.
Some brazilian testers, this is great!
Hope this contest will increase our rating!! Finger crossed.
I will try my best to reach pupil today. All the best to all participants.
I was afraid, but why that happened? contest frequency is decreased this month than other months.
Thanks for the contest.
My chance for pupil!
My chance for expert!
My chance for specialist
my chance to get rated lol
My chance for pupil!
My chance for recover lost rating in last contest.
my chance for experiencing twice delaying of Codeforces
Its 8:25 and I'm still waiting for my chance
How can I become a tester for Div. 3 contests if I am not a friend of the testers/setters?
I am not a friend of either of them. I think it's pure random ;)
Thanks for your reply!
Since I am less likely to give CP contests in the following few months, it would be nice for me to contribute to the CP community by becoming a tester for Div. 3 contests.
I would want to become a Div. 3 contest tester in the future — if Stepavly and Supermagzzz would want me to provide feedback for your contests, please give me a call!
Well, this time each tester has a ten years badge.
.
I am waiting for a div2 round
I am waiting for a div2 round that is unrated for me :)
7 problems! Wonderful start after an eternal gap.
Are the registrations closed??
No,You can register for the contest.
if i don't get 150+ rating i will do whatever the highest rated reply asks.
What is Obama last name?
is that even a question? Obama's last name is ofc Obama, you idiot
his first name is President
Oh, I thought his last name was gon.
"Care" of course
Solve CF problems at least 3 hours/day for 1 year.
please give me money
Deal.
We will watch this battle with great interest.
Edit: welp, this would be a disappointing result I guess.
our money
get 150+ rating
ugh, but i guess it doesn't count since my statement is technically incorrect?
What extension or script do you use to highlight submissions based on language?
Codeforces Enhancer
Would you please provide me the link or more details about is.
google it on chrome's store.
Blog of codeforces enhancer
I am sure nobody likes to see this.
Yes We all know that.
I don't like seeing <"almost-copy-pasted-part>"
That Irregular Bracket Sequence :V
As you can observe now, its_Atrap
As a tester, I recommend participants to open
https://mirror.codeforces.com/contest/<contest-id>/problemsrather than opening each problem page, during the contest.Reduces clutter and server load (ig).
Thanks sir, for this new bit of information.
Can u tell us where we can find the contest-id for contest before the start of the contest Thank you
Enter any contests and you can find the contest-id in the URL.
Edit: You can still find the contest-id in the
and it is
/contestRegistrantsroute by clicking1475for this contest. Luckily, the id gets incremented by one in each contest but you can't enter the contest before it starts.Actually there are two more or less direct links:
This one links to the contest, but currently forwards to this blog, since the contest has not been started yet:
https://mirror.codeforces.com/contest/1475 and is equivalent to the inline link Codeforces Round 697 (Div. 3)
That one links to the page where you can register for the contest:
https://mirror.codeforces.com/contests/1475
That second link is also used in Calendar
damn it i just got rick rolled
the real rick roll is in the delays
Thanks to Supermagzzz and Stepavly for preparing the div.3 contest.
After the last contest when it was showing no contest for near future, it was a little bad feeling but now this contest has filled us with new enthusiasm(mind the spellings).
Hoping for less plagiarism in the contest!
Hello everyone its the first div3 of this year and i am here to wish you all good luck for today. Have fun guys.
It is the Second. 1st was #693
Hoping for a great contest.
anyone having difficulties reaching codeforces ?
No, It's working fine for me.
This round has got a crazy number of registrants ~26000, let's hope the round goes smoothly
I already can't visit codeforces.com but I can visit this blog for some reason
I think they postponed the starting time.
Wish the pretest becomes strong.
To all my Indian brothers and sisters Happy Republic Day in Advance. 26th of January is celebrated as Republic Day in India to mark the day when the Constitution of India came into effect. JAI HIND
Delayed. :(
28k people o_o
I don't even know if that's good or bad lol
contest will start 15 minutes late
3 2 1 .....burrrr!
oh no contest was delayed for 15 mins :(
Соревнование началось — пройдите в интерфейс участника => я прохожу => соревнование начнется через 15 минут =) Upd: Еще 10 минуток :c
Dude, 28000+ registrations already, is this the highest up until now ?
Best of Luck Everyone. I wish you all get green in first try:)
thank you i would definitely get green
15 minutes delayed. Drink some water to keep yourself hydrated.
delay is better than unrated.
I hope not both :D
:/ both
Hope the delay is for good cause. Submissions to be judged fast
garam kar k thanda hi chor diya
waiting for 30k?
For a few seconds, I thought that problems are repeated:)
To All the Indians Happy Republic Day in Advance.
My goodness. See the crowd!! It's highest among all contests that held in cf. Congo cf!
This round is approaching 30,000 participants. This is year's first div 3, right ? Looks like some people are taking their new year's resolution seriously :P
My goodness. See the crowd!! It's highest among all contests that held in cf. Congo cf!
Delayed by 15 minutes. And now I am spending time in the comments section.
deleted
Ok, Done.
Is it the most popular round?
Have Fun & Good Luck!
with that many registrants if i get 3000th position I should be proud
Sorry for the delay.
No, how could you do that to us. :p
HAPPY REPUBLIC DAY TO ALL MY INDIAN BROTHERS AND SISTERS IN ADVANCE
**** **** JAI HIND
and what about non-indians?
You all can celebrate man...we beleive in Vasudhaiva Kutumbakam which means whole word is our family :)
I was waiting this contest. Good luck geeks!
I am excited to see what SecondThread will be doing in these 15+10 minutes in his stream.
The servers seem to be struggling...
Me After Seeing The Delay:-
25 mins late**
Nightmare scenario :D
movie name?
All the best MikeMirzayanov. 30k incoming!!!!
Highest registered participants.
Congratulations CF on achieving a milestone of 29k participants.
another delay?
again delay
Delayed 10 more minutes ?
Could have had my dinner in 25 mins :( Skipped it for contest
I controlled my shit
Instead of delaying they should close the registration lol.
How come again a delay?
+10 min
Again it's delayed by 10 mins!!!!!
I think that reason of this delay is good skill for getting more and more participants
Again delayed :(
What is going on??
Why delayed again?
Waiting for 30k ?
seriosly? Again? What happened?
8:30 ??
It seems it will be delayed until half of the participants go to sleep and we will deal with a normal number of participants.
nice joke, but staff of codeforces is not laughing now
I think they will delay it until 30k people register:)
I think they are waiting for 30k
why another 10 minute :( ????
contest is too much delayed :(
reschedule this contest.
common I am not having dinner just because of the contest and it's getting delayed....
More delay but hopefully rated
it's Monday morning I was just trying to get a quick competition in.. now two delays?
Contest registrations are increasing by O(1) complexity xD
What the hell?
almost 30 thousand registrants ... that's huge!!
30K lmao....hope to become Expert Today
DelayForces !
Close to 30k..!! May all registered participants give the contest.
More 10 Minutes to wait :(
GOT DELAYED AGAIN 10 MIN 300 ppl left to the 30k
did it just got delayed again? just hope there will be a long queue in the contest. they might be updating pre-test cases due to 29k participants. in order to prevent long queue. (just my guess). good luck to all including (people who made this round.)
What is wrong? Contest has been reschedule twice already :|
Can you reschedule the round again?
Don't extend it again
Are you kidding me?
That contest is put off 10min again means I couldn't get at least 4h to sleep in CHN.
Div-3 be like.. wait 10min more..;)
CODEFORCES
Why the contest is delayed?
Atleast tell us the reason for the delay.
I think it's due to the huge number of participants. what do you think?
WoW!
I'm waiting.
wow!
everyone is waiting
Now we have record of participants, but I think for another delay we will have antirecord
Now codechef might just get a new excuse XD
Its 30 minutes late. Why ?
I have to eat food..
ну иди поешь)
..
Highest number of participants in Codeforces history.
Cheers to everyone who has participated in the contest with maximum registered participants!
while(participants<30k): delay+=10mins
Why is the contest getting delayed??????????? I entered at 8:05pm IST to find out that the contest is starting at 8:20pm IST. When I enter at 8:20pm IST, it is showing delay of further 10 minutes!!
may be some question is wrong
Maybe they're testing if the servers can handle the load
but that is not good idea, delaying also increases number of registrants..
new year resolution effect 30k
There should be an option for unregistration from contest if delays come.
30k participants, This contest is going to be very much fun.
until I see -150 delta.
please no more delay :(
codeforces randi ,start krrde
You want me to find you on LinkedIn and send this comment to your recruiter? Delete it fast little bitch.
We often get stressed during or even before the contests, which leads to frustration. Keeping that in mind and not to forget the constant delays today i would like to appologise to absolutely nobody, do what u can , the king does what he wants.
Your frustration results in you calling this platform a "whore"? And you're no king. Just a sad pussy behind a keyboard. Don't shit where you eat. If you can't respect the platform then leave. Everybody here is "frustrated" but nobody is using these stupid insults like you.
I will not respect the platform and I'll not leave either. What can u do about it Mr. Authority?
I hope this countdown is not a countdown to the next delay
Come on!!!! My mom will beat me if i will not eat my dinner at time.
I'm rooting for your mom.
My mom even don't listen to my father.
They're gonna keep delaying the contest until some people unregister because of frustration :D. Don't blame them though, this is a historical milestone.
YES!! yEEEE! 30.000!gogogoGO! yEEEEEEEEEEES!!!!
Me watching contest getting delayed , after waiting for 1 month for div3 -
upload image
was the delay to hit 30k registrants lol
Now I am 16 years old.
When Contest starts, I will be 116 years old :D.
Highest number of participants in Codeforces history.
If it takes so much time to reload use m1.codeforces.com , m2.codeforces.com or m3.codeforces.com.
live streamers be like aisa pheli baar hua hai 17 18 saalo me
Contest will be delayed for 10 mins. If it doesn't start in 10 minutes just read first sentence again.
Congratulations for having 30K coders today.
Don't delay it anymore.OK?
Mike just wants achieve 30k :D
Number of comments increased by 200% due to this delay.
as well as no of downvotes for this blog :(
the delay might be to get 30,000 no of participants
Meanwhile:
Mike: "Wait! Just 10 minutes more and we hit 30k....."
25 mins delay but a new record :')
Hope a good result for all
30k on codeforces round!!! Congratulations!!
RECORD! It's 30k.
Seems like, cp has become like engineering in India, you have to do it, whether you like it or not.
look at 30K participants
Thanks to indian youtubers for making this possible -_-
Congratulations for 30k participants! This has been such a great platform.
There we go 30000+ registrations !!
25 mins late but... a new record :')
Reached 30 k participants. A big milestone :)
30000! Congratulations!!!!
Congrats CF for 30k participants..
Congratulations CF on achieving a new milestone of 30k participants.
20:04: Me to Mom: Mom, I will have dinner at 10:05.
20:05: Me to Mom: Let have dinner now; I will eat fast.
20:20: Me to Myself: Well wtf I ate so fast? Let write a comment and let the entire community know :)
20:30: Me to Myself: All the best :)
UPD:
21:00: Me: Please Codeforces, make it unrated, unable to bear queue timings :)
21:15: Regardless of rated/unrated, I stop giving the contest. #queueforces
21:20: I enjoyed the problems, will upsolve them later when the queue is not long, also Congrats on the 30k+ registration.
oh no! Queue of 5 min.
How do you know the length of the queue?
I've been waiting for 10 mintues and it's still not judged. So that's how I know.
TOOO LONG QUEUE uNRATED PLZ
#queueforces
o shit queue that too for this long
in queue "unrated"
please make this round unrated....very long queue timing..!!
Yes, please make it unrated. The queue is of more than 20 minutes.
Am I a noob king or C is actually tough.... Lol
Shut Up! You are not allowed to discuss about problems during contest.
make this contest unrated!
[Edited]
Reference:
https://mirror.codeforces.com/contest/1475/status/page/70?order=BY_RELATIVE_TIME_DESCFrom this page onwards for quite a few pages of submissions. (the page number will change as time goes, so a little ahead or behind, around 30 pages from the last page)
Shady activities. [Edited/]
Someone is purposely overloading the server. There are many accounts that have been created around 11 days back which have submitted codes that have lead to compilation error.
Why tho? :/
They may be college freshers
Probably not, the names are spammy, all created on the same day, submitted and went offline around the same time, submitted compilation errors around the same time. Very hard for it to be freshers, the names and profiles don't look genuine.
Make it an unrated contest please.. queues are unbearable
At this point they should just make this unrated, the queue is unbearable
Codeforces is really a awesome platform
In div-3 no of solution submit frequency is so much.
So, If in div-3, only <1600 rating people can attend thats much better for the server i think. >=1600 rating can practice it virtually though (:
Most of the participants in CF are below expert or unrated so that wouldn't matter
and i did not said by that all problem solved but can reduce (: just my opinion sir.
but that's 5k people submit 5k*7 solution in first hour mostly. cause they solved all before 1 hours. and initial time is most important.
The fact that the contest isn't rated for someone doesn't means that it cant be enjoyable on a competitive point of view
Contest has been declared unrated!!!!
I think everyone got the notification...
Why codeforces why?
Well not just a registrants record also a queue record
2021 == Extended Version of 2020 .
2021 == 2020 won and now it wants have some fun :)
30 000 participants dissapointed for the first time
A round of nice problemset is ruined.
So we were trying not to annoy delays for this?!!
Qᴜᴇᴜᴇғᴏʀᴄᴇs..........................................
to cc and cf : you either die a hero or live to become the villain
When CF Predictor shows +200 and the round becomes unrated...Sed lyf
Please consider restricting new acccounts from participating div.3 (more than $$$5500$$$ out of $$$30000$$$, two times as the number of $$$1600+$$$ people. It's really weird.) or upgrade the judge system. The number of participant is too high for the current system (or the system is a bit off today?)
Maybe I should call it Qulayforces,right?
No.
I guess, CF should only allow participants whose rating less than 1600 even to enter the problem-set page for Div 3.
This will increase the no. of people having rating greater than 1600 to participate with a new round , which will have a big adverse effect.
I do understand your concern, but I guess Div3 are meant to be beginner friendly (Please correct me if I am wrong), and in such a case, why could it be only allowed to participants below 1600. (Also, If I had offended anyone, apology). I wouldn't say that high rated people shouldn't take part in lower Division contests. But given the possible scenarios of long queues and site getting down, It could be a suggestive measure.
Suggestion is good but I think it is not practical
Is Codeforces taking inspiration from codechef nowadays?
Never in it's lifetime will Codechef have such a huge number of participants.
Queue 260 pages long :(
I'd love to sacrifice my Internet/CPU/Screen space to see ads on this website just to have better servers. Please admin consider this way of getting better servers.
I had such a bad spree and now cf predictor showed +115 and round is unrated... brb gonna drink some bleach with vodka
Very disappointing! Considering that there were 2 delays and the round was delayed by 25 minutes, it seems that they understood what was happening. Perhaps it was worth postponing the round a few days in advance, having solved the technical problems before. This is doubly sad because the tasks were interesting :(
They tried to prevent such unexpected issues by delaying the round a bit but still it could not be prevented :(
Anyways beautiful problem set! :D
The sad part is that today my exams got over, and I was like finally I can give the contest without much thinking about studying for exams.
Is that a coronavirus on your profile?
lol no! Its a polygon with thousand sides! That is a chiliagon!
Getting a +150 increase and seeing contest becoming unrated hurts :(
What is the procedure in this case? Can people discuss problems already as ratings are not impacted?
i think you can discuss with friends but not in the comment section
Sorry guys. I could not prevent the round from failing, as I was at the doctor's appointment.
Still infinite times better than Yesterdays Codechef cook-off.
But that was rated.
beside unbalanced div2 & div1,they said they have improved servers before contest , then servers didn't worked during the contest for 30 minutes , created unfair ranking gaps and then they were stubborn enough to make it rated .
Codechef is a joke nowadays. Only 2 short contests per month and that too getting server errors a lot, you can't even open IDE to submit the code forget about long judging time, similar thing happened in december as well. No wonder why CF is 10 times better than CC.
No problem MikeMirzayanov. Altough Iam sad about this round but ..... Get well Soon.
Got it. A ship was wrecked when the captain went to the doctor's.
First time I solved 3 problems in a contest. But unfortunately It is now UNRATED...sad
I was getting around 100+ rating in this contest but luck cannot favour you always :(
Remember! there's also people who left the contest earlier.
Problem G is not available on m2.codeforces.com, which is more strange than queue problem.
Remove div3 from codeforces. It was pointless idea from the beginning and as for now servers are not able to handle 30k submissions for easy problems and I don't think they will able in the near future. You're only disappointing people.
I think this is not solution
It is solution. Have you ever seen a queue on div1 round? Div2 rounds were unrated due to queue, as I know, but queue was caused by server issues (and extremely easy problem A and B). Today servers were on full power but anyway they weren't able to judge easy problems without queue. Removing div3 and making div2 harder will definitely solve queue issues.
Of course we can solve problem with this for temporarily but when codeforces get bigger few years later this solution is useless
I could bet if you were pupil, you wouldn't make this comment
What's the point of div3 round for you (and pupils)? Practice? No, you will never reach even expert if your practice consists only of div3 ABC problems. Compete? No, your CP level is too low for real competition. Competing with this level and being happy with 2000th place on contest instead of 3000th, instead of practicing, won't raise your rating and you'll be pupil for life.
Please make it rated, I'm getting 140+ delta :) :(
Cool, you got 140+ delta after most people left ;)
Ohh that's the reason for this miracle. I thought I done some extraordinary work today :)
-- Problem A, Odd Divisor
This problem asks us to check all divisors of n if there is an odd one among them. Note that the constrainst are set in a way the the simplest implementation of the factorization will go TLE. see https://cp-algorithms.com/algebra/factorization.html
Edit: Or just check if there is an divisor other than 2.
-- Problem B, New Years Number
Note that n is fairly small. So we can check all multiples of 2020, and if the difference to n is divisable by 2021. If none of them is, then ans is NO, else YES.
-- Problem C, Ball in Berland
We need to choose two pairs. So, we need to know foreach pair p1 the number of other pairs we can choose, if we have choosen p1. That number is the number of all pairs, minus the number of pairs having the one or the other member of p1 as a member.
Since each pair is distinct, we can count the frequency of all members in all pairs, and subtract that frequency from the number of all pairs.
-- Problem D, Cleaning the phone
Its a strange greedy. We can sort the applications by storage units per cost unit. So simply double the storage units of the 1-cost apps, then sort them. Then we choose the best ones until enough storage is cleaned. If not possible then ans=-1.
But, it can be that we can substitute one 2-cost app by a 1-cost app. For that, check if there is a not choosen 1-cost app that we can exchange agains the worst choosen 2-cost app, so that still enough storage is cleaned.
Not sure how to prove that there cannot be more than one such substitution.
-- Problem E, Advertising Agency
Of course we must choose the best bloggers first. But there can be equal bloggers, and if there are equal ones, we can choose among them.
Consider the number of followers of the worst of the choosen bloggers. Let cA be the number of bloggers with the same number of followers as that worst one. And cC be the number of bloggers with same followers as worst, and wich are choosen. Answer equals nCr(cA, cC). This is, because we can choose any cC of those bloggers among the cA ones.
-- Problem F, Unusual Matrix
Observe that it does not make sense to flip a row or col twice. Flip it once or not at all.
Then consider the first row. We can flip it or not-flip it. In both cases, we can see foreach column if it was flipped or not by comparing the fields of the first row of a[] and b[]. As a result we get the state of each col, flipped or not-flipped.
Then check all other rows if we can construct the b[] version of the row by using the column flips on the a[] version. If this is possible for all rows then answer is YES, else NO.
-- Problem G, Strange Beauty
We find the biggest possible set of numbers we can put into an array, then the difference to the number of all elements is ans.
Consider that we have put one number into the array. The next one must be a multiple of the first one. And then the next must be a multiple of the LCM of the first two ones... It turns out that because the last added number is allways a multiple of all numbers previously added, we can allways add each multiple of the previous number. So we can create a graph where each number has an edge to each multiple of it, then find the longest path in that graph.
Other possibility is a dp, where dp[i] is number of elements that can be added after having added element i.
Problems were really cool, thanks!
Small note:
A could be solved by checking if N is a power of 2 and outputing false if it is, else true
B can also be solved by removing as many 2020s as possible, ur left with only 1s to add to the 2020s removed, if there are more 1s than 2020s removed, then its false, else true
Wow, cool, I did not see this.
Another approach for D:
Fix the number of 1 cost applications and binary search to find how many 2 cost you need to take
Every time I will forget that we can construct an algorithm with time complexity O(n + n/2 + n/3 + .......n/n).
I have tried D with the same approach but it is not working can you tell me my mistake here is the link to my submission https://mirror.codeforces.com/contest/1475/submission/105410745 This approach is similar to spookywooky
Not sure about that. Mine looks like this 105418791
Video Tutorial A and B:https://www.youtube.com/watch?v=vMpkqoZZN0I
I don't see a single submission from your handle, why should one trust your solutions?
I was wondering how that person was able to solve an problem C and problem E and problem G in one minute???
problem A in minute 4
problem B in minute 5
problems C & E & G in minute 6???
His submissions are skipped
No matter the round is unrated, the problemset was really good. Thanks for making div3 rounds "for div3 participants."
Don't say something generally! yes, it mattered for me and for many users
Am I the only one who reduced F to a 2-SAT problem?
Can you please explain your 2-sat solution. Thanks in Advance!
Let's say $$$r_{i}$$$ is true if we do horizontal xor on ith row. Similarly define $$$c_{j}$$$ for jth column.
if ($$$a[i][j]$$$ and $$$b[i][j]$$$ are equal) it must be the case that either (both $$$r_{i}$$$ and $$$c_{j}$$$ is true) or (both $$$r_{i}$$$ and $$$c_{j}$$$ is false). Here we can add one edge (undirected) between $$$\neg r_{i}$$$ and $$$c_{j}$$$ and one edge (undirected) between $$$r_{i}$$$ and $$$\neg c_{j}$$$.
if ($$$a[i][j]$$$ and $$$b[i][j]$$$ are not equal) it must be the case that either ($$$r_{i}$$$ = true and $$$c_{j}$$$ = false) or ($$$r_{i}$$$ = false and $$$c_{j}$$$ = true). Here we can add one edge (undirected) between $$$r_{i}$$$ and $$$c_{j}$$$ and one edge (undirected) between $$$\neg r_{i}$$$ and $$$\neg c_{j}$$$.
Now this is like 2-Sat on an undirected graph, if a solution exists then $$$i$$$ and $$$\neg i$$$ must not belong to the same component. I used Union Find to check this
Brilliant solution. Thanks a lot for the explanation!
Problem E was quite easy ... probably somewhat problem C level.
And D was harder than G and F
Can you please help me in finding out where my logic for D is failing its giving wa on testcase 3
My logic -> Binary search on answer and for each mid(convience value) choose greedily between 1 and 2 for different partitions...
Link to my solution.
Any sort of help is highly appreciated...thanx!
Could someone explain this:
I can't believe that there exists a man who can solve 3 different problems(including the most difficult one) within 1 minutes. Although this round is unrated, such behaviors may violate the rules?
It is impossible to solve these 3 problems within 6 minutes without knowing the problem beforehand as I don't think these 3 problems were one-liners
Strong as Tourist has spent 12 minutes to solve them... What is more, I think this participant didn't know the problem before the contest started because I really trust Codeforces that it wouldn't allow problems leaked. It may be the result of group cooperation.
Any idea how to fix TLE on test-12 in problem G TLE_CODE
Precompute the factors for 1 to 200000 outside your solve loop, rather than calculating them every time
use array instead of map.since numbers are from 1 to 2*10^5 you can use array.
Here you go
gp_hash_tablewithout passingcustom_hashis just as slow asunordered_set.Here, it would just be faster to make a dp array and clear it everytime since the number of testcases is small. Even in the case where the number of testcases were large, you could selectively clear those indices which we used.
Thanks, a lot bud, highly appreciate it.
I really wonder what is test case 12
105411878
for problem E , my logic was, store frequency of each follower count and greedily select the bloggers with high frequency : in each step we see if the number of bloggers will exactly fit necessary number or less than required (in this case we just select them ,only 1 way) or more than required number (select required from available with that freq. my submission the combinatorics part is from galen colins library. please check
I have a weird solution for F. It is to check whether for every 2x2 submatrix, number of ones in matrix A and B must be even (for the same 2x2 submatrix). Is there a proof why it worked?
105379848
Some dumb reductions first.
Note that the order of flipping doesn't matter, there's no point in flipping the same row/columb twice. Take the xor of the two grids, now we need to check if the resultant grid (call this $$$x_{i, j}$$$) is reachable from the grid filled with zeroes.
Let $$$S_i$$$ be $$$1$$$ if we flipped the column $$$i$$$, $$$0$$$ otherwise; similarly define $$$T_j$$$ for rows. We see that $$$x_{i, j} = S_i \oplus T_j$$$. (You can get a solution from here by first setting $$$T_0 = 0$$$, then finding all $$$S_i$$$ and $$$T_j$$$ from the relations and finally checking if all the values are consistent.)
So, for any two-by-two grid we have $$$x_{i, j} \oplus x_{i, j + 1} \oplus x_{i + 1, j} \oplus x_{i + 1, j + 1} = (S_{i} \oplus T_{j}) \oplus (S_{i} \oplus T_{j + 1}) \oplus (S_{i} \oplus T_{j}) \oplus (S_{i + 1} \oplus T_{j}) \oplus (S_{i + 1} \oplus T_{j + 1}) = 0$$$.
This gives the necessity of the check, to prove that its sufficient we give an explicit construction of $$$S$$$ and $$$T$$$ which works, $$$S_i = x_{i, 0}$$$, $$$T_j = x_{0, 0} \oplus x_{0, j}$$$.
Induct on $$$a, b$$$ to show that $$$x_{i, j} \oplus x_{i, j + a} \oplus x_{i + b, j} \oplus x_{i + a, j + b} = 0$$$ (basically the xor of the endpoints of any rectangle is $$$0$$$). In particular, $$$x_{a, b} = x_{a, 0} \oplus x_{0, b} \oplus x_{0, 0} = S_a \oplus T_b$$$ as required.
Nice explanation, it is clear now. Thanks a lot.
Can someone help me in problem D? Why my code is giving Exit code is -1073741819 (RTE)? What does that exit code .... means? https://mirror.codeforces.com/contest/1475/submission/105404284
I am getting runtime error on test 2 of problem d..can anyone please provide some tc to make me understand what is the problem ..
https://mirror.codeforces.com/contest/1475/submission/105385557
Check out my explanations of problem F and G — solution
Anyone want to increase their hack count??
Here you go... :)
105318690
Can anyone help me in
uninitialized value usageerror, I don't know why I get this error. https://mirror.codeforces.com/contest/1475/submission/105411235I think it may have something to do with using %lld specifier, I may be wrong though.
I tried to use cout. But I get same error https://mirror.codeforces.com/contest/1475/submission/105439141
For F I use some greedy solution and can't prove it. Can somebody says why this works? 105382873
for problem C it never specifically stated that pair cant be repeated, doesnt that mean the i can use that as a test case in hacks?
Actually stated
It is guaranteed that each pair is specified at most once in one test case.oh, my B didn't notice that. you're a real G
Hello, can someone explain to me Problem G : why this sample of test 2 5 2 1 5 5 4 answer = 2
Isn't removing 5 is enough to meet the required conditions?
You need to delete both occurences of 5
One user seems to have solved 6 problems in 6 minutes, but later all of their submissions were tagged as skipped. I was just wondering if this was just a tester or a cheater? If it was a cheater, then obviously you had some kind of a leak.
Can E be solve by dp. Like we know the maximum followers we can get. And then by dp we can find ,the no. of sequence having k bloggers that has sum equal to max sum. I have tried liked this but getting wrong answer.
Yes, it's pretty easy with dp. You can use dp[i][j] with the meaning:
The answer will be dp[n][k].second. The transitions are also pretty standard(for every person i you can either take it or not in the solution). You can check my solution for more details: https://mirror.codeforces.com/contest/1475/submission/105385888
Unrated?Unfriendly!
I cannot see the problem G in m1.codeforces.com in the past contest:(
I am very angry about the fact that 1475F - Unusual Matrix is included in the set. What am I supposed to learn from adhoc problems???
Hello everyone, I can't solve problem A using a trivial algorithm. The program just prints NO for every testcase. Can any people tell why?? Here is my code: 105509143
You can't check just the numbers smaller than sqrt(n). For example, n=26 would fail for your test because it would check only if 26 is divisible by 3 or 5, which it isn't.
Thank you very much! One more question: Isn't it true that all factors of a number n less than or equals to sqrt(N)? That was why I didn't check them all.....
Only about half of them are smaller than sqrt(n)! Take a number i for example, if n is divisible by i, and n/i=k, then n is also divisible by k and n/k=i. But if all of the divisors were smaller than sqrt(n), then both k and i would be smaller than sqrt(n), and k*i would have to be smaller than n, where we get a contradiction! Your algorithm also has to go through all numbers i from 2 to sqrt(n) inclusive, and then if n is divisible by i, check if any of i and n/i is odd.
I was so close to finally reach specialist, I had a +219 delta... I guess I'll never reach cyan
Can anyone tell why this is wrong (question g). 106012046