Привет!
6 мая (воскресенье) в 17:05 (Московское время) начнётся Codeforces Round 479 (Div. 3) — первый в истории Codeforces раунд для третьего дивизиона. В этом раунде будет 6 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Наверное, участникам из первого дивизиона они будут совсем не интересны, а для 1600-1899 покажутся простыми. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо Neon за тестирование раунда.
UPD: Большое спасибо тестерам dreamoon_love_AA, eddy1021, step_by_step и kiyotaka, которые согласились протестировать задачи и нашли недочеты. Теперь мы полностью готовы к проведению раунда!
Надеюсь, что задачи вам понравятся. Если вдруг что-то не так окажется со сложностью задач, то будем подстраиваться в следующих Div.3 раундах.
Коротко о себе. Меня зовут Владимир Петров, я учусь на 3-м курсе в Саратовском государственном университете и еще со школы занимаюсь в Центре олимпиадной подготовки СГУ. В ICPC участвую в составе команды «Saratov SU Daegons» с awoo и Neon. Люблю читать и смотреть фантастику. «Песнь льда и пламени» читал 3 раза, жду публикации еще 2-х томов.
Удачи!
UPD2: Разбор
UPD3:
Поздравляем победителей (официальные результаты):
| Rank | Competitor | Problems Solved | Penalty |
|---|---|---|---|
| 1 | cMartynas | 6 | 69 |
| 2 | nimphy | 6 | 117 |
| 3 | Passenger | 6 | 124 |
| 4 | mandinga | 6 | 128 |
| 5 | raffica | 6 | 144 |
Поздравляем лучших взломщиков:
| Rank | Competitor | Hack Count |
|---|---|---|
| 1 | greencis | 36:-8 |
| 2 | Tlalafuda__Tlalafu | 10:-1 |
| 3 | STommydx | 9:-1 |
| 4 | dalex | 8:-7 |
| 5 | dreamoon_love_AA | 4:-3 |
| 6 | shnk | 2 |
Было сделано 97 успешных взломов и 297 неудачных взломов!
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
| Problem | Competitor | Penalty |
|---|---|---|
| A | kuzmoid | 0:01 |
| B | peach | 0:04 |
| C | Milhous8 | 0:08 |
| D | Milhous8 | 0:11 |
| E | s0mth1ng | 0:09 |
| F | DoveDragon | 0:14 |
What is the relationship between div3 & div2 problems. For instance A div1 is equal to C div2
This contest is for div3 only. I do not think there will be a relationship between div2 and div3. I mean can something be easier than Div2A? Maybe Div3A+Div3B+DivC are so close to Div2A. We will see after the round :)
This contest is only Div3 , so i don't think there's any relationship with Div1 or 2.
"We plan to include in these rounds simple training problems that will help beginner participants to gain skills and to get new knowledge in a real contest."
за взломы после раунда будут даваться очки?
Судя по тому, что контест будет "по правилам образовательных раундов", — нет.
I found a mistake for you :)) Please correct it.
Thank you, it is fixed now!
So will there have Educational Round like the time before updating? :P
Finally!
Last three lines was awesome . :D
:P
"The round will be hosted by rules of educational rounds..." Honestly, It's really boring! Given that this is a div3 and problems should be easy.. Then what is the use of the hacking phase ??!!
We will experiment with formats of Div. 3 rounds, but there are some reasons to start with rules of Educational Rounds:
This is what I have been waiting for long time: "**I prefer Div. 3 participants to solve problems during a round instead of spending time trying to hack**". Hacking is a good way to develop debugging skill. But a div3 participants should not spend the whole time trying to hack a problem just to increase rating instead of solving another problem.
Thanks Mike.
But what about the feeling of DIV3 participants. I really enjoyed codeforces round DIV1 / DIV2, due to div1 and div2, DIV3 is also should not be affected. div3 also must be same as daily codeforces round not educational type.
As Mike said, div2 rounds are not affected. So you can just ignore div3 rounds.
First time I saw about myself in any round announcement.
You might want to take a look at this!
Your link is not clickable. Check it.
It's rated for me so :D
unofficial participator for the first time :) :D
Why extended ACM-ICPC? Why not like a normal Codeforces round?
Here
Will I become Div.4 user if I lose rating in Div.3 contest?
As of 5/5/2018, there is no such thing as a Div. 4 user. The lowest is Div. 3.
Dude, don't you know about sarcasm?
and neither humor
Не ожидал, что Div.3 появится так скоро после анонса. Спасибо за усердную работу, Codeforces!
Hello, If this round is following Educational Round formats than I want to bring something to your notice. See the picture attached.
My friend solved Problem A and his solution for problem C failed. I solved Problem C and my solution for problem A failed. I just want to point out that Problem C was tougher than Problem A and anybody who solves tougher question should get better rank. I think people will say that it is for learning new skills and I should not concern myself with the rating. But I still think that this is unfair.
Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy.
So, I think, there will be no issues with Div3 problems, as at some points, we will figure out that it is eventually too easy, regardless of which problem in a contest (A, B, C, D, E, or even F).
In other words, soon we will realize none of any Div3 problems will be any tough to be obliged to be distinguished.
Still, the point system is better than the penalty system in my humble opinion.
ACM-ICPC scoring is used in many contests.
If you don't like the format of educational round, you don't have to participate.
If you don't want to be rated because of these rounds, you can always do virtual participation of solve problems regardless.
I am fine with whatever format you want to use, I am asking is it fair?
1) You complained about the rules of the contest.
2) You just said "I am fine with whatever format"
3) ?????????
4) Now you ask if the rules are fair.
Yes, they are since your signed up knowing them.
As I said, if you disagree with this type of scoring just don't participate. If you are annoyed at messing up on problem A check over your code more before you submit.
Hmm, thanks for helping.
Очень приятно, vovuh,
One more chapter is going to open from May 6 (Sunday) at 14:05 (UTC)..!!
Div3 => noobs?
once you, too, was thus noob
Hey bro cyan isn't too hot either. We're all noobs, just some less nooby than others.
Effective...
So which one do you like better? The books or the TV show? vovuh
I like books better than the TV show, but the TV show is also wonderful =) Especially Natalie Dormer =)
You've probably meant Natalie Dormer
Oh, yes, you are right, i made a mistake
В чем смысл "коротко о себе"?
За что минусы то? Я просто спросил.
Вопрос в том, отличается ли формула перерасчета рейтинга для div3 контеста от div2? Ведь если нет, то победитель сразу получит >= +300 рейтинга, и если у него рейтинг около 1600, то он войдет в div1, что как по мне не правильно.
Да не получит он +300 рейтинга, я гарантирую это
Я потихоньку начинаю сомневаться в этом
Ну ладно, получит, но в див1 не выйдет
Looking forward to concise problem statements without unnecessarily long storylines!
Div3 finally comes! No more falling scores!
One can only hope^_^
OK, then just bless!
tourist do you want to join us in div 3 :) ?!!
don't worry, they'll open div 0 for him
for tourist? I think Petr has higher priority in the current time.
He does not even need to look to the problems to solve them. :)
lol.u can't solve some problem even by reading them :)
Will div 3 participants be allowed to take part in div 2 contest?
Obviously...
Will it be rated for div 3 contestants?
when it is only div 2 contest then the user who's rating is less than 2100 can participate in this round and when both div 1 and div 2 round will be held , user who's rating less than 1900 can participate in div 2 contest as a official participant.... official means rating will be update
How many problems will be there?
You will be offered 6 problems
Waiting for a DIV2 contest. The sooner, the better. The more, the merrier. :)
Problem A : Print "Hello World"
HTTP Response: 500, 502. Website failed.
20 minutes of penalty is too much.
for a 2-hour contest, indeed. 20 minutes seems better with 3~5 hours contest.
AH ? I can't register while the contest is running !
What a pity!
20 minutes of penalty is too much.
I used 19min to solve all the problems.
But I got 1 penalty.. doubled the time..
20 mins of penalty is standard ACM rules. It encouages coding correctly instead of coding fast, which I think is ok. Also, the contest is targeted at people who can't solve all problems in 19 mins :)
Penalty is calculated as the sum of times each problem solved (+ 20mins penalties), not as the time of the last solution. So it's not doubled because of that, don't worry :)
You're right.. But I got "502 Bad Gateway" for 30 mins LOL
So? That's completely irrelevant to the discussion. Nobody cares how well you did in a div3 contest, mate.
Затупил 3 раза и смотришь как из-за штрафа скатываешься в помойку TT_TT
Thanks vovuh for this round , and thanks MikeMirzayanov for Div3 !!! This is the first time that i am able to solve all problems .
Spending 30 minutes to solve the last problem. Is it a little bit slow compared to how such contestants like me (1800s-rating guys) are supposed to be?
Why are there some (not all) unrated accounts in the official standings?
What exactly? Please, give me some examples of such handles.
official rank #1 for me is readers5 and rank #4 T_van for example
That happens pretty often in div2 if not all the time, even in older contests.
My guess has always been that some of those are smurf accounts created by high rated people just to be on the top spots in a contest. A lot of them are legit skilled people on their first contest, but some are left inactive after one contest.
Yes but the thing is that it's not supposed to happen with the new div3 rounds.
Sorry, you're right. Forgot that.
I think this was too easy even for div 3.
I agree. In Div 2, very few experts (the highest eligible rating) solve the set. In this one nearly every specialist and their mother solved it (not really but you get the idea). You never see 200+ eligible participants solve the set in a round.
Yes, It should be a little harder so only about 50 or less gets full. NOT 200. Even me solved the whole set! Maybe it should be for users whose rating less than 1400
First time in my whole life! I solved all problems! (but... It is div3)
.
.
Is there simple linear solution for C?
.
In C++, you're right (because there is std::nth_element). But I mean that in many standard libraries, there is sort, but there isn't nth_element. So in this languages linear solution will be much harder.
No, quickselect has a worst case of n^2, similar problem to your sort
Quickselect have O(n^2) worst time, nth_element in C++ have O(n*logn) worst time, but here is Medians of medians algorithm (or Introselect variation), which have O(n) worst time.
But it's not simple (or not obvious at least).
Будет разбор после?
It seems the difficulty is something like:
Div3 A, B = Div2 A
Div3 C = Div2 B
Div3 D, E = between Div2 B and Div2 C
Div3 F = Div2 C
I think Div3B is too simple for Div2B
Possibly. Honestly Div2 A and B feel more or less the same difficulty, at least in my opinion. Only thing I've seen is that Div2 B sometimes has annoying edge cases, so yeah you're probably right, it's probably A level.
Intially i was not able to look at question and was getting a continuous error of Bad Gateway 502
:(
I Accepted F after contest finished 1 sec...
(Sorry for my poor English)
how can solve the ploblem c?
Sort the elements, and the k'th element (1-indexed) is your answer. If k = 0, then just subtract 1 from the first element.
The no solution cases are when the k'th element equals the k+1'th element (why?) and when k=0 and the first element is 1, because subtracting 1 would be outside of your range (you may be tempted to try to be clever and subtract 2 so you don't have to handle that case separately, but that fails if the smallest element is 2).
I don't get how, for k=0, there could be an answer different than -1.
I mean, as I read it, there is no x «such that exactly 0 elements of given sequence are less than or equal to x.», regardless the value of the first element. Am I missing something?
What exactly do you mean by «because subtracting 1 would be outside of your range»? I guess you refer to the range [1, 10^9], but why should I subtract something?
Thanks
Say your sequence is 10 26 4, and k=0.
Simply output the number 3, and that is 0 elements from the sequence are less than or equal to 3. If the smallest element is 1, then there is no answer that is in the range from 1 to 1 billion.
Can E be solved using this logic: LINK
if you mean E,E is simple. Just for each connected component see that every node is connected to exactly 2 other nodes.
I tried this for problem D.
Take a boolean array
check[n]and mark all as false. Then I tried making chains. Take the first element and mark it as true and this will start a new chain. Then for each other false element in array check if it can be added to the chain started by this element, either by appending it to the beginning or to the end. If yes mark this as true too. For beginning, check if the new element divided by 3 is equal to first element in chain or if new element multiplied by 2 is equal to first element in the chain. Similarly we do for the end.However, I couldn't figure out how to decide a way to print all these chains in a valid manner. Is there any way to do figure this part out.
I think your approach is wrong or maybe i understood it wrong anyways this is what i did: A move consists of dividing by 3 (if divisible) or multiplying by 2. This means given a number we are taking away 3's and giving it 2's. So a state once reached will never be reached again. Why? Because to reach that state either you need to multiply by 3 or divide by 2 both of which is not a part of move. So what we can do is treat every element as starting element once and try generating the sequence from elements available. If all the elements are used you can just print that sequence.
This can be done by thinking of an array as a directed acyclic graph, and do a topological sort.
No need for directed graph...just make undirected edges and start from any end that fits into any one of given two operation.
Thanks, antipr000. I got it.
Can you check out the link I shared? There is a formula given to get the count of all cycles. Is it correct?
No, take the graph
4 6 1 2 2 3 3 4 4 1 1 3 2 4
Number of edges = 6. Number of vertices = 4. Number of connected components = 1. 6-4+1=3, but the answer is 2 because there is only one connected component and it isn't a cycle.
it has defined cycle differently not the traditional cycle we know of. See the examples and diagrams.
Задачи на контесте тестировались на полном наборе тестов , или только на претестах?
Полный, но еще взломать могут.
was this contest rated as written in the blog ?! "Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you." I didn't see any rating for the problems.
Ratings will be changed after whet Open Hacks Phase ends (in 12 hours approx)
Thnx vovuh for your efforts in making harder pretests. Really Appreciate it ! :-)
The round was good! Even though problems were easier quality remained high. It kind of reminds me of Atcoder Beginner Contests.
Angel.Yan (rank 578)'s submissions and __beyond (rank 581)'s submissions are almost the same (the differences are libraries, useless fors, spaces, blank lines). I believe they are cheating. Correct me if I'm wrong. vovuh
problem C ;
Output Print any integer number x from range [ 1 ; 10 9 ] such that exactly k elements of given sequence is less or equal than x . If there is no such x , print "-1" (without quotes).
equal to not equal than
vovuh
Thanks, but next time please send it via private message.
I can just delete the comment if you want !
Not necessary =)
Can anyone please explain why this submission got TLE while this one got AC ? I just changed the language from Java to C++. There was no I/O issue as well. I was clueless about my solution getting TLE and then in just hit and trial I converted it to C++ and it got accepted. :(
vovuh explained here: http://codeforces.me/blog/entry/59281?#comment-428862
"6-th test is anti-qsort test especially for Java solutions. Replace int with Integer and it will be ok."
Oh! Okay. But when it says specially for Java solutions, isn't it a bit unfair? Anyway, Thanks for the contest Vovuh ! :)
If I didn't add this test, somebody else would. So it's fair i think
Okay, got it vovuh . Thanks for the Contest !
Is it possible to solve problem E using disjoint set union?
my idea, maybe wrong.
UPD: solution 2
In fact, we are to check, if after each edge deletion, component becomes tree.
However, this solution is very complicated.
Simpler ones:
component is good if each node touches 2 edges
component is good if it contains k nodes and k edges (sorry, it turned out to be wrong)
"2. component is good if it contains k nodes and k edges"
Actually, this approach is incorrect as this is not a cycle component.
I tried this problem using disjoint set union. If I find a cycle, I checked if the degrees of the nodes having this edge is 1. If they aren't 1, that means that connected component is no longer a valid cycle. If they aren't in the same connnected component, then I check if any of them were part of a cycle. If they were, then I change that value to 0, signifying that the corresponding cycle is no longer a cycle. Can someone tell me what I'm missing here? I got a Wrong Answer on test case 18.
Мне одному кажется, что в начале каждого раунда несколько тысяч одномоментно пытаются получить условия, и CodeForces падает из-за этого? (я не могу придумать иных причин, т.к. остальное время КФ работает быстро).
Зря сделали див-3 раунды с открытыми взломами. Каждый контест будут всякие антиквиксорты во взломах, а это явно не то, что хочется видеть див-3-участникам.
Вроде не зря.
Если их на qsort взломают, пока они в div 3, они это увидят, запомнят и такое больше не повторится. Вреда это особо не принесёт, так как у них не такой большой рейтинг, чтобы о нем беспокоиться. Но если они сейчас не поймут, что qsort — штука опасная, то они могут на нем проколоться в будущем, когда это будет более болезненно.
Look at what Tlalafuda__Tlalafu does in hacks section (for problem B). He specifically wrote several solutions with this kind of code
if (n == 3 && t == "LOL") { cout << "MEM"; return 0; }And then he hacks himself several times.
Is this kind of behaviour legal in codeforces?
Why can't I hack solutions on C++17? The system gave me an "Unexpected verdict" several times on different solutions. Please rejudge all the hacks with this verdict, it is very important.
UPD: I can't even hack my own solutions which aren't on C++17. What's wrong, Codeforces?
Could you please explain the test you used to hack so many F solutions? I tried to find something in common in the solutions you hacked but failed to see the pattern. Your test seems to be tricky.
Div 3 noobs like me didn't know that using unordered_map makes the solution O(N^2).
http://codeforces.me/blog/entry/44731
So, this was an "anti-hash" test against STL's unordered_map... I'm new to Educational Rounds so I didn't think people actually use dirty tricks like anti-hash and anti-quicksort. I don't get why people do this but this broke all solutions with unordered_map instead of map. Well, learned something new, won't be using unordered_map on contests next time :)
I believe this hack does not necessarily mean that you should not use unoredered_map at all.
The thing is, the standard hash function which accepts integer values does nothing, it just returns the same number it accepts, so there is no problem with hashing itself.
The problem is solely with buckets count, because in a hash table there is a remainder operation "key % buckets_count" and in case if you take a lot of numbers with the same remainder, unordered_map will work slowly.
However, if you use it and call reserve(10000000) in the beginning, you will fix the amount of buckets to be over 10 millions and the hack simply would not work anymore. The maximum time conplexity will not be more than 100n, which is enought to pass 1 second time restriction.
Correct me if I am wrong.
This wasn't exactly what I meant, but I agree that reserve() will work for F. The problem is that this workaround will only work for this particular problem because of the 10^9 restriction. Given less tight bound (10^18) it will still fail.
And with 12-hours open tests you can even generate counter test for any particular hash function from universal family (not necessarily identity) and any particular buckets_count. The only way to protect against this attacks seems to be random sampling of hash function from universal family with good source of entropy.
The point was — why do you even need to bother about such details on a contest if you can just use map instead? It might be a bit slower but at least it has worst-case guarantees and it allows you to focus on a problem itself.
Problem solving is fun. I don't think it's fun to protect against hashmap-attacks.
I see, I would myself prefer map container to make sure my solution will work.
I was just too disapointed by the fact that a programming contest makes us choose the structure which 10 times faster in 0.0001% cases and 10 times slower in 99.9999% cases, that is why I tried to figure out the way how to use unordered_map and remain unhacked.
Anyways, codeforces is not only about good ideas of solutions, it also requires us to know the low level of how c++ works, it is just as it is.
I think it's because some of the author/tester solution fail on the same test.
Testers' solutions receive time limit exceed, because of this your hack gave an "Unexpected verdict". I hope I have fixed it now. Sorry for long delay.
Will there be any tutorial for this round??
It's already posted, here
i passed all of the problems!! yayyy
When will system testing start?
Yeh same question,i wonder how can i know when the sys test will start ? the contest just said "Finished"
When will the ratings be updated?
Pls, somebody explain, how my solution http://codeforces.me/contest/977/submission/37965169 for Problem F was hacked. But when i changed "unordered_map" to "map" it got accepted. It seems realy strange to me
Afaik Unordered_map is slower than normal map.
That'_s not true. unordered_map is getting slower when many hash collision happens. Otherwise, unordered_map is much faster than normal map.
unordered_map is based on Hash table. Normally a search operation of hash table works in amortized(1) but worst is O(N) (caused by hash-collision). std::map, on the other hand, is based on red-black tree, which has O(logN) complexity in search operation on average. Your solution was hacked by anti-hash test.
Why unrated participants get rated in this round?
You said that they need to do at least 2 Div.2 contest and solve at least 1 problem to get rated
Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.So although unrated participants are not trusted, they are still rated.But why they but them in a separate room?
Can anyone tell me what's wrong with my F approach? 37990081
You ignored MAP[A[i]] that was originally stored.
test : 9 10 11 12 8 9 10 11 10 11
ans = 4 yours = 3
Oh.. i thought map in c++ overrides values that exists already just like in Java
Yes, so change your "//m.insert(mp(a[i], m[a[i] — 1] + 1));" to "m[a[i]]=max(m[a[i]],m[a[i]-1]+1);", and this is the AC code which has a little change from your code
Yes, i got AC, thank you ;)
Thought C++ maps work as Java maps where you just use map.put(v1, map.get(v1 — 1) + 1) and it overrides v1 value if exists
How about the ratting changes? Can a people get the same ratting changes if he got the same place(among rated people) in div 2 and div 3 contests?
It's a wonderful effort for beginners like us to learn and improve !
It grow the internal effort of beginner programme,make hope to became a good programmer, I like it
You might also would like to take a look at the incredible achievement of Tlalafuda__Tlalafu, who made 10 wrong submissions for problem B and found bugs in all of them!
Думаю, что вам также будет интересно увидеть невероятный успех Tlalafuda__Tlalafu, который не поленился отправить 10 неверных решений по задаче B, а после этого смог обнаружить баги в каждом из них!
He just hardcoded a wrong output for some random input 10 times... is this sarcasm?
is no one here concern about rating inflation? In a normal div2 round, it seems like there's usually about 100 users who will be promoted to expert and some of the expert will drop, but this round, there seems to be about 250 promoted with 0 expert demoted.