Hi, Codeforces!
I'm glad to invite you to take part in Codeforces Round 917, which will take place on Dec/24/2023 17:35 (Moscow time). Round will be rated for participants with rating less than $$$2100$$$. Participants from the first division can take part out of competition.
There will be $$$6$$$ problems for $$$2$$$ hours. The problems are authored by IgorI, zidder and me.
Part of the problems in this round were in the Yerevan SU 28.1₀.₂₀₂3 Contest. If you participated in it or know at least one problem from it, please refrain from participating in this round.
We would like to thank
- Thanks to TheScrasse for excellent round coordination;
- Thanks to our testers: KAN, S_Voloch, Tmitmi, Pagode_Paiva, hgglmao, IceWolf898, daud04, dewana310, menborong, -dub-otrezkov-, rtckyw_, Bebo, Starswap, MCuong, line, shamir0xe, Adrisos, AbduSaber, pwned, TamimEhsan, Andreasyan, priyanshu.p, kzyKT, Lyde, mcdx9524, mihneacazan, PurpleCrayon, errorgorn, fishy15, maomao90, okwedook, higz, Akash., Kapt for giving valuable feedback for problems;
- Thanks to MikeMirzayanov for creating Codeforces and Polygon.
Scoring distribution: $$$500 - 1000 - 1500 - 2250 - 2500 - 3000$$$
We hope you'll like the problemset! Good luck and have fun!
UPD 1: Editorial
UPD 2: Congrats to our winners:
- Div1 + Div2
- Div2
]
As someone who has a birthday, please give me a contribution.
It can be negative as well:)
Are you Jesus??
Merry Christmas :)
belated Merry Christmas !!
Great!!!
As a tester, I recommend trying all of the problems (really good ones). Also I wish everyone positive delta as a Christmas present:)
Thank you, for your wishes for everyone who got it positive
Merry Christmas!
I will try it!
^_^
As a tester, I want to reach pupil after this round
but a tester can't participate in the round
May be by Magic feature.
Magic!
Looking like speedforces:( because D is 2250.
hgglmao This round is good?
i hope i become expert after this round
CM TIME
participate cf contest on Christmas Eve (east Asia time) this is really a round 😂
Big point difference between C and D
Hopefully I become a master after this contest!
Maybe I can reach specialist by the end of this year :)
Mate you just missed by 2. Maybe in rechecking later it may increase.......
Yeah, was almost there... maybe next time
And I'm confused how the hell on earth did your code for problem C got accepted...I just copied and ran your code and it's showing WA on testcase 38
Can you tell me what did you change to get it accepted?
Just ran the outer loop till d rather than min(d,max(n,k) and then checked inside the loop if n+(d-i-1)/2<=current_answer then simply break as checking beyond it wont give the maximum answer. Because the max n can go upto is 2000 where as d can go till 1e9.
I found that if I run the loop till min(2*n,d) it works.
Yeah same approach in editorial as well... no need of using min(2*n,d) just 2*n is enough
Congratulations dude you became specialist.
Thanks man
As a tester for the 1st time,i feel proud.
i often wonder what exactly does a tester do ? and how do even 1200-1300 rated people become tester
Specialist Time ! I hope .
yeeeeeey
Yo
Hope to become Expert.
Both A,B,C accepted... Hope to see myself Expert.
you are expert
hope is a good thing
maybe the best of things,
and no good thing ever dies.
I will finally give a Cf contest. Lets go.
As a contestant,I want to reach pupil after this round btw
best wishes for every one
Clicked me now, why all are LGM here
As a kawazaki I will participate
I read Kazekage
AbduSaber First tester from Sohag, Egypt :) , remember this name very well -_- .
Hope to solve all the problems!
As someone who has a birthday, please give me a contribution.
Really weak sample for C. Is it fun to see players wa2 again and again?
my last unrated contest
Hope will become expert
unbalanced forces !
Defeated by constructive round. so sad.
update: now I'm defeated by the FST XD
Am I missing something or does D effectively boil down to:
I spent 15-20 mins thinking of how to simplify this to something I could implement without going insane before giving up and going to problem E instead...
Had the same idea, how are you calculating the inversions for relative power shifts? My approach ended up double counting many things
I didn't implement it because I felt it would be an utter mess. As I mentioned I just gave up and went to solve E instead.
You don't need to simplify this to anything else. You can calculate this directly
I mean "simplify" the implementation so I don't go insane implementing this. I seriously doubt I could code this in less than an hour with all the debugging from minor mistakes that are likely to occur. It feels like a 10 mins to think, 1 hour to code problem.
Can u plz explain me your submission for problem B, why it is working ?
Whoever made C deserves lifetime sentence in jail.
was getting WA on pretest 3 :(
me too :(
What's wrong with it, I think it is a really good problem for Div2 C?
beta detected opinion rejected
How to approach B?
Sum of the first occurrence of each character is the answer. Suppose we have s = "abeakf". Then if we consider 'a' is the first character, we will have ["abeakf", "aeakf", "aakf", "akf", "af", "a"]. We only need to care about the first position of character 'a' in s, because if we tried to used the second 'a', the result string will be duplicated (these are "akf", "af", "a")
Essentially, the only difference between strings after "i" operations is the first letter. That's because you can't reach the other characters through these operations. However, that initial letter could be any letter present in the prefix of length "i" of the original string. So, you calculate the number of unique letters in each prefix and then sum them up. That's basically the answer.
Just add the left over length when ever you encounter a new character. for a string abcde the number of substring contributed by letter 'a' => $$$a, ab, abc, abcd, abcde = 5$$$, 'b' = 4... so on.
check the string from left to right, if i th character has not appeared before, answer += n-i
I thought of that in this way. Suppose you have a string "ayush",now if you want to find all the strings of size '4', "ush" will always be there so the string will be "_ush" now for the first character look at how many distinct characters we have encountered before we reach 'u' (2), so there are two possible choices for the first character. Do this starting from size 'n' to size '1'. Hope this makes sense to you!
thanks a ton man!
still don't know why in C, when I tried to iterate min(n, d) times, it gave me wrong answer, since I thought it is enough to make the array big. I used a large number instead like min(5000, d) and got AC.
i did min(3*n, d)
why?? can you explain why calculations after 2*n/3*n will be waste??
Suppose we have:
Then after
(2N-5) + 1
operation (1), we have:where
3N-4 = N + (2N-5) + 1
.Apply operation (2) to score
N-1
in(2N-4) + 1 = 2*(N-2) + 1 < 2*(N-1)
which beats the alternating method from the zero array.This seems much like a case specific example. How can you guarantee that the claim is true for any A and V ?
All the calculations from an initial array
A
only result in a single scoring operation before it gets reset to zero.As stated in the comment below, the largest score we can get from a single scoring operation is
N
— assuming every element satisfies the criterion.Calculations taking strictly more than
2N
moves are not better than scoring immediately (ie. transition to zero array; if needed) and then alternating operations 1 and 2, scoringN
.I produced the earlier example to show that in some case, we cannot perform much fewer than
2N
moves either.Oh, I get it now. Thank you so much.
UPD: I would like to explain mathematically (that's how I like to go about it). Let's say you have done operation 1 for the first $$$X$$$ days, and for the rest $$$(D-X)$$$ days, you'll perform both operations alternately. So your total score would be $$$S + (D-X)/2$$$ where S is atmost N. If you had performed alternating operations from the start, you would have scored $$$D/2$$$. Now, my prior answer is better only if:
Hence, you will get the most optimal answer in the first 2N days because S could be atmost N.
You can't get $$$d/2$$$ in general case because if you start alternating ops from day 1 you'll get $$$initialScore + (d-1)/2$$$. Proof: 238854323
oh I got it, we want to maximize the answer, so one possible answer can be d/2, via doing reset and cash score operations. but to further optimize our answer, we will be checking first at least 2*n days and check whether we can score of n-1 in these days or not. if we can that would give us maximum possible score.
$$$n$$$ is not sufficient. You can raise the answer by $$$1$$$ in $$$2$$$ steps using operation 2 but operation 1 can add upto $$$n$$$, so you need to check for the first $$$2 \cdot n$$$ steps.
I can proof. You actually need to do not 5000, but 4001 (additions). Because if you do 4002 additions and get 2000 score as return, you could have also done 4001 for 2000 score with the strategy — do one addition — cash the score
It don't know understand why you need to do that , main thing is that only 1 such position is possible after 0-array , so brute force till k , then all will give 1
but k is at most 10^9
no , sum of it over all t is given <= 10^5 . re-read the question
No k is <= 10^5
if k were to be 10^9 , then how would it be even possible to take v input
Oh, sorry my bad
why iterating over first k days will work?? is there any proof of it ?
nah , it FST'ed :( it should've been min(d,max(k,n)) , then it AC
I tried to solve B using DP, but got Memory Limit Exceeded at test-case 3, anybody else tried it using recursive DP, or DP?
same bro.
I did it by dp First reverse string s, then we are considering removing from either last or the second last position. Our answer is f(n-2,s[n-1]) f(i,x) = No of unique strings that can be obtained from (s[0:i] + x ) by 0 or more operations f(i,x) = 1 + f(i-1,x) if s[i]==x f(i,x) = 1 + f(i-1,x) + f(i-1,s[i]) — f(i-2,s[i-1]) otherwise subtraction is to avoid double counting
I used recursion, but not DP. First submition failed as I tried to save all possible subsrings https://codeforces.net/contest/1917/submission/238697805. And the next attempt was successfull when I decided just to increment answer https://codeforces.net/contest/1917/submission/238704078
I tried that too I reversed the array and used a stack dp but when I calculated the space complexity I was kinda convinced it would give me MLE so I tried a different approach
how to solve 'B'!!!
you can observe something from enumrating the resulting substrings
the resulting substring always is (a letter + a suffix of the original string) or its one of the letters on the original string that mean if u have abcd the resulting substrings will be: a b c d ad bd cd bcd acd abcd
as u see above you need to calculate number of different substrings containing last elemnt number of different suffix containing last two elements and so then sum them
calculate number of unique characters u can match with each suffix with an efficent approach ( use frequency table)
for every suffix[i] from n-1 to 0 :
my submission here
when you are doing
cnt+= m[j] — i;
Are you removing the double counts of the same character?
yeah, count only once
what happens if you submit right answer twice for pre tests?
i submitted D twice to avoid tle later.
Your second submission, and its submission time, is used. You are also penalized as if the first submission was rejected.
if your first submission fails? or regardless?
Regardless except in edu rounds
ok thanks.
Can anyone check why my code for C is wrong? I have been staring at it for 1+ hour and couldn't find the problem.
In the last 'for' loop, you are checking for the valid indices only till b[j]+1. You need to check the whole array.
Oh my bad, that was a last 15 seconds desperate attempt, I meant the one before that where I have b[j] instead of b[j]+1.
i think when u added to the first b elements in the array, you checked if an element became "good" meaning that a[i] = i but not if an element is now no longer "good"
Ohhhhh I didn’t check for good elements after b[j]. So sad. Thankss!
C is greedy af
I have skill issue.
The problem set is crazy :)
Recently all problems sets are very nice.
yes quite intuitive one. ig they want to make special ending for 2023.
D always getting wrong answer on pretest 5, what a sad Christmas Eve :(
BTW, could anyone please tell me what's wrong with my code 238736754 ?
Oh I see, forget to take those power of 2 exceeding ±20 into consideration ...
Not putting N = 2, K = 2 in the samples of E is cold-hearted lol :P
Also imagine debugging WA on E for 15 mins after "handling" this case just to make this fix and get AC ._.
Couldn't solve $$$C$$$. How to learn to notice all, what needs to be noticed?
You don't need to do so. Its just that after you do a reset operation then you can't get score greater than 1 after any number of operations. So its optimal to take a score of one from first element greedily after doing 1 reset operation
Surprisingly, I noticed this.
Lol I noticed it too and didn't solve C. I tried two +- different ways, but both have WA2 on pretests. I was only 10 points away from CM, sad :(
same stuff happened to me sad
I noticed this too but couldn't implement
How many can you get from first reset op?
N points
Here is my solution by the way, which didn't passed probably because of bug in implementation.
Fix an element in array $$$a$$$. I want to know, when it is good, i.e. $$$a[i] = i$$$. If $$$a[i] < i$$$, then after some movements on array $$$v$$$ it will become good, then it will become bad forever. Sounds like scanline. Let's calculate for all elements of $$$a$$$ the segment of numbers of operations of type 1 after which the element is good. Process them in decreasing order. Fix $$$i$$$. Then all $$$v[j] \ge i$$$ change element $$$a[i]$$$. I want to know the position in cyclic array $$$v$$$, after which $$$a[i] = i$$$, i.e. I want to know $$$(i-a[i])$$$-th element of array $$$v$$$ with only elements which $$$v[j] \ge i$$$. Assume, they are in some structure. Let there are $$$x$$$ satisfying elements in array $$$v$$$. Then I need to traverse the whole array some number of times, and them some prefix. So I need to be able to find $$$k$$$-th element. I can do it with Cartesian Tree (Декартово Дерево), or with "indexed set" (google "cses.fi Josephus Problem II").
div1 difficulty
not actually
more difficult than usual div2 rounds
I don't think I think A,B,C were just like they always are, maybe C was a bit tricky but it's core idea was very easy to notice
Can someone pls explain an approach for C?
My English is not good,in my opinion,the sequence is like stairs,because it can be added to ans when it equals to it position,so every time you do opreation [1,b[i]] +1,it will break the stairs,so if 1-n is 0,only 1 or 0 can be added to your ans after several +1 opreation. To be the best,you can do opration 1 once and do opration 2 once.In this way you can add 1 to ans for two oprations. after understand it,you can make a brute force on array 'a' to Calculate the best ans. it will be allowed on O(n*n) , you can according to my ans 238725053. I Hope i can help you.
Thank you much. I understood your solution) But there is one question. Why do you brute for i <= min(k, d-1). Why not further?
oh god,i'm wrong ans on test 26 Hhhhhhhhhh,i think you need a better person explain for you
Lol)) Anyway, thanks for answering)
Thank you for spoiling the mood for the new year :(
I was supposed to be CM, but FST in C spoiled the mood :(
Codeforces
------- NOSpeedforces
---- YESTrue A and B were speedforces couldn't say the same for rest of the problems
why we need to check 2*n instead of n in C?
really? how do you know
The max score u can have before 1st reset is n. In 2*n days, using the reset operation u can increase your score by n.
ty!
Yes because if it doesn't get give better result in this range there's no way it will give better if it's more since you can increase the score by 1 in 2 steps. I didn't realise that and checked way more than this by throwing and got Ac
Here is a case where checking up to $$$n$$$ fails:
Only optimal solution is doing op 1 five times then op 2.
After doing op1 5 times the array is [7 2 3 4] and doing op2 => answer is 1
But that is not the optimal solution
[2 0 1 2]
op2 => answer = 0 [0 0 0 0]
op1 => [1 1 1 1]
op2 => answer = 1 [0 0 0 0]
op1 => [1 1 1 1]
op2 => answer = 2 [0 0 0 0]
op1 => [1 1 1 1]
Answer is 2
Did I understood this right?
Doing op2 on array [7 2 3 4] gives 3.
Op2 counts the number of indices $$$i$$$ where $$$a_i = i$$$, in this case 2 3 4.
more like max(n,k)
optimizing knacksap with bitset is uninteresting
I think div2 B should be easier or I'm not participate enough
me too, I felt than C even easier than B.
Please explain why tourist's solution to problem C 238680690 passed the time limit. I think the condition in the
for
loop is doing the optimization, but I do not understand why.d can be upto 1e9 which goes way above the constraint
If
n + (d - 1 - u) / 2 <= ans
then this and the future iterations are useless since they won't improve the answer. And since the initialans
is $$$\frac{d - 1}{2}$$$, any value of $$$u \ge 2n$$$ will be useless. Therefore, this cycle performs at most $$$2n + 1 = \mathcal O(n)$$$ iterations.I get it now. Thanks a lot.
noting to say, but good night
nothing to say, avarage armenian round
min(n, k) gave wrong ans so i submited it with k i forget about k = 1e5 after wrong ans test 3 now waiting for fst :( now +60 will turn int0 -60
You don't get FST because $$$k$$$ is large, you get FST because checking the first $$$k$$$ days is not enough.
bro why is there no pretest regarding this. btw thanks for yesterday's contest problems were really interesting even though i didn't get them during contest but i enjoyed during upsolving them
I missed the "even", I would have been able to solve it if I noticed that. Now I think I have a working solution for the odd n. Could have been a nice E1 and E2 problem.
Yes, I didn't think a lot about odd $$$n$$$, but yes it's solvable (check Bonus in the editorial for the problem E)
Ohh What fresh hell is this !!
Really feels bad when you misread the problem.
For C I have an Idea, You can just keep doing Op1 till you get the max score out of it. Than hit the reset button i.e. do op1 and op2. So finally (mx_score + (d — op1)/2)
And this came after the contest is over. :(
couldnt make this work ( 238728699 ), wasted 2 hours
i mean you need to manually brute force operation 1 for k times. to get this
hm, i do not get why. Please prove?
As the score wouldn't increase more than 1 in 2 ops (doing op1 and then op2) after we have arrived at [0....0] array. So the task is to get the max score until we arrive at this 0 array.
Ah, true, misunderstood your statement
But there was one test case 26 where many people got fst with this approach
Attaching my sol for your understanding 238747957
I got fst with same approach at test 26. Really hurts bro
This contest was OVERKILL for me :(
Can anyone tell me whats wrong with my code for Question B? https://codeforces.net/contest/1917/submission/238702690
try this case:
daadc
B was tough to understand that the second occurrence wouldn't affect the answer but will be counted.
Why did my solution to C pass? I don't understand why it works.
C became a scam
weak pretests for C
waiting my c to get FST on test 26 :)
Can anyone tell me what's wrong with my code for task C? I have WA2 and O(n * log^2 k) asymptotics. 238736328
You guys were solving B with a set?
simple observation of first and last test cases: in first — aaaaa all chr are same and ans is 5; in last -abcd.... all chr are unique and ans is 210;
so we can assume that initial ans should be sum of 1,2,3..n, and we need to subtract some value when we have same characters: so first test case ans is 5 (15 — x) x is 10 here right, and for last is 210 — 0. and if you continue you could find this x calculating from similar chr in s
But why my approach do not work for summing up the diff initial char and last occured char using map
I did solve using a set. Code
Yeah there's like a couple hundred (?) copy pasted solutions like this
Could you explain why counting pairs?
Consider the string
abcdef
.I just wrote a tree describing all the possible strings. Something like this:
At length 5,
cdef
is constant. ifa
andb
are the same, then there is only 1 string possible. else 2 strings are possible.At length 4,
def
is constant. Ifc
andb
are the same, then there is only 1 string possible. else 2 strings are possible. Ifc
anda
are the same, then there is only 1 string possible. else 2 strings are possible.At length 3,
ef
is constant. Ifd
andc
are the same, then there is only 1 string possible. else 2 strings are possible. Ifd
andb
are the same, then there is only 1 string possible. else 2 strings are possible. Ifd
anda
are the same, then there is only 1 string possible. else 2 strings are possible.so on...
Calculate for each length and sum them up in answer.
PS: Fixing current character and comparing with previous seen characters is what I've considered as pairs.
So we already saw ef then we need to add pairs,
Then we saw def
Then cdef
and so on.
So your soFar set is describing this phenomena
Yes, for example: at length 4,
i=2
current character isc
and it's compared with previously seen charactersb
anda
.Congrats to guys who solved C! And I have a question, can we approach to this problem in this way, so everyday we compare two values: either we choose first option (cnt of all a[i] == i+1) or we go with second option to increase a's values (cnt of a[i]+1 == i+1 for i in range(0, v[day]) and compare this two values. And we implement it to every day. Is this correct approach?
Why so many solutions fsted on C?
They simulate the process from $$$1$$$ to $$$k $$$
However we should simulate from $$$1$$$ to $$$2n+1$$$
Can you explain why $$$2n + 1$$$?
If we do $$$x$$$ updates before getting the score $$$c$$$ in the $$$x+1$$$th step , the total score is $$$c$$$
But if we perform the operations normally (for a 0-array) the contribution will be $$$ \lfloor\frac{x}{2}\rfloor$$$
Than it is optimal to make updates in which $$$n\geq c\geq \lfloor\frac{x}{2}\rfloor$$$
Is it because I would have gained $$$n$$$ points in $$$2n$$$ days if the array were reset to 0. The maximum I can gain from an array is $$$n$$$ points and doing it beyond $$$2n$$$ days is wasteful.
min(2n,d) may be greater than k.
I thought that was kinda obvious
I love this round.
I love the super-weak pretest in C, which make me fst.
I love the interesting problems C and D, which made me stuck in implementation and debugging.
I love the random constructive problems taking the place of E and F, which makes the diffculty distribution so unbalanced and weird.
Oh. How I love it.
F is not constructive and implementation of C is very short. About weak pretests, I'm sorry.
Thank you for the weak test cases for problem C.
Now I can reach Expert with the help of FSTs.
By the way, thank you for the awesome round!
really bad the so called testers.
.
I was to reach Master without the help of FSTs XD
Anyway, congrats!
I wasted 15 minutes because I put n instead of 2n as the limit of days to use second op in C, but least my n log²n D didn't TLE'd and I'll need to use magic to become purple again :)
my color changed twice in 2 contest :D
Not inserting a test into the pretests for one of the most possible error patterns in C is a bad Christmas gift.
c
A to C was fine. but D was too much
its 2300 problem ;[
Please debug my code for problem D https://codeforces.net/contest/1917/submission/238781581
actually 2n days will give n points so if we waste 2n days then automatically we will get the max value i.e. n so if we are acquring n points after 2n days it is a waste its better that we just do the second operation then
yo that makes sense, thanks
worst round ever
Merry Christmas everyone!
Thanks for round! Tasks were really cool.
Beautiful problem F! Thanks!
To count the number of inversions, distinguish between the inner inversions and the outer inversions : here, the inner inversions are the pairs $$$(i, j)$$$ lying inside a block of length $$$k$$$ (the $$$a_i$$$ that are generated by the same $$$p_i$$$). This is easy to calculate, but for the outer (other) inversions : you need to find all pairs $$$(1 \leq i < j \leq n, 1 \leq i_1, j_1 \leq q)$$$ such that $$$p_i \cdot 2^{i_1} > p_j \cdot 2^{j_1} \Leftrightarrow p_i > p_j \cdot 2^{j_1 - i_1}$$$. Solving the problem when the difference $$$2^{j_1 - i_1} = 2^C$$$ is fixed can be done in $$$O(n \log n)$$$ (counting the "inversions" and multiply it by the number of pairs $$$(j_1, i_1)$$$ such that their difference is $$$C$$$, that is in fact $$$k - |C|$$$), and since there are $$$O(k)$$$ possible differences, we solved the problem in $$$O(nk \log n + k \log k)$$$, which is not fast enough. Let's detail what we did for the inversion part because it will be useful in the future : we store a set in which we will add progressively elements that will calculate for a fixed $$$j$$$, the number of $$$i < j$$$ such that $$$p_i > p_j \cdot 2^C$$$ : in particular we will iterate $$$j$$$ from left to right : for a particular $$$j$$$, we count the number of elements in the set that are $$$> p_j \cdot 2^C$$$ by applying upper_bound (this number of elements will be added to the answer), then we will insert $$$p_j$$$ in the set. That will efficiently calculate the desired answer. Now let's take a look at $$$p_j$$$ and notice all the upper_bound that we will do involving $$$p_j$$$ : they are upper_bound, and their keys are different, but the set is the same (each time, the set involved contains all the $$$p_i$$$ ($$$i < j)$$$). So now we can think differently : we store an array $$$repC[-k \to k]$$$ so that $$$repC[index]$$$ contains the answer for $$$C=index$$$. We will iterate $$$j$$$ from left to right, keeping track of the set $$$(p_1, \ldots p_{j-1})$$$, and do the respective upper_bound where the keys are of the form $$$p_j \cdot 2^C$$$ and add the respective elements to $$$repC$$$. However, notice that $$$C$$$ cannot be too big $$$(>18)$$$ or else no $$$p_i$$$ can be greater than $$$p_j \cdot 2^C$$$. (so we don't have to count anymore) Notice also that if $$$C$$$ is too small $$$(<-18)$$$ (let's say $$$C'$$$); at some point $$$p_j \cdot 2^C$$$ will be $$$0$$$ and so $$$j - 1$$$ elements will be added for each $$$repC[C < C']$$$. How can we do ? Since we don't have to answer instantaneously (we can answer offline), we can say that this is a query of addition of $$$j - 1$$$ elements to all $$$repC[-k \to C']$$$. Calculating after the respective $$$repC[index]$$$ is easy, and thus we are done with a complexity of $$$O(n \log^2(n) + k \log k)$$$. The neat part with this solution, though slower than the intended solution, is that $$$p_i$$$ doesn't need to be a permutation of odd numbers !
Here is my code : 238726631
I did the same thing with using ordered set 238746529. But I'm getting TLE.
I don't understand the n*n — 2 ?
where?
Thanks , it is indeed very helpful.
In Problem C: Checking over the v sequence only once was enough to pass pretest. At least this major corner case should have been included in pretest which is in test no. 26 :(
Can anybody tell How Problem B can be solved using DP since in the problem itself the tag is mentioned of DP
test 26 of problem C is like the grinch :(
I liked Problem E very much, thanks _LeMur_! I upsolved it. My idea with 6 was following: if
k
is small, then print the diamond of 6 ones on the first 3 lines of matrix, then fill squares of 2x2 on the following lines. And symmetrically opposite: ifk
is large, then subtractk = n*n - k
, and do the same with inverted bytes.Somehow my Perl code is running notably fast. Submission — 238764454.
Problem E-bonus (
n
can be odd):If
n
is odd andk
is odd, then initially we can putn
1's so that no two of them are on the same column or row. Simplest way — fill the diagonal. Then we need to fill remainingk-n
1's into the matrix. Notek-n
is even. Ifk-n
is divisible by 4, then we can fill matrix with(k-n)/4
squares of four 1's, otherwise we need to fill one additional "diamond" of 6 ones. No need to put squares and "diamond" compactly if we invert bytes to makek --> n*n - k
ifk
is big.I did it with greedy "multi-line" search and replace (it is slow). I believe code is correct (238861870).
Yes, Nice! It's correct. I am happy that you liked the problem :)
Hi, Codeforces There is more cheating in this round
look
https://codeforces.net/contest/1917/submission/238732112 https://codeforces.net/contest/1917/submission/238726346 https://codeforces.net/contest/1917/submission/238731850 https://codeforces.net/contest/1917/submission/238737489 https://codeforces.net/contest/1917/submission/238721843
i solved C but it's wrong in testing at 26th so the people who cheating make our rate more down
UPVOTE PLEASE "))
C is really good but i didnt solve it during the match TwT
please anyone tell me the problem in my code for problemm D: submission link: https://codeforces.net/contest/1917/submission/238781581
Guys,my rating for recent educational round was taken back.Is there anyone who is having the same problem?
That's because you cheated the contest ...
It seems the same incident happened for you.Have you received the email of plagiarism detection too?
Nope, I have my rating .. !!
Got it. Have you ever received such mail earlier?
I love Roll_Num_44