Всем привет!
В 20.07.2019 18:35 (Московское время) состоится Codeforces Global Round 4.
Это четвертый раунд из серии Codeforces Global Rounds, которая проводится при поддержке XTX Markets. В раундах могут участвовать все, рейтинг тоже будет пересчитан для всех.
У вас будет 150 минут на решение 8 задач. Разбалловка 500-750-1250-1750-2000-(1500+1500)+3250+4000.
Призы в этом раунде:
- 30 лучших участников получат футболки.
- 20 футболок будут разыграны случайным образом среди участников с 31-го по 500-е место.
Призы в серии из 6 раундов в 2019 году:
- За каждый раунд лучшим 100 участникам начисляются баллы согласно таблице.
- Итоговый результат участника равны сумме баллов для четырех лучших выступлений этого участника.
- Лучшие 20 участников по итоговым результатам получают толстовки и сертификаты с указанием места.
Задачи раунда разработаны мной.
Я хочу поблагодарить:
- arsijo за координирование раунда,
- 300iq, Aleks5d, arsijo, Ashishgup, Jeel_Vaishnav, Khairy, ksun48, cdkrot, Learner99, Noam527, stanislav.bezkorovainyi, TonySnark, Um_nik за тестирование задач,
- MikeMirzayanov за Codeforces и Polygon,
- Pretest за то, что они достаточно сильные, TLE за то, что они достаточно щедрые, system_test за то, что оно достаточно быстрое и Editorial за то, что они будут готовы сразу после контеста.
UPD: Раунд закончен. Надеюсь, что вам задачи понравились! Прошу прощения за проблему с задачей Е.
UPD2: Разбор
UPD3: Поздравляем:
UPD4: Результаты после четырех раундов.
What about _kernel_? He has feelings too
_kernel_ should be thanked for not participating in the contest
RuntimeError will be sad if he isn't referred.
DoNtTellHimWhatToDo
Pretests_Passed, YaAAbu, SuccessfulHackingAttempt and FailedSystemTest can also hold sway the contest. And MemoryLimitExceeded, we should not forget. :)
Thanks for 300iq, that we dont have.
And, of course, Accepted_ as a welcome guest of any contest
Maybe should be accepted?
And, wish that wrong_answer stays away
That's _Wrong_Answer
In fact, both of them.
Add moonpieXXIV to them..
Sounds great!But hope for no reading comprehension problems....
An old comment from the setter of the contest :)
Don't worry, red coders are able to set up contests with easy problems.
flashback of my rounds
Okay, some red coders.
The one "for those who don't want to click" is good for me. I'm so lazy.
You are as lazy as a lazy dynamic segment tree.
what up with your profile pic?
Tourist is coming soon
tourist blesses me!
seems like he will not come
Global Round = div1 + div2 + div3 = div6
[Error] no match for 'operator+' (operand types are 'div.' and 'div.')
Global round = max(div1, div2, div3) = div1; for divisions we use max;
I think that div1 > div2 > div3. My estimation is that div1 + div2 + div3 = div0.9
Let's downvote Errichto to make his contribution lower than Radewoosh
Let's downvote him to make his contribution lower than r_pi.
Why so many people don't like my comment
Why would you want to make contribution of Errichto less? I think his over all effort in helping the community is much higher than anyone else here.
8 problems and just 150 minutes is it enough????
Generally, educational rounds have 7 problems and 120 minutes of time. So comparatively it is enough.
Are you compare the educational with global round ?? educational is for div2 and global round for all division
For div3 also... (you can check contest history)
and for div1 users if you add 2-3 easy problems in contest, it doesn't change anything for them.
Required time for contest depends more on difficulty level than number of questions.
And also this round needs to test the abilities of people range from beginners to masters so it definitely needs to have enough time for all the people to solve the problems.
No, of course not. We need 300 minutes.
Btw, did anyone notice that majk is setting a global round and a local round these days?
Although we are Chinese,we still try to join in every Global Round.
But there isn't a "Codeforces Global Round 1" in your contest history.
he didn’t say he did join, he just said he tries to join
Most rounds is a bit late for Chinese,hope the contest can be earlier,and we won't stay up late and feel sleepy the next day.
I agree with your suggestion. I hope that in the future contests in Codeforces could start earlier, maybe 20:35 or 21:05 UTC+8 will work, so that we don't have to stay up very late and feel sleepy the next day.
Most rounds are a bit early for people like me on the US west coast.
Pretest?
TLE?
Editorial?
accepted?
wrong_answer?NO!
YaAAbu will be upset if none of you are talking about him.
upd?
so every body going to forget " system_test " ,because he is unrated ...(read last line of editorial. )
Without your mention, I even didn't notice.
Global round 3 is good go for global round 4
Wish you a job promotion :-)
Thanks MikeMirzayanov also for updating and adding amazing features in CODEFORCES regularly.
No one is talking about Memory_Limit_Exceeded. That's sad
i hope that will be funny:)
I hope that the meaning of all the problems are easy to understand.
me too
It could be the last contest which is rated for Div.1, and the last big global round before IOI 2019 Azerbaijan.
I hope everyone's good luck, as a participant of IOI 2019.
What is IOI brother?
International olympiad in Informatics
ok thanks.I will google it for more details.
You will get a K-pop band
It's actually a K-pop group not a band.
I have no experience in this subject, stefdasca would be better discussing this than me XD
Anybody prepare an IOI synchronized contest in Codeforces? That will be great.
I wish if there's something similar to this for the last rated round for Div1 before IOI2019.
Hope this will not happen :3
That's bad.
have a good contes :)
What's the meaning of "contes"? I have never learnt a word called "contes".
orz chenxiaoyan
orz tzc_wk
i hope i become yellow after this
What about UKE,OLE,_Wrong_Answer_
hope i InvincibleMario one day
Did anyone notice 'alice' and 'bob' in the blog tags? Be ready for some good game theory problems.
:3 Meanwhile, the problem will be like:
Alice and Bob are walking on a 2d coordinate system...... [Hard Geometry]
They start the game by drawing convex polygon in which the area of it doesn't exceed X squared units and is at least Y squared units, if a player can't draw a convex polygon without crossing an already drawn convex he loses, determine the winning player if both played optimally.
This problem is really easy. Solution:
If the original arena is less than Y, the 2nd player wins. Otherwise the 1st player wins. Just draw a rectangle (or any symmetrical shape) in the middle of the board. One side must be as long as the side of the coordinate system (so it split the coordinate system in 2 sides). The other side can be as low as required. Now the coordinate system is split to 2 equal sides, so the first player just need to copy the second players move ...
Interesting, someone could make various problems by tweaking its details.
By the way, Alice and Bob love graphs more than 2D plane xD
majk come back with a contest after Good Bye 2018
Hope I will be either retired.coder.1 or WHITE2302 . I don't want to be grey anymore.
Why no one has made an account with a nickname "Idleness_limit_exceeded"? :c
maybe the contest doesnt have interactive problems xd
How Global Round's rating distribution executes? Do Div1 and Div2 contestants get seperate rating? How likely Div2 contestants increase rating? Thanks!
TimeLimitExceed and timelimitexceeded will be sad if they shrink to TLE
I think TLE is abbreviation for --> tourist limit exceed please don't gimme negative feedback I am just joking
And MLE is for majk limit exceed (only joking :D)
an AK-king EvenImage
Why arsijo again?
why not ? because of just one mistake he did before ? i'm afraid for you ;
У вас тех полетел
Should I do it? I am new in programming.
[DELETED]
Why would you post this?
Maybe because Round #575 will be a div3 round? They just come off as rude though.
you can do some contests generally -- pratice more. There're so many basic problems for newbies, such as Div2A/B
Everything is gonna be Okay
madhav_1999 will become master today! — Prokhar
yashvardhan29 will become Foobar Elite today!
Could you please postpone the contest 15 minute later ?
And hopefully the round won't become Unrated.
Is there a page with current standings?
I hope that the contest will be good,funny and interesting like the announcement .
gl hf
i have to stay up late
i look like the panda in my photo
When this "prior to round" happen????? Only 15 minutes left......
Added now.
speedforces strikes again again
Now that the round is over, I feel I should comment on that. We considered both D and E to be tricky problems, even some very good testers had problems with them. Perhaps C and D turned out to be a bit easier that anticipaded.
F on the other hand, was a different beast. I originally proposed a completely different problem — with in my opinion a cute observation. However, it was geometry and testers almost went on a riot because of the implementation difficulty.
About $$$10$$$ days before the contest I came up with the problem that is now $$$F1$$$, but the testers saw it as too easy, even easier than D or E — and the gap between $$$F$$$ and $$$G$$$ was afwul.
So I realised then that we can increase $$$m$$$ and it adds to the problem. Suddenly, it was too difficult and it was the gap between E and F that was brutal. With the contest fast approaching and the tester's ranks dwindling, we realised that the safest way to mitigate was to split F.
Some small gap still remained though, but I'd say that the ratio of ACs on adjacent problems around $$$4$$$ is fine (after all, it has to reduce from couple thousand to only a few in around $$$6$$$ problems). Please try to understand that it is sometimes quite difficult to judge the difficulty based on a small sample of testers. Additionally, if you find out two days before contest it is going to be speedforces, the best solution is typically to keep it that way rather than to perform some ninja fixes.
What happened just now? My rank changed from 900+ to 400+ and to 900+ again...
[Edit] Got it.
arsijo curse
Спасибо за хороший раунд) Нет, он хороший не потому что у меня получилось решать задачи, потому что задачи были интересными) Побольше бы таких раундов
i am suffering subsequence string phobia.
" The round is still rated. " ?????? What the f**k ??????
My friend locked his problem E but he can't change his code after rejudged and already lost his rating
You seem to care a lot about your friend! I think HE can ask organizers to make it unrated just for him.
Why unrated after rejudged? I can't understand.
The round is always UNRATED or at the edge of UNRATED if arsijo is the coordinator.
How to solve G?
Actually, I didn't get pretest passed in this problem, but I have an idea.
Solution 1
You can replace the problem to a new problem as follows by using euler tour method:
To solve this new problem, you can use sqrt decomposition by query.
Let's think about to solve from query $$$1$$$ to $$$B$$$ with $$$O(N + B^2 log B)$$$ complexity.
Since you should process $$$B$$$ queries, The total complexity that takes to calculate all answer in query [$1, B$] is $$$O(N + B^{2}logB)$$$.
So, how to solve in not only query $$$[1, B]$$$, but also $$$[B + 1, 2B]$$$, $$$[2B + 1, 3B]$$$, $$$[3B + 1, 4B]$$$, and so on?
You can find the value of $$$a_i$$$ when query $$$B, 2B, 3B, 4B, ..., $$$ has just finished, by using cumulative sum method. Since the value of $$$b_i$$$ does not change, you can also solve in query $$$[B + 1, 2B]$$$ and so on, as same as query $$$[1, B]$$$.
If the backet size $$$B$$$ is nearly $$$\frac{B^{0.5}}{log_{2}B}$$$, the total complexity will be $$$O(B^{1.5} * sqrt(log_{2}B))$$$.
Solution 2
Since the constraints is $$$n \leq 200,000$$$, $$$q \leq 100,000$$$ and the time limit is 5sec, since the process is very light, I think that even straight-forward brute force $$$O(NQ)$$$ which is very very very very fast may pass.
Solution 2: https://mirror.codeforces.com/contest/1178/submission/57419391. He did again?
How to solve E?
If you consider two first and two last characters of the string, you are able to find one in first two and one in last two that match. Add them to your palindrome.
Hint: Since no two characters are adjacent, and there are only 3 characters in the alphabet, there exists a character in the first two characters of the string that equals a character in the last two characters of the string.
Since no consecutive letters are the same, you can make any even-length palindrome into a longer odd-length palindrome. So let's fix the middle of the palindrome, how about s[n/2]. Then you can show that from the midpoint, you never have to go more than two spaces to the left, or two spaces to the right to find two letters that are the same.
So at worst, it will take 4 spaces to add 2 letters to your palindrome.
Be careful of n=4 case (may need to try other midpoint).
How to solve E
E's solution is cute, although the problem is a little contrived.
EDIT: The key is pigeonhole principle. Take the last two and first two letters, there must be two letters that are equal (and not adjacent, since no two adjacent are the same). Take these two and recurse. If there are fewer than four characters, just take any one.
Can you share your cute solution :)
really kyot solution
i overcomplicated the problem :\
Am I the only one to try solving problem without that "no repeated letters" thing for 15-20 minutes before realizing that problem is totally different?
Just scroll down, I solved it without knowing that.
How? And can you prove your solution?
I can't prove it, but it makes sense.
My solution optimizes the $$$O(N^2)$$$ dp solution using next and before arrays and limiting the search on the first point the answer reaches the needed length.
Good tasks, thanks)
My girl friend is beautiful, smart, kind, rich, humourous and never blame anything on me!
I consider her a perfect girl friend.
Unfortunately, I discover that SHE is actually a man.
That's my point on the checker of the problem E.
Does that make me gay? Oh, man :(
you guy are so funny, hahaha
Not so many Pretest :(
How do you see this? Is it a browser extension?
m2.codeforces.com
No. Just using http://m2.codeforces.com/ :)
Good to know, thanks :)
But they are strong! :)
We had an issue with the problem E. The rejudge changed ~10 AC submission to WA in pretests. Since only ~10 people were involved in this issue, we do not see a reason to make this round unrated. If you have another opinion, you are welcome to share it.
You can make the contest unrated for these 10 participants.
Well, After 1.5 hour I noticed that my ac submission has wa. It's kinda unfair.
Thanks to Pretest XD
I saw you hacked A. Can you tell me please what was the hack for it ?
That would have hacked me because I misread the problem and thought that you can capture the 1 to have a total coalition size of 6, which would enable you to capture the 3s.
Many people misread problem A. ;_;
first four problems were not THAT hard as in previous contests
pretests too strong barely 10 hacks total
Oh, nice problem G, I've seen very similar things only a million times and it always ensured me at least one hour of fun coding and debugging, so happy to be given another chance.
Isn't problem F nice as well? Or I guess all the fun with it was too short for you to feel the excitement?
I would like to thank:
In Problem A, for testcase: 2 6 2
shouldn't the answer be 1 1 as the question mentions "If Alice's party has enough people to create a coalition on her own, she can invite no parties." i got an "unsuccessful hacking verdict" defender's output was: 2 1 2
2 1 2 is also correct. You don't have to minimize number of parties.
Yes but as i said the question mentions "If Alice's party has enough people to create a coalition on her own, she can invite no parties."
"She can invite no parties", not "she cannot invite parties".
To be fair, I understand the confusion now. English is ambiguous sometimes.
oh damn. need to take english lessons now...
I feel that mate. I got that twice
Both outputs are correct. Multiple solutions possible.
That's a good point, my solution also gives "2 1 2" but it passed system test... Maybe the intended meaning of "she can invite no parties" is "it is allowed that she doesn't invite any parties".
FML, I solved E for general strings
UPD: got TLE
Take this one: aabbcc
Answer is IMPOSSIBLE
Fine... I forgot this impossible thing.
please enlighten us with the solution!
I explained it here.
The link seems to be not correct.
Just little FYI from a noob coder if anyone doesn't know already..."str = str + xyz" takes waayyyyyy too much time compared to "str.push_back(xyz)"... got to learn that the hard way today :(
Well at least learned something :D
You can also do the following: str += xyz
str += something in strings is much faster than str = str + something for C++
Well, += just adds to the end of the string (I assume that it just push_backs), while str = str + xyz has to copy the whole string, then append, and then save that value in the original variable.
Thanks! Noted.
Another noob coder here... took me three TLEs to realize the thing.
Imo score distribution wasn't good enough (maybe it's just for me). I spent 1:30 for B, 0:15 for C and 0:30 for D.
Just look at this submission: 57419391
Brute force wins again!
It should fail on systests. The time is about 7s in the worst case.
But it passed! You actually win!
Long live brute force! (doge
The systests were too weak. Now it's hacked.
Was it hacked before the end of the contest? Because my understanding was that uphacking doesn't change official standings
No. Although the standings changed, maybe the original standings which is used for rating calculation will not change.
MikeMirzayanov kuviman fyi
https://mirror.codeforces.com/blog/entry/68538?#comment-528759
It passed!
They should hire you as a tester.
Every time I finished the code dugging, the game had just ended. What a pity！
I hope that I will find the bug more quickly next time.
You can optimize your wish by hoping to not make a bug next time
I only now noticed abs in G. Can't even read :(
What is the reason for the low constraint at problem D? It could be solved even with $$$10^6$$$ limit
That would be a huge spoiler to the solution (what number of edges can be linear to the number of vertexes).
Exactly. Also, the time complexity wasn't supposed to be critical in this problem.
I guess the $$$10^3$$$ is for people to easily test if their solution is correct in $$$O(n^2)$$$ time, coz it's not easy to prove that it works.
How can I output my graph with $$$10^{12}$$$ edges in that case?
Nohow? You'll get TLE in that case. And it's your problem, not autors
fast io
maybe super fast io
You should try bitsets, I heard they're pretty fast
So that users like me can go wrong , and find primes( degrees) using Goldbach conj. and stuck there.
In problem E, will there ever be a case where answer is IMPOSSIBLE?
No.
No, you will always be able to generate a subsequence. Since if you try to find a character from the first two characters and last two characters of the string and reduce the string to str[2:-2] everytime, you will see that you have to choose one character which is equal in 4 characters (two from the beginning and two from the end).
Since there are only 3 possible characters such that no two of them are consecutive and 4 possible places to choose from, there will always be a character which you can include two times from a group of 4 characters. Hence you will always be able to make the string.
I think some people just guested problem C after seing samples
Right. No idea why it's true xd.
Call the vertical segment white if it's white from the left/black from the right. Note that if segment is white then all others in the same row also white. Same for horizontal
4 choices for top-left square. Two choices for the rest along the top and the left. Only 1 choice for the remaining squares. i.e. if you choose the top row and the left column every other square is forced to be a single orientation.
Problem C has best samples ever
It would have been better if only one test case w=2 and h=2 was given. Then most of them who solved it just by test case would have to think of proof(including me lol).
E has got three greedy tags and two string tags...
It it just me, or prob.A's statement is TOO HARD to read? (you can check my submissions)
I'm not familiar with the Parliamentary System in some western countries :(
ovvo
In D, If n is prime, then the answer is a circular graph. Otherwise, create a circular graph at first and then create extra edges by connecting nodes with degree 2 to make the number of edges a prime number.
Is this the only solution?
Problem G can be solved using sqrt decomposition. In the contest I chose a bad block size and didn't get AC. I'm so done right now.
Using dfs order we can turn G in to the following range query problems:
Given 2n number a[1], a[2], a[3], ..., a[n] and b[1], b[2], b[3], ..., b[n]. You have to query max(abs(a[i])*b[i]) for some l<=i<=r and add a positive number x to a[l], a[l+1], ..., a[r]. Note that b[i] is set from the begining.
Now for each i from 1 to n, let w[i] be the sum of x added to a[i], then you have a graph of at most 2 lines representing the value of abs(a[i]+w[i])*b[i]. To get the answer for some query, just get max of all (a[i]+w[i])*b[i].
To update and query fast, split the array in to blocks of size S. For each block you can represent the lines using a Lichao tree or using CHT. I "upsolved" using CHT, but maybe Lichao tree will work as well. For each update query, simply update all the elements from the left most and right most block, and rebuild the two blocks, for all the blocks in between, keep an array w[] to know the elements in the blocks have been added by how much, this take O(Slog(S)+N/S). For each get query, you can just do the same, get the elements from left most and right most block, query each of the inbetween block in O(log(S)), so this take O(S+N/S*log(S)). Also this approach can be used even if you want to add negative number to a[].
Honestly I didn't think this would pass, and I hoped that it gets TLE. But it works, and I chose the wrong S, so I got TLE in the contest. This disappointed me very much on top of the also very dumb mistake I got in F2. Still the problems are very good. Codeforces rules are very punishing, so something like this is to be expected.
For anyone interested in implementing this approach, S=100, 200, 300, even 400 will get AC. Just don't be bad like me and use 500 or something.
Yeah, that sucks. I tried hard to cut the solutions with extra log factor — we had two such solutions and they all needed around 8 seconds on some cases.
On the other side of the road, there was Java that also needed to pass.
Needs more coke spilling
I was able to complete 4 questions in this challenge. I usually use ideone for compilation of my code . My code was copied by newbi/57387826, sos_123/57387881 . I was removed from this contest.This is quite unfair and strict actions should be taken against these contestants
As stated in codeforces rules about third party code
unintentional leakage is also a violationso be careful next time.I checked the submissions you mentioned. Both of them submitted the code before you.
I didn't register for the competition so I had a late penality of 10 minutes . I had compiled it way before submitting it . You can look in both of their profiles lots of there submissions are skipped .
Yes, I have seen it. Their all solutions are skipped in all contests.
Could anyone explain why my submissions still at Pretest Passed? I solved 3 problems but my rating has been counted as 0 problems.
majk:
Also majk:
Well ...
When t-shirt winners will announced?
We are still investigating the issue. We will post the winners after we get the official results of the round.
Thanks checker for good check.
MikeMirzayanov, это теги в задаче G. Наверное надо пофиксить.
what is wrong in this solution of problem E.
Can anyone prove this statement, for every n such that there is a prime between n and 3n/2?
https://en.m.wikipedia.org/wiki/Bertrand%27s_postulate — Here in "Generalisations" you can find statement that there exists a prime between 2n and 3n. There is also link to proof: http://www.m-hikari.com/ijcms-password/ijcms-password13-16-2006/elbachraouiIJCMS13-16-2006.pdf
thanks!!
T-shirt winners!
We used these files to find the winners.
file:///C:/Documents%20and%20Settings/Admin/Рабочий%20стол/Vardan/79194b70160be0e5f80b14b8ee236678.jpg
https://i.imgflip.com/35wj2n.jpg
Problem C: https://gurmeet.net/puzzles/truchet-tilings/index.html