I think very rarely it happens that the questions asked on the codeforces contests are available on google. But today's contest was a blunder in that aspect. As you must have already seen in the comments of the announcement blog that problems B, C, and D were available on the internet. "Participants should be ranked on the basis of how fast they solve a problem rather than how fast they search a problem". Now someone will say that even in ICPC you are allowed to copy from the net. You are allowed because you can copy some templates but you won't get direct solutions coz questions are unique. I don't have any issue with geometry problems and no one should have because we are here to learn cp and cp also includes geometry problems. But I believe that duplicacy of questions should never be promoted on codeforces and therefore today's contest is one of the very rare bad contests on codeforces platform. Sorry if it hurts anyone :(
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 23.12.2024 01:19:46 (l1).
Десктопная версия, переключиться на мобильную.
При поддержке
Can you please share the links you think the problems are copied from?
https://www.wikihow.com/Find-the-Area-of-Regular-Polygons
Area of regular polygon. After getting this, divide the answer by (n/4) and you instantly get AC.
Is it obvious that you have to divide area of the polygon by n/4 to get the answer? To me, this seems much less obvious than a calculation of a polygon area which is just a couple of trigonometry formulas.
Exactly.
don't get me wrong, I got that n/4 by pattern finding lol. So I didn't even use my brain to think about anything to solve that problem.
I don't get it, how did you find that out? I just created the polygon, and calculated the smallest square it took to cover the full thing.
C2
Problem D
Problem B was easily available on GeeksForGeeks
Both parts of C were readily available on this link
But I think that the problem setters didn't do that intentionally it was just a mere coincidence , since they are creating these contests for more than 20k participants everytime. It requires a lot of time and effort for creating good problems of all levels of difficulty. So instead of criticising them we must appreciate them for doing a great job in every contest.
P.S. For all those who are telling that the problem setters copied or something, please try to create some problems on your own and then blame others.
Also, for problem D, I'd say timelimit was a bit tight(should've been at least 2 seconds). An average solution takes 1 second. Then, timelimit should be that double amount(which is 2 seconds). It was a bit unfair for other languages(apart that my solution was O(n*log(n)^2) which timed out and could've passed in a timelimit of 2 seconds).
I think it was supposed to try to knock out nlg^2n sols, and wanted people to have nlgn, which you can see I did here: link. However it didn't work to well and instead it ended up just hurting particularly languages while cpp people could still often manage to pass.
Yeah, I agree with you. But still, seeing most C++ solution getting 1 whole second in problem D looks a bit uncommon.
Solution which was O(n*log(n)^2) with Fenwick tree got AC.
Deleted. Sorry for what I said as it was wrong. I didn't know that Fenwick was a lot faster to that scale.
Actually, it's a pretty well-known fact that most segment tree implementations are significantly slower than Fenwick tree. I've come across problems where the segment tree solution takes almost eight times the time taken by Fenwick tree.
Even major programming competitions sometimes have questions which differentiate by this type of constant time (not saying they are good questions, but they exist on major contests, so I think it is important to learn such things).
Agree.
The contest was just fine according to me. Nothing great but not bad either.
B is so easy to think, why would anyone go and search for it. Its just a waste of time.
Also I am fine with such basic geometry problems for C. I didnt know they were easy to google since i tried to find hints for C2 but could only find solution for hexagon.
For problem D, it requires you to actually think that BIT and binary search would work, only then would someone go and search for it on the internet.
Not to mention that a lot of people (for whom this round was rated) don't know how to BS on BIT in O(logN). A perfect example of an educational task imo.
The constraints were a little tight.
B is so easy to think, why would anyone go and search for it. Its just a waste of time.So are you OK with Div2 A and B being copied from internet in every contest? May be it was easy for you but could be difficult for many and they would search for it definitely.For problem D, it requires you to actually think that BIT and binary search would work, only then would someone go and search for it on the internet.Most of the coders with rating >=1600 have at least some idea about BIT, or Segment tree. May be you want to say that problems which are from topics not known to many can be copied from the internet.If you see, you can find a lot of questions (A and B of different contests) which somehow one way or the other you can find on the internet. That does not imply that it was copied.
atleast in past month i don't see any A and B googleable .Except today contest.
today's B was very standard.
I haven't looked at the rest of the problems so I won't comment on them.
But I will defend the existence of D in an educational round. Constraints were BIT tight and they did mentioned not allowing PBDS was the motive of that.
My reasoning is simple educationals were meant to be classical problems and that gradually stopped after they became rated for Div2s. It's good to see classical problems once in a while.
Most of the coders with rating >=1600 have at least some idea about BIT, or Segment tree.Bruh I will stick with my words that a lot of people don't know how to BS on a BIT in O(logN). +25 here again proves this. At the end of the educationals are meant for learning instead of the rating.
Honestly, I will choose Good old unrated edu over these edus anyday.
I agree with you. I have read about Binary Indexed tree, but when it comes to implementing things you are not much familiar with, it becomes hard. This was good for learning.
I think this is more of an argument for unrated edu contests than the problem itself. In a rated contest problems should not be that classical, but I would agree with your argument it would be nice to have unrated edu contests again with classical problems.
" it would be nice to have unrated edu contests again with classical problems" . You can see past rated edu rounds , they did not have similar issues .edu rounds are good and should be rated for motivation for participation .
You can see past rated edu rounds, they did not have similar issues.
Because they did not have 3 copy pastable problems, 2 of which very classical...
https://www.geeksforgeeks.org/order-statistic-tree-using-fenwick-tree-bit/ You don't need to know it,you just need to google it
I never said one cannot copy-paste it. Its even present in kactl notebook which I used in ICPC regionals. I just defended which it should exist in an educational round. As far as rating is concerned be assured rating of people who just copy-pasted will be balanced in few contests. There is really no point in just copy-pasting without understanding.
I learned how to do multiset with BIT and binary search before coding multiset from scratch aka bbst lmao. It's extrememly standard.
Exactly, if anyone has a basic knowledge of fenwick tree, he/she would be able to solve that question without any need of googling.
But the point of the blog is essentially that it shouldn't be extremely standard. I agree you don't need to google to solve it, it was just a BIT (ha) dissapointing. I was expecting something that further optimized memory like bloom filter or similar, which wasted my time trying to think of better sol bcz it seemed to easy otherwise.
Yes, it becomes standard only after realizing that it can actually be solved by BIT and that 28Mb is sufficient for that. A lot of people i know thought that it could not be solved by any such data structures and hence they were struck. Also 1300 people solved div2D (out of 10,000) in the contest which is pretty much what we expect in a normal div 2 codeforces contest.
PS — I agree that the memory limit was strict for languages like Java and Python.
I think having problems where needing to optimize the memory would be cool, but having the hard part realizing that the same standard solution would work in less memory isn't a very good problem imo, especially after the round seeing memory overhead was a problem in other languages as I thought must be case with BIT sol in cpp, but obviously it wasn't.
Can the same be implemented using Segment Tree? I read somewhere that Segment Tree's better than Fenwick tree so I never got around to learn BIT or something similar and always stuck to Segment Tree. Guess now is the time.
https://www.geeksforgeeks.org/order-statistic-tree-using-fenwick-tree-bit/ I have seen many submissions copied directly from here. You just have to google it. Another link :https://mirror.codeforces.com/blog/entry/69716 which you can come across by direct googling the question
That makes you a competitive cheater not a competitive programmer.
Googling is also an ART imo.
I want to bring awareness to a big issue with problem D. This kind of memory limit is far too strict. Just reading the input uses up more than half of the available memory, this kind of limit is far worse than having a tight TL to kill off O(n log n) solutions.
For one thing it adds nothing but frustration to the problem, even if it blocks some kind of unwanted solutions. Secondly other languages like Java or Python need a certain amount of memory just to run. For example
This means that you are left with just a speck of memory to solve the problem with. After a ton of work, trying out manual IO and manual calls to the garbage collector, 20 submissions later I was able to get AC in PyPy3 80530828.
I don't think problems with constraints like these should be in rated rounds.
Agree.
After the contest, my friend sent me this link : http://mathafou.free.fr/pbg_en/sol118.html Scroll to the bottom and you have direct one line formulas for both C1 and C2. It's the third result from top when you google "largest polygon that can be inscribed in a square".
For second question , i didn't got any such question on google but, could easily be converted into question of minimising distance between elements of 3 arrays. So yeah, if i search the other way around it was direct answer.
This was an educational round.
Obviously we would encounter problems based on class algorithms data structures as well as rare math topics.
If you were expecting common things like the number theory greedy or graph then it's your problem :)
Have a courage to speak against contest makers . Votes on the announcement tells everything .
Voters are the pissed off programmers from the contest.
I have enough courage to speak against makers if needed. But at least I don't have multiple alts because I am fear of negative contribution like you? and contribution of both of us tells everything :)
MikeMirzayanov Why you can't make comments and blog entries only possible if accounts are trusted?
"Voters are the pissed off programmers from the contest." .Because contest was indeed bad .
"and contribution of both us tells everything" . You gave up here only .Lol
Instead of doing that , i think voting system should be changed . I have made some comments from fake account because if i say these bitter but true words then i will get permanent attacks of downvotes .
Why don't you switch to your real account and then we will see who will give up when?
why don't you speak the truth that round was bad . Since it went good for you and you are div3 tester , you are making such comments.This round will be rated and i want it to be rated (it went well for me too according to cf predictor). But round was really bad .
Well about you share your handle and then we will decide? And saying round was bad will not make any changes excepting decreasing your credibility if you ever shared your original account
I know . But praising the contest makers will help you .
It won't ask them :)
you already lost the chance by making comments below .I never saw such comments by any of the contest makers . They do speak against comments but never comment like you .
Kiddo first clarify to your self what you think? I am trying to impress them or opposite. You are contradicting yourself. Ask your mumma to give you milk and put you into bed and stop crying
You get downvotes when what you say is stupid, and upvotes the few times they're not. If you really believe the words than why would you care about contribution, just say from your real account.
I didn't like many aspects of this round, and I'm saying it with my real account.
I completely agree.I do not have courage to speak against contest from real account . You are new to codeforces . I am seeing that now a days you are regularly making comments . Unless you go back to master you will see unexpected downvotes . It's bad but this is how most of the people behave here .There is no regulation of votes .
Why do you care so much about rating and contribution?
I don't like to talk to people having no manners in public forums .sorry i can't discuss further with you .
Ok Kiddo :)
Sure I disagree with what I'm downvoted on sometimes, but that's life, and sometimes people disagree with you. However, if you have -67 contribution, that probably says that what you say in general is usually wrong, or at least widely thought to be so.
Obviously we would encounter problems based on class algorithms data structures as well as rare math topics.If you were expecting common things like the number theory greedy or graph then it's your problem :)I never said that I was frustrated because the questions were not from number theory or greedy or graph. If you read my blog carefully, I have rather admired the author for choosing questions from wide range of areas and it is our responsibility to be prepared for any type of question. I think you didn't get what I meant.
Cry hard kis :(
I want to say a couple of words about today's D.
First of all, I would like to apologize to non-C++ coders for setting a tight memory limit. The reason why I did so is to get rid of straightforward PBDS or prewritten treap solutions (a treap, for instance, would require just something like 32 megabytes, hence the memory limit).
Why did I want to do so? Because the problem was not initially designed to be a data structure task. I wanted to give it on a local contest where people were familliar with binary search, but not with Fenwick/STree, so it seemed like a non-trivial binary search. I thought that most contestants would try to think about an easier solution instead of just writing or copying a data structure, but it turns out that I was wrong.
By the way, the case with B is almost the same: I wanted a solution without any complex methods such as two pointers or binary search, just simple observations.
Nothing wrong with the contest tbh. You are writing and preparing problems very frequently nowadays, so little misunderstanding is acceptable. I don't think so there is something wrong. You should not explain to shitty people who don't have courage to say with their real accounts because they are afraid of downvotes. Lmao!!
Yeah , now you will become tester of div2 as well by impressing them .cheap tricks.
So I have no idea what are you saying with one of your shitty alts
'shitty alts' . I won't be surprised if you start to abuse . lol . drink some water . I never used such words in any of my comments and again anyone . Go and them happy . You won.
LOL!!! Dude My name is abusing, what you expect from me? Kid have some rest and don't complaint your family I abused :)
going to lowest level ....... I don't know what you handle means. drink water man. I am educated enough and my elders have taught me enough to not abuse some one .
You can't comment whole shit in a single time. Why such pissed and toxic people even exits in such community who are being educated don't have enough credibility to be real :)
I even think you are upvoting your comments with other alts LMAO. Kid grow up or one day you will say same for ICPC contests.
Apt meme for the situation.
Literally translates to — "Sit down the child. You have to learn a lot".
It just means you don't know how testers are selected. First find that then comment on how one becomes a tester.
Agree!! This Kid think pikmike and bleddest will make me tester for their rounds after saying so!
Yeah i am kid .But sad that you being such wise man don't have manners .
Grow Up Kiddo or I will die due to excessive laughing:)
I do know . I think what i wrote went above your head .Also please upload memes with language do that everyone can relate and understand .
I think he translated the same in English. However why you are being so racist with language. Over 50% of participants are from India everything and everyone holds the right to say in their desired language.
another negative comment Learn some positive things wise man . You can ask you teacher that it's now racism .
LOL Kid it had upvotes and why are you interested in my past comments. See this is the reason you are a kid. You ain't taking responsibilities for the things you are pissed and blaming everyone in their replies
I would recommend to just ignore the fake account. With his -67 contribution, i would not expect anything constructive coming out of him. Just trolls and thats it.
Are you mentioning me? "don't have courage to say with their real accounts"
This round should be unrated. Problem D was totally unfair for non C++ coders.
How was it unfair to non C++ coders? I use Java. I used fast IO and BIT with O(logN) lower_bound search per query. It passed the pretests.
Man, literally every contest has problems that are totally unfair for non-C++ coders.
I think it's not binary search, but this extension of Fenwick tree is the easiest solution: https://petr-mitrichev.blogspot.com/2018/02/a-fenwick-bound-week.html. It's 2020 but somehow not everyone still knows it.
Wouldn't it be better if you replaced C with D allowing the PBDS solution?
That's still unfair to non-C++ coders
Thanks for speaking out about this — it's been bothering me all day. I spent a lot of contest time thinking there must be some "trick" to D, but turns out that even simple Fenwick tree failed with Kotlin, and I didn't even try doing binary search as the memory reqs would be similar. The only thing that saved the contest for me was that solving C2 apparently gave me enough standing to finally reach CM for the first time (according to unofficial projections)
I do have some concerns over the recent trend of tight memory limit problems; besides the non-C++ issues, will such problems even age well in the archive? As compilers change over time they might actually consume more memory, as far as I understand
I don't think that this kind of solution should have passed : 80502870. Clearly the worst case of this code is about 2e9 operations ( complexity O(Nsqrt(N))). I tried to hack the solution but could only reach upto 1403ms (with about 2e9 operations).
After getting to know that B,C and D were easily google-able. What should I do from next contest onward? Should I first search for problems on internet as soon as I see a task that can be found on internet or should I solve it myself investing a lot of time ? Second leads to significant decrease in rating . What do you think ? Also I vote of this recent Div2 to be unrated !!
I know people will downvote for no reason ! This round educated me about how can effective googling give you ratings, thus Educational round ! cheers !
The answer is very easy and simple.
Just google. Get one positive delta. Stay happy with this because you won't be lucky all the time. Then RIP after ~50+ years while narrating the story to your grandchildren how you got lucky once on codeforces.
I think there are a lot of people here who are just here to improve themselves and learn rather than just having a positive delta. I have participated in all the contests since I have been active no matter how many questions I am able to solve. There has been contests where I have not even solved 1 question and got a huge negative delta. But that should not matter to you if you are here to learn. The point is you should at least try. Writing a solution after googling a problem and writing a solution on your own are two vastly different things. Googling a problem might give you great delta, but in my opinion solving a problem on your own is more satisfying. You can always check the editorial after the contest and up solve the problems. I don't think I have ever googled a problem from any of the contests I have ever participated in. I honestly don't know much difference between Educational rounds and normal rounds, but still I think you should give problems a chance and try to solve them first. People here are telling B, C and D were google-able but still many of us have not googled them and just tried to solve it on our own. I am not against googling problems, but for beginners like me, I think trying it on our own is much better.
"...even in ICPC you are allowed to copy from the net"
Well, good luck doing that LOL
Imo D was a really good problem for an educational round. I am quite inactive on CF and don't know if this thing is trivial but an extension of Fenwick to do binary search + query in log(n) time is in my this year ICPC codebook and my teammates would have removed it if it was so trivial.
Maybe problem C wasn't good enough, but i really enjoy solving E, F, G. In my opinion, you can't judge contest based on 1 or 2 easy tasks.
For the majority of rated contestants, (the majority being Expert or below), problems C and D are the hard but solvable ones whereas E and beyond are too hard to solve within contest. So it's fair for a rated contestant to judge a Div2 contest based on problems A,B,C,D.
Is there an editorial for this contest? I'm pretty sure I had the right answer but my doubles were imprecise or something like that so I kept on getting like .3 off of test case 3 in sample C1 (n = 200), although it may be my incorrect logic (my solution was 1 + 2 *( diagonal length of 2(n-1)gon))
Is it bad really. I think it's rather fine