Всем привет!
Скоро состоится Codeforces Global Round 6, время начала: 17.12.2019 18:05 (Московское время).
Это шестой раунд из серии Codeforces Global Rounds, которая проводится при поддержке XTX Markets. В раундах могут участвовать все, рейтинг тоже будет пересчитан для всех.
Соревнование продлится 2 часа 30 минут, вас ожидает 8 задач, при этом одна из задач будет представлена в двух версиях. Разбалловка 500-750-1250-1750-2000-2500-3500-4000.
Призы в этом раунде:
- 30 лучших участников получат футболки.
- 20 футболок будут разыграны случайным образом среди участников с 31-го по 500-е место.
Призы в серии из 6 раундов в 2019 году (текущие результаты):
- За каждый раунд лучшим 100 участникам начисляются баллы согласно таблице.
- Итоговый результат участника равны сумме баллов для четырех лучших выступлений этого участника.
- Лучшие 20 участников по итоговым результатам получают толстовки и сертификаты с указанием места.
Задачи этого раунда придуманы и подготовлены мной. После раунда я буду доступен в Discord для обсуждения задач.
Я благодарю следующим людям:
- XTX за поддержку этой серии раундов,
- BledDest и isaf27 за помощь по координации раунда,
- darnley, dacin21, craborac, nk.karpov, Roms, defolaut за тестирование раунда (надеюсь, будут еще тестеры),
- MikeMirzayanov за Codeforces и Polygon.
Присоединяйтесь!
UPDATE: Раунд окончен! Надеюсь, что он вам понравился, несмотря на то, что последние задачи оказались сложнее, чем мы думали. Системное тестирование скоро начнется.
UPDATE 2: Разбор
UPDATE 3: Поздравляем победителей:
I am always waiting for such a DIV1 + DIV2 round :)
Div2 ppl — Let's rank up above some div1 guys.
Div1 ppl — Let's not get outperformed by some underdogs.
(Few days after reaching Div. 1 xD)
More like, "Few days after reaching (Div. 1 + Div. 2)/2 xD".
Hoping to see a colour change.
anupamshah_ ?
Hopefully not this one .
how you changed colour?
I bursted into laughing when I read this reply.
How have you been on Codeforces for 18 months ad still have no idea how he changed colors.
¬_¬
Once upon a time there were instant editorials after the end of contests.
Then you'll be happy to hear that it is already written.
Can you share the links?
The SHA1 sum of the editorial to F is cc9919706a5a693e08430f184db20200b614dc00.
I hope that you'll upload more than just SHA1 sums after the contest.
He asked for a link. You should've posted something like this.
I don't know why I hovered to read the URL and THEN clicked.
Preemptively reading what you're clicking at is survival instinct. Clicking anyway is poor survival instinct. In retrospect, I could've added .onion at the end.
atulyakv
thanks for the editorial!
Im always waiting for it before and after the contest :)
You know what is better? Editorial before the round happens.
lol
Can some red coder suggest how a person (not very good at maths) can reach that level?
I_love_Tanya_Romanova had posted some great answers on Quora regarding that, you may wanna refer them :)
Can you please share the link of that answer?
Well he has posted a lot of answers, here are some of those and although I don't really follow him but some of my friends do, and have really seen nice improvements.
1 2 3 4 5
Hope it helps :)
Nightmare05 now I know why you were asking....
See here
what a coincidence?
You here asking how to be red and in problem set problem is based on same topic.
Maybe they have written the statement because of my comment :)
It was a coincidence, I came up with the story on Sunday, couple hours before your post.
And alsi problem are based on math because you have wirtten "not very good on math". :3
But d and e related to data structure and I love problem on data structure ❤❤
Я думаю это будет крутой Раунд :) Помню прошлые и надеюсь что этот будет еще лучше) PS: И сложнее))
Me Everytime
I always make strong pretests.
Also, I never seen this Codeforces Round 470 (rated, Div. 1, based on VK Cup 2018 Round 1) before, officer.
Kheili strong bood koskesh kioooni
|:
Alan test 11 soal E pashm ame mane?
Anyone noticed the blog tag “Alice” and “Bob”?
Sounds like there'll be game theory problems
Sounds like majk always creates problems about them
This round for disha :- my high school crush Hoping to get better rating
Missed 2 of them because of my final exams. Tomorrow I have my finals in algorithm design. This time, to skip this contest would be to not study. Therefore I must do the contest, of course, only because I want to study.
So we have tourist and wxhtxdy both registered for the round, it will be fun stalking the standings page.
Why can't comments be sent in Chinese?
Oh shit goddamn grey Indians who love maths disliked my comment and made my contribution < 0
hope to see dark blue in the profile today.
disagree
not in your profile brother
yep, i am just king of humor
disagree
agree
Hope that I will get rank in 3 digits.
А когда объявят разбалловку задач?
Distribution ?
Well done, majk did everything for after-contest.
attending university classes makes my iq lower by 20 but I will try
atulyakv
Speedforces!!
You forgot to include Mathforces XD
Комментарий удален по причине нарушения правил Codeforces
What was the solution to problem E, although I got a AC, I still feel that a lot of solutions will fail systest including mine.
E is easier than D...
Calculate the loss and profit of each person.
Assign the money from the ones in loss to the ones in profit one by one.
What is pretest 2 of B?
If the remainder of x%14 is zero the answer should be "NO".
I found my bug, thank you all the same
xi <= 6 && xi >= 1. For this case answer should be NO.
You meant remainder wrt 14 right?.
Actually I was talking about specific case when xi is straight between 1 to 6 (not after modulo). In that case my initial code was giving YES, but the actual answer is NO. And that is what I think is the second pretest.
How to solve D?
Look up Splitwise
god damn it I needed 2 more minutes to submit C
nvm
Could you guys show me some hints for D? <3
Calculate the loss and profit of every person. Now you have an array with positive and negative numbers. Store them in two separate vectors 'take' & 'give'.
Assign the money from the vectors 'give' to 'take' element by element greedily.
My attempt for 1266D - Decreasing Debts is similar to yours, but I had one question.
I'm sorting the vectors of givers and takers by their amount , but i noticed that my solution gets accepted even if i don't sort them.
Isn't it a necessary condition to sort the vectors?
https://codeforces.me/contest/1266/submission/67138128
It isn't necessary. The idea is if A has to give x to B and B has to give x to C. If not simplified, this 'x' is counted twice. After simplifying , it yields , A -> C 'x'. The issue here was that B who overall, does not want the money is being given the money and money is being taken from B. But, since in the two arrays you have formed , you are only creating transactions that will never be nullified by some other transaction, all transactions are valid. Sorting is therefore unnecessary.
Thanks I got it now
Can you explain it further why there is no need of sorting? Thanks in advance
A simple case to think can be, suppose
A has to give 10 to B. C has to give 5 to D.
How does sorting help?
Yeah, I got the point.
One more question:- If we want minimum number of transactions, we should go with sorting, right?
Thanks
Problem D --> Splitwise Algorithm Was easily available on internet. This is sad lol.
50 minutes of debugging for a frickin number of line in output for problem D. at least i found out the mistake last sec.
How to solve B in cpp?
Does anyone have a test case for problem E that will fail the basic solution?
The reason for so many fails on test case 11 is the handling of the order of events. If you kept track of number of bonuses to a resource, there is a possibility of adding and subtracting the same resource in a single query i.e., a bonus (a,b,c) just ends up replacing the exact same. Only if I had swapped 2 lines...
Am I the only one who treated D as a graph problem and keep finding patterns?
I related it to a graph and GCD problem...
Me too, it could be simple greedy solution but made it mess by including graph theory
Can you explain, how to solve it greedy please?
Yup, tried solutions involving moving all children to a parent node (Not even going to start with how I was trying to make it a DAG to root it in the first place) and all sorts of other absurd stuff treating it as a graph problem.
me too i was trying to do something with weighted directed graphs . you are not the only one.
Can someone explain me how to solve D with realisation moments. I've got, that if we have edges like a -> b; b -> c, we can make them a -> c and remove a -> b and b -> c.But how to code it?
Look at my comment above. Now I know I'm not the only one.
Easily available on internet. "Splitwise algorithm" or "Minimize cash flow between friends".
I am so unlucky problem C i solved in last minute when i was submitting my solution 10 sec was left but unfortunately i failed. Feeling unhappy.
How to solve D?
https://codeforces.me/contest/1266/submission/67110424 Can someone tell at what test case my code is failing for D. I tried many, all succeeded, but it gives WA in pretest 5
Out of curiosity — how many people proved their solutions of D and E?
out of curiosity — how do you expect someone to answer the exact number of how many people proved?
Also IMO problem D is easily proved, but E is indeed the type of problem that many participants submit the correct solution without proper proof.
You know what the fuck I mean :D
Out of curiosity — why did you think he was asking about the exact number?
he asked "how many". But even an approximation would be too hard to get, so his question is somewhat pointless.
I did, I guess that's why I'm so slow. :(
I had a proof outline of E in my mind, just that if we produce the obvious minima, there's always a reached bonus because equal sums and proof by contradiction, and if we imagine that this reached bonus isn't a bonus but a normally produced resource, the same idea applies by induction. At that point, I told myself that I have nothing to lose by believing I didn't miss something important.
D is just obvious. We have the minimum required cash flow and we can send this flow any way we want.
I did
I couldn't prove D or E , I was just lucky that my solutions passed as I had no concrete proof. Had any one failed, I would have no idea what to do. Though, D was close to a proof, in the sense that if some subset of people is losing some amount and others are gaining that much(in terms of net amount) then that amount of edges must be there and it turns out we can attain that lower bound precisely, making it the best
Come on Whatsapp if u r interested in proofs
Are the tests weak for E or this testcase isn't possible? ~~~~~ 3 1 1 1 3 1 1 2 2 1 3 3 1 1 ~~~~~
You can't get awards for reaching the goals.
Ow, Tnx
How to solve C for r,c >= 2 ?
Well, consider two things :
1 can never appear in the square. (Why?)
A row which makes gcd as 1, can be multiplied by x to get a gcd of x.
Now think of some numbers which make gcd 1 :), and you're almost done
Thanks.
1) if we take 1 , then it will make gcd in 1 row and 1 col as 1, so we will have 2 ones in our b array
2)about that I thought , may be I will do like this for ex. for 4 9 2 3 5 7 9 11 13 15 17 4 12 20 28 36 44 52 60 68 6 18 30 42 54 66 78 90 102 8 24 40 56 72 88 104 120 136
I don't know why doesn't it work
Well, how about choosing consecutive numbers rather than all odds and one 2? Maybe since you're skipping out some even numbers, if you could have just chosen them also, you might have gotten a lower answer?
This comment explains it the best
D was easy to google -> https://www.geeksforgeeks.org/minimize-cash-flow-among-given-set-friends-borrowed-money/?fbclid=IwAR1AYYIT1ldzxihOOCJNBhA14IzoWkhjasSfsQyMh4Y4iufSunz7qfQNsqo
This is N^2 but same logic can be easily implemented in nlogn
https://codeforces.me/gym/100812 problem A
It was really difficult round :( Grandmaster for 3 days (P.S. D was quite interesting, though)
Hello, dear majk, it seems to me that you would be good at doing olympiads for mathematicians!
And not for programmers...
Oh shit goddamn grey Indians who love maths disliked my comment and made my contribution < 0
The ability to speak does not make you intelligent.
I did it from 10 fake accounts.
PROBLEM D: just find out balance for each person: for each line of input:
balance is negative : he must give money
balance is positive : he must take money
every giver returning money to taker eliminates one giver or taker. no need to sort.
67119475
Greedy $$$\mathcal{O}(m^2)$$$ solution for D passed the system tests but failed to this test:
This is sad because I have similar solution which got TL5.
D is neat because it both is a real life problem and can be solved with a real life approach.
E is however weird. It just feels like you just do what it tells you to do.
Hi everyone, here is the list of T-shirt winners!
Thanks :)
It's me!!!!
This is sth I never thought!!!
You can't even image how excited I'm!!! Right now!!!
Because I have never won a prize in cf before, so I want to knwo how can I get it??
thanks a lot!!
It's me too, I think i can imagine how excited you are because this is the first time i won a prize in codeforces, too. I have the same question as you: how can i get it.
Our team will contact you. Just wait.
Any news? Can't wait to get my first CF t-shirt :)
No worries, you will get it very soon!
eatmore, can you explain your approach on H? It's different from my solution, and I only managed to hack it via massaging the stress test.
My solution is using simulation with memoization. I don't know its time complexity. My implementation can probably be optimized, but I didn't have time to do it during the contest.
It works like this: there is a map, where the key is the current vertex and the current state of some set of vertices. The set is such that, starting from the current state, the token will enter each vertex in the set at least once before entering a vertex that is not in the set. The value is the vertex that is reached and the new state.
This approach should work really well on structured graphs, like red edge from $$$i$$$ to $$$1$$$ and blue edge from $$$i$$$ to $$$i+1$$$ for all $$$i$$$.
I think that my solution can be adapted to solve your bonus problem as well.
Div1+Div2 rounds are always fun to give <3
yeah!!! these sure are fun :)
1266B - Dice Tower teaches me that i need to read problem's statement carefully.
If someone wants to feel some pain.
My Solution to E in the contest at the very last minute Submission.
Later, when I found the bug. Submission
weeps :(
Why can't comments be sent in Chinese?
because it's codeforces and not 程式设计forces
The reason is not enough
Lol, it's definitely not Кодforces ether.
congrats neal !!!
Thanks! Finally made it.
why my dp solution get Wrong answer for problem A.
here https://codeforces.me/contest/1266/submission/67097431