By pikmike, history, 18 months ago, translation, ,

On Aug/03/2018 17:45 (Moscow time) Educational Codeforces Round 48 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extented ACM ICPC rules. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them.

The problems were invented and prepared by Ivan BledDest Androsov, Roman Ajosteen Glazov, Adilbek adedalic Dalabaev, Vladimir Vovuh Petrov and me.

Good luck to all participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 eddy1021 7 299
2 djp_cqq 6 240
3 halyavin 6 248
4 BigBag 6 250
5 IcePrince_1968 6 286

Congratulations to the best hackers:

Rank Competitor Hack Count
1 halyavin 80:-21
2 Doriath 45:-10
3 antguz 25:-1
4 applese 12
5 Ne0n25 11:-2
236 successful hacks and 417 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
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 .................. 1:16

UPD: Editorial

• +234

 » 18 months ago, # |   +76 Thanks to MikeMirzayanov for Codeforces and Polygon platform.
»
18 months ago, # |
-42

But is it rated?

•  » » 18 months ago, # ^ |   -14 rated for the participants with rating lower than 2100
 » 18 months ago, # |   +13 What's up with these two comments? They seem to be visible for a split second when I reload this page.
•  » » 18 months ago, # ^ | ← Rev. 3 →   +29 Comments with extremely low rating don't get deleted, they only get style="display:none" applied to them when the page loads
»
18 months ago, # |
-37

But ?detaR tI sI

 » 18 months ago, # |   -15 hope not a mathforces or hackforces
•  » » 18 months ago, # ^ |   -62 hackforces is cool
•  » » 18 months ago, # ^ |   -31 i see you have hackfobia
 » 18 months ago, # |   -121 Downvoted the blog already. Because the last 2 educational rounds were shitty.
 » 18 months ago, # |   +2 Hey man you forgot to Thanks MikeMirzayanov for Codeforces and Polygon platform.
 » 18 months ago, # |   +156 i will stop commenting ..
•  » » 18 months ago, # ^ |   -26 you will miss me ...
 » 18 months ago, # |   0 10 mins penalty or 20 mins?
•  » » 18 months ago, # ^ |   0 I think 20 minutes.
•  » » » 18 months ago, # ^ |   0 You are thinking wrong
•  » » 18 months ago, # ^ |   +1 10
•  » » 18 months ago, # ^ |   +13 It is 10 minutes for Educational Rounds and Div3 contests. See this comment!
 » 18 months ago, # | ← Rev. 2 →   0 Please do not disable problemset submissions during contest.
 » 18 months ago, # |   -63 Some downvotes please, I want to reach desired 69 contribution.
•  » » 18 months ago, # ^ |   0 I love how this actually worked, now I have 69 contribution.
 » 18 months ago, # | ← Rev. 2 →   0 8000+ participation just wow gonna be challenging :)
•  » » 18 months ago, # ^ |   0 it's almost 9000 now!
 » 18 months ago, # |   +37 why 10 minutes delay :(
•  » » 18 months ago, # ^ |   +5 to get 9K participation
•  » » 18 months ago, # ^ |   +11 To update the writers list:
 » 18 months ago, # |   -30 I love CodeForces delays ^___^
•  » » 18 months ago, # ^ |   -20 ^______________________________^
•  » » » 18 months ago, # ^ |   -32 ^______________________________^
•  » » » » 18 months ago, # ^ |   -30 ^___________________________________________^
•  » » » » » 18 months ago, # ^ |   -30 ^___________________________________________________________^
•  » » » » » » 18 months ago, # ^ |   +15 Slutty_PumpkinJafarIsBackPracticing recursion without a basecase ?
•  » » » » » » » 18 months ago, # ^ |   -9 OMG you're so funny
•  » » » » » » » » 18 months ago, # ^ |   +11 OMG I know :P
•  » » » » » » » 18 months ago, # ^ |   +4 You dont have hir.
•  » » » » » » » » 18 months ago, # ^ |   0 :(
•  » » 18 months ago, # ^ |   0 Where is Ted??
 » 18 months ago, # |   +4 I HATE CODEFORCES DELAY
•  » » 18 months ago, # ^ |   0 Like
 » 18 months ago, # |   0 10 Min delay !! Welcome back codeforces <3
 » 18 months ago, # |   +13 10 seconds --> F5 --> 10 minutes :)
•  » » 18 months ago, # ^ |   +8 a short sad story :(
 » 18 months ago, # |   +2 Codeforces site already running slow, even before contest has started.
•  » » 18 months ago, # ^ |   +8 True.. It's slow here too.
 » 18 months ago, # | ← Rev. 2 →   +21 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.
 » 18 months ago, # |   +1 +10 minutes in my wasting time sad :(
 » 18 months ago, # |   +5 502 Bad Getaway-- CF wants to make you late for school.
 » 18 months ago, # |   +3 I hope there woudln't be any lagginess during the contest since we're having ~9k participants
 » 18 months ago, # |   -26 Educational rounds are useless !!
 » 18 months ago, # |   +6 Well 9000 participants ! Love codeforces and this competitive programmers family.
 » 18 months ago, # |   -12 "IS IT RATED?" in CodeForces is just the same as "Is ThIs Loss?" in reddit && other meme portals :)
 » 18 months ago, # |   0 9k! Congrats!
 » 18 months ago, # |   -16 is this a div1 contest!! :|
 » 18 months ago, # |   +1 Any hints for C and D?
•  » » 18 months ago, # ^ |   +13 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
•  » » » 18 months ago, # ^ |   +1 Why does this method work? Any intuition or proof? Thanks :)
•  » » » » 18 months ago, # ^ | ← Rev. 2 →   +21 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 x2) Set ans[i, 1] = ans[i, 1] xor x3) Set ans[1, j] = ans[1, j] xor x4) Set ans[1, 1] = ans[1, 1] xor xThen all xor-values of all rows and columns will remain the same, but we will get rid of some non-zero number.
•  » » » » » 18 months ago, # ^ |   +1 This was beautiful. Thanks for the nice contest :)
•  » » » » 18 months ago, # ^ |   +4 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.
•  » » » » » 18 months ago, # ^ |   0 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."
•  » » » » » » 18 months ago, # ^ |   0 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.
•  » » » » » 18 months ago, # ^ |   0 what will be there in cell(1,1)?
•  » » » » » » 18 months ago, # ^ |   0 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] = bi for i in [2,m] and matrix[i][1] = ai for i in [2,n].
•  » » » » » 18 months ago, # ^ |   0 @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?
•  » » » » » » 17 months ago, # ^ |   -8 I understand what you mean, try reading these comments:firstsecondCleaner and better proof from BledDestAlso 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.
•  » » 18 months ago, # ^ | ← Rev. 2 →   +3 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.
•  » » » 18 months ago, # ^ |   0 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
•  » » » » 18 months ago, # ^ | ← Rev. 2 →   +1 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.
•  » » » » » 18 months ago, # ^ | ← Rev. 5 →   -9 ....
•  » » » » » » 17 months ago, # ^ |   -8 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).
•  » » 18 months ago, # ^ |   -8 Consider every point as "End" cell where vasya will end his journey and also the fact that each cell could be visited only once. You'll notice only possible end points are indices with (i+j) "ODD". (First move in a zig-zag manner to the adjacent cell at same column and traverse all the way round back to the End cell). P.S Zig-Zag manner means move to unvisited cell at same column and from there to adjacent cell at next column(Repeat). Please do ask if its not clear.
 » 18 months ago, # |   0 How to solve C?
•  » » 18 months ago, # ^ |   0 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
•  » » » 18 months ago, # ^ |   0 Yeah I got it, but couldn't find that ith column fast enough =(
•  » » » » 18 months ago, # ^ |   0 You can sweep the entire column.
•  » » » » 18 months ago, # ^ |   0 Yeah :P it used prefix sums. So goddamn hard to implement and test, gosh, took me 20 minutes.
•  » » 18 months ago, # ^ | ← Rev. 4 →   +14 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.
 » 18 months ago, # |   +16 In F, you always put edge at same place right?
•  » » 18 months ago, # ^ |   0 I don't think so, but i got WA. :(
•  » » » 18 months ago, # ^ |   +5 I am missing some corner case. Mine gets WA on 23rd so I think I am right.
•  » » » » 18 months ago, # ^ | ← Rev. 2 →   0 You can always add edge at same place.
•  » » 18 months ago, # ^ |   +5 Yes
•  » » 18 months ago, # ^ |   0 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.
•  » » 18 months ago, # ^ |   0 Yes, there is always one optimal place that the edge should always be placed
 » 18 months ago, # |   0 What's 6 pretest for D?
 » 18 months ago, # |   -24
 » 18 months ago, # | ← Rev. 2 →   +8 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.
•  » » 18 months ago, # ^ |   +28 And you still leave endls in your code. I changed endl to \n and it got AC in 750 ms instead of 1980
•  » » » 18 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » 18 months ago, # ^ |   +84
•  » » » 18 months ago, # ^ |   0 What about long long main() ?
•  » » » » 18 months ago, # ^ |   +4 you can replace int main() with int32_t main();
•  » » » » » 18 months ago, # ^ |   0 Or you can just write main(). By defaualt it assumes int. and No it's not undefined behaviour.
•  » » » » » » 18 months ago, # ^ |   0 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).
 » 18 months ago, # |   0 Show unofficial isn't working!
•  » » 18 months ago, # ^ |   +8 Because it's Educational and after hacking phase you can choose division.
 » 18 months ago, # |   +15 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.
•  » » 18 months ago, # ^ |   +11 Flow sounds a bit overkill
•  » » » 18 months ago, # ^ |   0 Maybe, but solution is quick when you've seen similar problem.
•  » » 18 months ago, # ^ |   +12 How do you build the network?
•  » » » 18 months ago, # ^ |   +38 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.
•  » » » » 18 months ago, # ^ |   0 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.
•  » » » » » 18 months ago, # ^ |   0 We want the maximal flow, so it’ll saturate fully if it can. That’s what we want.
•  » » 18 months ago, # ^ |   -38 That's why you are still blue.
 » 18 months ago, # |   +29 Why "wrong answer 154th numbers differ — expected: '-0.0000000', found: '-0.0000000', error = '-0.0000000'"?Submission
•  » » 18 months ago, # ^ | ← Rev. 2 →   +28 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.
•  » » 18 months ago, # ^ | ← Rev. 3 →   +31 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.
•  » » » 18 months ago, # ^ |   0 oh..I understand . However , the checker for the submission you have seems work properly .
•  » » » » 18 months ago, # ^ |   +8 Yeah, it's been fixed :) It was saying "expected: '', found: '12'" when I linked it
•  » » » » » 18 months ago, # ^ |   +8 The judge still seems to have issues for E...http://codeforces.com/blog/entry/60980?#comment-449222
 » 18 months ago, # | ← Rev. 2 →   0 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.com/contest/1016/submission/41190766
•  » » 18 months ago, # ^ |   0 I'm desperate -_-
 » 18 months ago, # |   0 I submitted a hack but the verdict is still not shown (spinner for the last 10 minutes). How much time does it usually take for hacks to show the verdict?
 » 18 months ago, # |   0 How to solve problem E?
•  » » 18 months ago, # ^ | ← Rev. 4 →   0 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.
•  » » » 18 months ago, # ^ |   0 *** (y - sy) / y ***
•  » » » » 18 months ago, # ^ |   0 Corrected.
»
18 months ago, # |
-32

Is It Rated?

•  » » 18 months ago, # ^ |   0 Are you rated?
• »
»
»
18 months ago, # ^ |
-26

Am I rated?

•  » » » » 18 months ago, # ^ |   -11 Downvote that comment !
 » 18 months ago, # |   0 Nineteen minutes lagging i hate my internet XD
 » 18 months ago, # |   -35 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?
•  » » 18 months ago, # ^ |   -24 Lol why did you use hashing here? n00b
 » 18 months ago, # |   +3 Why there's no * after those orange or higher people ? All participants are official ?
•  » » 18 months ago, # ^ |   +8 Yup, it's been like that for a while now. Everyone is official, rated status doesn't depend on that.
»
18 months ago, # |
-31

Is It Rated or Contributed?

•  » » 18 months ago, # ^ |   +9 Yes. You will be down-voted.
 » 18 months ago, # |   0 When will there be a tutorial? Anyway, I will try to solve more problem myself. :p
 » 18 months ago, # | ← Rev. 2 →   +15 Congrats to djp_cqq, who managed to gain a 450+ rating change after his first contest!
•  » » 18 months ago, # ^ |   +33 Waaaait a second...
•  » » » 17 months ago, # ^ |   +21 I'm actually a big fan of djq_cpp!
 » 18 months ago, # |   0 Could anyone please help me with my E problem? No idea how to make it work faster, O(nlogn).
•  » » 18 months ago, # ^ |   0 #define endl '\n' may help
•  » » » 18 months ago, # ^ |   0 where is the super fast editorial this time?
•  » » » » 18 months ago, # ^ |   +16 Not all editorials are ready so please stand by.
•  » » » » » 18 months ago, # ^ |   0 no problem captain!!!
•  » » » 18 months ago, # ^ |   0 Still didn't help(
•  » » » 18 months ago, # ^ |   0 How to solve problem E,just a hint.....
•  » » » » 18 months ago, # ^ |   +5 Some hints are described here: comment.Editorial should be within 2 hours, since one of authors is slowpoke.
 » 18 months ago, # |   +8 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 18 months ago, # |   0 Where are the solutions?
 » 18 months ago, # |   0 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...
•  » » 18 months ago, # ^ |   0 Can you please tell me which submissions have got AC, but now is catching TLE?
•  » » » 18 months ago, # ^ |   0 adedalic See here for the AC one, and the copy-pasted one I submitted that TLEs.
•  » » » » 18 months ago, # ^ |   0 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.
•  » » » » 18 months ago, # ^ |   0 More over, it seems that IO operation more than twice slower in C++11 in comparison to C++17
•  » » » » » 18 months ago, # ^ |   0 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...
•  » » » » » » 18 months ago, # ^ |   0 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.
 » 18 months ago, # |   0 No editorial?
 » 18 months ago, # |   -8 Can somebody explain for problem D why the greedy always works/doesn't mess up the impossible case?
 » 18 months ago, # |   0 Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).
 » 18 months ago, # |   0 can someone explain C
 » 17 months ago, # |   0 I was really educated.
»
17 months ago, # |
-29

But is it contributed?

 » 17 months ago, # |   0 Hi!
•  » » 17 months ago, # ^ |   0 Hi
•  » » » 17 months ago, # ^ |   0 Nice to meet tou!