Hi!
We're glad to invite you all to participate in Codeforces Round #360(Div. 1 and Div. 2) which will take place on Wednesday, 29 June, 20:05 Moscow time. Check it in your timezone!
The problems are designed by Man (Parsa Abdollahi) and me. It's our first Codeforces round and we hope you enjoy competing it as much as we enjoyed preparing it! (^◡^)
Our special thank goes to JeBeK (Peyman Jabbarzade) who helped us a lot in preparing and testing the round. Many thanks to GlebsHP (Gleb Evstropov) for his help in preparing the contest, and MikeMirzayanov (Mike Mirzayanov) for great platforms Polygon and Codeforces. We also want to thank Zlobober (Max Akhmedov) for testing our round.
We wish (and expect!) you all many Accepted solutions! ( ゚▽゚)/
UPD: Problems are going to be about Pari and Arya.
UPD2 Congratulations to the winners!
Div. 1:
Div. 2:
Editorial + some challenges will be published soon.
UPD3: The editorial is out!
Very good time ! Thanks Mr.Shokri
Yeah , same for us. :)
Very terrible time! It is 01:05 in china.If my mom find the light in my room at that time, she must kill me! Awfully!
Then try to win the round and you'll have an excuse! :)
Same in China T_T
Actually, that was China too. :|
I think he might have meant, "It's the same for me, I'm in China as well."
I hope both tourist and Petr will participate. And let the battle begin!
You should also hope both JIBANCANYANG and jqdai0815 will participate.
But you can't compete in the same division right?
When I was in America, I used Facebook, Twitter, and many other social networks that Americans are using.
Usually the first thing I feel when I open either online web pages or their mobile apps is that the UI is simply ugly, untidy and not easy to read. And when I look deeper into them, I found the logic of menus are usually not user-friendly. Company as large as Facebook spent too much space of their app menus to show the privacy settings or other. Are these settings necessary? Maybe. But Facebook puts them their to avoid law suit rather than help the users to achieve some useful function. (Sometimes few people like to sue a company who provides them free service for the service is not good enough lol)...
Regarding the mobile app. I noticed that Facebook and Twitter consume a lot of data but providing no more information than WeChat and QQ. I think they just don't care about optimizing app performances. The iOS version of Quora is another example. Is it really necessary to refresh the entire frame every time I move into the detail page of a question and move back to main feed? The app works like a web broswer rather than an app. It is slow and waste too much data.
As a person who uses Chinese apps more often, I have to say that the user-experience of these popular International social apps s-u-c-k...Forgive me for bad words. But before I explore the content, the web design and app performance are already pushing me away.
Once I look into the content. I feel that there is nothing more interesting or more important as well. I can not even come up with an example about the important and valuable information I acquired from Facebook (Trump is winning? China does not have democracy? lol). Even my American classmates do not really like using Facebook any more...
In terms of functions. Alipay and Wechat Pay in China has achieved I believe everything Apple Pay are still trying to achieve. We scan our phones to check out in restaurants, super markets. We order tickets, hotel rooms and we call cabs with one finger, in one app...
As a whole, I do not see any significant advantages Facebook or other social networks have over convenient and beautiful local apps...If there is one, maybe arrogance and ignorance? Because they even believe that the reason why they do not have too many Chinese users is that China Government bans them...
Maybe they will experience a user number explosion at the first several weeks of cancelling the banning order. But everything probably just returns to the beginning after all.
R E K T
Lucky jqdai0815... #:-s
be glad. jqdai0815 will participate
Petr didn't participate but tourist is currently 2nd and last time he was second he had a -48 rating change. Petr still has a chance :)
Come on, now it becomes even more thrilling!
That is a good time
Good luck guys
That is a good time Good luck gays
i hope to get into the same room to take my revenge and hack you as you hack me last contest
It's a good thing to hacked :3
Unlucky me , didn't get in the same room maybe i'll take my Great Revenge later ,,,, time pass and revenge grow up
Better to get hacked than to get system test failed.
In case you have not locked. Otherwise, you feel bad due to locking in case of hack.
You should thanks hacker because your solution is Wrong and you can fix before contest end :)) :))
Whoa, it starts at 2:00 AM and ends at 4:00 AM... I'll have to go to bed early in the evening and wake up then.
And I couldn't but add some emojis. (๑>ᴗ<๑)
It is really sorry, and I guess you are Indian from your time.
No, she is a Korean I believe.
Is there any reason to believe this person is a 'she'?
It just doesn't feel right if she is a boy based on her profile picture and her typing style.
Hmm... well I wouldn't hold such prejudice. Cause well...I'm pretty sure your wrong on the gender thing.
As a matter of fact I am a girl. Why do you think I am not a girl?
I don't believe you're not a girl. Nor have I expressed that belief. I myself am gender fluid, I literally can't make gender distinctions.
Okay, I was being vague on purpose. I happen to know that person. You may observe we go to the same school...
I see. I misunderstood your words because I am still learning English...
Why do you not participate in contests?
Because I sleep early and codeforces round are always so late in the midnight.
Wait how can you tell someone gender by typing style.
Because he used cute emojis and boys I met never use emojis... Maybe I should meet more people.
The time difference between this round and the previous one is only half hour, I don't think half an hour is a big deal!!!
But it is really quite too late for me..
excited for the round
What a bold statement
What a bald guy
So it's 2π in radians :) :D :v
11:05 pm to 01:05 am(Bangladesh) then wait for system testing.... then wait for rating.......DAMN!
After That Bangladeshi people have "sehri" and Sleep :)
I think the time is perfect for Bangladesh people this time...
"tarabi" > diner > contest > wait for system testing > ("sehri" + wait for rating ) > go to sleep :)
whoa, I can sleep longer =))
If CF contest starts at usual time, I just have 2 hours to sleep; but today I can sleep in ~3 hours (maybe)
Although the contest starts a half an hour later, I feel very comfortable and excited =))
Hope the contest goes well =))
*p/s: sorry for bad English =))
I have Linux embedded system final tomorrow, but nothing stops me from participating this round :>
pari?!
napari ?
Pari is a Hindi word for 'fairy'/'angel' in English.
I think it means an angel and not a fairy .
angel is called farishta
It's a Persian word! More details (Press Ctrl+F and search Pari) / More Details 2
Exactly, India was once part of Persian Empire and thus origin of a lot of Indian words is Iran, not India.
india became india after 1947, earlier it was(at the time of mughals and before) just indus valley civilization!
India has many different language derived from many different language branches. Using the term "Indian words" is like using the term "European words". It doesn't make sense. Most of the Indian languages were developed before the Muslim conquest of India so has very little to do with Muslim/Mughal empires.
The only language influenced by Muslim/Mughal rulers of India is Urdu which is spoken by Muslims across India.
Some of the Indian languages like Sanskrit and Hindi might have similarities with Persian language because they were derived from a single source. Refer: https://en.wikipedia.org/wiki/Proto-Indo-European_language.
Though I am not going to debate on exact origin of word Pari, I would definitely disagree with your sweeping statement that "origin of lot of Indian words is Iran". It's complete BS.
plz tell me the name of the BOOK or link of VIDEO tutorials from which i can learn PYTHON from very BASICS.I know C .
I started to learn from this link. I really recommend this. This link is the best resource that you'll ever get.
Hello, I am a new user here. I was wondering whether editorials are released for every contest and where do I find them?
Go to contest page(problemlist), after that find "Tutorial" in the bottom of the right panel, next to "Announcement".
Thank You
A girl is Arya Stark of Winterfell and is going home.
Pari, she calls herself.
: |||||| People never want to stop spoiling ...
People never want to stop not watching GoT on time and complain about the spoilers.
Actually Arya meant in this statements is a Persian boy, not Arya Stark (But it'd be great, right?).
SUPER COINCIDENCE: We have national team trainings currently going on and at every break we play tank trouble game just like Arya :D
Pari must be a fake account of Arya.
Plus for Pari and Arya!)
In fine :)
Actually, trying to get AC with suboptimal solutions is a good strategy quite often — for example vs .
I'm pretty sure by unoptimal solutions he means "tofs" (thats what we call it in farsi) it means spits, things that aren't supposed to work but take advantage of the tests, like Submitting a solution which is n ^ 2 but has a lot of breaks or a wrong solution which passes because there were no tests against it
if the girl has a name a man can bring back her eyes - the girl has no name.
it looks like someone banged your head on keyboard while registration ,no offence intended :)
Ac is an Ac, no matter if it's optimal or not
of course but trying to get AC with non-optimal solutions isn't so smart
I thought so, but then I saw people getting ac with brute force solution in this gym problem Polycarp and Palindromes in a contest where I couldn't come up with an optimal solution...
you're right , that's weird
hacks are coming and they will be here soon
So it's gonna be your day today :D
in div2 rounds I hack others , but in div1 I'm the one who will be hacked hahaha
loool
the hunter becomes the prey :3
Good luck up there :D
thank you
Good luck down there :D
down there , here I come
It's holiday here \o/!!..hope weird problems haha
tourist has been already registered , waiting to see Petr too in the contest.
when I was div2 few days ago , I was just like you waiting for them to register and see what they can solve , but now I'm not waiting for them at all . just wishing to stay pink as long as I can hahaha
I think you're purple not pink :D
maybe :p
Blue is my favorite , nothing else
tourist 1st on CodeForces , peter 1st on TopCoder
How many problems and score distributions?
Arya be like...
Today she will slay us with the statements!
The name of the problme E in div 2 should be "SUCH THAT". :p :p
[Temporary Deleted]
But Brock Lesnar (jqdai0815) came from nowhere
Good Fight Between tourist & jqdai0815 :)
How to solve D?
If you know value of , then you can know value of . Infact, it will be same.
Proof is very simple. . You know value of t. Write x = k * (a * b * c) + t, where k is some integer. Now, you can see that
$x \, \% \, a = t
$x \, \% \, b = t
$x \, \% \, c = t
You said that if x = k * (a * b * c) + t then . This is not true.
However, it is true that
will be to be accurate.
I have used this approach: (c1*c2*c3___*cn + 1) and 1 will give same modulo (equal to 1)on dividing with c1,c2,c3___cn. Now check whether (c1*c2*c3___*cn + 1) and 1 give same remainder on diving with k. If yes ,print yes else print No. EDIT:It will fail system test as it is WA on: 2 4 2 8
You need to compute LCM of all numbers and check that it is divisible by K. To avoid overflow after each LCM operation you can do GCD with K. Then the final number should be equal to K.
How to prove such solution?
Two numbers x and y have the same remainder modulo c[i]'s if and only if abs(x-y) = lcm(c[1], c[2], ... c[n])
Now if x mod k and y mod k are not the same, then there will always be ambiguity for Arya. x mod k and y mod k will be the same iff lcm(c[1], c[2], ... c[n]) % k is 0 since the differ by this amount (or a multiple of this amount)
from where i can learn those type of theory?
From the CF comments section after a failed attempt to solve a problem :P
If LCM of c1,c2..cn is not divisible by K, then (x+ m*LCM) (m= any +ve integer), would give different remainder for K, but same for c1,c2..cn as m is increased. Hence, not possible to uniquely determine remainder with K
Here is another view on the problem and explanation.
Any set of distinct numbers C (e.g. c = {3, 4, 6} as below) "generates" unique remainder sets for increasing positive numbers X with Period = LCM(c1, c2, .. cn). Those unique remainder-sets allow to uniquely distinguish remainders x mod k. E.g. remainders row "2 1 5" always correspond to (x mod k) == 5, or "1 2 4" to (x mod k) == 10. So to have things unique CycleLength = LCM(C) needs to be "syncronized" with K, more presicely it needed CycleLength % K == 0.
Out of that two solutions come:
Find LCM and check if it is divisible by K. If true "Yes", otherwise "No". Solution #1
Factorize K to prime powers. E.g. factorize K=108 to 4 * 27, or K=12 to 3 * 4. If EACH of that prime powers divides any number from C-set — the answer is "Yes", otherwise "No". In fact it has the same meaning as in "1": if each prime power from K can be found in some subset of C numbers then => (c1*c2*c3*..cn) % K == 0, which leads to LCM(c1,c2,c3..cn) % K == 0. Solution #2
LOL. I have checked if K is divisible by LCM(a, a + n) ._.
"To avoid overflow after each LCM operation you can do GCD with K" How can we prove that after taking GCD with k answer will not be affected.
We are interested only in divizors of K. Other numbers give no information about X mod K (by Chinese Remainder Theorem). Therefore with GCD we will not interesting divizors.
Check if k is divisible by (LCM of all c[i]).
I think you mean't the other way around.
lem1: if you have reminder of x to two numbers p&q that gcd(p,q)=1 you can understand reminder of x to pq.
lem2: if you know reminder of x to ba so you know reminder of x to a.
so if k = p1^a1 * p2^a2 * ... you have to check that all p1^a1 & p2^a2 & .. are in all c's or not.
i forgot to check ai s & i get wrong answer :'(
Let's say we have input:
n = 6 k = 7
c1 = 1 c2 = 2 c3 = 3 c4 = 4 c5 = 5 c6 = 6
Now we can create the table of remainders R[ci][xj]. Each cell contains the value x mod c:
Now let's look at the 1'st column (from top to bottom):
1
We can think that the vector = (0, 1, 1, 1, 1, 1) corresponds to 1 mod 7 =
1
.Now let's look at the 2'nd column (again, from top to bottom):
2
This column can also be represented as a vector = (0, 0, 2, 2, 2, 2) corresponding to 2 mod 7 =
2
.Each column is a vector representation of the corresponding value x.
Depending on the value of x, we get different columns of remainders. If it is possible to form a function , then the answer is "Yes" (we can determine the value x mod 7 by using only remainders x mod ci). If you cannot form a function (i.e. the same input vector can lead to different values: = and f( ) ≠ f( ) ), then we cannot properly encode a single remainder x mod 7 with a vector of remainders of ci. In that case, remainder x mod 7 has more capacity to store information about x, then the capacity of the whole set of ci values.
Cool table
Who else got Div2 C: Wrong answer on case 15?
Me, because I forgot that the graph may have more than 1 connected component.
I did take care of that. Or may be I thought I did. Let's see.
I got too many TLE on testcase 15 and it turned out to be I was using global "i" in bfs function. ;((
connected components!
Also, even if it was given that there is only one connected components formed by the edges, another issue might have been using 1 as a root for BFS. It might be the case that 1 is actually disconnected.
dat feeling when u finished div2C solution with 40 seconds on the clock, submit, but forgot you used zero-based indexing... :(
Where's the editorial??
After solving ABC I checked whether I didn't register for Div2 contest ._.
How to solve C easily?
Note that picking a good subset (k; x) is like picking two subsets — one with sum x, the other with k-x.
That leads to an obvious O(N * K^2) dp solution.
I hope this will be descriptive enough (dp are bitsets):
Will solution with bool array get TLE?
No. 500^3 is still pretty fast (my code took 15ms xd). I chose bitsets, because they were pretty handy here.
I recieved TLE on test 19 using a
O(N*K^2)
solution. :-(Maintain an array of sets S[i][j] = numbers you can make if you get a subset of c[1..i] which has sum j (bitset recommended). Consider the cases:
i) Your subset doesn't contain c[i]
ii) Your subset contains c[i], but you don't use it (to make sum j)
iii) Your subset contains c[i], and you use it
Bitset can help you union these sets quickly. It is obvious that you just have to maintain last 2 rows of array S, so the space complexity is O(K^2)
It's a very good contest! Thank you! My favorite task is c! And can anybody explain d?
User fakee clearly got some sweet revenge against Barichek:
On another note: Thanks to the authors for a nice contest I enjoyed solving the problems a lot. I hope you will make more contests!
And yashkumar18 took revenge from i_need_job for just trying to hack his solution :P
(link)
Edit : I still don't know how to upload pictures in comments :/
I got TLE in TC 19, div2E...
A lot of solutions will fail in Div2D including mine. I hacked all the solutions (there were only 2 :p ) in my room with this case.
I'm sorry, but why?
X=1 and X=5 give the same remainder when divided by 2 or 4 but they give different remainders when divided by 8.
Thanks!
For example, you can't tell if its 5 mod 8 or 1 mod 8
For X = 1, 1%2 = 1, 1%4 = 1
For X = 5, 5%2 = 1, 5%4 = 1
So, you can't really uniquely identify X % 8.
Check 1 and 5, they have same reminders mod 2 and mod 4.
I don't think div1 C should be div1 C.
Yes, you are right.
It took me whole contest to solve Div2 C,D,E. It took tourist and TooSimpIe just 12 minutes to do that!
There is a reason why they are Red.
Is O(qm) intended complexity for div1-D?
If it was, then the task was all about optimization and luck. I got TLE in pretest 15 with O(qm) but kllp passed pretests in 2600ms with the same idea and time complexity.
my (NlogN + M * (DSU)) per query passes in 2 seconds.
Our solution is .
I got O(q·(m + n·logn)) in 967ms: 18804248
I've got O(mq3 / 4α(n))
Can anyone please check my solution for Div2C 18806227 ? Thank you.
Try to add g[v].push_back( u ); your code.
I'm curious if the O(qmα (m)) is intended solution in div1D. If so — why limitations are so strange (n, m ≤ 105 will be ok). If no — seriously?!
And Oscar goes to
foreach .. break
in div1E. Spend about 20 minutes trying to solve problem withoutbreak
. Withbreak
problem becames... div1C.FYI, I have in D.
How to solve it with that
break
? At the end, I came up with the following solution but don't know if it's correct. Find SCC's and for each SCC from which there is no edges find the smallest cycle. The answer is .I think it is correct (I hope so :) )
It's funny that for much time I tried to solve a version without
break
too. Still, it's our fault, not organizers. And I'd say it's at least div1D difficulty, not div1C.Yeah, but they could write much more readable code. It looks like it was intended :)
I wouldn't say it's like D, I don't solve D in 20mins like it solved E)
I think using segment tree to store the useful edges in its range can solve div1 pD in , which is asymptotically faster but...:P
OMG, that break is not within if --___--?? Where is the hidden camera??
n, m ≤ 10^5 still holds when n, m ≤ 10^3.
There was no m ≤ 1000 condition.
but m is up to 5·105
= = I meant the pretests are probably weak that it looks like n, m <= 10^3.
Hints for Div1 D?
suppose k = 2^3*3^7*5^3, then you just need modulo wrt to 2^3,3^7,5^3 to find modulo wrt k. Note that if you have modulo 2^2 and not 2^3, we will fail
To find modulo wrt to 2^3, just check if on of the numbers is divisible by 2^3.
sort edges in descending order . You need to find the first index such that edges taken till that index form a non bipartite graph .
Terrible grammar. Someone send the statements to jacksfilm for YGS
This is what I tried for Div 2 C. Can someone tell me the fault in my algorithm. So I maintain two hash maps for the two Vertex Covers. Initially I pick up the first edge, and put each of the vertices in this edge in each hash map. So if edge is (u, v), then A hash map will contain u and B hash map will contain v. I then have 2 copies of the edges of the graph, namely s1 and s2. For s1, I remove all the edges incident on u. For s2, I remove all the edges incident on v.
Now I call a function that processes my logic. So basically I check all the edges from s1, Let the current edge at any time be (u1, v1). So if u1 is present in hashmap B, and v1 is also present in hashmap B, then its not possible to split and I print -1. However if one of them is present in hashmap B, for example say u1 is present in hashmap B, I add v1 to hashmap A, and remove all the edges incident on v1 from s1, and continue the same procedure for other edges in the set. I am unsure of the case where neither of them is present in hashmap B. In that case I do not know which vertex I should add in hashmap A.
Finally, after removing all the edges from s1, and no problem was encountered. I proceed to call the same function for s2, but now interchange the roles of hashmap A and hashmap B. If after doing the same process, if s2 set becomes empty, and there was no problem. I print out the keys of the hashmap in sorted order. So my question relates to that step when neither of the vertices in a given edge are present in the other hashmap. In that case which, edge should I consider adding. I thought of a solution to add the vertex with higher degree, but I guess it won't be correct. Any help would be appreciated. Thanks!
Consider a square-shaped graph, and pick any edge as the first edge. If when processing s1, the edge opposite to this edge is checked, since this edge is also in s2, the function fails. However a square shaped graph has an answer in the form of opposite vertexes (A: (1, 3), B: (2, 4)). Is this what you meant?
Last time tourist got on second place at CROC he got -48 in rating. Toady he is on second place again and 30 minus points is enough for getting petr #1 at codeforces. (let's just wait for the rating changes :D)
In Div1-C Problem. What i and j are here ? Are they 2 subset sum ? Errichto Solution 18788820
Yes, two subset sums. Consider dividing elements into three parts with sums i, j and s - i - j where s denotes the sum of elements so far.
Thanks.
What a round. It felt like i was giving an English Language exam -_- Wasted 90+ minutes to understand the problem D (Div 2) and still i didn't get what it actually asked -_-
How funny!!! What were the system tests for Div2 B? My wrong code got AC! :p
Here
Why? Seems alright to me.
How can it seem alright? Just check with some inputs. For example 20
Click
Oh great! The line s[0]=s[0]-- reduces s[0] in my compiler but here it doesn't :/ Why is that?
Just you use postincrement.
"s[0]=s[0]--;" is equal: char t = s[0]; --s[0]; s[0] = t;
I am quite surprised by JoeyWheeler's performance.
Thanks mate >_>
What is so surprising? He solved 3 easy problems with a little mistake in one and got stuck on harder problems (D's acceptance rate is inflated because of passing bruteforces). Happens to me all the time and remember about tourist's 168th place once.
It seems that Div2D simple solutions are getting AC just taking lcm. I believe that it wouldn't be difficult to construct a counterexample using large primes and the product will overflow. Can someone tell me if I'm right or it can be proved that it will fit in unsigned long long?
Even if you calculate lcm as a*b/gcd(a,b), the a*b part cannot exceed 1000000*1000000, which fits under long long int range.
It is just in the first operation, but after it should overflow. Anyway, in the submission I saw, the guy used some smarter approach to make it pass.
I used gcd instead of lcm so that it would never overflow. (Failed in systests because of a bug but this one works.)
Submission
Edit: sorry, just realized I had previously put the wrong submission
I tried to hack such submission, but finally noticed that the guy made a[i] = gcd(a[i], K) before. Then LCM will not overflow K.
fuck cin/cout.... (problem D div 2)
Today I managed to be solving three (!) problems which were not tasks prepared by organizers :). In Div1D I considered intervals of cities not intervals of roads and wasted more than hour on that. In Div1E firstly I didn't notice break. Then I noted break, but I considered version with that break within if :P. I didn't solve any of them ;).
Waiting for Editorial ...............
The first idea for solving div2B was to generate first one hundred even palindroms ( yes, i know that it would get TLE ) , but when checking results i saw that the n-th palindrom is equal to n+reverse n , and solution which displays n+reversen is accepted , but i dont understand why .. why ?
Start by noticing that palindromes with even number of digits are made of two equal parts. That is, if you cut them in half, both parts will be equal, but reversed.
For Div2, Problem C (NP Hard) — I was not able to represent the graph as an adjacency matrix (boolean) due to memory constraints (Since 1 <= V, E <= 100,000). However, I see that the accepted solutions have used an array of vectors of the same size. I am confused if the test case uses a complete graph with V equal to max-limit, won't this exceed the 256M memory limit, even if a vector is used?
m<= 10^5
"""two integers n and m (2 ≤ n ≤ 100 000, 1 ≤ m ≤ 100 000) — the number of vertices and the number of edges in the prize graph, respectively."""
Div2 ==> Finished
Div1 ==> Pending system testing
:/
There is no systest because you are trying to construct test aganist O(qmα (m)) in D ?)
Seems like they've failed to construct such test
The time complexity is at most O(q(m + n2)) instead of O(qmα(m)). Because the distance of each vertex to the root of the disjoint-union set is at most O(n).
Isn't O(q*n^2) with given constraints is ~ 10^9 instructions. I was under the impression that this will get TLE. Looks like that is not the case. How to predict whether a solution design will get TLE or not?
You are right, and the constant factor is not 1 (more like 3 or 4). But TL is 6 seconds.
Before the system test: finally i will be a div1 user :D
After the system test: good bye div1 for ever ;_;
Before systests : ~600.
After systest : 296.
get rekt but i can get much of experience,thanks authors for nice problems TT
)
Do you even meme bro?
No, I am doing this first time :/
All I want to have editorials to learn something new.
Keep trying, eventually you will find the correct meme (or realize that it doesn't exist at all).
Meme editorials (bro)?
TLE on 1B with
cin
andios :: sync_with_stdio(false)
:(Why can't authors add a proper max-test in the pretests! :/
AC Code with scanf — 680 ms
AC Code with cin and ios :: sync_with_stdio(false) and cin.tie(0) — 982 ms
TLE Code with cin with ios :: sync_with_stdio(false) — ≥ 1000 ms
I got TLE due to
cin
too -> 18790984.Got AC with
scanf
in 342 ms -> 18809097It sucks to get tle just due to slower I/O :(
"Pari never tries to get ac with non-optimal solutions" — aren't constraints in D explicit invitation to code bruteforce ._.? Even tourist and jqdai0815 coded bruteforces -_-. Stupid problem. Try doing some statistics on how many AC to that problem are brutes (I guess >=80%).
I'm curious why so many red guys are confident with bruteforce.
They probably realized it is a Div 2 contest.
There was two reasons why I complain:
1. It is too easy for div1D
2. Why n ≤ 1000, I don't use it.
But the constraints are small enough for this solution to pass.
These may happen for everyone who is preparing a contest for the first time.
So that explains it... I found the actual solution (or something that has the same complexity at least) and it was some ugly Frankenstein union of a bunch of different algos, when I looked at the standings and thought "no way 70 people coded that :o"
Fun facts:
using a O(n lg^2 n) or O(n sqrt n) approach gets TLE in B
using a O(qm alpha n) approach gets AC in D
As Swistakk says, I thought I registered for Div 2 after solving ABC.
Well, I should have gone back to office and let my mother participate this round for me.
More fun facts, random_shuffle AC in div1C. 18807562
random_shuffle has become quite an efficient problem solving tool recently!
Another fun(?) fact: Around 70 div1 participants got TLE in B because of input speed.
TFW you set a need-to-optimize problem's TL to 6s and a ****ing huge input one to 1s.
If you ask me, yes I'm butthurt))
qm log(n) works in D tooI now understand that my solution is qm + qnlogn. Sorry for being misleading
using a O(n lg^2 n) or O(n sqrt n) approach gets TLE in B
n = 10^9 an O(n) solution passes and everybody loses their minds
n = 10^6 an O(n sqrt n) solution doesn't pass and everybody loses their minds
STFU people :3
no offences, just kidding, i'm a noob
Got wa on 25th test case for div2B.i just increased size of string to 200005 from 100005 and it got accepted.can anyone explain why?
the answer can be as long as 200000 as given n will have 100000 digits... hope that helps.. :)
But i didnot put the answer in a string
maybe because your string b didn't have a proper '\0' null terminator in the right place. why still it gives correct output for increased array size I don't really know.
Lol, so stupid idea in Div1D really passed... I wonder, what did authors expect to see when they set 6 (!!!) seconds TL.
When you see jqdai0815 solved Div2 E in a period of 4 mins
The advanced algorithmic technique to get AC in div1D
18808466
18810544
Any idea as to why this works/doesn't?
The second submission has better memory locality so cache works better.
Mine are also fun:
18810392
18810587
tourist is't the first !
I am really surprised, my solution in B div1 is nlogn
TLE using cin even with ios::sync_with_stdio(0) and cin.tie(0) and cout.tie(0)
Used scanf and printf it got AC
TLE solution: http://codeforces.net/contest/687/submission/18804476
AC solution: http://codeforces.net/contest/687/submission/18810350
I never saw this happen on a site like Codeforces, I really can't believe it happened and why time limit is too strict?!!!
I wish i see good explanation to what i saw today and why the author made the time limit so small !!
If he made time limit 1.5 seconds as an example only intended solutions will pass too.
Your solution is slower than the intended one. Cin/cout is slower than printf/scanf.
I think gcd is log or more
so total is nlogn, only my constant factor is bigger, i know, but the same complexity, if time limit is too tight it means other languages will not get AC
sieve() takes a lot of time. My method just takes gcd() and does not take sieve() method, with " ios::sync_with_stdio(0) and cin.tie(0) and cout.tie(0)", and faster than your AC solution more than 100ms.
My Python solution was judged TLE on pretests, then submitted a C++ version and got AC =) I tought there were multiplicative factors on execution time to equalize results...
I think that if they make some updates like special Time Limit for each lang that's will be better
Yeah, but it's a huge amount of work =P
Still tourist is first
tourist — Petr = 1 ! The game is still on :)
Some time limits were definitely problematic :/ Enough people mentioned Div1B (input), but my problem was with Div1C — my O(N*K^2) solution got TLE, which I fixed easily with some microoptimizations but I didn't expect them to be needed... Was there some good reason for this time limit (e.g. a worse solution that might've passed otherwise)? If not, it's frustrating that constant factor optimizations made such a big difference in this contest (also in Div1D apparently).
Well after enough optimizations my O(n^4) for Div2E/Div1C got AC'd
18812616
Maybe they are justified about their strict time limits after all...
On Div2D/Div1B, many C++ codes which get TLE31 get AC by just adding one line of code at the beginning of main:
ios_base::sync_with_stdio(false);
example:
http://codeforces.net/contest/688/submission/18801250 vs http://codeforces.net/contest/688/submission/18811446
Time limit should not have been only 1 second.
Luckily I read this. http://codeforces.net/blog/entry/10
My solutions are showinh the verdict skipped what do i do are my submissions wrong or what??
If more than one submission for a problem pass the pretests, the most recent one will be considered and the rest will be skipped
I think it is intetesting that tourist-Petr is 1. But I don't deem it interesting that my rating is now 2899!:(
Matches your username ... I think that's pretty interesting
lol
The last chance to be a lgm before retiring? lol.
Possibly. It should be informed that retiring means the end of OI contests(for high school students) in China. If I fail in the contest in july(NOI 2016), I will retire and this is my last chance. And I should mention that programming contests in China are easy to fail.
But whatever it is I narrowly missed this chance. :(
matthew99 is Illuminati Confirmed
lol... really magic
Congratulations to matthew99 on winning China NOI 2016!
Can any body tell why this submission 18804553 is WA ? I saw some AC solutions and its the same idea .
I think you are not handling multiple connected components correctly. For example, on the case "4 2 1 2 3 4" your code does not put vertices 3 or 4 in either group.
Thanks, but as it said in the statement we can keep vertex for ourself , so i can keep vertex 3 and 4 , and give vertex 1 to Pari and give vertex 2 to Arya , right ?
You can keep a vertex to yourself . Not an entire component -_- . See the sample input , there are 4 nodes but node 4 isn't in the output !
I am thankful that my solution got hacked. Or else would have gone back to Div 2 today :)
Uh ... So there is UPD3 but no UPD2 ...
I think that's why we didn't see the score distributions, they skipped it (?) ... ._.
Now it's fixed, editorial is out guys! :D
I wish that next begin time will be early
Help needed!!
I tried to solve the problem DIV2 C in this way . Consider a component of graph if there is an odd cycle leave that component. Otherwise do a 2 Coloring of that component . Suppose two colors are red and green. Then for every component red vertices belong to one set and green vertices to other set. If we can find no component without odd cycle we print "-1".
But I am getting WA on 30th test case. Can somebody help me? Here is my submission :- http://codeforces.net/contest/688/submission/18815978
A graph G will have two disjoint vertex covers if, and only if, it is bipartite.
G is bipartite two disjoint vertex covers:
Choose partition A to be the first vertex cover. Since there are no edges (u, v) such that , one of the end points, say u, is in A and the other v is in partition B. Therefore, for every edge we have that it is covered by both a vertex of A and another by B, and each partition is a disjoint vertex cover.
Two disjoint vertex covers G is bipartite:
Suppose G is not bipartite, then, for any pair of partitions A, B, including our vertex covers, there exists an interior edge (u, v) in at least one of the partitions, say A. That is, we have an edge untouched by B. Which is an absurd, since both A and B are vertex covers.
I think that should be it (didn't find any hole in the second step of the proof). With this we have that the problem becomes a matter of determining if G is bipartite.
Where is editorial?
No rating change for me! Now that's called consistency. :p
waiting for the editorial ....
where is the editorial?. when it will be published?
In div2 B problem, constrants were n<10^100000. If constrants would be n<10^5, then it would be little difficult for me to think over that.
So Petr chose to sit still and defeat tourist without coding himself. Wow, he is about to win!
How I use Chinese Reminder theorem to Problem number D?