Hi Codeforces!
I'd like to invite you to join Codeforces Round #446 which will be held on November 17 at 17:35 MSK.
And yes it is rated.
The contest is prepared by Omid Azadi (omidazadi), Mehrdad Saberi (Batman), Arshia Soltani (ckodser), Aryan Esmailpour (Aryan) and me (I honestly didn't do anything).
And also thanks to Mahdi Amiri (Amiri), AmirReza PoorAkhavan (Arpa) for helping us, Weihao Zhu (Tommyr7) for testing the round and Nikolay Kalinin (KAN) for round coordination and Mike Mirzayanov (MikeMirzayanov) for awesome platforms Codeforces and Polygon.
You will have 2 hours and 5 problems each division.
Contest theme will be about Seven Deadly Sins but the statements will be short and brief.
The scoring distribution will be posted soon and good luck and stuff.
Update 1 : The scoring for both divisions is 500 — 1000 — 1500 — 2000 — 2500.
Update 2 : The round is over. Hope everybody had fun and enjoyed it. And as you can see the round is rated so yay!
Top 5 Div1 participants :
1.jqdai0815 (The only one who solved all problems)
3.dotorya
4.SkyDec
5.ksun48
Top 5 Div2 participants:
1.shoob
3.SLLN
4.fdoer
5.dl1997
The editorial is posted.
Do you mean the anime "Nanatsu no Taizai" or just the typical Seven Deadly Sins? I hope it's the anime one! :D
Sorry but it's the typical one :(
Mahdi_Jfri If you didn't do anything so why did you write the announcement?
I wrote it so now I have done something!
Oh, it seems Mahdi_Jfri have done a very important and great thing. I think so too.
Due to CF Round #444, #445 was unrated, everyone is hoping that this contest will be rated. I hope so too. There’s a risk of getting 1000+ downvotes in this announcement if it is unrated, as far as see the last 2 contests. So I think less than half can have courage to write an announcement if they’re writer. So I think he is brave, and he make great contribution.
But I hope this contest will be rated with 99.99999999...% = 100% probabilities.
why are you always whining about downvotes. please get over it.
No. But I think that mentioning about upvotes/downvotes is important to support how much contributed it is about writing today’s contest announcement.
Btw it seems there are many other way to support his contribution. (Writing announcement is originally a type of contribution.)
Yeah we really don't care about that.
Is it rated?
For now yes :)
Hmm..
The "greed" problem will probably involve greedy technique as its solution.. or it might be a trap.. :|
Just a prediction lol~
Haha :)
"Wrath" will actually not be a problem, it's just the feeling that you have when the servers go down mid-contest.
I hope it won't look like this
We hope that this round will not become unrated magically.
UPD: Ok, ok... I hope...
It will be enjoyable contest. Because it has a tag best round ever. . .
Previous two round was unrated. Now what should be our expectation from this round????
"Best round ever"
sa1378 is my bro xd he won't betray us
We have a binary random variable X with Bernoulli distribution.
P(X = 0) = 1 - p — probability of an unrated round
P(X = 1) = p — probability that the round is rated
What is the probability that X = 1, given that we saw X = 0 two times in a row?
This sir is a glorious comment.
You deserve my upvote.
(Not that it matters because it has so many down votes any way)
Seven Deadly Sins, I was looking forward to more Arpa and Mehrdad adventures :(
Is it unrated?
we make this unrated!
externalgoal, you are so suspicious. But please, don’t open your solution during the contest... You want downvotes... I know. But we’re wanting strongly, a rated contest. Please don’t open your solution during the contest... please...
Just wrote a piece of code to answer this ultimate problem.
Unrate or riot!
I will sabotage this CF and get a very bad rank for all you guys, because whenever I get a good rank, contest becomes UNRATED and when I get a bad rank, contest is RATED.
Taking one for the Community.
Mission Successful
Is late registration there? I am returning to codeforces after a while — is it there in all contests now?
hi I'm kinda a noob and was wondering what the difference between dev.1 and dev.2 is... would really apreciate it if someone answered... tnx
Okay so div1(div stands for division) is for people with ratings in the range 1900-9999 and div2 is for us noobs below 1900 rating.
Since you haven't played any CF rounds, you will be playing in div2 to get your rating first. Your default rating is 1500 I guess.
Is the CF great now ? :D
After the situation of past CF contest it might be improved enough :)
Good to see "the statements will be short and brief" Waiting for the statements!
Arpa and Batman's contests are always amazing!!! i think this tradition return its value :).
..... ... re ... .....
I like the confidence in the problem-set of this contest
Yaaaay a Persian contest! I hope I can wake up for this lol
Upvote me, please. When I look at my contribution, my mood falls down.
Do not be beggar! Do not look for easy ways!
Just comment wisely and you will faint , when you see your contribution.
said the gray...))
I am not gray (now)...:):):)
Can't agree more, I wanted to say this but didn't dare to do it :( Negative contribution is like saying "Codeforces community will become better without you", and now I started to think if it's true.
Can I have positive contribution like others too?
Foolproof way to increase contribution:
https://snag.gy/X3qRLQ.jpg
What do you mean?
well , all people with good contribution don't wear capes , some just comment in that manner , and magic happens :) :)
Hope that there would be no issues like the last "rated" contest...
Seven deadly sins:
I really like the first one ^__^
Are this names from fullmetal alchemist?)
It is delayed?
Deleted
Why only Iranian guys? Other guys also cool. People though are divided by the nation but to show discrimination on the public site is stupid.
Yeah!!! I love this anime!
Take a look at first comment :(
it would be better an anime
I hope this time it will be rated!
Again rated, again...
Congratulations! So how did you handle it?
Let's wish good luck codeforces servers)
Hope today is the day Codeforces Servers get out of gray
Five Deadly Sins for Codeforces
Asking if it is rated.
Not writing "thanks to MikeMirzayanov" in round blogs.
Underestimating div2-A http://codeforces.net/contest/812/problem/A.
Envying tourist :)
Downvoting this comment :DDDDDDD
my three TOP only one things I have known in this world.
1 the sun. 2 the earth. 3 the only way to change the color of our handles in codeforces.
I hope everyone here to pass this way positively in this contest! Good luck to Everyone!!!
the only way to change the color of our handles in codeforces
When will Christmas come?
Is it rated?
here is the guy who tries to make his contribution -200 .
Fix your damn servers..
Why it is so slow...I submit a code 5 minutes ago…… and now I found I got a WA
Seems like it will be a 3rd consecutive unrated round.
Yep, I have to wait 5-6 minutes for each submission.
Thanks god for short problem descriptions
problem Ds difficulty is inverse of Cs difficulty for the past 3 contests, i think. D is very difficult.
It is really really disappointing that the server issue is still there :/ I mean, how can one enjoy a contest in the current situation where almost every submission takes 5-6 minutes to give verdict, even hacks. It's frustrating :(
It doesn't look like problem div2C has much to do with "Pride".
Have you notice the case when there is more than one 1 in the array? The idea is that the solver can be proud of themself when they come up the solution and forget to handle this.
I do hate problems where not all the corner cases are part of the pretests because it's stupid to lose a whole problem for a particular case. But, in this particular problem, if you proved your solution, you'd easily see this case (now, again, I believe it should be included in the pretests), so it's pretty unlikely for one who proved it to fail on that case. So I'm not taking "their" side, but I just think that you haven't actually solved a problem until you proved it. These corner cases, though, should not cost any more than just an extra submission (after seeing you failed on pretests)
Problem Div2 B TLEd because of slow I/O (cin/cout in c++), and worked well with faster I/O (scanf, printf). Doesn't make it interesting.
Same here. I don't see why the need for 10^6 max value for n (instead of the usual 10^5).
Will this work for Div1B/Div2D ? Output the next element in sorted order for each number. like if array is [2,4,1,3] output [3,1,2,4]. Seems too easy(given the constraints N <= 22) but i cant find whats wrong with this.
try 3 5 6 2
I was nowhere close to the solution but I think maybe n < 22 is for checking whether the condition is true for your logic
Yes, it is.
Wht's the role of a[i]?
Actually it works perfectly. If you choose one subset that does not contain the biggest element from the first array, then there is a map between elements in the first array to a bigger element in the second array (the one it becomes). Otherwise there is a map for a smaller element, so sum will never coincide.
I thinks the n up to 22, was a misleading clue to confuse contestants. I tried to come up with a 2^n dp but completely failed.
Very interesting D.
very good (trolling) name for problem Div1D. I really lazy to code all this cases...
Yes it was so hard for me too.
How to solve Div 2 D/ Div 1 B and div 2 E/ div 1 C?
Div1B
If any repeated elements are present then no solution
Else put b1 = a2 , b2 = a3 , b3 = a4 , ... bn = a1 (Assume a is sorted)
Isn't 5, 3, 4, 1, 2 a counter-example?
yes, array should be sorted first and after that shift.
Maybe i misunderstood smth, what will be the output for 5, 3, 4, 1, 2?
1 4 5 2 3
I mean in his solution
Sorting the array a initially won't change the problem.
[3 1 1] has no solution??? I think [1 1 3] is solution for this input. Am I wrong??
array elements should be distinct so the test case isn't valid!
I understand your solution, but is there any formal proof why it always works???
after sorting a let c[i] = b[i] — a[i] then c[1] , c[2] , c[3] , ... , c[n-1] > 0 while c[n — 1] < 0 and sum of C's is 0 so obviously no proper subset will have sum of c as zero.
Div1C
consider all edges with weights <= C , then any minimum spanning tree (forest) consisting of these edges will have the same set of connected components
So have an offline solution where for each i from 1 to MAX , you first check if for all query edges with this weight if they can be added , if not then mask this query with "NO". Then forget these query edges and add actual tree edges with weight i.
This works because of the reason mentioned at the beginning.
"any minimum spanning tree (forest) consisting of these edges will have the same set of connected components"
Can you please elaborate on that a bit more?
TIA!
Does solution to D use this?
Of course.
My solution which I hope is correct (it passed the pretests and it really makes sense) doesn't involve that observation (even thought at some point I made it and hoped it'd help, I didn't find it of any use)
Heck test for Div2C:
3
6 10 15
What will be the answer for this case? My code prints 5 for the former test case you posted. For this test case, it prints 4.
4
4 (If my solution is correct :p )
4
[6, 10, 15], [6, 2, 15], [6, 2, 1], [6, 1, 1], [1, 1, 1]
If the gcd of all is not 1, it's guaranteed to be able to make some element to 1 within (N-1) trial.
How to solve D? I was thinking in terms of bitmask and reversal of highest bitcount numbers.
If the sequence is sorted, (I call it as a1 a2 a3 .. an), then the B seq is a2, a3,a4,a5..an,a1. Then just for every element in the A sequence, print the smallest element that is bigger than it.
What if a isn't sorted?
Sort, solve, unsort back
got it!
yay! Finally Rated Round ! I need +1 rating gain for becoming specialist again , and finally I will be specialist once again. :)
My attempt today in a nutshell. (Div2C/Div1A).
Well, many thanks to the problem setter xD (No, really, this is the best pretest set I've ever seen — hacking comes in so many levels :) )
The tag does say "best round ever" anyway
Meow, precisely confident <(")
Then the feeling when the TL 2000 ms and the participant code runs 1996 ms(
Will this work for Div1B/Div2D? Output the next element in sorted order for each number. Like if array is 2 4 1 3 print 3 1 2 4
That's my solution and it passed pretests.
Yes, and it's easy to prove. Let's consider for convenience the permuted arrays a and b:
If we take any subset that doesn't contain the last element, the sum on the lower side will definitely be bigger. So, we'd only have a problem with those that contain the last element. We need to balance a difference of aN — a1 with a subset of the values a[i + 1] — a[i] for 1 <= i < N. The nice part is that all those are positive and only if we choose them all will we be able to balance the differences (otherwise the total balance from the second part is still too small)
I understood the proof when subset doesn't contain the last element. I didn't get how you proved the sums will be different when the subset contains the last element. Can you explain it again in more detail ?
Let 1<=i1<i2< ..<iK<N be the positions you choose so that you get equal sums, when adding position N to these. You must have:
a[i1] + a[i2] + .. + a[iK] + a[N] = a[i1 + 1] + a[i2 + 1] + .. +a[iK + 1] + a[1]
By moving terms from a side to the other, you get:
(a[i1 + 1] — a[i1]) + (a[i2 + 1] — a[i2]) +... + (a[iK + 1] — a[iK]) = a[N] — a[1].
Now, on the right part you have a positive constant. On the left part you can choose for each position j with 1 <= j < N whether j is part of the chosen subset, and in the same time, whether you add a[j + 1] — a[j] to the sum on the left side or not. All the possible values of the form (a[j + 1] — a[j]) are positive. So choosing any of them increases the sum. Now, if you choose them all, you get (a[2] — a[1]) + (a[3] — a[2]) + ... + (a[N] — a[N — 1]) = a[N] — a[1], which would be alright, just that you can't choose all the indices. So you need to give up some of them. But since all of them are positive, giving up any of them will lead to a lower value on the left side, which means that unless you choose all the positions you can't get equal sums, which is exactly what you need
Yeah , Got it. Beautifully explained. Thanks a lot :)
If you don't mind Sarvagya, Can I ask you something?
You have not given any contest from quite sometime and after each contest ends, you ask "how to solve problem X?" Do you give contests with a fake ID? Because it seems so. If yes, why?
Please don't ignore. Thanks.
Why would I comment with this account if I am participating with a fake one?
Why would you comment "how to solve problem X?" just after any contest ends if you haven't participated or haven't seen the problems?
And seeing problems without participating during contests make doesn't makes sense.
Huh, I do this all the time — I just do not have enough time to do any Codeforces Round until recently so I just read the problems and ponder(?) about them in my free time. Also I want to improve my thinking speed for ACM (I rarely code — my code sucks) so it really helps. I also have friends who read problems and seek for solutions without participating to gather as many ideas as possible (lol idk how it works but oh well).
Not trying to 'solve' the case or anything, just pointing out it is not that abnormal at least for me.
How to solve div2 D/E ?
How to solve div1.E ? I am not good at this kind of problems, but anyway, nice contest and nice problems.:)
I see it can be solved by generating function.
Author's solution is completely different unfortunately we didn't predict that it can be solved by generating function :(
Can anybody explain me why my first div2 B submission got tle on test 9 having the complexity O(n) and using cin — cout, but after that i used scanf — printf and my second submission got accept. Why?
cin/cout is by default synced with scanf/printf, which caused the I/O process in C++ submissions to be pretty slow on large input if we don't switch of the sync. Personally, I'll insert
ios_base::sync_with_stdio(false);
on any source code files I create to switch off the default sync.cin/cout
is slow.If you want to use
cin/cout
, include these three lines at beginning of yourmain()
function.Cin/Cout is slower than scanf/printf. Keep it a rule of the thumb when n >=1e6 the IO becomes the bottleneck. Use scanf/printf or instead http://codeforces.net/blog/entry/10297
thanks for advices and explanations
Thanks for nice problems! Is there any neat way of solving Div1D? I tried some long and ugly dp which took 1hr to code but don't even pass samples
My solution (it's different from author's) uses dp on tree and I can't say it's ugly. I will post a link to my submission after the system testing ends.
Here is my solution: 32407269.
I wrote this program for Div.2 B but still got Time limit reached in pretest 9: could someone please tell me whyyyyyyyyyy?
include<bits/stdc++.h>
using namespace std; int main() { int n,s=0; cin>>n; int arr[n]; for(int i=0;i<n;i++) { cin>>arr[i]; } reverse(arr,arr+n); bool arr2[n]; for(int i=n-1;i>=0;i--) arr2[i]=true; int count=0; int last=0; for(int i=0;i<n;i++) { if(arr2[i]==true) count++; if(arr[i]!=0) { if(last<=i+arr[i]) { for(int j=last;j<=i+arr[i];j++) arr2[j]=false; last=i+arr[i]; } } } cout<<count<<endl;
}
sorry for that....
cin/cout
is slow.If you want to use
cin/cout
, include these three lines at beginning of yourmain()
function.tnx man :D
Great thanks for the short statements, this just made my day :D i hope all setters do the same
Also for the interesting tasks, enjoyed doing them...
Why break the consistency, let's make this round unrated! :D
How to solve div2 C?
Let's suppose array contains count number of 1's.
You have to find the minimum length of subarray, whose gcd is 1, let's say, it is p. First you have to create one 1 using (p - 1) operations on that subarray. Then, change other non-one elements into 1 also using (n - 1) operations. So, ans = n + p - 2.
Can Anyone Explain How To Solve Problem B Div2.
You need to answer whether the i'th person will die in O(1).
He will die if there is some other person to the right j > i which can reach the i'th person.
Just take input 10^6 element using cin>> cause TLE in problem B. -_-
I think this is a good thing to teach people how to use their's language from time to time =)
What's the motivation behind the constructive algo for Div2D/1B? Like, how did you arrive at the thought of trying exactly that algorithm?
Is it normal to lock after getting hacked?!!!! KAN MikeMirzayanov
Race condition! :P KAN
At least you got revenge.
fofao_funk Yeah, it tasted sweet! xD
Problem Div 2-D is overestimated !! it should be categorized as B. Also the constraints is so tricky (22 numbers?!!), that tends my way of thinking towards something like backtracking and bit-masking. But it so easy just sort the numbers and replace each one with the next element after sorting.
Whatever I didn't take care that the numbers will be distinct and I have known that after the contest.
Actually if n > 22 then we can't check if the participant answer is correct or not.
Well, i believe they can be slightly (~40) more if you would write meet-in-the-middle knapsack in checker (however this only increases possibity of incorrect checker and doesn't really change anything).
That could have been another task ;) As it was with D,E here: https://arc079.contest.atcoder.jp/assignments
Noob jafar
wide author
:(
Actually there is a way — you could specify a way to generate testing subsets and provide a number — for example first X subsets in lexicographic order. You could also provide some additional number of subsets given explicitly — to verify some random subsets on larger sequences.
Long check :(
can someone plz tell me how to solve div 2 D and why that works
hey , congrats to moejy , he is the second on codeforces now :D ,again,
Thanks a lot for this sweet contest! Really glad it went well, unlike 2 previous ones.
Tests to div1 C might have been better. Accepted submission: http://codeforces.net/contest/891/submission/32408123
Fails almost example test (replace vertices in first edge):
And here is my accepted solution.
Which fails the following test:
Hi guys! Unfortunately, Codeforces API is down, that is the reason why CF-Predictor doesn't work.
You could find last saved snapshot here: div1 div2.
UPD Official rating has been updated, but API still down.
Both snapshots are of div1.
Great problems with short statements, I really enjoyed it, thanks!
can someone plz tell me how to solve div 2 D and why that works
My solutions were skipped because somehow someone copied my solution for Div1-A.
http://codeforces.net/contest/891/submission/32389480
http://codeforces.net/contest/892/submission/32400911
I have no idea how this happened. And no, I didn't use Ideone. KAN, please fix this!
I see there is a flaw in codeforces to disqualify someone: when you lock a problem, it is possible to view roommate's code, then send it to other :)
Damn, you're smart, brilliant observation :) I wouldn't come up with it by myself.
Is there an easy (no matter if allowed by rules or not) way to get that code without retyping it? Anything easier than text recognition programs.
I already thought that I got hacked since I didn't use Pastebin/Ideone either. And now it is like 50/50 :)
P.S. I don't remember how it works — can one read codes by all contestants after locking (without being able to hack them), or only codes in his room? None of the coders in my room have problem C locked, so in case you can only read codes in your room — for me the reason should be different.
You can only read codes in your room.
I think that Flash applet gets the code from the server in a text representation and then renders it in a non-copyable widget. Will try looking into this.
IIRC you can read the code only in your room. At least with the current interface.
Hmm, looks like you can also disqualify yourself if you are doing poorly in contest and don't want to lose rating: just submit your code again with fake account.
Is this how it works? :)
Cheating should result in account removal, to prevent this.
That might work only if you can be sure when someone has cheated. As you can see, 2 red coders that most likely haven't thought of cheating were caught by the system. Even if any of them used ideone (which they didn't), do you think that because of a mistake (not of a desire to cheat), they should have their accounts removed?
I've always thought that an interesting method to try to deter cheating would be to consider the cheater as earning a score of 0 (or maybe -INF) in the contest (and consider all of his/her submissions as incorrect). This way, cheaters would still lose rating, which I think may do a better job preventing cheating.
but wouldn't they have to solve the problem to lock it?
My solutions were skipped too because somehow the SAME guy (Helli.code) copied my solution for Div1-C. LoppA/32401950, hellicode/32405243. (Link for his submission is broken right now).
I don't use Ideone too, I coded and tested the program in my computer and only submitted to codeforces. I also have no idea how this happened.
Well, we will look into this and think what to do. Btw, these submissions are completely identical, so I doubt someone retyped it.
This time we will roll back ignores for first submissions in a group of identical. After it we will recalculate ratings. But from this moment we will notify if someone submissions look like your and in case of repeated notifications we reserve the right to apply penalties.
I feel that if someone did deliberately retype their submissions in order to sabotage them, those malicious guys would probably just do it to the same group of people again to damage their rating, especially upon reading this comment so Codeforces should probably be more careful of that.
Getting into the same room, then retyping without a single mistake, indentation etc.? Seems unlikely.
For me it seems more likely that passwords were leaked or there is another flaw in this website.
I get the same trouble here
the same trouble
http://codeforces.net/blog/entry/55843?#comment-395662
Something is not right. User I_love_Tanya_Romanova does not appear in standings, even though he participated in the round and hacked my A submission.
Edit: Ok, looks like he was disqualified, but shouldn't all his hacks be removed too? They should be removed from final tests if they were added. KAN could you please comment on this?
Maybe all submissions in the round were opened for viewing? I can't believe red users cheated.
I got disqualified since my code for div1C matches with code for div2E by user best.code. I don't know exact way how it leaked yet :)
Do you think the part about hacks is really that important? As I recall, out of my hacks three were like
And one was something like
I don't think they aren't covered by model tests and other hacks :)
"I don't know exact way how it leaked yet :)"
Perhaps you should ask EdwardSnowden.
There's one way to do that:
Or have a friend in Div1 to do steps 1-3 for you.
It was mentioned that no one else in his room locked C.
In that case Codeforces should just start using HTTPS
best.code copied my div1B I don't know exact way how it leaked yet too
Thanks for the short statements:) But there were several mistakes in russian version
Fullmetal Alchemist ^_^
10 minutes before the end until the contest, I pasded problem B by using priority_queue. T_T
I used segment tree in case of I can't pass problem B...because at that time I was sleepy and I couldn't come up with a good way to solve it(I even submit a wrong answer solution using dsu trick in segments...)
Now I think everyone will take me as a fool because I write a segment tree in a div.2 B problem...
In Round#419 Div2 ,I used Segment tree for B,too.I thought for 1 hour and submited for 5 times,pretest passed.Unluckily,I fst in the end(TLE)...
orz xlj
I think we should always come up with a suitable solution for one problem,instead of just writing data structures or some other things without deeper thinking.But sometimes these "force" methods can save us in some condition...
.
I will sabotage this CF and get a very bad rank for all you guys, because whenever I get a good rank, contest becomes UNRATED and when I get a bad rank, contest is RATED.
I will sabotage this CF and get a very bad rank for all you guys, because whenever I get a good rank, contest becomes UNRATED and when I get a bad rank, contest is RATED.
I will sabotage this CF and get a very bad rank for all you guys, because whenever I get a good rank, contest becomes UNRATED and when I get a bad rank, contest is RATED.
Hey Don't always think like this
You are not weak as you got good rank sometimes,but bad rank warns us more about our methods of thinking,coding and so on.It's just a coincidence that you got good rank but the contests are unrated.Instead of just complaining for the bad rank,you should believe in yourself and review the mistakes you made in some bad-ranked contests,then you will learn more and be easier to get good rank next time.
UPD:OK maybe you all don't like to encourage others or he was just joking = =
can someone please find why i am getting TLE in test case 9 in questuion 2. my code. and when i remove macro rfl it gets accepted! please explain.
include<bits/stdc++.h>
using namespace std;
define fl(i,a,b) for(int i=a;i<b;i++)
define rfl(i,a,b) for(int i=b;i>=a;i--)
define int long long
main() { int n,count=0; cin>>n; int arr[n]; fl(i,0,n) cin>>arr[i];int sum=0; if(n==1) { cout<<1; return 0; } rfl(i,1,n-1) { if(arr[i]>sum) sum=arr[i]; if(sum>0)count++; sum--;
}
Sweet revenge by ovis96 xD
Can someone help me with Div2D/Div1B?
Maybe I have misunderstood the problem, but judge says: "wrong answer there are 2 sets with equal sum".
Input:
1 3 4 5 2
My solution:
3 4 5 2 1
pick second and last element of each array, 3 + 2 = 4 + 1
Thanks! I was thinking that it should be some interval like [1, k].