Hi all! This round is prepared by me, caustique, el_sanchez, KAN, malcolm. I thank Gerald, who has organised our work and helped us with tricky situations, MikeMirzayanov for the system of organasing contest Delinur for the translation.
I hope that all problems will be OK and everyone will find intersesting problem for him/her.
Winners:
div1:
div2:
I apologise for the mistakes in statements. I will be more careful in the next time.
scoring system?
Standard. Score distribution is not defined at the moment
The word is actually "standard". I've seen it get misspelled a lot on this site, it's about time I let people know how to spell it correctly.
[http://www.oxforddictionaries.com/definition/english/standard] [http://www.merriam-webster.com/dictionary/standard]
Thank you =)
This is a common bug for all Russians :) In fact, the word "standard" in Russian is spelled like "standartny" with "t" but not "d". And even if you know the correct English spelling sometimes it may be hard to remember the correct ending.
Cool, thanks! Now I know why it keeps happening! :)
Oh,I smelt some special tricks..
I think we should careful with problem A. :)
yes ı misunderstood problem A. I thought digits bigger than k werent allowed :(
Yes. And I was spend for 15 minutes to thinking about sample test 2 util the announcement appear
I guess the problems will be short and interesting. Like this blog.
You know what's interesting?
Did you know facts are considered to be interesting. So this proves there are things that are universally interesting.
I don't understand your mind clearly. But I think interesting 's different with every pepple. With me, that 's tricky test and many solution has ben hacked! O_o
hope problems will be good..
don't even hope that problems would be so easy for you
A strange comment for a gray one...
Guy that writes gray code?
No.Guy who has the rating very small(of colour grey).You are purple, I guess
giygctr gotcs metrr o'le!!
wut?
giygctr gotcs metrr o'le!!
why is today's problemset so hard?
This round is similar to Round 144 Div1 результаты This round prepared by tunyash too.
look at Antoniuk at div. 1. He worked well :D
P.S : He is in last page.
this exam very suck for div 2 everyone have solved A and B and no one able to resolve the C , D , E
I can't agree with U. Problem C was just an exercise for Range Tree, main problem was to realize it(I wasn't successful in it ._.).
sum(x,y,z,t)= (s[x]+...+s[y])*(s[z]+..+s[t]) = a
you can solve this by fixed [x] and [y] and pre calculating [z] and [t]
nothing about Range Tree i guess.
Damn, U're right, it's easier way :)
Does anyone knows the 4-th test for B?
I think, something like — 5 0 0 0 0 0, answer is 5
I think 5 0 0 0 0 0 will output 2
No:)
0 + 0 = 0 .. so 5 zeros will yield answer 5
If anyone can tell me what is the pretest 3 for problem A div 2 I would be very thankful...
Show your code.
Here:
5162244
Upload it here.
Here:
http://pastebin.com/YhY9af03
The digit in number can repeat.
It's false.
UPD: It's true.
k goes from 0 to 9....
Why should I return false like that if I am already doing the repeated number exclusion with the set?
EDIT: By doing the vv.size()==k+1 I am assuring that my function also returns correct values, yes or no?
I don't understood problems.
What if k == 0 and numbers on liste equals to zero too? Your programm return automatically 0 when k == 0 But for this input:
It should return 1 instead of 0
http://codeforces.net/blog/entry/9625#comment-151387
This input is invalid (1 <= ai <= 10^9)
The test would be like this:
Answer should be 1.
No leading zeroes are allowed, from my understanding:
"The first line contains integers n and k (1 ≤ n ≤ 100, 0 ≤ k ≤ 9). The i-th of the following n lines contains integer ai without leading zeroes (1 ≤ ai ≤ 10^9)."
So that wouldn't be a valid test....
No leading zeroes are allowed, so it can be like this:
Answer still should be 1.
MISTAKE: k-good number should contain each digits no more than k, but if number contains each digits no more than k AND other digits more than k, it still be k-good number.
case 2 0 0 0
answer =2 your code gives 0
Numbers can't be 0.......
1 0 10
interesting observation about k == 9, but k == 0 ...
Does anybody know what's the 5-th tests for C ? I would be very thankful
0 00 и 0 110
aaaand the naswer is 9
Kind of: 0 005 answer: 27
i am so f**ing idiot
Div 2. Problem C
The moment I realized I can't think better than O(n^3logn) or O(n^4) for MaxSum in a rectangle.
That was the moment I realized the array contained only digits so I could do it in O(n^2).
Most enlightening moment I got in a contest.
I had an O(n^2log(n)) solution that I couldn't finish coding. I'm not sure if it is correct though, because it uses O(n^2) space.
how do you do n^3logn?
where are the editorials/tutorial to div2 213?
not posted yet i guess
The bad description of problem D div2(problem B div1) really makes me mad!!!!
I read it more than 5 times and still don't know what are you talking about, until I found the Note at the bottom and read the Note more than 5 times.
How can you use nothing to exchange something?
You should say:
Set x can contain nothing.
Set x and Set y can't contain the same item instead of the shit of "Note that each item is one of a kind and that means that you cannot exchange set {a, b} for set {v, a}. However, you can always exchange set x for any set y, unless there is item p, such that p occurs in x and p occurs in y.".
"John knows that his city has n items in total." Ok, there are n items in the city, but how many items in the market?
For the second sample, why cost two days? why not three days? Input 3 5 1 2 3 output 6 2
first day =
{} -> {1,2}
now assume he leaves
{1,2}
at his home.second day =
{} -> {3}
so now he has all of
{1,2,3}
with him in two days.Thanks, I got it. It's hard to understand this problem of the poor description, but the solution seems not that hard.
Any Ideas for problem C , Div 2 ?
You observe that in a rectangle the sum is (Ax1+A(x1 + 1)+...+Ax2)*(Ay1+A(y1 + 1)+...+Ay2), where x1,y1,x2,y2 are the corners, and the maximum sum of a sequence is 9*n.
Range Tree. U just need to find all x1, y1, x2, y2: sum(x1, y1) * sum(x2, y2) == a. But you should do it smart: 1)Find all x, y: a % sum(x, y) == 0 2)for each of them find all x1, y1: sum(x, y) * sum(x1, y1) == a
It seems like this solution is )(n ** 4 * log(a)(because of Range Tree)), but it is O(n**2 * k * log(a)), where k is number of divisors of a(close to log(a)).
No range tree. You just need to factor n and n is equal to the multiplication of range sums that can be calculated in quadratic time
No.You just keep a vector ap where ap[i]=number of sequences of sum i, i<=9*n. For a subsequence [i,j], if A%sum(i,j)==0, you add at result ap[A/sum(i,j)].Take care at the case when sum(i,j)=0 and when A=0
Anybody home ? someone start system testing
In problem A
When writing
Let's call a number k-good if it contains all digits not exceeding k (0, ..., k).
Here, doesn't it mean that a k-good number can't have any digit greater than k ???
So far I know, it means, a k-good number can have all digits without those which are greater than k. Any digit in that number can't exceed 'k'.
It has given me a lot of pain.
You cannot assume that it does not contain digits greater than k as long as it has not been mentioned in the statement.
Actually, you just cannot assume something when it has not been specified in the problem statement.
Nooo, finally found out one minute after the competition, that my C gave time limit exceeded because I forgot to print the final \n. First time I've had that bug :(
Got owned for the 100th time by integer overflow for div1 A T_T
<epic fail>
in my code was:
typedef int li;
...
#define int li
</epic fail>
P.S. Of course, it must be
typedef long long li
Same here, mistakes like this will kill me someday.
Hoping rating doesn't decrease much ...
Overflow too. T_T
Congratz lovelymoon for his E 5163338 :D (11.996s, TL is 12s)
What is the intended solution for Div1 C? Is it possible to prove it without testing all valid inputs?
UPD: Sorry, here was the solution for B, not C.
Correct. That is, however, the solution to Div1-B :)
Ah well, that makes sense:) Sorry
Well, since you already wrote it, you should probably leave it around, maybe in a separate thread.
I think this is solution for Div1 B, not Div1 C
I understand that the reduction works, but why does that mean that the restriction doesn't mean anything? Why can't the algorithm still find a move that is illegal?
Consider any two sets A and B, with c(A) + d >= c(B). Let their intersection be denoted as C, meaning A\C and B\C don't have anything in common.
c(A) = c(A\C + C) = c(A\C) + c(C) >= c(B) — d = c(B\C) + c(C) — d
c(A\C) >= c(B\C) — d
We can substitute set A\C with set B\C, thus turning A into B.
Therefore, for any two sets A and B such that c(A) + d >= C(B) we can turn one into another in one step.
Every step in our algorithm does exactly that, so every move we make is legal.
Does that explain it?
Yep, I got it now, thx.
I thought we have to swap whole set we have currently with some other set. Really poor problem statement. :(
Yes, I thought that too, until I analyzed the sample test cases.
Mmm. My solution constructs correct set with k' ≥ k elements. It's possible to prove, that we can obtain correct set for any k. But then I use statistic to prove, that I can obtain correct set with exactly k elements. I will write about it in editorial.
Nice contest and interesting problems.... Like your other contests....thanks!
Is there an alternate solution for Prob:C Div2 ? Something using Data-Structures ?
k-good numbers input 1 0 1000000000
Output
1
really 1<0?
It must contain all digits who doesn't exceed k, so if 0 wasn't present, the number was invalid. But it can contain digits who exceed k, that's not a problem. So, yes , 1 > 0, but 1 0 1000000000 should get for output 1
very bad translation, it is k-good if it contains all of (0,..,k) was better, I'm not American by the way
kind of know the reason. "the number contains all digit from 0 to k " is not equal to " the number only can contains all digit from 0 to k.". I should not have this assumption.
Actually problem is in "not exceeding k (0, ..., k)". There was no need of this portion.
When writing
Let's call a number k-good if it contains all digits not exceeding k (0, ..., k).
it means, a k-good number can have all digits without those which are greater than k. Any digit in that number can't exceed 'k'.Anyway which happened it was to be happened. No doubt, short description of last contest was nice to see. But we also hope better translation from this great community.
tanks for the contest. this was to this date my best contest and I don't think I am ever going to get a better rank in codeforces. I didn't like problem C, I solved using simple backtrack. problem A and B and D were great.
That moment in which you get WA #115 on Div1-D because you forgot that rand() only goes up to 32767... :(
Can you describe your idea?
Suppose you know GHD divides some element a[i] of the array. You can then take the gcd of a[i] and all other elements, and count how many times each of the divisors of a[i] also divides other elements of the array (should be easy to do in n log n). The largest one that appears more than n/2 times is the GHD.
Now, the question is finding such an element a[i] quickly. But as GHD divides at least half of the a[i]s, the chance that you take an a[i] that has the required property is over 50%! So just take a[i]s randomly until you run out of time.
I see such chuck of your code. It doesn't seem to be O(NlogN) as announced in your short editorial, it's rather O(NlogN + (number of divisors of a[i])2 which consumes much more time.
Can you tell how you're going to process this part of solution in O(NlogN) time?
Maximum number of divisors for a number up to 1012 is less than 7000. So it is not considerably worse than O(NlogN) part I think.
It's true assumption when one is trying to code working solution during a contest but what if the numbers will be up to 10^16? You still we be able to factor one number quite quickly and to calculate all GCDs quickly but the part with 2 loops to traverse list of divisors will be bottle-neck in such solution.
I'm just trying to figure out better approach to solve this problem.
vector d represent the divisors of a[idx] which is theoretical have at most 2*sqrt(a[idx]) elements. but practical it is much less.
What a weird solution !
thank you.
that too, it was the last test! really unfortunate!
please update ratings! thank you so much
I hope Petr rise again :)
:)
I just found the "problem revision"(30) in the detailed submission page.
But What is the problem revision? Thanks for help!
Problem Lang Verdict
365D — 30 GNU C++ Wrong answer on test 8
This contest is very great, with so many rand() needed and some hard problems :-P
Editorials please !! :)
hi everyone, for problem B,
why this verdict???
1 1000 Answer 1 Checker Log wrong answer Answer contains longer sequence [length = 1], but output contains 0 elements
You don't print anything. Look at if(n==1)
Could anyone have a look on my submission 5162269 for Matrix problem? I don't understand why I am getting a run time error...
It looks like you divide by zero in this string.
i think it maybe because you are trying to compute
a%(it->first)
anda/(it->first)
, but the value ofit->first
maybe zero if the string contains a0
character.Thanks for the contest, Finally I became blue!! :D ..
at the very beginning i got problem A,B done within half an hour while just before the contest end,i wrongly took the lower bound of ai as 0 and think i may be able to hack some careless guys who also didnt handle the data 0,so i quickly submitted problem A again with speical judgement for the case when ai is 0,...then the system reply tell me ai must be >= 1.and my rank in room suddenly drop from 8 to 16.. it really proves that evil will be rewarded with evil.ToT
A and B 's very easy. But C 's so hard. (Just with me :) )
i liked the problems, though i could not participate
Is there someone fix the description of problem D. Free Market? How to understand this statements: "Note that each item is one of a kind and that means that you cannot exchange set {a, b} for set {v, a}. However, you can always exchange set x for any set y, unless there is item p, such that p occurs in x and p occurs in y.". For the samples, second one, why 2 days? one change a day, at least three days? input 3 5 1 2 3 output 6 2
How could those get AC?
link to previous comment
I look forward to editorial
it has been published here
Thanks for beautiful problems.I enjoyed so much :)
Unbelievably lucky! lovelymoon's (div1 winner) E problem takes 11996 ms (TL is 12s) on the maximum test case :)