Hello everyone! Codeforces Round #268 is coming soon! We invite you to participate in this round. It will be held on September 20th at 17:00 MSK.
Problems have been prepared by me. Thanks xyz111 and dhh1995 for giving me the idea of some problems. Thanks vfleaking, foreseeable, MinakoKojima, Ruchiose and xllend3 for testing.
I also want to thank Gerald for helping to prepare this round, Delinur for translating the statements, and also MikeMirzayanov for Codeforces and Polygon.
It is my first round on Codeforces. Hope you will enjoy this round.
You'll help a boy named Little X in this round. Good luck and have fun :)
UPD
Round has finished. Thanks for participating.
Congratulations to the winners.
Div. 1
Div. 2
Congratulations to ecnerwala, the only participant to solve the problem D!
Unfortunately, no one has solved the problem E in both divisions.
Editorial for the round will be added tomorrow.
UPD
Editorial is here.
Looking at the level of the setters, I would say a Div 1 round would have been possible :( Edit: I thought today's round was their round, don't mind :P
So you got one xd.
OMG, I am blind, ignore that :D
Too much red users in one blog...
another china round! good luck everyone :)
Why "Little X", but not simply "x"? :)
Maybe the oxymoron (little big x) is intended?
Звали?
x is usually name of the variables, it could create confusion too :P
It's the first time to see contest announcement before the start of previous contest :D
Why are there so many numbers in the handles of the problem setters ? =D
No, many handles for testing not problem setting
many Numbers in handles
not many handles
Thanks :D
Because 233 is a special number in Chinese... It means "LOL"(Laugh Out Loud) in English which shows a man bursts into laughter. And we use repeating "3" many times strengthen the funny meaning. 233 is a photo id in a famous forum of China. here is the photo.
Link is broken.
poor link...
what is APEX KEK means
Oh right, I should've included a
and apex = top (it's made using rarely used words, like nay = no). I just found the "poor link" reaction seriously funny :D
Oh...I thought LOL is the short from Lots Of Laughter... After clicking your URL, I have just known LOL is short from Laugh Out Loud......
It's hard to say what people want it to be (and it doesn't really matter), it could even be short from "Lots of LOL" :D
fix the photos.
Yessssss
Chinese round -> more math
There is actually going HackerRank contest "Ad Infinitum — Math Programming Contest September'14 ". It lasts 2 days :). Give it a try.
First of all, before this commented is downvoted, I would like to point out that codeforces is for developing your algorithmic knowledge. Depending on your definition of "algorithmic", math could be considered an algorithm; and this is a perfectly valid opinion. However, what is the point of competing in coding contests if all you want is math all the time. Every time you post, it's about math; nothing else. Coding contests are meant to introduce you to varied ways of thinking, not limited to math.
I'm agree with you and I don't know why many people downvoted you. Someone like math, someone not. But everyone love coding. I think we shouldn't care about kinds of problems.
Oh, god, I think I can't participate any more Chinese round, because it is 6:00 am here.
Btw, I guess more testers you have then more difficult this round will be.. let's see if it is correct.
early sleep and early wake~ After brushing teeth and washing face, you can participate the Chinese round relaxedly
Have fun getting used to the U.S :)
nice
newSolar BigGod is here! You are a Yellow! But you say you are only div2.....
When did I say that? I didn't use this Id for more than half a year.
So, its going to be a typical chinese round . good luck everyone :)
Сделано случайно.
My last contest in summer! I'm going to school on Tuesday! Hope a good contest! Good Luck!
I think it's everyone's last contest in summer in northern hemisphere :|
Yes I think you're right!
It's not your "last contest in summer" when you don't compete :|
(Dabbe)
(nice) :D
:|
It is already 20th of September. What kind of summer do you have?
I have registered for the contest, but due to time constraints (I have to participate in a qualifying round of some other contest), I will not be able to participate for the entire 2 hours. Can I appear as a virtual participant (If I participate for the first hour of the contest)?
No, if you submit during contest, it will be counted in your actual participation and rating changes will also apply. So it is better to take the entire contest as a virtual contest at some suitable later time.
I will try to help Little X as much as possible but can Little X tell us score distribution ?
Attention please,it's a Chinese round!There is reason to believe that it's impossible for the konjacs(its Chinese name ‘juruo’ means the people with low level like me)to improve rating.Good luck to every super cattle(you may be able to understand it)! TAT
Many GranMaster & Master for prepare this round. My premonition told to me that "be careful with tricky test"
Ehm, score distribution?
It seems that I will participate in the next contest (Div2) Officially :D
The hell is your graph?
I am sure , someday , your graph will be a great inspiration for many many coders !!!
Thanks :) hope that also
You were right. Welcome back to the hell, fella :D
yep I did it :D
500 — 1000 — 2000 — 3000 — 3000 :(
B(div1) 4 7 9 2 4 5 7 If someone need.
The answer is "YES 1 1 1 1", right?
would it be correct if ans is YES 1 1 1 1 ?
Yes. ) But any people have answer : "NO".
Or
3 5 8
2 3 5
(sometimes they remove numbers from first set without checking if first set stay valid)
Edit: the answer is "NO", but some were giving for output "YES 0 1 1"
Also when a == b some codes enter inf.loop
what was the hacking case in div-1 B...my solution got hacked :(
How to solve C ??
I took the following greedy approach:
I used the following :
How do we solve Div2 Problem C?
There are several ways to solve it. You can see that with N < 4, there is no answer. With N = 4, you can easily take (1 + 2 + 3) * 4 = 24. N = 5, 2 * 4 = 8, 3 * 5 = 15, 8 + 15 + 1 = 24. From N = 6, 4 * 6 = 24, 3 — 5 = -2, -2 + 2 = 0, 0 * 1 = 0, then for i from 7 to N, 0 * i = 0, and finally, 24 + 0 = 24.
I took special cases for 4,5,6 and
and for n>=6
used pre-created sequence for 5 and 6 based on even or odd n,
made every element n and n-1 as (n)-(n-1)=1
and multiplied all the ones in the end.
Can anyone share his/her approach in Div2 C problem ?
If n is even and >= 4: 1 * 2 * 3 * 4 = 24 n-(n-1) = 1, (n-2) — (n-3) = 1 and so on. So just multiply the 24 with the ones.
If n is odd and >= 4: 5 * 4 + 2 + 3 — 1 = 24 n-(n-1) = 1, (n-2)-(n-3) = 1 and so on. Same.
There is no answer if n < 4.
Great. Got it thanks :)
for n >= 6 erase all numbers except 2,3,4 using: (5 — 6 + 1) * z
for n = 4 and n = 5 — hardcoded answer
Yes got the idea now couldn't think about it in contest :(
Thanks :)
How to solve Problem D of Div. 2 ?
My solution was, to just use pair(value,pos) in a set, and modify the set comparing function to consider only the first value. Then just keep checking if each element has its match in either A or B. hope it passes final tests :)
I pretty much did the same. Got hacked. :-(
Link: http://codeforces.net/contest/469/submission/7879744
Edit 1:- I got what is wrong with my solution. Edit 2:- I never considered that empty sets are allowable.
Your graph is inspirational !!!
It's a bipartite matching problem ;)
Hm, i had two maps, one <int,bool> where i stored if there exists some number, and one where do i keep position of that number in initial array. Then, for every number, check map1[a-array[i]], map1[b-array[i]], if there is both do sth, if there is only one put it into the set, if there is none return -1. See my code for details UPD: It failed on systest, so this approach may be wrong
Pick a number in the list, say x. Then we are interested in whether a-x and b-x are also in the list. If
1) Neither are in the list, then partitioning is not possible.
2) If only a-x is in the list, then both x and a-x go into set A
3) If only b-x is in the list, then both x and b-x go into set B
4) If both are in the list, then this is inconclusive. We need to further check b-(a-x) and a-(b-x) according to the same rules (for example, if only b-(a-x) is in the list then all of a, a-x, b-x, and b-(a-x) go into set B).
The implementation of this is pretty straightforward, though in contest I mishandled the a=b case (which requires special handling as a-x=b-x=b-(a-x)=a-(b-x)=...). See 7882478.
Why do we need to check further ??? Can you give test ??
i got it on contest , but i missed when cout no
hopcroft-karp bipartite matching
Hii, palmerstone, I like your approach using Hopcroft karp, but I am having trouble understanding the case when both a-x and b-x (along with x) are present in given array. Here's a part of your code
how did u came to such conclusion that when both a-x and b-x are not present, there can't be any possible matching?
What do you mean? x is an element of the given set. If both a-x and b-x are not present then it is certainly not possible to include x in any of the sets, is it? Hence not possible.
Oh yes. Thanks, I get it now... By the way can you please tell what does array L and R store in your implementation of hopcroft-karp ??
My solution for div2 D/div1 B:
Assume that b>a because we can switch them anyway and b=a is trivial case. Let x be the smallest value which hasn't been assigned yet to either of the sets. If there exist a value b-x, then we have to pair values x and b-x into set B because value b-x can't be paired into set A because a<b and therefore a-(b-x)<x and there exist no values smaller than x. So we know that if there exist value b-x, we have to pair it with x. If there doesn't exist value b-x, we have to pair x with a-x into set A. If we can't do that, the answer is NO. This approach can be implemented just by iterating over elements which haven't been assigned to either set in ascending order. 7874034
Can anyone tell me the greedy approach to solve div1 B?
Have you really requested a greedy approach to this problem in reply to comment where greedy approach was explained?
Actually , I have seen a few greedy accepted solutions . But could not understand their proofs.
OK, so here you got greedy solution with full explanation and proof: http://codeforces.net/blog/entry/13836#comment-188500 ...
What's the solution for problem C? Is it some kind of greedy/constructive algorithm based on number theory, or is it dynamic programming? The numbers are from 1 to N, so I assumed it was a number theory problem but couldn't come up with a solution.
For numbers up to 3 answer is 'NO'.
Just notice this if(n<4) no soln if(n==4) 1*2*3*4=24 if(n==5) 4*5+3+2-1=24 and for all other numbers, if n is even then you do the 4 thingy and keep doing i+1-i=1 for all the numbers, and at last do 24*1=24 as many times is you need same thing for odd n, just you would use 5 thing
You can get the 24 by using 2, 3, 4 or 1, 2, 3, 4. For the neighbor number, say, i and i + 1, we can get 1 by using
-
operator, and 1 can be eliminated by*
with other number. Then I think you get the answer:-)if n is less than 4, obviously no solution. Then 2 cases, if n is even, we can reduce the sequence to 1,2,3,4 (after which we just multiply each element one at a time). By subtracting n and n — 1, multiplying 1 and 1, then n — 2 and n — 3 and so on.. if n is odd, you can similarly bring it to 1,2,3,4,5, we can reduce to 2,3,4 by doing the following: 1 + 5 = 6, 6 — 3 = 3. After this we just multiply each one again. Hope its clear :)
A much easier solution is to get 1 by doing n-(n-1) and then 1-1=0. Now do i*0=0 for all i from 5 to n-2. And then do 2*3*4 = 24. For n<=6 pre calculate the ans. I hope you get it.
mine is same as rishul_nsit Sol Link
This contest reminds me of the Codeforces Round #146 (Div. 1) which was prepared by WJMZBMR... Codeforces Round 146 (Div. 1)
To those who have problems with div. 2 C here is my approach:
First print out the answer for cases n <= 5. Then for n > 6 you realize that you can make 24 by multiplying 6 and 4. Then you are left with the burden of creating n — 2 more operations, thus, you subtract adjacent numbers so you get a long chain of 1's, be careful that you cannot use 6 and 4 again. Then you simply keep alternating between: 1 — 1 = 0 1 — 0 = 1
until you are left with 1 or 0 then you can just do either 24 + 0 = 24 or 24 * 1 = 24
I did this approach during this contest and it seems to work. I was a bit dumb for the first hour because I forgot to print out "YES" at the beginning >.<
Haha I forgot to print "YES too :P
My solution was as follows: the n = 4 is easy, because we can just multiply 1 * 2 * 3 * 4 = 24. The n = 5 is a tiny bit trickier, but we have 4 * 5 = 20, then 20 + 2 + 3 — 1 = 24. Now, if n > 5, we can take the two largest numbers, n and n-1, and subtract n-1 from n to get 1. Now, our list is 1, 2, 3, ..., n-3, n-2, 1. If we multiply the two 1s, we are left with 1, 2, 3, ..., n-3, n-2, which is the list for n-2, a smaller case! This means that n = 6 will work, since we can reduce it to the n = 4 case, n = 7 will work, since we can reduce it to the n = 5 case, and so on.
my answer is 1*2*3*4*(6-5)*(8-7)*...*(n-(n-1))=24 for n is even 5*4+3+2-1*(7-6)*(9-8)*...*(n-(n-1))=24 for n is odd
Our Little X is in upper case. Too big!!
Fuck math with no programming!
Thanks, that's what I was asking for!
Got butthurt? Go away.
Why so serious?
Because he was rude, used swear word and continues math-hate here which I'm completely fed up with.
I am not sure, but only the last problem seems to be mathematical one.
First one was also mathematical more than programming I'd say. But, a major chunk of programming is maths and logic, so it is only expected.
Of course all the problems are about math here(discrete math mostly), but here, I believe people mean complicated math by saying "fu**ing math again", but noticing that 6*4=24, a*0=0 and a*1=a.
That was one fast system test!
Why so weak pretests???
I guess lots of Bs will fail.
Also there was too many WA2 in problem A... For constructive problems, first sample should be more difficult. :|
IMHO, pretests complexity is completely up to the Problem Setter.
I spent all 2 hours on problem D but still cannot finish coding it...
Calculating "lexicographically smallest" one is very confusing, and I couldn't make solution without very complex iteration. Doesn't there exist any simpler solution?
Indeed. If it weren't for this "lexicographically smallest" than it would be doable with centroids and that kind of stuff, but it is a significant obstacle :/.
Yes. Thinking about centroid is fun, but I think main part of this problem is more complex part, because only 1 people solved it despite thinking about centroid is not so hard...
Like 90% of 469D - Two Sets has failed tests. Lol!
Wow, system test over in 10 minutes this time!
thanks for the fast system test~ I think I could back to blue.
I think just like you :/
Me too :\
Edit: Hey, we both stayed in div1! :D
problem A:
for n=1,2,3: no
for n=4 : 1*2*3*4
for n=5 : (3*1+5-2)*4
for n>=6 : 2*3*4+(6-5-1)*7*8*...*n
for div 2 B And D
what is the bug in my solutions ??
Code_B
Code_D
For D:
as i understand from this case
a-x can be equal to x ,, is this right ??
Yes.
still WA on the same case ??
Code_D
Im I using the right approach ??
Try this test:
3 5 6
2 3 4
Your solution is totally wrong
about D:
it will fall on the case
3 2 6 1 2 4
because 2-1=1.
as i understand from this case
a-x can be equal to x ,, is this right ??
right.
about B: Your check for intersection doesn't look right. See if you can find your error here: if ((x >= a[j].first && x <= a[j].second) || (y >= a[j].first && y <= a[j].second))
can you please explain why this is wrong?
Same question, please explain what's wrong here?
Seriously... 17 months ago
Anyway, look at the conditions inside the if statement. What is it doing? Is it checking that the two segments overlap, or if one segment is completely within the other segment? What we want is for the two segments to intersect, one segment does not necessarily have to completely contain the other.
Isn't this code wrong 7871552 ??
Test: 2 1 0 0
1 5
2 4
7 7
UPD:The inputis illegal sorry.
I think it is wrong. The answer should be 0, but it is giving 1. oh! Inputs are not valid.
Ehh..
if (n % 4 == 1) { ... cout<<"3+1 = 4\n"; ... }
There wasn't any pretest for n % 4 == 1? It's really disappointing :\
My solution for div-1 B using dinic's algorithm for maxflow TLEd :(
I thought it would run in O(E * sqrt(V)) time as all edges are of unit length. Can anyone please let me know why dinic would be suboptimal? Isn't it the same as Hopcroft-Karp for unit graph?
My Submission
The nodes in the subgraphs can have at most 2 degrees. I think you didnt need such a complicated algorithm
My implementation of hopcroft-karp got Accepted in 514 ms
Solution
By the way, somebody solved problem E in Division 1...
and Failed A...
What a sad story :((
printf("24 + 0 = 24\n");
:((Same story
Err, what's wrong with 24 + 0 = 24 ?
My code for n=4 prints in the end 24 + 0 = 24
same story got 1 wa because of that
Great test for problem D Div 2. Lots of Failed System Test
Can you give me an example on which my code doesn't work ? ( Sorry for my poor English) http://codeforces.net/contest/468/submission/7883022
Why would everybody use tonns of #define? It puts my bum on fire.
Because it's easier to write MP than make_pair or something else... You write faster
It makes code harder to read in my opinion. Especially when I see that 50% of code are definitions for "for" and other shit.
If you use snippets you can write fast enough. As for me is more important to think fast, not write.
FOR0(x[i],8) vs. for(x[i]=0;x[i]<8;x[i]++) not only saves keystrokes, but also reduces probability of typing errors.
Ok-ok. I understand, I am bad programmer if I don't use #define.
It's well... output : YES 1 1
Sorry. Try this.
Thank you very much for this example :). Now, I understood why my code doesn't work
I can not understand the reason why many of the chinese authors make hard and mathy problem set. In my opinion, contest's easy problem should be easy. Otherwise it is not motivating enough for people to participate.
I've entered for the next div2 contest.The konjac(its Chinese name ‘juruo’ means the people with low level like me) has no human rights.
winter is coming
when will the ratings be updated?
About Div1 B. Does anybody have a case with an odd n and positive answer? Or could explain why this is possible? I assumed this wasn't possible during the contest, but apparently it is. Maybe I misunderstood the problem.
1 10 20 5
5 is in the group A and 10-5 is also in the group A
Oh i see, thank you.
No problem. :D
can someone explain why this solution is incorrect? http://codeforces.net/contest/469/submission/7867443
you should use resize not reserve
reserve only reserves space but the size of your vector stays the same. it is only useful for example you read numbers and push them back of a vector. the vector resizes itself when you push back sometimes. if u know how many numbers u are going to push back then u reserve some memory and when u push a number back of the vector it doesnt allocate new memory
I understand. Thank you !
How to solve Div 2D/ DIV 1B ?
the numbers create a group of chains. just have a look at my code: http://codeforces.net/contest/469/submission/7880049
Can you please tell me what is wrong with my solution : http://codeforces.net/contest/468/submission/7883509
Task D div 2 (Two Sets) Test Case 9:
How could the correct answer be YES 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ?
when it is stated in the text: If there is a way to divide the numbers into two sets, then print "YES" in the first line.
You should know that {} is a set. it is an empty set.
It is like sharing 5 apples between you and me. You take all of the apples and I get none of them. But what we just did was sharing :D
Note
It's OK if all the numbers are in the same set, and the other one is empty.
You Didn't read this Note:
"Note It's OK if all the numbers are in the same set, and the other one is empty."
By the way, I got WA too in this case :(
Can any one please point out the mistake in my code. I am a newbie and am unable to find the glitch in CODE 469D. Thanks in advance
In your solution you can use a number in 2 sets at the same time. check this: 3 20 18 5 15 3
Its answer should be NO
When will they update ratings?
Chinese Round again, so difficult problems again...
Can anyone tell me what's wrong with my code for problem D, please?
7882442
Thank you!
Check this test:
10 12 14
3 2 10 9 4 9 3 2 5 10
Answer is:
YES
0 0 1 1 1 0 0 0 1 0
Edit: Sorry. Test is incorrect.
Explanation: Some numbers may occur several times and you should put some of them in set A, and some other in set B.
Edit: It's not true. My mistake.
That's not true, the problem statement specifies that the numbers are distinct.
very interesting and enjoyable problem indeed..i enjoyed this very much :D
I have a question regarding this submission 7868179 Div.2 problem A .. I unsuccessfully tried to hack the solution using a testcase where the algorithm will try to access h[100] while the size of the array is actually 100! so the last element i can access is h[99], but the hack was unsuccessful .. any explanation ??
When you access beyond the range of an array in C/C++, it gives an undefined behavior. This undefined behavior may or may not throw an exception.
My first time doing the first three problems . Best wishes.
So much math, it's awesome round!
jqdai0815 Thanks! It was a great Round!
Could anyone clarify on grading policy?
I've successfully submitted solutions for 2 tasks without penalties or resubmissions but my final round score is negative why it could be so?
Thanks!
Cuz you have 1497th (-520) place whereas you had 977th place at previous round.
Round Stats
I just wanted to leave this here: 7878473
In case you're too lazy to open, here is the whole accepted code to C in Python (authored by ZhouYuChen)
I have to say that I'm impressed :P
A really neat/impressive solution!!
What is the logic behind the solution?
Let S(l, r) be the sum of digits of numbers form interval [l, r]. Take big k and see that S(1, 10k) = S(2, 10k + 1) - 1 = S(3, 10k + 2) - 2 = ...
Here we have with x=10^100 — 1 and t=m-(450*10^100)%m = m-r , where r<m
S(t,t+x) = S(1,1+x)+(t-1) = S(1,10^100)+(m-r-1)
Above must be equal to 0 when taken mod m
(S(1,10^100)+(m-r-1))%m should be = 0
S(1,10^100)%m + (-r-1)%m
If the above steps are accurate, I cant follow the proof after that.
Can you please explain?
Thanks.
You are taking a hard way to understand this problem. I used the same idea and I think I can explain more clearly.
There are 4 things to observe:
1) S(1,10^k) = 45 * k * 10^(k-1) + 1
You can try to convince yourself doing some mathematical proof or just run a script that calculates in a brute force fashion when k is small.
2) S(1,10^k) = S(2,10^k)-1 = S(n+1,10^k+n)-n
This is the trickiest part! In the first case, l = 1 and r = 10^k. What happens if we increase them both? l = 2 and r = 10^k+1. In this case, we "removed" one element whose function value equals to 1 and "added" another one whose value is 2 (10^k+1 has two 1's and a lot of 0). You can observe (by induction) that the same holds for any value we add to both l and r. Therefore, this formula I wrote here is correct
3) S(1,10^k) % M = x if and only if S(M-x+1,10^k+M-x) % M = 0
Well, if you add M-x to both boundaries of S(1,10^k), you will have S(1,10^k) = S(M-x+1,M-x10^k) + x — M, according to property (2). Then you take modulo M and you will have S(M-x+1,M-x10^k) % M = [ S(1,10^k) + M — x ] % M = [ x + M — x ] % M.
4) S(1,10^17) > 7 * 10^18
Finally, as a is at most 10^18, you have to find a power of 10 that guarantees a sum that is greater than that value. I wrote a simple script in Python that calculated S(1,10^k), according to formula (1), for some k and I found that k = 17 was enough.
If you have any further questions, you can take a look at my last submission for this code or write a message.
Regards
Can someone explain the greedy approach to Div.2 D / Div. 1 B Two Sets?
http://codeforces.net/blog/entry/13836#comment-188500
This round taught me a lesson and warned me about my deficiency in coding details. Besides I eventually understood that you may never think about getting more rating in Chinese Round. But actually it may not be the reason for not participating the contest, for the main purpose that we compete in CF isn't the for the rating. Even so, there will be a long time for me to regain my confident and to participate another round especially the Chinese Round.
Can anybody explain what is the flaw in my approach Solution ?
Can any one tell how to approach problems in competition so that it takes less time complexity and how to approach math problem fastly.
And what's the time complexity of program if i write n^2 solution to the problem in test case loop.
There are no shortcut, you know what to do.
What do u think about bold line .
And what's the time complexity of program if i write n^2 solution to the problem in test case loop.
O(t * n ^ 2)