Привет, Codeforces!
В 16.09.2018 13:35 (Московское время) состоится Codeforces Round #509 для участников из второго дивизиона. Участникам раунда будет предложено 6 задач и 2 часа на их решение. Обратите внимание на необычное время начала раунда.
Раунд будет рейтинговый для участников второго дивизиона (с рейтингом менее 2100). Условия будут доступны как на русском, так и на английском языках.
Раунд начнется через 2 часа после начала квалификационного этапа и закончится с ним в одно и тоже время. Поэтому мы просим участников квалификационного этапа не распространять задачи до начала раунда. К сожалению, все задачи не поместятся в стандартный Div. 2 раунд, поэтому мы выбрали шесть из них.
Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Иван BledDest Андросов и Александр fcspartakm Фролов.
Благодарим MikeMirzayanov за возможность провести зеркало квалификационного этапа и за платформы Codeforces и Polygon, Антона arsijo Цыпко за помощь в подготовке раунда, а также IlyaLos, Perforator, kuviman, HolkinPV, MaxZubec, stanislav.bezkorovainyi, Karasick за тестирование.
Как обычно, разбалловка будет объявлена ближе к началу раунда.
UPD: Разбалловка: 500-1000-1500-2000-2500-3000
UPD2: Разбор
After 9 days, wait is over.
Так а можно было бы два раунда провести, не?
боюсь, что сложность задач квалификации не позволит.
Лучше б сделали контест со всеми задачами, как в прошлом году.
Вот это стадо...
Early tomorrow morning there is also the Qualification Stage of Singapore (mirror available on Kattis).
Looks like the ICPC preparation is underway simultaneously all over the world :D
How to solve D and E?
My soln for D —
You can refer here (Question is a bit similar to this) to find all cycles in D.
One observation — if there exist 2 edges of a vertex which leads it to 0 then this vertex belongs to the soln set => vertex belongs to cycle.
Now all cycles which have zero as vertex belongs to the soln set. And If at least one vertex of cycle belongs to soln set then all vertex belongs to the soln set. So dfs2 was made to find soln set which marks all cycles which belong to soln set. And then runs dfs2 for all vertex of this set.
Another approach for D that I found after contest time (should give some credits to my friend tantam75 for some ideas within it, not sure if this was his exact approach coz' I didn't fully manage to get his words :D).
A junction can be considered safe if there are at least 2 paths from junction 0 to it (obviously, junction 0 is a safe junction itself).
Therefore, I'll transform the given undirected graph to a directed graph (each bidirectional edge will be considered as 2 edges between two junctions, just with different directions).
With this new graph created, I'll perform 2 separate DFS traverse, both started from 0:
The first traverse will give me a directed subgraph (consisting of directed edges) that allow me to reach every junction from junction 0 (yet not the other way around). After that traverse being complete, I'll delete that whole subgraph.
The second traverse will let me know if each junction is safe (i.e. there exists another path from 0 to that junction, after deleting the first path given in the previous subgraph).
The subgraph deletion can be handled easily if adjacency list of each junction is maintained by a set instead of vector/array.
I think this approach will fail on following test case. 3 3 0 1 0 2 1 2
Because deleting a subgraph will delete 2 of 3 edges. And based on which 2 edges are deleted remaining graph will have 0 or 0,1 or 0,2 as an answer.
But in fact, all 3 vertexes are in soln set.
Actually, I should apology for my explanation being a bit vague.
The subgraph being deleted is a directed one, that means I'll only delete the edges that can lead from junction 0 to other junctions (but not the other way around).
Therefore, after 1st DFS, directed edges (0 → 1), (1 → 2) will be deleted.
The second DFS can still reach all other junctions (one possible path is 0 → 2 → 1).
(Explanation edited in the main comment as well).
How to solve C, E ??
My idea for E: binary search + flow
You can binary search the answer: with each value z, build a bipartite graph that, there exists a edge between (xi, yj) if aij ≥ z. z can be the minimum value of a combination if the maximum bipartite matching of the newly built graph equals exactly N — this could be solved by maxflow algorithms.
(I didn't solve it during contest time, just knew the idea, but couldn't implement maximum bipartite matchings properly :-P)
You can solve C using dynamic programming. First observation: after building N characters, we can uniquely determine the last N characters.
So let's dp(i, j, k) be the number of ways, we are at i-th character, already at j-th character of string s from prefix and at k-th character of string s from suffix.
Then answer will be sum of dp(n, j, k) where j >= k.
Solution for E: first we binary search the answer, let's assume we are at mid, build a network flow, add an edge with capacity equal to 1 from source to every row, add an edge with capacity equal to 1 from every column to sink, then for each row and each column (assume it's i-th row and j-th column), if aij >= mid then we add edge from row i to column j with capacity equal to 1. Then if maximum flow equal to size of board then l = mid + 1, else r = mid
i don't understand this line properly. "The round will start 2 hours after the start of the Qualification Stage, so they will finish around same time." can you please explain it in details?
It means that Quals is the 4-hour length contest
when i can start? from the qualification stage?
You can start tomorrow on 13:35 (moscow time) at cf round
it is rated for div2.
I have 1900+ rating.
Is it rated for me or not?
It is rated for Div2. My rating is 1900+ is it rated for me?
Yes
Perfect time for Chinese users!
You are right!
thanks for Codeforces!
the begin time is so good!
I'm Chinese too. The time is really wonderful!
Wonderful time!Thanks for codeforces!
Wow! It's wonderful. And I hope that the description of the problems will concise
After the Contest:
………………
I can only make a joke:
"My English is so bad"……
Очень нужно переделать объявления:
В русском несоответствие рейтинговый для второго дивизиона — с рейтингом менее 2100.
В английском просто рейтинговый для второго дивизиона.
В чем истина? Или 1900-2099 это уже Div2?
Это всё еще див1, но для таких людей див2 раунды рейтинговые. Это нововведение появилось вместе с последним крупным обновлением.
It Was So long time.
Roms, are problem statements gonna be long like in NEERC rounds or adapted to CF round?
The statements' format will be as in usual div2 rounds.
Personally speaking, I think that Codeforces is the best oj in the world.
8000+ contestants
Solved 2 problems for the first time
queue
My submission has been staying in queue for 5 minutes, any help ?
I have much more penalty on pC because of the queue, can I have some points back?
Edit: Actually, 40 points won't affect me too much, but I feel sad for those who were actually affected by the delay.
If one is not good at English (such as me) : then :
Is it EnglishForces???
Is it Codespeed???
……
Or maybe... SpeedForce!
……
Result of not thanking KAN XD
Неужели так трудно было написать в условии задачи С, что все значения a_i различны, а не во входных данных? Это было очень легко пропустить☹
Прошу прощения, не подумали, но по-моему, входные данные являются такой же частью условия как и легенда.
why the f I checked my submission after I had locked.....
EnglishForces
What's wrong with this solution for D? 42940213
Test Case 5-
2 1
1 2
3 4
Your output is 3. But the answer is 2. My one attempt failed due to this. :P
This problem set seems to be the most balanced one in recent times on codeforces:D
Btw how to solve F? I could reduce it to finding maximum number of points lying on a straight line in a given set of points,but couldn't use the property that distance between adjacent points(along one co-ordinate) is same.
let assume your picks B and A , and B-A is T;
so in the first line you get A + 2t + 4t + 8t, and in the second line a+t , a+3t ....
you only need find the answer for every t which is power of 2.
because for example picking t=6 is subset of t=2;
I guess you can find an answer of every power of 2 .
Note: for every T you should look at numbers in mod 2t. so increase mapA[a[i]%2t]++ and mapB[(b[i]%2t)]++
so look for the maximum mapA[i] + mapB[i+t];
please consider making it unrated
Test case #6 of problem C? anyone.
test case 5 on problem d ?
I think it is similar to
2 1 1 5 6 10
The answer is 5. Wrong solutions might output 9.
Anyone has idea what pretest 7 for C is?
https://codeforces.com/blog/entry/61876
this says editorial posted 3 hours ago
It was saved in drafts.
ohh
i think cf started div4...
Any idea on what might be the pretest-9 in Div2 C? Thanks
Why i can't see another's solutions?
How to solve E?
Each input must be in the form of
i nsince node n will fall into one of the parts after erasing an edge. Ifi nexists multiple times, add nodes with smaller indices between them.RIP all contestant who thought that A can be equal to B in F...
Isn't "RIP all contestant who didn't thought that A can be equal to B in F" ??
Wait, so it turned out that the clarification for my question is incorrect?
I'm really sorry for that(
When your question arrived, the only thing I had in mind was "A and B are on the different sides of the tube, how can they be equal?" I haven't thought that the question was about x-coordinates.
I could not solve F in time, so it didn't affect me anyway.
I think BledDest is formally right in this case...
In F, for the test
would the answer be 1 or 2 (ray bouncing off vertically)?
I have the same question
It should be 2, since there is no restrictions on relative positions of A and B. I'm sorry for the absence of such test in the pretests, trying to break some clever solutions, I forgot about this basic one.
2. I got hacked for this case.
Got fst for this case
Explain me please why I got TL on pretest #9 (Problem C) Solution
cur=upper_bound(ms.begin(),ms.end(),pp);complexity of upper_bound on set is O(n), If you want to use upper bound use s.upper_bound(value to be searched) which is O(logN)
One more bit of information in addition to what you've said: http://www.cplusplus.com/reference/algorithm/upper_bound/.
I just don't get it why would that take runtimeerror
even if i erase an iterated element from set I should still be able to reach the iterator value
I kept getting runtimeerror until i changed this... but why would that work for some test but not for pretest 9
solution
Lol.
After you've erased the element, the iterator is invalid. Essentially, it can be seen as a nullptr or any other random trash.
I know that means this is a mistake but that worked for some tests and it shouldnt at all if it is
It's called undefined behavior. Sometimes iterator might still point to the memory which has useful data, sometimes it might not.
well that's a better explanation thx
If I submit a solution at time t, my submission is inque for a hour, what's the final submitted time of the solution? t or t+60?
Of course t. Penalty is counted by the time of submission, not by the time of judgement.
OK, thanks.
Maybe I will become green tomorrow...
why pA with counting sort would pass...
a O(1e9) solution passes the test with 534ms...
The round just became worse... :'(
There are same submission of problem C by some participants so please look into this matter. MikeMirzayanov
http://codeforces.com/contest/1041/submission/42933160 http://codeforces.com/contest/1041/submission/42936047 These two submissions are the same. There may be more cases like this.
sans21 amc1996 pls upvote gourav comment.
The logic similarity is coincidence. There is a wrong submission as well as the number of successful submissions are also different for both users as well the code.(Problem D). Though well meaning, this is a false flag. MikeMirzayanov
Chal jhootha...kisi aur ko banana...hume sab pata h
RATED PLIZZZ
Tutorial #1 and Tutorial #2 redirect to the same link
Rated Rated Rated xD
Give me back my purple <3
I can't make a submission, seems like practice mode is disabled. Is this supposed to happen?
Practice mode is disabled during system testing. You can submit now.
I know that. Systest was over, and usually practice mode is instantly enabled. Thanks for answering anyway!
How does this soln passes System Test Cases?
It iterates from 1 to 1e9 in worst test cases.
Even passes Test Case (My failed hack.)
3 1 1000000 1000000000
with time 15ms.
Because of compiler optimizations, that source is literally O(n), which is good enough. I once got tricked by this, and i've learned my lesson since
Tags for problem A
https://gyazo.com/3874d1fae9f8da4c56d05359da48d26e
So many tags lmao.
What wrong with D? Don't make me scare :(
WTF?
that troll is strong
When somebody being a candidate master and can edit tags.
)
For all of you who had WA on E on test 33 and don't know why. My problem was:
Pair p contains (1, 1) instead of (0, 1) :/
I would be grateful if someone could explain briefly what is the cause of such behavior.
Arguments of any function/constructor could be calculated in any order (it's not strictly wrote in C++ standart). Thus, some compilers use left-to-right calculations, some of them use right-to-left, some of them could even use some crazy rules.
You can learn more here: https://en.cppreference.com/w/cpp/language/eval_order
Спасибо авторам за задачи! Скажите, пожалуйста, будут ли доступны все задачи квалификации на этом сайте? Если нет, то где тогда можно будет их дорешать?
Ты поосторожнее с такими вопросами, тут таких не любят:
http://codeforces.com/blog/entry/61811?locale=ru#comment-457884
http://codeforces.com/blog/entry/61811?locale=ru#comment-457896
Why does everytime I spend hours during contest to get an idea but the idea hits my brain in just about 10/15 minutes after the contest is over? So frustrated... :(
Its okay as long as you keep getting ideas. Some of us dont even get the idea.
What's the point of getting the idea though if you can't submit in contest time? Well it's still better than nothing but submitting correct in contest is what it really matters
Time will improve with time. Dont worry.
Wrong answer on sample test cases isn't supposed to get time penalties, correct?
I accidentally submitted an incorrect solution to the 3rd question (which was wrong on sample test case 2) and I got time penalty. Is this wrong or am I incorrect?
Only failure at the 1st test can be ignored.
Oh okay.. Thanks
I failed WA in D test 11, any ideas what I do wrong? (Was trying to solve with 2 pointers)
Sorry, it's offtopic.
Anyone knows how to add Codeforces contests to google calendar?
Upd:- Got it now.
Can problem D get a DP tag too? My approach was to calculate the covered distance when I start from the i'th segment and using previously stored data of other segments which are already calculated. Of course, there are better approaches to this problem.
u
=A=
Easiest F I've ever seen
Can somebody help me in problem C 43011918, i am getting the message "wrong output format Unexpected end of file — int32 expected" on test case 13 ,but i am not able to find any such mistake where i am accessing value from any wrong index.Thanks in advance!
It means you wrote less than n-1 commands
Thanks man.
А остальные 6 задач из квалификации будут в виде контеста или тренировки? + их разбор
Нет. Саратовцам же это невыгодно. Вдруг их кто-то решит и получит какие-то знания? И так на весь южный подрегион спалили.
Вас, конечно же, не волнует, что с заливанием тренировки могут быть некоторые проблемы, Вы, конечно же, считаете, что эти злые саратовцы жадничают и не хотят делиться своими задачами! Но мне кажется, что Вам просто хочется оставить очередной язвительный комментарий по поводу каждого произошедшего события. Но смею вас заверить, что как только проблемы будут решены, тренировка появится на Codeforces.
Спасибо, что хоть в четверг ответили.
Full Qualification Stage have been added to Gyms.