Hello, Codeforces!
I would like to invite you all to the International Coding Marathon 2017, under the banner of Technex'17, which will take place on Thursday 23rd February 2017, 20:05 IST. The contest will be held as a combined Div.1+Div.2 round which will be rated for participants from both divisions. The prizes for the event have been sponsored by D. E. Shaw & Co..
The Indian Institute of Technology (BHU) Varanasi, India is proud to present the 78th edition of its widely renowned techno-management festival, Technex'17, to be held from 24th to 26th February 2017. Offering a myriad of diverse events across fields such as programming, robotics, and aero-modelling, it witnesses enthusiastic participation from all across India and abroad.
The problemset has been prepared by me(DeshiBasara), vikhs_96, Prateek1996 and ishankarora. We would like to express our heartiest thanks to KAN for his constant help in preparing the contest and MikeMirzayanov for the amazing Codeforces and Polygon platforms. We also thank ashmelev and winger for their invaluable help in testing the problems.
UPD1: The start time of the contest has been delayed by 10 minutes.
UPD2: The scoring is 500-1000-1500-2000-2250-3000-3250.
UPD3: Thanks to all those who participated and heartiest congratulations to all the winners. The winners, who are eligible for prizes, will soon be contacted regarding the same.
Overall top 10:
1. ainta
2. tourist
3. LHiC
4. halyavin
5. jcvb
6. mnbvmar
7. uwi
8. jqdai0815
9. Syloviaely
10. Radewoosh
Indian top 5:
1. rajat1603
2. Baba
3. akulsareen
4. sampriti
5. PrashantM
Some of the problems were not up to the expectations. There were some issues with the site too. We deeply regret the inconvenience caused.
UPD4: The editorial for the round has been uploaded.
Prizes
Prizes worth INR 100,000 up for grabs!
Overall 1st place: INR 35,000. Overall 2nd place: INR 25,000. Overall 3rd place: INR 15,000.
1st place in India: INR 10,000. 2nd place in India: INR 6,000. 3rd place in India: INR 4,000.
1st place in IIT (BHU) Varanasi: INR 4,000. 1st place among IIT (BHU) Varanasi freshmen: INR 1,000
Participants will have 2 hours to solve 7 problems. The scoring distribution will be announced soon.
Good luck everyone! Hope to see you on the leaderboard.
Congratulations everyone on the 4th century of contests here on Codeforces :) :)
Both Div1 and Div2 Coder's Got opportunity to participate #400 Together
Hello everyone, I wrote a couple of hint-by-hint solutions here (problem C and problem D): https://www.commonlounge.com/discussion/b7b8f55f00bd4cd7a9dd7ef9d6067418/all/e1c9c7c034324f539d81343124095d72
Feel free to discuss the other problems as well. :)
I'm a most stupid man, failed system test C — solution , because I calculate k^i for i < 32 ....
changed it to i < 60, and AC.
Yeah many people made that mistake. Assuming that the corner case is going to happen for k = 10 instead of k = 2.
i made the same mistake! :(
I thought "What is INTERNAT? Is it a typo of INTERNET?" and it took me a while to understand that it is actually "INTERNATIONAL".
7 problems 2 hours! Hope A B will be for all.
All are for all, not just 2.
Wish ALL high rating.
:)
Lately there are to many contests from India. Soon codeforces will become an Indian contest webcite :)
Anyway, I hope all the red and yellow coders rating increases. All the dumb ones may suck.
I don't think you are Indian — you even don't know spelling of website?. Don't try to defame a country or a website. Hope you get a break from your miserable commenting life.
It doesn't matter what you think. Your life is miserable.
I am amazed to see how much free time you have.
so what the F should u do?
What happens if the 1st place in India get top 3 overall? Does he get both of the prize?
In such a situation, he will get the prize for top 3 overall. The India topper prize will be given to the next Indian in the ranklist.
Еще одна соточка) Ждем 500
Am I the only one who didn't know what this currency is??? And how much is it in Dollars :D
I know I won't get any prize, but I was just wondering :3
The currency mentioned is INR (Indian Rupee). 1 USD = 66.98 INR (As of today) INR 35000 = 522 USD, INR 25000 = 373 USD, INR 15000 = 223 USD
Thanks, Now I knew that the currency in India is Rupee :D
I hope that this time we will see at least two tasks with level >=Div1C and that there will be no tasks worth 2000 points that are a good fit for Div1A :P (yes, I am regarding to last contest).
IMHO problem D,E,F in last contest are good fit for div1B and are much harder than usual div1A. Maybe div1B is just as easy as div1A to red coders :D
I'm a simple man. I'll be happy if the round won't become unrated because of the issues with the server.
How happy would you be if the round was rated despite issues with the server?
Moderately happy.
G says "do some complicated digit DP". F says "do centroid decomposition". E looked nice at first, but after you find g(n) = n it's pure implementation. Stopped reading problems here. I think the problems are fine, but it suits better for a d2-only round. I don't say the problems are too easy — F and G are time-consuming and it's hard to solve everything in 2 hours. But there should be problems that require non-trivial idea.
Well, for me it is the first time when I wrote centroid decomposition. Now it is not just crazy idea that is only needed for problems that I can't solve anyway.
Yes, I didn't say the problems are easy. If the purpose of this problem is to introduce centroid decomposition, shouldn't it be used in educational rounds?
You don't need to break down by finding centroid of trees. Just the center of diameter will work as well I guess.
Edit: Something like this: 23787939
The centroid decomposition part of F is just Round 190 C (link: http://codeforces.me/problemset/problem/321/C)
BTW, I don't think "center of diameter" algorithm is correct for arbitrary graph, but maybe it's correct for problem F because the polygon partition graph is somehow special.
Absolutely agree, and you haven't seen D, it's the worst today, I guess (I've seen it hundreds of times).
Actually I suddenly find these contests very useful for my training to the finals but it was definitely not interesting to solve most of the last rounds.
Is it Rated?
Is this just a single event? If so, why is it called a marathon when it's just 2 hours?
Because Codeforces users run very fast.
I've just discovered that there are people who finish 42 kilometers (marathon distance) in 2 hours! That is insane!
2 Hours and a few minutes actually. That's why this round was extended.
Unlike Codeforces.
From the second paragraph I understood that this contest is a part of a bigger event.
Does anyone has GATEWAY TIMEOUT errors?
I do
BTW, nice way to check whether a site is down link
I hate postponing :D
Кфик не болей. Посылка уже тестируется минут десять.
I am doing contest from office , now you guys postponed it i have to go late by then :/
Waiting for a long time, but it is postponed. :( :(
Any writer's girlfriend missed the registration?
I have short.
You have short
I have long :/
You have nothing.
Rating prediction for this contest could be found here (after contest begins)
Extensions:
About CF-Predictor
Good luck & high rating to everyone!
This happened because I use free (low performance) server to calculate rating changes. Once a few minutes it does "standings request" to codeforces and then calculate prediction. So prediction always late for couple minutes. Yesterday, delay was up to 7 minutes.
Gives me a wrong rank
And according to this nobody has rank 651...
Queue :(
Seems like Unrated Contest :(
15 minutes still no verdict! should I leave this problem or not?! Not sure it will pass :( Please Make this Unrated. So many suffered from this —
never ending loading...
Is it just me or this contest is too lag to do any hacking?
Is Codeforces server on AWS ? If not, then I think it's time to move on AWS.
I am getting long loading times as well. not sure if there is a problem with my browser or with Codeforces.
same here but no response from judge site :(
Can't access ɔopǝɟoɹɔǝs˙ɔoɯ
It has been more than 20 minutes that I cannot open any of the contest pages...
If You are reading my comment,i have jumped off the roof (Connection TimeOut)
Endless loading drove me to play hearthstone in order to keep a good mind.
THIS TIME WE DON'T even NEED ANY REASON TO DO CONTEST UNRATED.
I think after such an incident there should be a announcement clearly stating further action like extending contest time/contest being unrated/no changes . Although, its done in most cases, not yet in this one though. EDIT: It seems they heard me.xD
ямар аймар гацдаг юм бэ хха болилоо нтр
My grandma runs faster than CF.
They said in a clarification "It was down for only a few minutes"
Is it only me who couldn't able to access the site whole time?
it was down for ~30 mins for me.
The site seemed to play Hide and Seek with me :P
if few minutes count for 20% of the contest then yes .
30+ mins for me
Lets pray and hope that this round will be unrated :(
Most of the time it was down for me.
It was down for me for about 20 to 25 minutes and even when it was up it was slow AF.
Still could be worse...
:)
It was down at least 30 mins for me too.
I believe it was down for 15 minutes. I submitted C and got WA on pretests and just after 15 — 16 minutes, I was able to submit again and got pretest passed.
Sometimes people exaggerate because it was not a good contest for them.
Nope.. Actually it was down for 30+ minutes. It was playing hide and seek >:(
"Extended by 10 minutes"? I had to wait more than 40 minutes to send C again, it means 250 points lost... Codeforces is a great platform but please fix that high availability.
The website was down for more than 20 minutes and earlier the queue was big..I submitted B for 700 but got only 500....please make this ****unrated****
Why is my 3rd hacking attempt still waiting while my 5th attempt has been judged? And someone else hacked that solution later and succeeded, while mine, which was earlier is still waiting.
my hack attempt: 303111
How come I submit for 700+ and get 600+? I suppose I'm not the only one encountering this.
Codeforces servers were slow for the contest.Lost lot of time because of this.
What a weak PP of problem C.So sad:(
Can anyone give a hint on how to solve D?
use DSU
How? I first thought DSU, but couldn't see how even and odds can be handled
Of course if we only care a switch need to be toggled odd number of times or even number of times.
If a door is locked,it means one of the switches which control it need to be toggled odd number of times while the other even.The situation that a door is unlocked is similar.
We can check if it's ok using weighted DSU
I still don't get it. We don't know which switch will be toggled how many times. For example, if door A has switch B and C, such that door A is initially closed, then B+C is odd, but we don't know whether B is odd or C is odd. How did you handle this?
Sorry if my question is stupid, I don't know how to apply this concept with weighted dsu very well.
Maybe that's because my English is really bad.
It means when we use DSU we record the relationship of a point with its father.I don't know its name in English exactly.
We needn't know exactly whether A or B is odd.We only need to know the sum of them is odd or even.If we need the sum is odd while we need the sum is even,the answer is NO.At any other situation,we can always get a solution to make all the door unlocked.
Why does DSU work? If we're doing regular 2-SAT we have to build directed edges from >y and >x right (this is the case that the doors are locked)? But in this case DSU makes these bidirectional edges, which I assume is incorrect? It code it and it actually works for some reason, but I have no idea why.
In this problem,all the edges are bidirectional.So we can use DSU.
Thank you. I was being stupid :)
I think that it is 2sat problem. I solved it using DSU.
for each room , let its 2 switches be a , b. Now if that room is off then a and b must be different else they must be same. So just make a graph and check for bipartite.
If all rooms are opened then answer is YES. Else, there must be at least one room that is locked, try first switch and second switch to make this opened with something like dfs.
isn't this 2^n?
You should just try first room that is closed.
I don't get it. so for each room that is closed, you have 2 choice. so you recursively do this. How is this not 2^n?
Notice that if I have a valid solution, I can toggle all switches and the solution remains valid. So set Switch 1 to 0. This will decide the values of all switches which are connected to 1. (Using the doors as 'edges' of the graph).
Do this for each connected component once. Complexity O(N)
nvm, it is wrong. There can be multiple connected compunds:(
I think 2-SAT
Its basically a slightly modified version of this problem
Hey, I wrote hint-by-hint solutions here: https://www.commonlounge.com/discussion/b7b8f55f00bd4cd7a9dd7ef9d6067418/all/e1c9c7c034324f539d81343124095d72
Asking for answer modulo 1e9+7 when it's quite small is evil. :(
Actually I didn't even check if I passed the pretest because the internet is too slow. Then I found I didn't modulo 1e9+7 when I submitted F. I left the bug there for half an hour :P
Well, at least it was in the pretests
I did the exactly same thing. Fortunately, I saw the line asking for modulo in less than 10 minutes after submitting (of course I couldn't see that the solution actually got WA, because 10 minutes is way to fast for one to get the score)
Actually, I also was a victim of that, but I think it was necessary. Otherwise it would be strong suggestion that result is small which was probably a big hint in this problem.
B hack?
2
F*ck
Is it the correct answer?
11 1Yes.
I thought it was in pretests.
I had an if for n < 3, but I was printing 2 for primes and 1 for composite. It failed pretests, because I printed 1 and the color was 2.
Lol ! I was hacked twice in problem C one hack for K = 1. and one hack for K = — 1 :D
I wrote for 1 but missed for -1 :P
Lol I have no idea how didn't I see the modulus in the problem statement :D But that was fun , I was waiting for the second hack :D
same here totally missed that mod in constraints
I covered k = 1, but forgot k = - 1 and hacked people with these two cases. Nobody hacked mine lol
ROFL :D Then you didn't have a >= yellow in your room :D
Lucky!
codeforces really needs to scale up to handle more users.
What was pretest 4 problem D?
In this pretest graph for switches isn't connected.
Could someone give me a hint for problem C please?
Prefix sum + map for frequency
i used unordered_map and i got tle. i know that unordered_map is teoretically a lot better, can you help me with an explanation please?
Same for me :'(
Count me in too :( I attempted C before B and now my C failed due to this and B got less points anyway.
me too..
Unordered map isn't a ordered container.You'll have to calculate lower/upper bound in this problem.
Depends on the solution. I only need to check for inclusion in a set.
unordered_map's is constant time lookup in the best case, but the worst case is linear lookup if there are many hash collisions. It is possible to generate test cases against unordered_map. I also used unordered_map and got TLE. After failing systest and changing to map, it got AC. Should've known this earlier :(
Hey, I wrote hint-by-hint solution to problem C here: https://www.commonlounge.com/discussion/b7b8f55f00bd4cd7a9dd7ef9d6067418/all/e1c9c7c034324f539d81343124095d72
Thanks
Steps to solve problem E:
1.f(n) = φ(n),it it obvious.
2.Open aops.com ,search for g(n) and find that g(n) = n.
3.It is obvious that φ(...φ(n)) is quickly decreasing.
That's all,find Fk(n).
Very original to combine all 3 steps, like.
Or google phi-phi-phi on hackerearth instead.
I open www.baidu.com in step 2 :D
Попробовал в D написать dsu. Объявил 4 переменные (f1, f2, g1, g2), осталось написать union(f1, g1), union(f2, g2).
Пишу union(f1, f2), union(g1, g2), блокирую. Ах да, оно проходит претесты.
Ужасно перевели задачу B на русский: кто бы мог подумать, что простой делитель — это делитель, являющийся простым числом, а не делитель, отличный от 1 и самого числа. Уверен, большинство русскоязычных об это споткнулись.
Great round, very nice problems!
Wanted to submit C in last 2 minutes but nevermind codeforces servers didn't wanted me to gain ratings :/
I was waiting for submitting B more than 30 minutes. The server was totally down. Please make it unrated. MikeMirzayanov
YES IT HAPPENED TO ALMOST EVERYONE.
tourist expression when reading your comment :
THAT'S WHY I SAID ALMOST HE SOLVED ALL QUESTIONS IN CASE OF SERVER DOWN
BELEIVE ME IF THERE WILL BE A TSUNAMI,tourist WILL TOP IN CONTEST
Is there any nice way to solve F?
I could see that the dual graph of the planar graph described would be a tree and that we should do centroid decomposition on it but I had no clue as to how to actually implement anything.
I can probably help with implementation after converting polygon to graph. You can decompose tree using center instead of centroid using BFS-like idea (and DFS to find center). I've done something similar here: 23787939
IMO, the most challenging part of this problem was building the graph (tree ;) The idea I used was:
The most important fact I used to build this tree clean was that the id of each region is determined by the two nodes with bigger id on the border of the region.
Put the nodes of the polygon in a line in order 1, 2, ..., n Then put the diagonals as segments on this line (u, v) (where u < v) Notice that if two segments have non zero intersection, one is completely inside the other. If we include the segment (1,n) we can say that each diagonal denotes the region that is inmediatly above it. The DIRECT including relation might be interpreted as a parent-child in a tree, Order this segments by start in increasing in order and break ties by length (in decreasing order). This order is the preorder of the tree, so you only need to rebuild the original tree from the preorder.
The rest of the problem, is using centroid decomposition, similar problem where the tree is given can be found here on codeforces.
My solution. 24937275
Good luck
I want to hack someone in the last minute, but CF lags and forbids me to do so :( (Quite sure his solution is wrong)
**15 MINUTES LONG QUEUE ANF AFTER THAT 45 MINUTES OF SERVER DOWN **
** I JUST REMEMBERED PRINCIPLE OF MUTUAL EXCLUSION**
** 1 HOUR SITE RELATED PROBLEM EXISTED AND IN RETURN WE GOT 10 MINUTES._wOWO_
Let's vote: Strawpoll.
Those polls always get biased results. People who are fine with the status quo will scroll past the poll while those who want the round to be unrated will vote.
When you missed E because of slow Internet connection... I would have a sleepless night if that solution got AC...
Is it just me or will unordered_map TLE on C? Somehow when I test my solution on a large case for C it doesn't seem to be able to close to running in time whereas changing it to map makes it work almost instantly. Not sure why this is happening (I didn't try to construct cases to fail unordered_map solution)
24923074 (n = 100000, k = - 2, ai = 229)
I think first checking whether an item exists in the map could speed up as it won't store anything in map incase no such value exists.
I tried to construct cases to fail unordered_map.
Generator
It takes about 4 seconds.
Why it TLs unordered_map in GCC (24943025), but in VS2010 it is AC (24943348)?
Because hash maps implementations are different. GCC uses libstdc++ library while Visual Studio uses Microsoft STL.
That can give MLE, but I am not sure. If you want to get some element from the map, better to do
if (map.find(element) != map.end())instead of just takingmap[element]Ty CF. If you didn't crash I could have had F. :'(
It would be nice, if problemset could be loaded as pdf by clicking just one button near the button "Complete problemset". When contest lagged today, I already solved E and sent it(although forgot to make %MOD operation and knew verdict only after 20mins) and wanted to open F, but I couldn't do this for the next 20 minutes. If problemset was downloaded at the start, problem could be read during this hard laggs.
You can click on Complete Problemset and then print the file to pdf.
I hacked one person with this test 5 8 0 0 0 0 0
He calculates all power till 50,then push them to set and forget about overflow. And i found that 8^21 = 0.
I accidentally resubmitted C twice instead of once due to network issue 24941488 24941490 What can I do? This is really sad.
Any hints on how to solve F? The only solution I thought of is build a tree and then find center of the tree, color it, remove it from the graph and recursively color the remaining set of trees but that doesn't look like an easy solution to implement.
Not the center but the centroid. The other part is correct.
It's F. It doesn't need to be easy to implement.
Most of the solution is unfortunately copypasting. First, you should divide a planar graph into "walls" and then you perform centroid decomposition on it. Both functions can be copypasted from a library, if you have one. I didn't have :c
My approach: Sort the walls based on their "length". Now the wall with minimum length and the boundary between two endpoints form a region. Let W denote the wall and R1 denote the region. Remove R1 and now W is a new boundary edge. Then mark R1 on W. When you finally remove some region R2 containing boundary edge W, build an edge between R1 and R2.
Has anyone this bug? I hope that this submission will be taken into account.
The problems take time but the ideas were straightforward.
Maybe only E wasn't since you needed to write something down before conclusions, unlike F which was screaming "build this fkin tree and run CD".Actually E is pretty known(that sum of phi (d) is N — 1 for d | N) so neither E was much of a problem
Oh, if this is well known, then yeah, boring problemset.
There were some serious technical problems with the website in this contest.
Предлагаю сделать раунд нерейтинговым. Очень долго(час) не грузилась вкладка "отослать"
Why do I get TL 13 in C? (code)
I've wasted more than an hour trying to pass test 13. In the end I got to know that set/hashset count works in linear time.
Used map and everything will be fine :(
E — let's add a random function which is well known to be an identity function
F = http://codeforces.me/contest/321/problem/C + duality on planar graphs
great problemset...
I've finished the code for F 3 minutes after the contest ended. However, I had some trouble in building the graph (well the tree), especially because it was hard for my to determine the polygons. How did you do this part? I've hardly managed to come up with some strange recursive function and some strange disjoint data set to find out the polygons.
Ohh and about the fact that F didn't bring anything new, let alone E, I agree. I also hated that most of the scoreboard was decided based on hacks. In my room there were 4 or 5 hacks in total. I found 3 of them by myself and CF was moving so slowly that someone else got them before I could even type the numbers...
My method:
build initial graph from i to i — 1 as well as from 1 to n
build additional edges as input, two-wayed
build the graph from largest valued polygon:
first, identify the largest element that still has an edge left choose the closest edge to walk, where the distance is defined as the "non-input" edges needed to walk from u to v, i.e. u,u-1,...,v delete that edge, mark it too. (when an edge is marked twice you add it into the tree) define lastdist = dist(first vertex, second vertex) while we didn't return to largest element find the furthest vertex from itself, that does not exceed or equal n — lastdist delete the edge, do markingYa and this problem is too original and standard... (and boring)
I agree, hacks will play a big role in the standings. It's the sort of thing I always do when finding components in a planar graph. For every node, sort the edges by their angle. In this problem, that's just sorting them by their index.
Now, let's say we will traverse each component in CCW order. Find a previously unused (directed) edge and then in each step choose the edge that creates the smallest directed angle with the previous one, this can be done with a simple lower_bound. When you return to the starting node, you found a component.
Savage of a contest
hogloid, I hate your -1 :D
I couldn't open the site for over 30 minutes. I think it should be unrated.
LOL, that's a "few" minutes
How to solve C?
I wrote hint-by-hint solutions here: https://www.commonlounge.com/discussion/b7b8f55f00bd4cd7a9dd7ef9d6067418/all/e1c9c7c034324f539d81343124095d72
#FIXCF
How to understand F?
have waited for "codeforces.com/contest/776/submit" for over 30min
Couldn't do anything for 20 minutes after I finished F. I hadn't even read G then. Although I'm not sure if I can finish G in contest time, still feel a little bit upset :(
I strongly recommend to hold such a kind of contest in Div2 only...
This has prevented lots of black coders winning a div2 contest =)
My D will fail because I assumed there is only one connected component :(
We're friends... mine will too XD
In task C, the current winner mnbvmar has:
Looks like it's going to fail?
Seems like a lot of people did miss the k = 1 or k = - 1 case, so we could probably expect some changes in the leaderboard.
you missed the first part ?
He is using int and multiplying by K until 1e16.
You forgot this:
This should be considered code obfuscation. Obfuscating the code just for the purpose of reducing other contestants' points for incorrect hacks.
The reason for this, is that this define is among code which is not considered the actual solution. You should not be reading somebody's template code in order to understand the solution.
Also if that code is considered the actual part of the solution then all the macros and functions should be used in the program. If they are not used — it means that this is unnecessary code, which makes it harder to read and understand the solution.
Go away. I am sick and tired of explaining why this is huge bullshit.
No it's not. Making solutions unnecessary complicated is a bad practice in general — you should have known that.
It is also against the rules which says that there can be no more than x% of unused code. That rule is usually violated by some templated code and nobody complains about it as everybody just skips that and reads the "real" solution. If you are required to read the template code in order to understand the solution that rule should apply.
You are explaining something which can't be explained. Not a big surprise that you are sick and tired of that. If you see the int, it should be an int. If it was some sort of custom type like INT or INT64 etc., it could be justified. Such thing at least indicates, that you should go and check that type. It is not possible to deduce that int is long long, without carefully reading the whole templated code.
I care about getting ACs instead of WAs because of overflow and I don't give a single %^&* about people unsuccessfully hacking my code, I do not have any intention in misleading people (even though it may mislead somebody, but I don't care about it). End of topic.
Your intentions do not matter. What matters is % of unused code. That rule is usually relaxed by the fact that you put a bunch of templated code, which is not used in your solution.
I also said few times already, that changing existing type to something else, requires reading the whole source code — which does mean that your templated stuff, should be considered a core part of it. Because of that, you should reduce your template and includes only to the things which are really used in your solution.
Everything which is not used, should be counted against the % of not used code.
There is no such rule on CF. Haven't you seen codes with 1000 lines of template codes at last pages of sort by solution size submissions. Such a rule exist on TC.
This is not code obfuscation. It is to avoid unnecessary WA caused by overflow.
When you hack, you're supposed to know the language specific, in this case you should know that
#define int lnog longis possible in C++.oh I didn't read that..
EDIT : oh turns out it is fine....
Tricky: define int LL
RIP solutions of Those who handled k = 1 but not k = -1 case in C.
After a long time there comes a contest in which i could do both A and B....Hoping to get rejected in system testing....
Codeforces can you please stop allowing contests from Indian Problemsetters? Especially contests with blue problemsetters...
If you really want to have these shitty contests, make them Div 2 only please.
You are kidding, right? The problem was with the servers. Don't target people who were not responsible for making this contest what it was.
I think he meant the problem quality was not good enough for div1 contestants.
Racist...
Last 2 contests have been by indian blue problemsetters, and the problem quality is utter SHIT.
If you don't believe me go check the comments under the last contest, and you'll see I'm not wrong.
You can't draw such conclusions from 2 contests. Having two shitty contests in a row is in no way justification to ban an entire country from problemsetting.
Furthermore, I'm willing to bet that the problem has less to do with India and more to do with blue. The way those contests were set up also makes me believe they received less coordination from KAN and the Codeforces team than the average round (since they were created for some sort of festivals, not regular rounds). I might be wrong on this obviously.
"Utter shit" is also definitely exaggerating. The problem quality was below average, but I've seen way, way worse.
What were you missing, people who got WA #3 on F?
C was given on geeks for geeks just needed minor changes, and the long queue otherwise the contest was good.
About 30 minutes I could not do anything on CodeForces :(
Problem G:
Why are there no sample case whose digit is more than 4? Sample case should contain "essential" case I think, and in this problem, the main part is DP on digit, but all sample cases don't require that!
next time you host a contest for Div1 and Div2 combined, please make sure that the site doesn't get down in the middle of the contest
Please take my 5 cents
and I have a not-necessary 1e9+7
Super fast System Testing. Came late but came strong...
I have a dream, that one day codeforces will be stable and fast
Please add problems to practice section.
Is this contest ranked? The site did not work most of the time!!!
TLE on test 101 in problem C :(
C — unordered_map: TLE. map, set: AC. seriously?
yes, because element accessing complexity is linear and logarithmic respectively.
I think you are not right, because how i know, unordered_map make this for constant, not linear
Then what is the reason behind TLE for using unordered_map ??
Constant is bigger, than log sometimes(
In the worst case — linear.
No, paradox1 is correct in the worst case.
unordered_mapuses a hash function to determine where to store the value. On random data, you can expect that there will be not too many collisions (that is, different values that hash to the same integer) and you would expect each lookup to be (roughly) O(1). However, if there are a lot of collisions, then each lookup can be as bad as linear. Test cases can be constructed (for example, here) to try to make each lookup linear. On the other hand,mapis guaranteed O(log n) in the worst case.Similar thing happened to me yesterday in a contest.
scanf/printf: TLE
cin/cout: AC
Is this even possible?
It happened.
Can i see the submissions, please?
TLE-https://www.hackerearth.com/submission/7372868/
AC-https://www.hackerearth.com/submission/7373096/
Thanks.
unordered_map is not suitable for a small number of elements (which in this case is 10^5) as it works on hashing..(Probing slows it down.. due to collisions)...
Nice problems!
Can someone be generous enough to tell me how to decide whether to use normal map or unordered map ????
Hash your number by xoring with a random number when using unordered_map.
How can I generate "really" random numbers?
You don't need to? just use rand so that neither a hacker nor system test can guess the salt value.
It's never "truly" random. We can generate pseudo-random numbers using rand() function in C++, which will do the job the same way in practice.
Always use
map=)A hint for the next contests: Open all problem pages at first minute, at least you will be able to read the others problems and dont feel useless when the site crashs completely :(
What is WA in D on test 55, jqdai0815 also had this problem? :(
When it's unlocked, you need to add edges between a and b.
I guess D was supposed to be solved with SCC, (at least I did it that way). This method does not yield any corner cases.
When you see second sample of problem A:
what is the solution of problem c. Thanks in advanced.
I used prefix sum, and binary search.
Can you please tell me the idea of running binary search on prefix sum in detail.
Store all the numbers that should be found (k^0, k^1, ..., k^j) in the array (note that max number that can be found is 10^9 * 10^5 = 10^14). The size of this array is logarithmic (note that you should probbably treat k=1 and k=-1 as a special case and form the array manually).
In order to find the ranges with sum
xyou can use the prefix sums. For each prefix sum p[i] you should find the amount of sums p[j] such thatp[i] - p[j] = x. It can be done using a map.My code: link
http://codeforces.me/contest/776/submission/24923436
http://codeforces.me/contest/776/submission/24943032
wtf :/
please re-evaluate my submission :/
966 is extremely close to 1000 so its just a matter of fluctuation.
Blue at last ,after a long wait .....
I got TLE for using unodered_map. But when I used "map" instead of "unordered_map" it passed.
with map 24943858
with unordered_map24939864
Can anyone please explain..
See here.
This post can be useful
Had +17 in prev round, now -17 lmao.
Where is editorial?
"I'm fucked up,I'm black and blue"...
Problem:C -Mollys Chemical Hey, I am getting TLE on 13th tcase. While most of the solutions are based on similar logic. My time complexity is O(N*60*log(N)). Solution:http://codeforces.me/contest/776/submission/24941529
Time complexity for multiset
count(x)is O(lg n + (number ofxs in the multiset))Search of a lot of similar values in multiset can be linear. Use map<ll, int> instead.
in Problem D
"You need to tell Sherlock, if there exists a way to unlock all doors at the same time."
So this doesn't mean that I need to find a way to toggle the switches so that the last move will toggle all the doors from locked to unlocked, and now they are all opened at the same time !!?
Wow. I waited for 20 minutes after making a submission, without being able to find out whether it got accepted or not or even read other problem statements. After that, I just went home, as it was clear the contest was going to be unrated and there's no point in waiting for Codeforces to work again. Now it turns out the contest is rated and my last submission got WA on E because I forgot the %mod operation.
#roadtoyellow
There's nothing really tricky in that, just add "unordered_" in C, change "sw" to "doors" in D and forget "+1" when sorting array in F :P. And before that, screw up similarly 6 previous contests.
Now I need to screw up few more contests as dreamoon_love_AA did to pretend I did everything on purpose :P.
If only getting yellow is as easy from down here :(
Actually I don't get it. Was wondering what you meant that adding "unordered" solves C — I used unordered map and it did not work. After reading this post (and looking on your solutions) I submitted it with normal map, and it passed... Perhaps there is some rule of thumb when use unordered_map, and when to use map? Isn't it actually a flaw of the tests? The programs should not fail due to small multiplicative constant, should they?
He meant adding unordered gave him TLE — see his submissions. Also, its not multiplicative constant but O(n) worst case time for unordered map vs O(logn) for map.
I know. Perhaps did not state it clearly enough. What I am asking is "Why is it so?". Appears stupid.
Ah, and the complexity is constant on average and we perform many queries, so it should be faster.
Complexity is constant on average in an ideal world(perfect hash functions, random data), but you can construct test-case against stl's implementation knowing the inbuilt hash function and clever test data.
Ok, give me a test which makes a randomized quick-sort quadratic please...
Anyways I believe the tasks should not be about using the correct implementation of map, but rather about a the Mathematical problem.
Sorry, the difference is quite big.
Then the question is not about the test but rather why the unordered map performs so horribly bad here?
Its due to hash function. If you know which values collide, you can create those values only. Such a case has already been provided which breaks unordered map hash function in this question here: http://codeforces.me/blog/entry/50585#comment-345218.
thanks for the link!
I wanted to explain how one can screw up contest in three simple steps. Adding unordered was simple trick to magically transform AC into TLE.
Let's guess who will be Sorry_Swistakk.
Haha :D. With my current performance anyone will do ;p.
Why this contest is rated? Is it because we have 10 more minutes to deal with the previous 30 minutes' trouble??
Even then, it doesn't make sense. Those users who started working on a problem shortly before Codeforces stopped working, were almost completely unaffected. Whereas other users couldn't do anything during that time. 10 extra minutes for everyone won't fix the disadvantage some participants were already placed in.
At this point I just try to open all the stataements asap. I mean, it doesn't excuse the lags but it helps in case they actually happen.
Deleted
D was a nice problem !!
Editorial??
Can anyone tell me why my problem C got TLE when I use unordered_map, but got accepted after I change unordered_map to map, and nothing else? Does it have constant as huge as O(logn)?????
There is anti-hash test for C++ apparently. Ironically enough in Java it is the other way around, HashMap (unordered_map) is fast enough, and TreeMap (map) is too slow.
How to prove that phi(phi(...(phi(n))) will become 1 fast enough?
If n can be divided by 2, then we have phi(n)<=n/2, otherwise we will find phi(n) be divded by 2 if n>1.
phi(even) number is atmost half of it. so in 2 steps a number decreases by atleast half of itself. there you go.. O(log N). EDIT : I did not see the others comment before me :P
Note that, for n>2, phi(n) is always even. So, after the first step we will always have even numbers (except the last 1). For even numbers, phi(n)<=n/2 (because all even numbers below n are not coprime with n). So, at every step phi(n) reduces by at least half, which leads to log(n) time.
Thanks guys, I've got it. Sorry for such a stupid question :)
D is almost the same as this one if we consider switches as nodes and doors as edges.
And in F, the coloring part is exactly the same as this one.
Such old ideas can hardly surprise me :(
In problem F it wasn't trivial to come up with an easy implementation to build the tree. The coloring part is common by now, therefore I think the complexity wasn't so low.
If somebody wants link for similar to D one where they can submit themselves, this is link.
B:failed system test on test 4 ... does the pretest have only 3 test cases?:||
The harder version of problem E was already used on Codeforces in our with riadwaw contest: http://codeforces.me/contest/396/problem/E. (One can say that today's E had a different idea, but no, it does not have an idea).
I think we should avoid problems with output Yes/No and small number of pretests. I saw really mad solutions in my room. To be honest they were completely bonkers and those solutions passed pretests. Unfortunately I didn't have the courage to hack them. For me they were equivalent to:
(rand()&1) ? puts("Yes") : puts("No").On the other hand my solution in which I used n instead of m in one place passed pretests too, which costs me many points.
Could anyone explain solution of problem D?
How to get Prizes? I didn't receive any message.
We will send you the money in a few weeks. Sorry for the inconvenience caused.