### DeshiBasara's blog

By DeshiBasara, 4 years ago,

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 I_Remember_Olya_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. Retired_MiFaFaOvO
9. Syloviaely

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.

• +201

 » 4 years ago, # |   +106 Congratulations everyone on the 4th century of contests here on Codeforces :) :)
•  » » 4 years ago, # ^ |   +19 Both Div1 and Div2 Coder's Got opportunity to participate #400 Together
•  » » 4 years ago, # ^ |   +18 Hello everyone, I wrote a couple of hint-by-hint solutions here (problem C and problem D): https://www.commonlounge.com/discussion/b7b8f55f00bd4cd7a9dd7ef9d6067418/all/e1c9c7c034324f539d81343124095d72Feel free to discuss the other problems as well. :)
•  » » » 4 years ago, # ^ |   +3 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.
•  » » » » 4 years ago, # ^ |   0 Yeah many people made that mistake. Assuming that the corner case is going to happen for k = 10 instead of k = 2.
•  » » » » 4 years ago, # ^ |   0 i made the same mistake! :(
 » 4 years ago, # |   +248 I thought "What is INTERNAT? Is it a typo of INTERNET?" and it took me a while to understand that it is actually "INTERNATIONAL".
 » 4 years ago, # |   -33 7 problems 2 hours! Hope A B will be for all.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +14 All are for all, not just 2.
 » 4 years ago, # |   -23 Wish ALL high rating.:)
 » 4 years ago, # | ← Rev. 2 →   -243 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.
•  » » 4 years ago, # ^ |   +43 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.
•  » » » 4 years ago, # ^ |   -169 It doesn't matter what you think. Your life is miserable.
•  » » » » 4 years ago, # ^ |   +5 I am amazed to see how much free time you have.
•  » » 4 years ago, # ^ |   0 so what the F should u do?
 » 4 years ago, # |   +13 What happens if the 1st place in India get top 3 overall? Does he get both of the prize?
•  » » 4 years ago, # ^ |   +65 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.
 » 4 years ago, # |   +10 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
•  » » 4 years ago, # ^ |   +37 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
•  » » » 4 years ago, # ^ |   +3 Thanks, Now I knew that the currency in India is Rupee :D
 » 4 years ago, # |   +265 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).
•  » » 4 years ago, # ^ |   +31 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
•  » » 4 years ago, # ^ |   +69 I'm a simple man. I'll be happy if the round won't become unrated because of the issues with the server.
•  » » » 4 years ago, # ^ |   0 How happy would you be if the round was rated despite issues with the server?
•  » » » » 4 years ago, # ^ |   +16 Moderately happy.
•  » » 4 years ago, # ^ |   +238 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.
•  » » » 4 years ago, # ^ |   +19 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.
•  » » » » 4 years ago, # ^ |   +24 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?
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +11 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
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +13 The centroid decomposition part of F is just Round 190 C (link: http://codeforces.com/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.
•  » » » 4 years ago, # ^ |   +31 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.
 » 4 years ago, # | ← Rev. 2 →   -77 Google Hash Code starts an hour after the round ends.. It'd be a really exhausting day!
 » 4 years ago, # | ← Rev. 3 →   -60 Is it Rated?
•  » » 4 years ago, # ^ |   0 The contest will be held as a combined Div.1+Div.2 round which will be rated for participants from both divisions.
 » 4 years ago, # |   +93 Is this just a single event? If so, why is it called a marathon when it's just 2 hours?
•  » » 4 years ago, # ^ |   +130 Because Codeforces users run very fast.
•  » » » 4 years ago, # ^ |   +20 I've just discovered that there are people who finish 42 kilometers (marathon distance) in 2 hours! That is insane!
•  » » » » 4 years ago, # ^ |   +32 2 Hours and a few minutes actually. That's why this round was extended.
•  » » » 4 years ago, # ^ |   +51 Unlike Codeforces.
•  » » 4 years ago, # ^ |   +5 From the second paragraph I understood that this contest is a part of a bigger event.
 » 4 years ago, # |   +66 Does anyone has GATEWAY TIMEOUT errors?
•  » » 4 years ago, # ^ |   +34 I doBTW, nice way to check whether a site is down link
 » 4 years ago, # |   +6 I hate postponing :D
 » 4 years ago, # |   -8 I am doing contest from office , now you guys postponed it i have to go late by then :/
 » 4 years ago, # |   0 Waiting for a long time, but it is postponed. :( :(
 » 4 years ago, # |   +41 Any writer's girlfriend missed the registration?
 » 4 years ago, # |   +5 I have short.
•  » » 4 years ago, # ^ |   +10 You have short
•  » » 4 years ago, # ^ |   0 I have long :/
•  » » » 4 years ago, # ^ |   0 You have nothing.
 » 4 years ago, # |   +51 Rating prediction for this contest could be found here (after contest begins)Extensions: About CF-PredictorGood luck & high rating to everyone!
•  » » 4 years ago, # ^ |   +29
•  » » » 4 years ago, # ^ |   0 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.
•  » » 4 years ago, # ^ |   0 Gives me a wrong rank
•  » » » 4 years ago, # ^ |   0 And according to this nobody has rank 651...
 » 4 years ago, # |   0 Good luck everyone!
 » 4 years ago, # |   +2 Queue :(
 » 4 years ago, # | ← Rev. 3 →   +31 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 —
 » 4 years ago, # |   +7 Is it just me or this contest is too lag to do any hacking?
 » 4 years ago, # |   +37 Is Codeforces server on AWS ? If not, then I think it's time to move on AWS.
 » 4 years ago, # |   +8 I am getting long loading times as well. not sure if there is a problem with my browser or with Codeforces.
•  » » 4 years ago, # ^ |   0 same here but no response from judge site :(
•  » » 4 years ago, # ^ |   0 Other sites were loading very well except Codeforces on my browser. bad luck :(
 » 4 years ago, # |   +14 Can't access ɔopǝɟoɹɔǝs˙ɔoɯ
 » 4 years ago, # |   +31 It has been more than 20 minutes that I cannot open any of the contest pages...
 » 4 years ago, # |   +4 If You are reading my comment,i have jumped off the roof (Connection TimeOut)
 » 4 years ago, # |   0 Endless loading drove me to play hearthstone in order to keep a good mind.
 » 4 years ago, # |   +18 THIS TIME WE DON'T even NEED ANY REASON TO DO CONTEST UNRATED.
 » 4 years ago, # | ← Rev. 2 →   +2 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
 » 4 years ago, # |   0 ямар аймар гацдаг юм бэ хха болилоо нтр
 » 4 years ago, # |   +196 My grandma runs faster than CF.
•  » » 4 years ago, # ^ |   -25 MY GRANDMA RUNS FASTER THAN CF AND SHE IS IN FREKIN' COMA
 » 4 years ago, # |   +33 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?
•  » » 4 years ago, # ^ |   +49 it was down for ~30 mins for me.
•  » » 4 years ago, # ^ |   +8 The site seemed to play Hide and Seek with me :P
•  » » 4 years ago, # ^ |   +3 if few minutes count for 20% of the contest then yes .
•  » » 4 years ago, # ^ |   +9 30+ mins for me
•  » » 4 years ago, # ^ |   +2 Lets pray and hope that this round will be unrated :(
•  » » 4 years ago, # ^ |   0 Most of the time it was down for me.
•  » » 4 years ago, # ^ |   0 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...:)
•  » » 4 years ago, # ^ |   0 It was down at least 30 mins for me too.
•  » » 4 years ago, # ^ |   0 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.
•  » » » 4 years ago, # ^ |   0 Nope.. Actually it was down for 30+ minutes. It was playing hide and seek >:(
 » 4 years ago, # |   +71 "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.
 » 4 years ago, # | ← Rev. 2 →   +21 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****
 » 4 years ago, # |   0 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
 » 4 years ago, # |   +2 How come I submit for 700+ and get 600+? I suppose I'm not the only one encountering this.
 » 4 years ago, # |   +18 Codeforces servers were slow for the contest.Lost lot of time because of this.
 » 4 years ago, # |   +2 What a weak PP of problem C.So sad:(
 » 4 years ago, # |   +18 Can anyone give a hint on how to solve D?
•  » » 4 years ago, # ^ |   +1 use DSU
•  » » » 4 years ago, # ^ |   0 How? I first thought DSU, but couldn't see how even and odds can be handled
•  » » » » 4 years ago, # ^ |   0 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
•  » » » » » 4 years ago, # ^ |   0 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.
•  » » » » » » 4 years ago, # ^ |   +3 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.
•  » » » 4 years ago, # ^ |   0 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.
•  » » » » 4 years ago, # ^ |   0 In this problem,all the edges are bidirectional.So we can use DSU.
•  » » » » » 4 years ago, # ^ |   0 Thank you. I was being stupid :)
•  » » 4 years ago, # ^ |   0 I think that it is 2sat problem. I solved it using DSU.
•  » » 4 years ago, # ^ |   +41 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.
•  » » 4 years ago, # ^ |   0 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.
•  » » » 4 years ago, # ^ |   0 isn't this 2^n?
•  » » » » 4 years ago, # ^ |   0 You should just try first room that is closed.
•  » » » » » 4 years ago, # ^ |   0 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?
•  » » » » » » 4 years ago, # ^ |   +8 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)
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 nvm, it is wrong. There can be multiple connected compunds:(
•  » » 4 years ago, # ^ |   0 I think 2-SAT
•  » » 4 years ago, # ^ |   0 Its basically a slightly modified version of this problem
•  » » 4 years ago, # ^ |   +21 Hey, I wrote hint-by-hint solutions here: https://www.commonlounge.com/discussion/b7b8f55f00bd4cd7a9dd7ef9d6067418/all/e1c9c7c034324f539d81343124095d72
 » 4 years ago, # | ← Rev. 2 →   +159 Asking for answer modulo 1e9+7 when it's quite small is evil. :(
•  » » 4 years ago, # ^ |   +35 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
•  » » » 4 years ago, # ^ |   +75 Well, at least it was in the pretests
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 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)
•  » » 4 years ago, # ^ |   +104 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.
 » 4 years ago, # |   0 B hack?
•  » » 4 years ago, # ^ |   +1 2
•  » » » 4 years ago, # ^ |   0 F*ck
•  » » » 4 years ago, # ^ |   0 Is it the correct answer?11 1
•  » » » » 4 years ago, # ^ |   0 Yes.
•  » » » 4 years ago, # ^ |   0 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.
 » 4 years ago, # |   +11 Lol ! I was hacked twice in problem C one hack for K = 1. and one hack for K = — 1 :D
•  » » 4 years ago, # ^ |   +3 I wrote for 1 but missed for -1 :P
•  » » » 4 years ago, # ^ |   +1 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
•  » » » » 4 years ago, # ^ |   +3 same here totally missed that mod in constraints
•  » » 4 years ago, # ^ |   +9 I covered k = 1, but forgot k =  - 1 and hacked people with these two cases. Nobody hacked mine lol
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 ROFL :D Then you didn't have a >= yellow in your room :D
•  » » 4 years ago, # ^ |   0 Lucky!
 » 4 years ago, # |   +35 codeforces really needs to scale up to handle more users.
 » 4 years ago, # |   0 What was pretest 4 problem D?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 In this pretest graph for switches isn't connected.
 » 4 years ago, # |   +4 Could someone give me a hint for problem C please?
•  » » 4 years ago, # ^ |   +6 Prefix sum + map for frequency
•  » » » 4 years ago, # ^ |   +12 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?
•  » » » » 4 years ago, # ^ |   0 Same for me :'(
•  » » » » » 4 years ago, # ^ |   0 Count me in too :( I attempted C before B and now my C failed due to this and B got less points anyway.
•  » » » » 4 years ago, # ^ |   0 me too..
•  » » » » 4 years ago, # ^ |   0 Unordered map isn't a ordered container.You'll have to calculate lower/upper bound in this problem.
•  » » » » » 4 years ago, # ^ |   0 Depends on the solution. I only need to check for inclusion in a set.
•  » » » » 4 years ago, # ^ |   0 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 :(
•  » » 4 years ago, # ^ |   0 Hey, I wrote hint-by-hint solution to problem C here: https://www.commonlounge.com/discussion/b7b8f55f00bd4cd7a9dd7ef9d6067418/all/e1c9c7c034324f539d81343124095d72
 » 4 years ago, # |   +3
 » 4 years ago, # |   +3 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.
•  » » 4 years ago, # ^ |   +37 Or google phi-phi-phi on hackerearth instead.
•  » » 4 years ago, # ^ |   +3 I open www.baidu.com in step 2 :D
 » 4 years ago, # |   0 Great round, very nice problems!
 » 4 years ago, # |   +11 Wanted to submit C in last 2 minutes but nevermind codeforces servers didn't wanted me to gain ratings :/
 » 4 years ago, # |   +10 I was waiting for submitting B more than 30 minutes. The server was totally down. Please make it unrated. MikeMirzayanov
•  » » 4 years ago, # ^ |   +3 YES IT HAPPENED TO ALMOST EVERYONE.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +1 tourist expression when reading your comment :
•  » » » 4 years ago, # ^ |   +4 THAT'S WHY I SAID ALMOST HE SOLVED ALL QUESTIONS IN CASE OF SERVER DOWNBELEIVE ME IF THERE WILL BE A TSUNAMI,tourist WILL TOP IN CONTEST
 » 4 years ago, # |   +21 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.
•  » » 4 years ago, # ^ |   0 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
•  » » 4 years ago, # ^ |   +16 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. 24937275Good luck
 » 4 years ago, # |   0 I want to hack someone in the last minute, but CF lags and forbids me to do so :( (Quite sure his solution is wrong)
 » 4 years ago, # |   +1 **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_ I JUST REMEMBERED LAW OF EQUIPARTITION OF ENERGY **
 » 4 years ago, # |   -41 Let's vote: Strawpoll.
•  » » 4 years ago, # ^ |   +22 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.
 » 4 years ago, # |   +10 When you missed E because of slow Internet connection... I would have a sleepless night if that solution got AC...
 » 4 years ago, # |   +8 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)
•  » » 4 years ago, # ^ |   0 ans+=ma[a[j]-tmp]; 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.
•  » » 4 years ago, # ^ |   +33 I tried to construct cases to fail unordered_map. GeneratorIt takes about 4 seconds.
•  » » » 4 years ago, # ^ |   0 Why it TLs unordered_map in GCC (24943025), but in VS2010 it is AC (24943348)?
•  » » » » 4 years ago, # ^ |   0 Because hash maps implementations are different. GCC uses libstdc++ library while Visual Studio uses Microsoft STL.
•  » » 4 years ago, # ^ |   +3 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 taking map[element]
 » 4 years ago, # |   0 Ty CF. If you didn't crash I could have had F. :'(
 » 4 years ago, # |   +42 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.
•  » » 4 years ago, # ^ |   +3 You can click on Complete Problemset and then print the file to pdf.
 » 4 years ago, # |   +12 I hacked one person with this test 5 8 0 0 0 0 0He calculates all power till 50,then push them to set and forget about overflow. And i found that 8^21 = 0.
 » 4 years ago, # |   +43 I accidentally resubmitted C twice instead of once due to network issue 24941488 24941490 What can I do? This is really sad.
 » 4 years ago, # |   0 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.
•  » » 4 years ago, # ^ |   0 Not the center but the centroid. The other part is correct.
•  » » 4 years ago, # ^ |   +3 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
•  » » 4 years ago, # ^ |   +5 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.
 » 4 years ago, # | ← Rev. 4 →   +1 Has anyone this bug? I hope that this submission will be taken into account.
 » 4 years ago, # | ← Rev. 2 →   0 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".
•  » » 4 years ago, # ^ | ← Rev. 2 →   +5 Actually E is pretty known(that sum of phi (d) is N — 1 for d | N) so neither E was much of a problem
•  » » » 4 years ago, # ^ |   0 Oh, if this is well known, then yeah, boring problemset.
 » 4 years ago, # | ← Rev. 2 →   +16 There were some serious technical problems with the website in this contest.
 » 4 years ago, # |   +32
 » 4 years ago, # |   +3 Why do I get TL 13 in C? (code)
•  » » 4 years ago, # ^ |   0 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 :(
 » 4 years ago, # | ← Rev. 2 →   +135 E — let's add a random function which is well known to be an identity functionF = http://codeforces.com/contest/321/problem/C + duality on planar graphsgreat problemset...
•  » » 4 years ago, # ^ | ← Rev. 2 →   +1 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...
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 My method:build initial graph from i to i — 1 as well as from 1 to nbuild additional edges as input, two-wayedbuild 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)
•  » » » 4 years ago, # ^ |   0 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.
 » 4 years ago, # |   +2 Savage of a contest
 » 4 years ago, # |   -11 hogloid, I hate your -1 :D
 » 4 years ago, # | ← Rev. 2 →   +38 I couldn't open the site for over 30 minutes. I think it should be unrated.
•  » » 4 years ago, # ^ |   0 LOL, that's a "few" minutes
 » 4 years ago, # |   0 How to solve C?
•  » » 4 years ago, # ^ |   -6 I wrote hint-by-hint solutions here: https://www.commonlounge.com/discussion/b7b8f55f00bd4cd7a9dd7ef9d6067418/all/e1c9c7c034324f539d81343124095d72
•  » » 4 years ago, # ^ |   +1 let p[] - unique power of k's ' which absolute value less than 10^15 k = 1. p[] = {1} k = -1 . p[] = {-1, 1} k = 2 . p[] = {1, 2, 4, 8, ..., 2^60} and etc. now. sum(i) = a[0] + a[1] + .. + a[i] we need number of that intervals which a[h] + a[h+1] + ... + a[i] = k^x but a[h] + a[h+1] + ... + a[i] = sum(i) - sum(h-1) so if we know sum(i) and k^x --> sum(h-1) = sum(i) - k^x need calculate number of h, 0<= h < i and sum(h-1) == sum(i) - k^x there assume sum(-1) = 0. let freq[ sum(i) ] -- number of h, where 0<=h < i, and sum(i) == sum(h). so ans(i) = freq[ sum(i ) - power(k,x)] , where x >= 0 and k^x < 10^15. answer = sum(ans(i), i = 0..n-1) //let coded: vector p; if (k == 1) p.push_back(1); else if (k == -1) p.push_back(1), p.push_back(-1); else { long long ky = 1; while( ky < (long long)1.0E+16 && ky > - (long long)1.0E+16 ){ p.push_back(ky); ky *= k; } } map freq; freq[0] = 1; long long sum = 0, ans = 0; for(int i = 0; i < n; ++i){ sum += a[i]; for(int j = 0; j < p.size(); ++j) ans += freq.count(sum - p[j]) ? freq[sum-p[j]] : 0 ; ++ p[ sum ] ; } cout << ans << endl; 
 » 4 years ago, # | ← Rev. 3 →   +24 #FIXCF
 » 4 years ago, # |   +3 How to understand F?
 » 4 years ago, # |   +23 have waited for "codeforces.com/contest/776/submit" for over 30min
 » 4 years ago, # |   +36 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 :(
 » 4 years ago, # |   +148 I strongly recommend to hold such a kind of contest in Div2 only...
•  » » 4 years ago, # ^ |   +2 This has prevented lots of black coders winning a div2 contest =)
 » 4 years ago, # |   +5 My D will fail because I assumed there is only one connected component :(
•  » » 4 years ago, # ^ |   0 We're friends... mine will too XD
 » 4 years ago, # | ← Rev. 2 →   -21 In task C, the current winner mnbvmar has: int s = 1; while (abs(s) < 1e16) { diffs.push_back(s); s *= K; } Looks like it's going to fail?
•  » » 4 years ago, # ^ |   +5 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.
•  » » 4 years ago, # ^ |   +26 you missed the first part ? if (abs(K) == 1) { diffs.push_back(K); if (K == -1) { diffs.push_back(1); } } else { int s = 1; while (abs(s) < 1e16) { diffs.push_back(s); s *= K; } } 
•  » » » 4 years ago, # ^ |   -13 He is using int and multiplying by K until 1e16.
•  » » » » 4 years ago, # ^ |   +17 You forgot this: #define LL long long #define int LL 
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   -35 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.
•  » » » » » » 4 years ago, # ^ |   +20 Go away. I am sick and tired of explaining why this is huge bullshit.
•  » » » » » » » 4 years ago, # ^ |   -35 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.
•  » » » » » » » » 4 years ago, # ^ |   0 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.
•  » » » » » » » » » 4 years ago, # ^ |   -52 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.
•  » » » » » » » » » 4 years ago, # ^ |   +43 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.
•  » » » » » » 4 years ago, # ^ |   +15 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 long is possible in C++.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 oh I didn't read that..EDIT : oh turns out it is fine....
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 Tricky: define int LL
 » 4 years ago, # |   +24 RIP solutions of Those who handled k = 1 but not k = -1 case in C.
 » 4 years ago, # |   +1 After a long time there comes a contest in which i could do both A and B....Hoping to get rejected in system testing....
 » 4 years ago, # |   +12 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.
•  » » 4 years ago, # ^ |   -28 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.
•  » » » 4 years ago, # ^ |   +32 I think he meant the problem quality was not good enough for div1 contestants.
•  » » 4 years ago, # ^ |   -17 Racist...
•  » » » 4 years ago, # ^ |   +16 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.
•  » » » » 4 years ago, # ^ | ← Rev. 4 →   +23 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.
•  » » 4 years ago, # ^ |   0 Any comments regarding Codecraft-17 and Codeforces Round #391 (Div. 1 + Div. 2, combined) and Manthan, Codefest 16? Those were pretty good actually.
 » 4 years ago, # |   0 What were you missing, people who got WA #3 on F?
 » 4 years ago, # |   0 C was given on geeks for geeks just needed minor changes, and the long queue otherwise the contest was good.
 » 4 years ago, # |   +41
 » 4 years ago, # | ← Rev. 2 →   +7 About 30 minutes I could not do anything on CodeForces :(
 » 4 years ago, # |   -16 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!
 » 4 years ago, # |   +15 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
 » 4 years ago, # |   +545
•  » » 4 years ago, # ^ | ← Rev. 2 →   +41 Please take my 5 cents
•  » » 4 years ago, # ^ |   +31 and I have a not-necessary 1e9+7
 » 4 years ago, # |   +6 Super fast System Testing. Came late but came strong...
 » 4 years ago, # |   +57 I have a dream, that one day codeforces will be stable and fast
 » 4 years ago, # |   +3 Please add problems to practice section.
 » 4 years ago, # |   +8 Is this contest ranked? The site did not work most of the time!!!
 » 4 years ago, # |   +24 TLE on test 101 in problem C :(
 » 4 years ago, # |   +18 C — unordered_map: TLE. map, set: AC. seriously?
•  » » 4 years ago, # ^ |   +5 yes, because element accessing complexity is linear and logarithmic respectively.
•  » » » 4 years ago, # ^ |   0 I think you are not right, because how i know, unordered_map make this for constant, not linear
•  » » » » 4 years ago, # ^ |   0 Then what is the reason behind TLE for using unordered_map ??
•  » » » » » 4 years ago, # ^ |   +1 Constant is bigger, than log sometimes(
•  » » » » 4 years ago, # ^ |   0 In the worst case — linear.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 No, paradox1 is correct in the worst case. unordered_map uses 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, map is guaranteed O(log n) in the worst case.
•  » » 4 years ago, # ^ | ← Rev. 3 →   -11 Similar thing happened to me yesterday in a contest.scanf/printf: TLEcin/cout: AC
•  » » » 4 years ago, # ^ |   0 Is this even possible?
•  » » » » 4 years ago, # ^ |   0 It happened.
•  » » » » » 4 years ago, # ^ |   0 Can i see the submissions, please?
•  » » » » » » 4 years ago, # ^ |   0 TLE-https://www.hackerearth.com/submission/7372868/AC-https://www.hackerearth.com/submission/7373096/
•  » » » » » » » 4 years ago, # ^ |   0 Thanks.
•  » » 4 years ago, # ^ |   -8 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)...
 » 4 years ago, # |   +10 Nice problems!
 » 4 years ago, # | ← Rev. 3 →   0 Can someone be generous enough to tell me how to decide whether to use normal map or unordered map ????
•  » » 4 years ago, # ^ |   0 Hash your number by xoring with a random number when using unordered_map.
•  » » » 4 years ago, # ^ |   0 How can I generate "really" random numbers?
•  » » » » 4 years ago, # ^ |   +5 You don't need to? just use rand so that neither a hacker nor system test can guess the salt value.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » 4 years ago, # ^ |   0 Always use map =)
 » 4 years ago, # |   +22 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 :(
 » 4 years ago, # | ← Rev. 2 →   0 What is WA in D on test 55, Retired_MiFaFaOvO also had this problem? :(
•  » » 4 years ago, # ^ |   +1 When it's unlocked, you need to add edges between a and b.
•  » » 4 years ago, # ^ |   -21 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.
 » 4 years ago, # |   0 When you see second sample of problem A:
 » 4 years ago, # |   +1 what is the solution of problem c. Thanks in advanced.
•  » » 4 years ago, # ^ |   0 I used prefix sum, and binary search.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +4 Can you please tell me the idea of running binary search on prefix sum in detail.
•  » » » » 4 years ago, # ^ |   0 calculate prefix sum in array D keep a map, and for each element(E) in D, keep all indices (i) such that D[i] = E in the map[E]. for the current power of k (pk), iterate through D with current index i, we have to look for D[i]+pk, because we want their differense to be pk. recall that map[d+pk] contains such indices, but we need the ones bigger than i, here the binary search comes to help.
•  » » 4 years ago, # ^ |   +1 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 x you can use the prefix sums. For each prefix sum p[i] you should find the amount of sums p[j] such that p[i] - p[j] = x. It can be done using a map.My code: link
•  » » » 4 years ago, # ^ |   0 Thanks
 » 4 years ago, # |   0 http://codeforces.com/contest/776/submission/24923436http://codeforces.com/contest/776/submission/24943032wtf :/please re-evaluate my submission :/
•  » » 4 years ago, # ^ |   +3 966 is extremely close to 1000 so its just a matter of fluctuation.
 » 4 years ago, # |   +5 Blue at last ,after a long wait .....
 » 4 years ago, # |   0 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..
•  » » 4 years ago, # ^ |   +5 See here.
•  » » 4 years ago, # ^ |   0 This post can be useful
 » 4 years ago, # |   0 Had +17 in prev round, now -17 lmao.
•  » » 4 years ago, # ^ |   0 There is no Len then :) .
 » 4 years ago, # |   +1 Where is editorial?
 » 4 years ago, # |   0 "I'm fucked up,I'm black and blue"...
 » 4 years ago, # |   0 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.com/contest/776/submission/24941529
•  » » 4 years ago, # ^ | ← Rev. 3 →   +1 Time complexity for multiset count(x) is O(lg n + (number of xs in the multiset))
•  » » 4 years ago, # ^ |   +1 Search of a lot of similar values in multiset can be linear. Use map instead.
 » 4 years ago, # | ← Rev. 2 →   +4 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 !!?
 » 4 years ago, # |   +9 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.
 » 4 years ago, # |   +209 #roadtoyellowThere'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.
•  » » 4 years ago, # ^ |   +44 If only getting yellow is as easy from down here :(
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 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?
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » 4 years ago, # ^ |   0 I know. Perhaps did not state it clearly enough. What I am asking is "Why is it so?". Appears stupid.
•  » » » » 4 years ago, # ^ |   0 Ah, and the complexity is constant on average and we perform many queries, so it should be faster.
•  » » » » » 4 years ago, # ^ |   0 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.
•  » » » » » » 4 years ago, # ^ |   0 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.
•  » » » » » » 4 years ago, # ^ |   0 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?
•  » » » » » » » 4 years ago, # ^ |   0 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.com/blog/entry/50585#comment-345218.
•  » » » » » » » » 4 years ago, # ^ |   0 thanks for the link!
•  » » » 4 years ago, # ^ |   0 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.
•  » » 4 years ago, # ^ |   +29 Let's guess who will be Sorry_Swistakk.
•  » » » 4 years ago, # ^ |   +5 Haha :D. With my current performance anyone will do ;p.
 » 4 years ago, # |   +9 Why this contest is rated? Is it because we have 10 more minutes to deal with the previous 30 minutes' trouble??
•  » » 4 years ago, # ^ |   +13 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.
•  » » » 4 years ago, # ^ |   0 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.
 » 4 years ago, # | ← Rev. 2 →   +11 Deleted
 » 4 years ago, # |   0 D was a nice problem !!
 » 4 years ago, # |   0 Editorial??
 » 4 years ago, # |   +3 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)?????
•  » » 4 years ago, # ^ |   0 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.
 » 4 years ago, # | ← Rev. 2 →   +20 How to prove that phi(phi(...(phi(n))) will become 1 fast enough?
•  » » 4 years ago, # ^ | ← Rev. 2 →