Добрый день!
В 14.12.2019 14:05 (Московское время) состоится Отборочный Раунд 4 олимпиады для школьников Технокубок 2020. Раунд будет длиться два часа. По его результатам лучшие участники (но не более 45% от общего числа участников раунда) будут приглашены на финальный этап в Москву. Для регистрации на раунд и участия перейдите по ссылке. Не забудьте заранее зарегистрироваться на раунд! Для опоздавших будет открыта дополнительная регистрация.
Зарегистрироваться на Отборочный Раунд 4 →
Соревнование открыто для всех в виде отдельных раундов для первого и второго дивизионов.
Для всех участников всех трех редакций этого соревнования будет пересчитан рейтинг.
Параллельно с Отборочным Раундом будут проведены открытые рейтинговые раунды для обоих дивизионов, в них могут принять участие все желающие.
Напомним, что согласно правилам раундов Codeforces во время соревнования ваши решения будут тестироваться только на претестах (предварительном и неполном наборе тестов), а системное тестирование состоится после окончания раунда. Обратите внимание, что претесты не покрывают все возможные случаи входных данных, поэтому тщательно тестируйте свои программы! После прохождения претестов у вас будет возможность заблокировать решение, тем самым получив привилегию искать ошибки и взламывать чужие решения, но отказавшись от возможности перепослать ваше решение при каких-либо обстоятельствах (например, даже если вы найдете ошибку или вас взломают). Со временем задачи падают в стоимости. После системного тестирования учитываются только полные решения. Подробнее про правила соревнований можно прочитать по ссылкам:
Регистрация на олимпиаду Технокубок еще открыта. Победителей и призеров олимпиады ждут значительные квоты при поступлении в престижные технические вузы России и ценные призы! Если вы — школьник 8-11 классов и пока не зарегистрировались на Технокубок, то самое время сделать это:
Зарегистрироваться на олимпиаду →
После регистрации на олимпиаду не забудьте зарегистрироваться на Отборочный Раунд!
В финал соревнования будут приглашены лучшие участники каждого из отборочных раундов (но не более 45% от общего числа участников раунда).
Этот раунд составили задачи моего авторства, задачи Михаила Endagorion Тихомирова и Владимира voidmax Романова! Огромная благодарность тестерам: Kostroma, never_giveup, Supermagzzz, AdvancerMan, Stepavly, unreal.eugene, cannor147 и geranazavr555!
Для тех, кто впервые на Codeforces: в таблице ниже вы можете найти примеры решений на всех поддерживаемых языках:
| Группа языков | Языки программирования / компиляторы | Примеры |
|---|---|---|
| C | GNU C, GNU C11 | 10903473, 17029870 |
| C++ | GNU C++, GNU C++11, GNU C++14, GNU C++17, MS C++, etc. | 23794425, 5456501 |
| C# | Mono C#, MS C# | 3195513, 3794163 |
| D | D | 5482410, 2060057 |
| Go | Go | 7114082, 21366098 |
| Haskell | Haskell | 455333, 1668418 |
| Java | Java 8 | 25491359, 23678167 |
| JavaScript | V8 | 35963909, 35681818 |
| Kotlin | Kotlin | 25779271, 25204556 |
| OCaml | OCaml | 6157159, 1281252 |
| Pascal | Delphi, FPC, Pascal.NET | 1275798, 1259434 |
| Perl | Perl | 2519448, 1277556 |
| PHP | PHP | 413942, 35875300 |
| Python | Python 2, Python 3, PyPy2, PyPy3 | 35883730 (Py2), 36179112 (Py3) |
| Ruby | Ruby | 1837970, 1289551 |
| Rust | Rust | 25180002, 35652442 |
| Scala | Scala | 35847980, 2456025 |
Удачи!
UPD: Разбалловка:
- Технокубок: 500-1000-1500-1500-2000-2500-3250
- D1: 500-1000-1250-2000-2250-3000
- D2: 500-1000-1500-1500-2000-2500
Looking forward to A1, A2, B1, B2, C1, C2, C3
you forgot the final D1,D2
What is happeninggggggg!!!!!
3 rated contests in 24 hours :3 :3
Maybe that means some official div1 participants in div2 contest?
I don't think that would happen. They must have left 2 hours gap between tomorrow's 2 contests, so that they can update ratings.
Will the ratings be updated after finish of both of them or individually?
Individually I guess. Otherwise, some div1 participants will end up participating in div2 contest
There will be 3 Rated contests in 24 hours, it will be a happy weekend !!!!! Thanks to the writers of these contests. :)
Unfortunately one of them clashes with my class time.
All three having unusual starting time.
Thanks for reminding me so that i don't make a mistake like last div3 where i started 30 minutes late.
There are three (3) contests in 24 hours and you're unhappy that one of them clashes with something else. People are really hard to please!
I don't want to miss single one. :(
I like your chart, it is going streight upwards.
Short notice for so many contests.
Tomorrow is a great day.. Make a contest..take 2 hours rest..Then again...Boom.. Feeling very much excited...
so many contest!!! I've been waiting a long time!!!
Flood of contests!
Please don't use that word. It sounds negative :(
For those who may want to take part in both rounds.
Two div1 contests in the weekend! Great!
Will EvenImage able to reach at the top position today?
Even if EvenImage overtakes Tourist today, tourist will be able to overtake him later. Also, a lot of Legendary Grand Masters like Radewoosh will compete. It is not as easy as you think!
I know tourist will beat him in next contest. But today he hasn't registered till now. So I was curious about it :)
Seems like your prediction was wrong. You got minus for only 606. Other two gave you positive rating.
WTF there're so many contests in a row (in a column?)
Разбалловка будет?
I hope the problem statements are short and clear.
I think problem with short statement are hard to solve compare to problem with long statement.
Scoring distribution?
Score distribution for the contest?
When Three contest starts at different time
There is still this issue.
:D
The output on A for div 2 is still wrong.
There is a very long queue :(
Queue is taking a long time
Why I can't submit, though I have registered? It says you have submitted exactly same code before, when I submit any code, though there is no submission in my submissions or standing. Why? I tried to submit by editing my code. It is same.
RIP queue
queueforces right now
Such a long queue. This round should be unrated.
Queue finished. And there was many queue in some of the previous rounds but that rounds doesn't become unrated so this round should be rated because the only worst thing is queue.(There isn't any problem...)
I submitted solution for problem A, then about 9 minutes later it gives WA. Then I submitted problem B solution, it took 11 minutes to show verdict AC. People who submitted earlier didn't face that problem I guess. So, how is that fair?
I know but in previous rounds it doesn't be unrated for long queue. So i think this contest should be unrated too.
Even if it's annoying, it's "fair" in a sense that the guy who submitted earlier was rewarded for his speed.
Probably it should be good to close gym during online rounds.
How to solve B without building tree of biconnected components?
DFS from $$$a$$$ without going past $$$b$$$, call the set of reached vertices $$$r_a$$$, and DFS from $$$b$$$ without going past $$$a$$$, call this set of reached vertices $$$r_b$$$. The answer should be $$$|r_a \setminus r_b|*|r_b \setminus r_a|$$$.
I did the same. Can you please tell how can we solve it by building tree of biconnected components?
I did the same, got TLEd
Did you use memset?
If you use a memset on an array like vis[200005] on each testcase... Then as the constraints says, there can be a testcase with 40000 sub-tests.
2e5*4e4=8e9... Then you will surely get a TLE.
generator:
UPD: There is a mistake in my generator. Fixed.
Oh man, you're right. I'm creating a vector array of size 2e5 for every test. resubmitted and got AC. Daaang this could've been my first time solving an E in a contest.
Is it true that the common of ra and rb are the vertices that lie one at least one path between a and b? So we can use this to find all vertices that lie to at least one path between vertexes a and b in a graph?
We can't (if you mean simple path). a = 1, b = 3, but 4 doesn't lie on the path from 1 to 3.
Right so is there a solution to this?
If you're asking about how to solve the problem "given an undirected graph $$$G$$$ and two vertices $$$a$$$ and $$$b$$$, find all $$$v$$$ such that there exists a simple path from $$$a$$$ to $$$b$$$ containing $$$v$$$", I thought about it for a bit and here's what I came up with:
Note that for a tree the answer is trivial; there is only one path from $$$a$$$ to $$$b$$$, so all the vertices from that path must be the answer. Now, for a general undirected graph, we decompose it into the biconnected components tree, and now there exists a path of blocks and cut vertices from $$$a$$$ to $$$b$$$ in our BCC tree, and we take all of the vertices in those blocks and the cut vertices on the path and that should be our answer. I don't know if there's a solution with a simpler algorithm, but I couldn't think of one.
what is bcc?
Biconnected components.
It seems that the answer is $$$(\text{No. of vertex not reachable by 'a' without going through 'b'}) \cdot (\text{No. of vertex not reachable by 'b' without going through 'a'})$$$
I'm so stupid. :(
Yeah... After the contest I realized that it is correct:
Define three subsets of the n-2 vertices except a and b:
A={Ai} be the subset of the vertices which can only reach a without passing through a and b;
B={Bi} be the subset of the vertices which can only reach b without passing through a and b;
C={Ci} be the subset of the vertices which can reach both a and b without passing through a and b.
It's obvious that these sets contains all the n-2 vertices and the three sets have none in common. (Since the graph is connected there shouldn't be a point that can't go to both a and b.)
For each unordered pair (x,y) (x!=y):
1)x and y both belong to A. Then there is a path x-...-y don't contain b.
(Both x and y can reach a without passing through b)
2)x and y both belong to B. Then there is a path x-...-y don't contain a.
(Both x and y can reach b without passing through a)
3)x belongs to C. Like 1) and 2), the path needn't contain both a and b.
If y belongs to A or C the situation is similar to 1).
If y belongs to B the situation is similar to 2).
4)x belong to A and y belong to B. then x can't reach y without passing through a or b.
Otherwise:
If a is not on a valid path x to y, then x-...-y-...-b should not contain a (Since y belongs to B). Then according to the definition of B, x belongs to B.
If b is not on a valid path x to y, then y-...-x-...-a should not contain b (Since x belongs to A). Then according to the definition of A, y belongs to A.
Both two suppositions lead to conflictions.
so the answer is |A|*|B|.
Can you please explain it more.
Explain with this example.
I have graph with 11 nodes. Consider 10th node as a and 11th node as b.
Now edges are:
According to your explanation:
A = [1,2,3]
B = [7,8,9]
C = [4,5,6]
So the answer must be |A|*|B| = 3*3 = 9.
But my question is why we aren't considering the path 1-a-4-b-5 as valid?
I know you have written last two lines regarding this but still I am not getting.
Please help me out.
For the solution 1-a-4-b-5...
It doesn't prove that all the paths from 1 to 5 pass through a and b.
Simply we can find another path 1-a-5 proving that the pair (1,5) is invalid.
Ok so we need to find pairs x,y such that all paths from x to y must contain a and b. But in question it was written that find pairs x,y such that any path from x to y must contain a and b.
Please clarify this.
I wonder what is different between those two statements. :(
Logically, "all the things are" equals to "any of the things is", I think.
P.S. Maybe you understood the problem as "Find pairs x,y such that there exists a simple path from x to y that contains a and b"?
Run two DFS from a and b individually ignoring b and a respectfully and save the visited nodes in two sets. Now, we have to delete the commonly visited nodes from the two sets. Then, the answer will be the multiplication of the size of these two sets.
Find connected components of the graph without $$$a$$$ and $$$b$$$. Then for each component, determine whether it is adjacent to $$$a$$$, $$$b$$$, or both. The answer is the product of (sums of sizes of components adjacent to $$$a$$$ only) and (sums of sizes of components adjacent to $$$b$$$ only).
My approach was bit different. I did it by doing dfs from a. Find the sum of size of subtree of b's children in dfs tree from which there is no back edge above b. Now, multiply it by (n — (Size of subtree of a's child which contains b) — 1).
I made two dominator trees, using a and b as roots. The answer is: ((size of subtree b on first tree) -1) * ((size of subtree a on second tree) -1)
Another way to find it:
Run a dfs from A and as soon as you reach a vertex (and it's not visited), add it to cnt. If you reach B, add it to cnt but do not move forward. It's obvious that n — cnt is equal to the nodes that are not reachable by A if we disconnect B.
Do the same from B and you'll find the nodes that are not reachable from B if we disconnect A. Now, if we get 1 node from cntA and 1 from cntB, we can see that the only way to connect them would be to pass through both A and B. Hence, it's a valid answer!
So, if we multiply cntA and cntB, we get the answer! :)
Can anyone tell me why my solution is wrong? 66888589
My approach was as follows :-
Remove all the edges from and to b, then count the number of nodes which can't be visited through dfs from a, since these nodes could be visited by adding the edges of b, this simply means that any path from a to these nodes passes through b. Count this number and let it be A.
Do the same after swapping a and b. Let the new number be B.
Then the answer should be A*B, this fails testcase 18 :(
UPD :- Nevermind, I messed up ll and int, fuck my life
Too many query problem resulted in too long queue. :(
Any particular edge cases on Div1 C? Failed on pretest 48 :/
Check when shortest side is greater than the biggest number of duplicates.
One of my best contests ever. Thank you Endagorion.
CF-Predictor is predicting you're going green :)
What is testcase 3 in Div2C
Try "ttwoonee" For me this was the case.
is answer 2 3 6 acceptable?
Yes
Thanks BTW for your time.
Does your solution pass this case?
The answer is
in my machine Does it matches with your answer
I see your code in comment below. I think "twone" is making both f2 and f3 true in your code which makes an issue here. As it match both with "two" and "twone" starting from t. I hope using else will solve your problem.
And why are you trying to match "twon"?
t##oo#ee Your answer should be correct
Not t##oo#ee it's tt#oo#ee. Here 2 is no of index and 3 and 6 are index.
Can someone explain Div2 D?
[Deleted]
Resulting sequence can be made of the form — (10)(00,00,00,....00)(01+10, 01+10,......,01)(11,11,11,.....11)(10)
In Div1C did the authors want an O(n sqrt(n)) solution to pass, or not?
If "yes", then why set TL to 1 second, isn't it right on the edge? Would the problem be spoiled by 2 or 3 second TL?
it can be solved in O(nlog(n)) but still 800 ms for me ...
It's easy to improve $$$O(n \sqrt{n})$$$ solution to $$$O(n\log(n))$$$ with 2 pointers.
Yep, I did it as well, took like 4 lines of code. Thanks :)
My question is not how to do it, but whether authors thought about it, or just decided on a 1 second TL by default.
Actually, my question to the public is: Did your fast and furious C++ O(n sqrt(n)) solution pass successfully?
Yes — 66860664
Let's say the size of the compressed input array is m. Then the submission with O(n log(n)) (sort the original array) + O(m log(m)) (sort the compressed array) + O(m sqrt(n)) ≈ O(n sqrt(n)) passes in 0.5s.
Sometimes you may spend a lot of time making a very efficient code just to be bypassed by someone with a bruteforce approach.
I think author set 1 second, cause it can be done in O(n). my solution pass pretest about 200ms.
what is the O(nsqrt(n)) solution ?
Compress the array, and then for i = 1..sqrt(n) find the amount of numbers such that for each a count(a) in input is no greater than i, thus for the current i you may have a rectangle with sides i, count(...) / i;
My solution has O(n) complexity :O Capped by the input tho. only took sqrt(n)*log^2(n) to binary search the grid. Upd : nvm. i got sort.
Is it just me or was this round overkilled? I tried hard stuff but in the end, if I had a screencast, it would look like this.
Tell me, no one (especially me) is gonna fail in system test.
THIS IS THE POWER OF CODEFORCES TO HOST MANY CONTESTS IN A ROW SALUTE CODEFORCES
The true way to solve Technocup Elimination A,B,C(sometimes D) problems:
Maybe it will help someone next year...
Looks like the key to doing well in contests nowadays is having code snippets for everything.
Can you elaborate? I did A,B,C without needing anything specific (unless my solutions fail).
Did you not use biconnected components for B?
i found B very easy .. just 2 dfs to check the component of each vertex in G-a and G-b ..
Oh, I see. I just did a dfs on a and b, and broke the set of vertices reachable from each into different parts, and then multiplied those reachable by a but not b, and those reachable by b but not a. It probably is the same solution, but the code seemed short (I wrote it myself, didn't use some library code).
Can anyone explain how to solve Div.2 D, please?
Check the first and the last digit of each string. And you'll be able to classify them as [0~0], [0~1], [1~0], [1~1]. If the second and the third group are all empty, handle that case separately, otherwise regulate the size of the second and the third group properly.
Everyone is posting screenshot of list of contest to get UPVOTES .
what are the edge cases in Div 2C
Maybe this "twoooneeee"
is the answer
acceptable?
ok. now try "ooonee"
my answer is
What about "oonnee"?
answer 0
Can you show me your code.
Are you sure about s[n + 3]? Also, this scheme:
one->f1; twone->f2; twon->f3
is very strange.What to do with "twontwontwo"? You doesn't even look at "two" itself.
1) two -> t#o 2) one -> o#e 3) twone -> tw#ne
I tried the same but failed in TC 3
Do you need my code? I was doing like this and it worked.
the case you're looking for is probably
twooneThank you man, but none are correct. I think there is some kind of overflow of large value
after you handle the case of
twone, make sure you're advancing iterator by 3, otherwise it'll check the case ofoneafter handlingtwo. This was the case with me.I did the same and my solution passed two test case,
I think "twone" is making both f2 and f3 true in your code which makes an issue here. As it match both with "two" and "twone" starting from t. I hope using else will solve your problem.
There are none. No of indices are twone + (twone-one) + (twone-two).
Remove allways the middle character of the match.
if the string is "ooneee" , you should only delete 'n' not('o' or 'e') coz if you did you will get oneee or oonee (Invalid output)
I did the same, unfortunately it's not working Thank BTW
svkrdj I have the same problem with it. Could you find out the issue behind it? Please help me with it.
try twontwontwo
This is the output given by my machine. What is the answer?
PS: Can you please tell me what is in pretest 3, if possible?
As there are multiple test case so there can be many things. For me it was "ttwoonee". Can you show your code?
My code
I've basically stored the starting indices of the substrings where, "one", "two", "twone" occur. And stored them in 3 vectors. And then removed characters accordingly.
Please add '\0' at the end off character array when you are using it as string.
But I guess it's not helping. What should I do? Where's the problem?
I added '\0' at the end of array as 'one\0', 'two\0', 'twone\0' and s[input.size()]='\0'
Don't forget to increase legnth of s by 1.
It got accepted for me then why not for you?
Thanks brother. AC now! Such small mistakes can do big blunders. Lost a lot of time due to it.
So many data structure in your solution. String,character array, integer array, vector, map. I have rarely seen such many data structure at a place. :p
.
I solved the idea for E quickly and was happy about it, but I kept getting wrong answer on test 3 :(
Isn't the solution: We check if both a and b are articulation points and then multiply the number of nodes on a's side(nodes that can be reached by a but not b) by the number of nodes on b's side?
UPD: Can anyone check what is the bug in my code? 66862954
The idea is kinda seems correct, but it can be simplified by thinking it like:
Answer = (n -Size of the component where 'a' is present after removing 'b' and its incident edges) * (n -Size of the component where 'b' is present after removing 'a' and its incident edges).
This requires just 2 dfs's.
You can find my submission here.
Your idea is correct, but probably you have a bug in your implementation. Anyway, you can solve it much more easily, see here: https://mirror.codeforces.com/blog/entry/72120?#comment-564067 (I used a similar approach)
I also get the idea for E quickly but i have no time to code.
when I saw A,B,C then --------->
But When I saw D&E,------------->
How to solve Div1D?
We do subtree dp. For each vertex $$$v$$$ we calculate 3 dp values: when parent $$$p$$$ of $$$v$$$ is taken before we go through edge $$$(v, p)$$$, when $$$p$$$ is taken by edge $$$(v, p)$$$ and when $$$p$$$ is either taken after edge $$$(v, p)$$$ or never taken at all. To calculate it we go through edges incident to $$$v$$$ in sorted order and store intermediate dp for wether we have taken $$$v$$$ and $$$p$$$.
Aren't the first two states the same, because they do not affect the token on v and the tokens in the subtrees? (Of course, the distinction is needed when descending to subtrees)
In the first case when we pass through edge $$$(v, p)$$$ we do nothing and in the second case we have to take $$$p$$$(and in order to do that we must ensure that $$$v$$$ is not taken yet).
Oh right. I was trying to do something similar with just 2 states, I guess that's why I couldn't solve the problem.
How to solve E?
Run two DFS from a and b individually ignoring b and a respectfully and save the visited nodes in two sets. Now, we have to delete the commonly visited nodes from the two sets. Then, the answer will be the multiplication of the size of these two sets.
Actually, we don't even need the sets. I did it in this way: my used[] has an integer type, and I exited DFS when I see a or b. Counted, how many vertices visited twice. Obviously, if used[V] == 2, then it has been visited by both APs. Then just subtracted this value from vA and vB, where vA — number of vertices, accessable from a, and vB — ... from b. The answer, as yours, multiplication of vA and vB.
Pretest 2 of Div2D ???
UPD : I think I found the case when both [0-0] and [1-1] type are present and I was handling this case seperately when abs( number of [0-1] — number of [1-0] ) will be even which was not required at all. After removing this part from the code, it passed perfectly.
How to solve Div1C? I figured that we can simulate the process for each rectangle height (at most sqrt(n)), but I couldn't do that in O(n).
I also do the same, but consider only rectangles where height is smaller than or equal to width. Now consider that you don't need to simulate the process (except at the end). If you have a fixed height H, you know you can't take more than H samples from each number. So, with Fenwick tree, count the sum S of all numbers from which there are at most H samples. Then, count the number N of numbers which occur more than H times in the array. In the end, calculate S + H * N — this is the maximal amount of numbers you can get. You can then find the max. width you can have for height H.
All my countercases to similar approach failed only when W < H, this is so simple, yet so effective! Thanks :)
Why the announcement for problem D in the contest was titled "Problem E" ??
Can someone show me pretest 3 for DIV2 C please?
I can't figure out why it failed for me.
Struggling for the same
mine was wrong bcz I didn't consider string of single character(of length 1.) and I got runtime error...after taking this in care it passed. so u can check this.
Is there any successful hacks in this contest? Strong pretests!!
In problem D there is a problem in the constraints!
It's written "The sum of word lengths doesn't exceed $$$4*10^6$$$" but the length of a single word isn't mentioned, so we should consider that the maximum length could be $$$4*10^6$$$. I submitted D at minute 46 (with setting $$$2*10^5$$$ the size of the char array) but before the end of the contest I noticed this problem and I changed the size of the array to $$$4*10^6$$$ and resubmitted.
Now after the contest I resubmitted the code that has only $$$2*10^5$$$ array size and it passed! This is totally unfair. You either should consider my first submission or modify the tests for all of the contestants.
UPD: Please look in it, it would give me 150 ranks up! Endagorion voidmax
I almost missed it...Although I didn't get good results in it...
Two rated contest within 4 hours of difference
Not satisfied with the delay of submission verdict. Did a silly mistake and got WA on test 1 after 10 minutes.
For Div2 Problem C- "As simple as One and Two", an important test case is missing.
The test is repeated 'twone' and it will lead to TLE in some solutions.
Test generation in Python
In my opinion, it should atleast be added to the testcases for those who try it in practice later so as to fully test correctness.
Е*аный рот этого казино, спасибо за 3 секунды
I BECAME THE PURPLE!!!!
Cherry bomb!
Same here :)
For div1 E:
We can merge a and b to the same value and then output changes in b in reverse order.
Pick random r.
Let $$$f(x) =\sum_{i=1}^4 (x_i-r)^2 + \dfrac{x_i \gt r} {100}$$$.
$$$|x_i-r|$$$ also works.
Just do operation what minimizes $$$f(a) + f(b)$$$ the most.
Damn, not again... I'm not doing great at making testcases for this kind of problems, do I.
Your solution seems to timeout on a case
What if I do 20 random moves in the beginning?
UPD: Does not work.
I'd expect a sufficient amount of fiddling should be enough to pass any given test.
I really should have made this a multitest, seems so obvious in hindsight.
My Div1C code passed pretests (50+ tests). It failed the main tests (runtime error on test 33). I submitted same code again twice after contest. It passed both times! Why?! How?
Two consecutive ACs submitting same code after contest https://mirror.codeforces.com/contest/1276/submission/66875312 https://mirror.codeforces.com/contest/1276/submission/66875827
RE on main tests of in contest submission https://mirror.codeforces.com/contest/1276/submission/66867062
Never mind, now that I had a look at pretests, it was a dumb out of bounds access.
Why can't we see others submissions and tests past samples?
Does anybody know why this code for Div 2 E failed?
#include using namespace std; #define ll long long #define ld long double #define endl "\n" #define dbg(x) cout << #x << " = " << (x) << endl; const ll MOD = 1000000007; const ll INF = 0x7fffffffffffffff; template void print(T v, int l = 0, int r = 5){ for(int i = l;i < r;i++) cout << v[i] << " "; cout << endl; } int t; int n, m; const int M = 300000; vector> g(M); int v[M]; int vnum = 0; void dfs(int x, int y) { v[x] = 1; vnum++; for(auto i: g[x]) if (!v[i] and i != y) { dfs(i, y); } } int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> t; while(t--) { memset(v, 0, sizeof v); int a, b; cin >> n >> m >> a >> b; a--; b--; for(int i = 0; i < m; ++i) { int x, y; cin >> x >> y; x--; y--; g[x].push_back(y); g[y].push_back(x); } vnum = 0; dfs(a, b); int xx = n — vnum — 1; vnum = 0; memset(v, 0, sizeof v); dfs(b, a); int yy = n — vnum — 1; cout << max(0, (xx * yy)) << endl; for(int i = 0; i < n; ++i) g[i].clear(); } }Answer can be > INT_MAX Use long long for final multiplication
Is it wrong answer on pretest 18?
There're at most 2*1e5 points, xx * yy may become 1e10 as a result, you may use long long to store it.
Can you, please, open test's verdicts
What was the idea for Div2 D?
Why submissions aren't visible?
Can someone explain why this solution is failing? 66858891
Edit: It fails in the case
1 t
But I still can't figure out why?
Please post the editorials
Can someone please explain or provide a small case why this IEP based solution for E is wrong — 1. Add total pairs
We subtract those pairs which are in same component after removing a — because they can be reached without a.
Same as 2 but after removing b.
We add those pairs which are in same component after removing both a and b because they are subtracted twice.
6 8 3 4 1 2 2 3 2 4 3 5 4 5 5 6 You will get a negative answer
Thank you!
Why are the solutions not visible?
Can anybody see why does this code(div2 E) failed?
Can someone please explain the approach for DIV2 D and also the corner cases?
Thanks.
ConstructiveAlgorithmsForces
Welcome to the russian contests
Why cant we see testcases?
How to solve div2D and div2E?
Div2 D
Notice that the only important thing is the first and last character of the string so the possible values are (0,0), (0,1), (1,0) and (1,1)
Notice that you can continue alternating the (0,1) and (1,0) they will continue forming a good sequence and you can add all the (0,0)'s in between any (0,0) and (0,1) and all the (1,1)'s in between any (0,1) and (1,0)
With that said you just have to check if it's possible to alternate the (0,1)'s and (1,0)'s also reverse a few of them as possible and check that the reversed value is unique.
My solution: Link
This is the best I can explain my solution it's really difficult to explain it and I hope the code helps.
2E: Delete every nodes that can reach both A and B without going through the other. Now the answer is (how many nodes that can reach A)*(how many nodes that can reach B).
And pay attention that the answer may over INT_MAX. I got WA on test18 because I didn't notice this before :( .
When we can see the results of Technocup? How many people will be invited to the final?
Well...When will the solution be given?
still could not see others solutions?
In Div 2 F I'm getting WA on TC 37 and I'm not able to figure out why. Anyone else got WA on fixed it? It would be great anyone is able to give some corner test case.
editorial?
Please provide editorials
I was really busy these days hosting 3 rounds. Unfortunately, for my problems (D2A-D2F) I can write solutions only tomorrow. I hope you liked them :) It seems most ideas are written in the comments.
Nice contests for newbies.
In D2-E, why the answer of testcase 2 is 0, we can go from node 1 -> 2(a) -> 3(b) -> 4. So we have a pair and the answer should be 1?
Excuse me, when will the totorial be published :D
yes please...will it be published or not
Editorial Link.