Привет, Codeforces!
В такой замечательный день недели, как 03.08.2018 17:45 (Московское время) состоится Educational Codeforces Round 48.
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Иван BledDest Андросов, Роман Roms Глазов, Адилбек adedalic Далабаев и Владимир vovuh Петров.
Удачи в раунде! Успешных решений!
Поздравляем победителей:
| Место | Участник | Задач решено | Штраф |
|---|---|---|---|
| 1 | eddy1021 | 7 | 299 |
| 2 | ppc_qjd | 6 | 240 |
| 3 | halyavin | 6 | 248 |
| 4 | BigBag | 6 | 250 |
| 5 | IcePrince_1968 | 6 | 286 |
Поздравляем лучших взломщиков:
| Место | Участник | Число взломов |
|---|---|---|
| 1 | halyavin | 80:-21 |
| 2 | Doriath | 45:-10 |
| 3 | antguz | 25:-1 |
| 4 | applese | 12 |
| 5 | Neon | 11:-2 |
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
| Задача | Участник | Штраф |
|---|---|---|
| A | bazsi700 | 0:01 |
| B | bazsi700 | 0:05 |
| C | yjq_naiiive | 0:17 |
| D | teja349 | 0:10 |
| E | yjq_naiiive | 0:49 |
| F | eddy1021 | 0:41 |
| G | comfi | 1:16 |
UPD: Разбор задач
Thanks to MikeMirzayanov for Codeforces and Polygon platform.
But is it rated?
Уже достаточно давно просят уменьшить фазу взломов. Есть причины. Почему никто не реагирует?(
What's up with these two comments? They seem to be visible for a split second when I reload this page.
Comments with extremely low rating don't get deleted, they only get style="display:none" applied to them when the page loads
But ?detaR tI sI
hope not a mathforces or hackforces
hackforces is cool
Hey man you forgot to Thanks MikeMirzayanov for Codeforces and Polygon platform.
i will stop commenting ..
10 mins penalty or 20 mins?
I think 20 minutes.
You are thinking wrong
10
It is 10 minutes for Educational Rounds and Div3 contests. See this comment!
Some upvotes please...
Some downvotes please, I want to reach desired 69 contribution.
I love how this actually worked, now I have 69 contribution.
why 10 minutes delay :(
to get 9K participation
To update the writers list:
I love CodeForces delays ^___^
^______________________________^
^______________________________^
^___________________________________________^
^___________________________________________________________^
_VanGogh_
AghaTizi
Practicing recursion without a basecase ?
OMG you're so funny
OMG I know :P
You dont have hir.
:(
I HATE CODEFORCES DELAY
10 seconds --> F5 --> 10 minutes :)
a short sad story :(
Codeforces site already running slow, even before contest has started.
True.. It's slow here too.
I think there is a problem, contest is delayed but Hightail was able to parse 2 question's TC. Using this anyone can get extra time in these scenarios.
+10 minutes in my wasting time sad :(
502 Bad Getaway-- CF wants to make you late for school.
I hope there woudln't be any lagginess during the contest since we're having ~9k participants
Well 9000 participants ! Love codeforces and this competitive programmers family.
"IS IT RATED?" in CodeForces is just the same as "Is ThIs Loss?" in reddit && other meme portals :)
Как всегда, баланс между задачами просто ошеломителен.
Ну что за "как всегда"? Для educational раундов это скорее исключение из правил.
is this a div1 contest!! :|
Че то сложно... Всегда знал, что я Div3
Any hints for C and D?
D: You don't have to fill the entire table, just try to fill exactly one column and exactly one row, other cells are 0
Why does this method work? Any intuition or proof? Thanks :)
Suppose you constructed an answer with some number x in cell [i, j].
Then you may:
1) Set ans[i, j] = ans[i, j] xor x
2) Set ans[i, 1] = ans[i, 1] xor x
3) Set ans[1, j] = ans[1, j] xor x
4) Set ans[1, 1] = ans[1, 1] xor x
Then all xor-values of all rows and columns will remain the same, but we will get rid of some non-zero number.
This was beautiful. Thanks for the nice contest :)
I think it's like this;
Let a = (first column) xor (all rows from 2 to n)
and b = (first row) xor (all columns from 2 to m)
Both a and b represent cell(1,1) xor submatrix((2,2) to (n,m)), so they should be equal.
If they are not equal then it's impossible to construct a matrix that satisfies the given constraints.
And if they are equal, then we can fill all the submatrix((2,2) to (n,m)) with zeros and no contradiction will occur.
Can you elaborate the last line — "And if they are equal, then we can fill all the submatrix((2,2) to (n,m)) with zeros and no contradiction will occur."
You're right, I didn't know how to explain that part very well.Let me try again.
At first I thought; what can stop us from filling all of that submatrix with zeros? the only "possible problem" will be at the cell (1,1) because of the two values a and b(from the above comment); they represent the same thing but have different expressions that depend on the two input arrays.So they must be equal(or else no matrix will be correct no matter the values you choose).
Now that the submatrix is all zeros, and the value at cell (1,1) is fixed, can we have another "possible problem" or "contradiction" with the other cells ? (cells (1,2) to (1,m) and (2,1) to (n,1)).
No, because the xor of any of these columns/rows(columns [2,m] and rows [2,n]) only depends of the first cell in that column/row and the zeros, so in other words no column/row will touch the first cell in any other column/row.
So for any of these columns/rows nothing is stopping us from putting the value of it's first cell as the xor of all it's cells(since all the others are 0s, the result will be correct).
Try to come up with counterexamples and you'll get it.
what will be there in cell(1,1)?
We chose to fill the submatrix from (2,2) to (n,m) with zeros, so a and b(from the above comment) will both be equal to the value in (1,1).
Using the two input arrays;
a = b1 ^ a2 ^ a3 ^ ... ^ anb = a1 ^ b2 ^ b3 ^ ... ^ bmYou need to verify if they are both equal.
If they are, fill that submatrix with zeros, fill the first row like this:
matrix[1][i] = bifor i in [2,m] andmatrix[i][1] = aifor i in [2,n].@glays I wanted to know can you give any proof/surety that by following above strategy there is no way such that if you use use some other strategy you can make a matrix while this method returns "NO" i.e answer doesn't exist using this strategy?
I understand what you mean, try reading these comments:
first
second
Cleaner and better proof from BledDest
Also re-read the editorial.The first equality in it must be true, because both expressions represent the xor of all elements in the matrix, so they must be equal.If not, it's just impossible i.e. these constraints can not form a matrix.
Well, first off I didn't AC problem C but I hope my approach was correctly. Basically, you can observe that since there are only 2 rows, and you need to visit every glade exactly once, you need to travel in a snake-like pattern from the start (going down, left, up, right, down, etc.). But you can also go all the way to the last glade of the row and 'loop' back to visit all the other unvisited glades in the other row. Please correct me if this approach doesn't work! Thanks.
Edit: I suck and created an array too small. It passed afterwards.
i thought exactly that but could not implement it...like : for going all the way to n... same cell can be multiplied with different number like 1 if we come straight from 0 or 3 if we zigzag like : 0->up->right->down....how do calculate for such different values
Yeah that was tricky for me as well. Let's say you're at row 1 column 3 (1 indexed). You can get here and multiply by 2 (by going right from the start) or by 4 (if you zigzag down from the start). When you calculate going all the way to the last column of the row and return on the second row from this glade, you can notice that the difference between going right from glade (1, 1) and right from glade (1, 3) is the sum of all the numbers from ((1, 3) to (1, n) + (2, n) to (2, 3)) * (4 — 2). Hence, you can use prefix sums here to speed up the computation.
....
You multiply by (4-2) because if you reach glade (1, 3) and multiply by 2 (and then go all the way to the last column and return), then you multiply the subsequent numbers by 3, 4, 5, etc.
If you reach glade (1, 3) and multiply by 4 (going to the last column and return), then you multiply the subsequent numbers by 5, 6, 7, etc.
Since you are multiplying the same set of numbers in the same order, by putting the multiples side-by-side you can notice the following:
First situation: 3, 4, 5, 6...
Second situation: 5, 6, 7, 8...
Each number in the first situation is multiplied 2 less than each number in the second situation. Thus, the difference between the sums of the two situations is (sum of numbers from (1, 4) to last column and return) * 2, with 2 being the same thing as (4-2).
How to solve C?
There is one pattern of going only: Zigzagging up to the ith column, then go all the way to column n and return. I don't want to get in details of how to calculate this, pretty long. But yeah you get the basic idea
Yeah I got it, but couldn't find that ith column fast enough =(
You can sweep the entire column.
Yeah :P it used prefix sums. So goddamn hard to implement and test, gosh, took me 20 minutes.
Suppose you're at cell (1,1), there are three possible ways.Either you;
go straight to (1,n) then down to (2,n) and back to (2,1).
go down to (2,1) then straight to (2,n) and up to (1,n) then back to (1,2).
zigzag your way to (2,1) then (2,2) then (1,2) then (1,3).Now that you're at (1,3), repeat.
The first two can be precalculated using (painful and annoying) prefix and suffix sums.But it's not obvious at first.
By the way, there are only n different routes.
In F, you always put edge at same place right?
I don't think so, but i got WA. :(
I am missing some corner case. Mine gets WA on 23rd so I think I am right.
You can always add edge at same place.
Yes
I didn't have time to implent anything, but I figured the same too. It seems weird though, because if it's true, then the queries make zero sense.
Yes, there is always one optimal place that the edge should always be placed
What's 6 pretest for D?
чё за прекол С за 40 минут пишется а D за три минуты
I changed all long long into int, all long double into double, then I passed problem E instead of TLE. But I submitted it when the contest was already finished.
And you still leave endls in your code. I changed endl to \n and it got AC in 750 ms instead of 1980
I tried several times again. I got TLE on 8 with long long, long double and endl. 1980ms with int, double and \n. 1590ms with long long, long double and endl. 1434ms with int, double and \n. 311ms with printf.
What about long long main() ?
you can replace int main() with int32_t main();
Or you can just write main(). By defaualt it assumes int. and No it's not undefined behaviour.
It's also not something supported in the C++ standard. In might work in GCC (or at least the version of GCC that codeforces uses), but it won't work on other compilers (try visual studio and clang).
Show unofficial isn't working!
Because it's Educational and after hacking phase you can choose division.
Problem D can be solved using flow. Bits are independent of each other, so treat one at time. Do matching to see where to put the 1's. XOR into some matrix and check at the end.
Flow sounds a bit overkill
Maybe, but solution is quick when you've seen similar problem.
How do you build the network?
First consider simpler problem. Limit values to 0 and 1. If we want the values in a row to XOR to 1, there must be an odd number of 1s in that row; if we want it to XOR to 0, there must be an even number of 1's. It is the same for columns.
The number of elements in a row depends on how many columns there are, and vice versa.
There are some cases to consider. Let number of columns be c. If c is even, and we want some row to XOR to 1, there can be at most c - 1 1's in that row; if we want to XOR to 0 and c is even, we can put all c ones in that row. The other cases follow from this and are easy to work out. These values become the capacity of edges from source to row and and column to sink...
For edges in between, place edge between each row and column. Saturating the edge is like putting a 1 in the cell that is the intersection of that row and column. Obviously we can only put a single 1 or 0 in a cell so those edges have unit capacity.
Now we run max flow on this bipartite graph. Saturated edges represent cells with 1 in them.
...
Now we take the same problem for general case of numbers, not just 0 and 1. Note that all bits in binary representation of number are independent, as I said before.
So we take the simpler problem I described above and do it 30 times, for bits indexed 0 to 29, because the problem is bounded by a billion in the problem statement, the base-two log of a billion is just over 29.
Do all the flows and put the resulting values in the matrix. To check if there even exists a matrix we simply validate the matrix produced by XORing its rows and columns and comparing to inputted XOR values.
Thanks for explaining. Still confusing because there seems to be no explicit constraint on parity. For example, nothing prevents an edge of capacity 8 going to sink from saturating to 7.
We want the maximal flow, so it’ll saturate fully if it can. That’s what we want.
That's why you are still blue.
Why "wrong answer 154th numbers differ — expected: '-0.0000000', found: '-0.0000000', error = '-0.0000000'"?
Submission
This is one of the standard checkers from polygon, there should be no bugs. However, its output on par with the integer sequence one is definitely broken now. It looks like it checks fine, just outputs the wrong thing.
Like take a look at any wrong submission for problem B or F, output of the checker is wrong while the answer is also wrong.
oh..I understand . However , the checker for the submission you have seems work properly .
Yeah, it's been fixed :) It was saying "expected: '', found: '12'" when I linked it
The judge still seems to have issues for E...
http://codeforces.net/blog/entry/60980?#comment-449222
ответ (скопирован вердикт посылки 41190467) wrong answer 216th numbers differ — expected: '0.0000000', found: '-0.0000000', error = '0.0000000'
Насколько сейчас известно — это баг в комментарии стандартного чекера rcmp6. То есть проверяет правильность он верно, а вот комментарий выдает с багами вывода действительных чисел. Аналогично страдал ncmp. В скором времени отображение комментариев поправят.
can you show me that why my code in Problem C got WA in test 7, please :(((((. I think my code WA in bignum but can't fix it :(((( http://codeforces.net/contest/1016/submission/41190766
I'm desperate -_-
How to solve problem E?
consider query point Q. find intersection of AQ and BQ with x-axis. The amount of x-axis covered in this range is proportional to shade time. To get actual shade time multiply by (y - sy) / y. I think my logic is correct although I couldn't debug my code.
*** (y - sy) / y ***
Corrected.
Is It Rated?
Are you rated?
Am I rated?
Test for Comment Editing
Nineteen minutes lagging i hate my internet XD
I saw some solution use hashing with only 1 modulo and got hacked on problem B. I am considering which type of test did hackers use to hack?
Lol why did you use hashing here? n00b
Why there's no * after those orange or higher people ?
All participants are official ?
Yup, it's been like that for a while now. Everyone is official, rated status doesn't depend on that.
Is It Rated or Contributed?
Yes. You will be down-voted.
When will there be a tutorial? Anyway, I will try to solve more problem myself. :p
Congrats to ppc_qjd, who received a 450+ rating change after his first round!
Congrats to ppc_qjd, who managed to gain a 450+ rating change after his first contest!
Waaaait a second...
I'm actually a big fan of djq_cpp!
Could anyone please help me with my E problem? No idea how to make it work faster, O(nlogn).
#define endl '\n'may helpwhere is the super fast editorial this time?
Not all editorials are ready so please stand by.
no problem captain!!!
Still didn't help(
How to solve problem E,just a hint.....
Some hints are described here: comment.
Editorial should be within 2 hours, since one of authors is slowpoke.
Need editorials!
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
I ak ioi!
Is the judge for E broken? I do not think this submission should TLE...
I even tested the solutions of people on my friends list who got it AC, and they also get TLE...
Can you please tell me which submissions have got AC, but now is catching TLE?
adedalic See here for the AC one, and the copy-pasted one I submitted that TLEs.
Seems that compilers differ, maybe C++11 one has slower iostream functions than C++17? Probably it's worth trying getting rid of cout for printf or submitting in C++17.
More over, it seems that IO operation more than twice slower in C++11 in comparison to C++17
I barely get my initial submission accepted in C++14 and it still TLEs in C++17.
cin/cout with the special speedup should be on par with printf though...
Lol the problem was taking in floating-point numbers instead of integers, if you take the input as integers it still passes C++11 (I know from stalking vamaddur's submissions)
Apparently difference is so great, taking in floating point makes the whole program (which is nlogn) take more than 2x runtime.
Can somebody explain for problem D why the greedy always works/doesn't mess up the impossible case?
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
can someone explain C
I was really educated.
But is it contributed?
Hi!
Hi
Nice to meet tou!