text:
### KAN's blog

By KAN, 4 years ago,

Hi!

The Codeforces Round #398 (Div. 2) is going to be held on Saturday, 18 February 2017 at 9:05 UTC for participants from division 2.

The round is based on XIII Nizhny Novgorod Olympiad in Informatics for high school students named after V. D. Lelyukh, which will take place on Saturday in Nizhny Novgorod. However, not all problems from the Olympiad are included into this round.

The problems were prepared by KAP, I_Remember_Olya_ashmelev, ZhNV, kuzmichev_dima, mmatrosov, mike_live, arsor and me.

You will be given two hours to solve five problems. As usual, participants from division 1 can take part out of competition.

Scoring: 500-1250-1500-2000-2500.

UPD: The contest is over, thanks to all who has participated! Congratulations to the winners:

Div. 2:

Div. 1:

I apologise for the problem difficulty of the problem B, we expected much more accepteds. Hope you liked the problems! The editorial will be posted in 1.5 hours after the Olympiad is finished. Editorial.

We know about the issue with ratings, they will be rolled back and then updated properly. Don't worry.

• +135

 » 4 years ago, # |   +730
•  » » 4 years ago, # ^ |   -8 megmi
•  » » 4 years ago, # ^ |   +10 This comment has more likes than the blog.
 » 4 years ago, # |   +156 Do not thank MikeMirzayanov? DANGEROUS!!!
•  » » 4 years ago, # ^ |   0 WAT THE 5 TEST (A) SANAVA GLITCH
 » 4 years ago, # |   -42 ** ** *****?
•  » » 4 years ago, # ^ |   -35 ***, ** ** *****!
•  » » » 4 years ago, # ^ |   -52 ***, ** ** *****!
•  » » 4 years ago, # ^ |   -22 **** this meme
•  » » » 4 years ago, # ^ |   -49 Comment here to get Free downvotes !! :D
 » 4 years ago, # |   -35 Wait, correct me if I'm wrong (not likely haha) but if someone has a friend who participated in the XIII Nizhny Novgorod Olympiad then he could technically get some advice from him regarding the problems... Are there any countermeasure for that or should we all try befriend some novgorodians?
•  » » 4 years ago, # ^ |   0 "The round is based on XIII Nizhny Novgorod Olympiad in Informatics for high school students named after V. D. Lelyukh, which will take place on Saturday in Nizhny Novgorod."I assume these rounds will run almost simultaneously.
 » 4 years ago, # |   +73 That feeling when you open "Contests" tab and there's this
•  » » 4 years ago, # ^ |   +16 No wonder the queue is so long......
•  » » » 4 years ago, # ^ |   -33 why you are everywhere ? Codeforces Round #398 (Div. 2) Codeforces Round #397 (Div. 2) Codeforces Round #396 (Div. 2) . . .
•  » » » 4 years ago, # ^ |   -15 This Week Codeforces achieve 4th Century.......
•  » » 4 years ago, # ^ |   0 It is so much exciting. isn't it... :)
 » 4 years ago, # |   -23 SOORY,BUT THIS CONTEST MAY BE UNRATED BECAUSE CF SEEMS NOT SO WELL
•  » » 4 years ago, # ^ |   0 be cool
•  » » 4 years ago, # ^ |   0 ^wtf
•  » » 4 years ago, # ^ |   +28 U seem not so well
•  » » » 4 years ago, # ^ | ← Rev. 2 →   -19 c
 » 4 years ago, # |   +12 That moment when it's holiday but you have to wake up early to participate the contest :(
 » 4 years ago, # |   0 Wish the problems to be very Interesting! ^_^
 » 4 years ago, # |   -12 5 problems but 10000 ideas
 » 4 years ago, # |   -16 i hope every one have good contest and i hope the problems be interesting and have many ideas.
•  » » 4 years ago, # ^ | ← Rev. 2 →   -10 c
•  » » » 4 years ago, # ^ | ← Rev. 3 →   0 GOH KHORDAM
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 ...
•  » » » » » 4 years ago, # ^ |   0 haji mikonameta
 » 4 years ago, # |   -31 Well, i would like to suggest that stat using March 2017 Calendar to manage all the work related activities.
 » 4 years ago, # |   +4 I cannot register to the round, could somebody explain why ? thanks
 » 4 years ago, # |   +23 The most creative(in aspect of the difficulty) contest ever, and in my humble opinion, no other contests will beat this dishonorable record :D
 » 4 years ago, # |   +1 Love the change in friends standings page! :)
•  » » 4 years ago, # ^ |   0 What is it?
•  » » » 4 years ago, # ^ |   0 Now you can see your actual rank amongst your friends.
 » 4 years ago, # |   +9 Nice and tiny questions You can solve them with push and shove
 » 4 years ago, # |   +3 What sort of contest is this. I couldn't do any. #Senseless
 » 4 years ago, # | ← Rev. 3 →   +44 Why I can see the questions of other participants?
•  » » 4 years ago, # ^ |   +29 The most ridiculous question is "give me 5 test case" :D And he got answer
•  » » 4 years ago, # ^ |   +1 At least I finally understand how frequent the admins received messages during a single contest. And I know why they sometimes respond slow. (I hope the high frequency of messages in this contest is not related to the unclear English statments)
 » 4 years ago, # |   -18 One of the best problem sets in a while. Keep it up guys!
•  » » 4 years ago, # ^ |   +4 yeah, definitely, hard though interesting
•  » » 4 years ago, # ^ | ← Rev. 2 →   +12 For you...
 » 4 years ago, # |   +24 I do think the legends of the problems are toooooooooooo long to read. Maybe shorter legends and clearer problems instead?
 » 4 years ago, # |   +151 Hardest Div2 B I've ever seen
•  » » 4 years ago, # ^ |   0 difficult
•  » » 4 years ago, # ^ |   0 true that.
 » 4 years ago, # |   +63 scoring distribution should be 750-2000-2000-2000-2500
•  » » 4 years ago, # ^ | ← Rev. 2 →   +6 nonono it should be 750-3000-1000-1000-2500
•  » » » 4 years ago, # ^ |   +1 1000 for C and D? It is not Div1 contest!
•  » » » » 4 years ago, # ^ |   +13 Just mean to emphasize the interesting problem B...
 » 4 years ago, # |   +21 Rating prediction for this contest could be found here or there.Extensions: As you could see unfortunately, it is bit difficult for my service to handle such amount of request. I'm sorry for that again, hope mirror solve this problem.
•  » » 4 years ago, # ^ |   +8 RIP RATINGS
•  » » 4 years ago, # ^ |   0 The link isn't working. The page opens and shows some error HTTP Status 500 — An exception occurred processing JSP page /roundResults.jsp at line 15type Exception reportmessage An exception occurred processing JSP page /roundResults.jsp at line 15description The server encountered an internal error that prevented it from fulfilling this request.exception
•  » » » 4 years ago, # ^ |   0 Second one is working.
•  » » » » 4 years ago, # ^ |   0 My name isn't there :/
•  » » » » » 4 years ago, # ^ |   0 Found it +33
•  » » » » » 4 years ago, # ^ |   0 902 vatsalsharma376 33 1587 1453 1486
•  » » » » 4 years ago, # ^ |   0 not any more :D
•  » » » » » 4 years ago, # ^ |   0 For now both links contains my final prediction:)
•  » » » 4 years ago, # ^ |   0 Use second link
•  » » 4 years ago, # ^ | ← Rev. 2 →   +6 This time the results were lot different. This shows -22 negative rating change whereas i almost got exact positive rating change.Edit: It seems something is wrong with cf rating changes...
•  » » » 4 years ago, # ^ |   0 I hope my service doesn't broke codeforces:) Actually now on your rating graph your place in the contest is 203, but in standings it is 319.
 » 4 years ago, # | ← Rev. 2 →   +161 how to solve B
•  » » 4 years ago, # ^ |   +17 Even reds couldn't solve B :(
•  » » 4 years ago, # ^ | ← Rev. 6 →   0 At first, you must find such time between ts and tf, when there won't be anyone. The waiting time at this case 0. If there are always someone, then u have to find time among all pre-visiters, which is the smallest ( a waiting time, not arrival time).
•  » » 4 years ago, # ^ |   0 that's a popular "WTF so standard easy-peasy problem" among russians :D
•  » » 4 years ago, # ^ |   0 Lets try to stand in front of every person p in the queue — optimally, we need to come 1 minute earlier than p. Find the minimum of that waiting times (and don't forget to check will it be enough time to become documents)Before printing the answer check what if we will come after all persons — will it be enough time (t) to become documentsComplexity O(n)Sry for bad english)
 » 4 years ago, # |   +6 Someone Please tell Me What the hell was pretest 4 of div2B ?? Any ideas anyone. Wasted the entire contest reading the question and finding bugs on the same.
•  » » 4 years ago, # ^ |   0 Initially I assumed that the starting time can be any time < e. But I got 5 WAs on pretest 4, lol. When I changed it to start_time < e-t, then I passed that case.
•  » » » 4 years ago, # ^ |   -8 The problem statement clearly states "If the receptionist would stop working within t minutes, he stops serving visitors (other than the one he already serves)." Your answer indicates that the receptionist ALSO STOPS SERVING THE ONE HE IS SERVING. Did I get that right?
•  » » » » 4 years ago, # ^ |   0 Yes, I got confused by that line as well. :(
•  » » » » » 4 years ago, # ^ |   0 Exactly if start_time
•  » » » » » » 4 years ago, # ^ |   0 There is probably no such input because "It is also guaranteed that Vasya can arrive at the passport office at such a point of time that he would be served by the receptionist."
•  » » » » 4 years ago, # ^ |   -8 Yes it has to be "ALSO STOPS SERVING THE ONE HE IS SERVING.". I also had the same doubt and clarified it early (luckily). I believe problem statements weren't clear on this.
•  » » » » » 4 years ago, # ^ |   0 The problem statement is extremely clear on this. In fact, it clarifies that the statement "stops serving visitors" does not relate to currently served visitor. Model solution and tests are simply broken.
•  » » » » » » 4 years ago, # ^ |   +5 No I was wrong, the key part of the statement that I read incorrectly was "If the receptionist would stop working within t minutes". So the statement is concerned with time (end — t), like satyaki3794 said. After that time point the receptionist does not accept new customers, but he will serve the current customer through, and be done with him before end time.
•  » » » » 4 years ago, # ^ |   +5 No, obviously not
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 You can finish exactly in tf. Example: ts = 3, tf = 7, t = 4. It is possible.
 » 4 years ago, # | ← Rev. 2 →   0 How to solve A
•  » » 4 years ago, # ^ |   0
 » 4 years ago, # | ← Rev. 2 →   -19 What the Fuck ? It is impossible to solve the 3rd problem in Java if u use adjacency lists.Why >>>? I get MLE for storing the edges. Is this even fair ?
•  » » 4 years ago, # ^ |   0 I have solved using Adj list in java only.
•  » » » 4 years ago, # ^ |   0 MLE Code , Linear in Time and Memory :http://codeforces.com/contest/767/submission/24771836
•  » » » 4 years ago, # ^ |   0 No you didn't :| Isn't this you — 24759322? RTE in test 32 :|
•  » » » 4 years ago, # ^ |   -8 Stack overflow ho gaya naa bhai ? Kuch bologe abhi ? Khud pe jab guzarti hai naa, tab pata chalta hai
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   0 http://codeforces.com/contest/767/submission/24775881forgot to increase the stack size that's why.
•  » » » » » 4 years ago, # ^ |   0 http://codeforces.com/contest/767/submission/24775207My submission, 150 % same, code just a different language (C++)Manually stack size increase kare bina.
•  » » 4 years ago, # ^ |   0 I don't know java much but isn't this adjacency list?
 » 4 years ago, # |   0 Was B binary search? I was trying to binary search between the times of the people in the queue and took the best one out of all the gaps but I couldn't get it to work.
•  » » 4 years ago, # ^ |   +2 First check if there's a time before tf such that no one is waiting for processing. Then vasya can come at this time, and wait for 0 second.If not, and if there are k different arrival times in input, then try to see if there's a minimum waiting time possible for the preceding time for all these k values. Additionally, check the time after all values in input are processed, if then vasya can still get his request processed, before tf.
•  » » » 4 years ago, # ^ |   0 Thanks! That makes a lot of sense actually.
•  » » » 4 years ago, # ^ |   0
•  » » » » 4 years ago, # ^ |   +1 Can't access your code. You can check my submission. I wrote comments for everything.
•  » » » » » 4 years ago, # ^ |   0 Can you link your submission?
•  » » » » » » 4 years ago, # ^ |   0 codell n,m,a[N],b,c,d,k,h,w,x,y,p,q,t,ans,res,ma,mi,T,act=0,pas=1,cur,flag,now;ll ts,tf;vector< node > vec;typedef map Mapp;Mapp cnt,start; void input(){ ios_base::sync_with_stdio(false);cin.tie(NULL); cin >> ts >> tf >> t; tf--; cin >> n; forr(i,1,n+1) cin >> a[i];} void solve() { //vector< pii > v; cur = ts; forr(i,1,n+1) { if( a[i] <= cur ) // a[i] has to be processed { cur += t; } else // vasya can come at this time { cout << cur; return; } if( cur > tf - t + 1 ) // no vacant slot { break; } } if( cur <= tf - t + 1 ) // all processed, can come now { cout << cur; return; } forr(i,1,n+1) cnt[ a[i] ]++; // how many people come at each time cur = ts; // serving time for(auto u : cnt) { start[ u.ff ] = cur; cur += u.ss * t; //finish[ u.ff ] = cur - 1; if( cur > tf - t + 1 ) break; } // check coming before each group mi = 2e18; // waiting time ans = 0; // vasya's arrival time for(auto u : start) { vec.pb( node( u.ff, start[ u.ff ] ) ); //, finish[ u.ff ] ) ); } forr(i,0,vec.size()) { ll arrive = vec[i].arrive - 1; ll start = vec[i].start; if( mi > start - arrive ) { mi = start - arrive; ans = arrive; } } cout << ans; } int main() { input(); solve(); return 0; }
•  » » 4 years ago, # ^ |   0 Just check Ai, Ai - 1, ts, and after all people. (Ai is arrival time of i)
 » 4 years ago, # |   +2 lucky I skipped the 2nd one for last
 » 4 years ago, # |   0 Please, someone explain E to me. I think I reduced it to knapsack but with big dimensions.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 You don't need to do knapsack. You always choose one of these per day: paying with notes only OR paying exactly. And "paying with notes only" can be thought that you get 100 coins and some dissatisfaction. So greedy will work. Simulate from beginning. Whenever you don't have enough coins, choose a day with minimum dissatisfaction from the past and add it to the answer. Priority queue will be enough to implement this.
•  » » » 4 years ago, # ^ |   0 Ooooh, we get the change back, I just ignored it :D Thank you!
 » 4 years ago, # | ← Rev. 2 →   0 I guess time limit for D is too strict, my Nlog(10^7) + Mlog(10^7) didn't pass. Plz have a look and tell me if I am missing something: http://ideone.com/Tdob4l
•  » » 4 years ago, # ^ |   +12 I think their intended solution is with time complexity O(n + m + 107). And I passed pretest with this time complexity.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 But shouldn't my solution pass too as it is well within 10^8 compuations?
•  » » » » 4 years ago, # ^ |   0 I think using set is with big constant on each operation like insert and upper_bound, which leads your solution TLE.
•  » » » » » 4 years ago, # ^ |   0 I guess all operations of set takes log( set.size() ) time which I computed earlier, and then too I don't find a way where computation increase to 10^8. Can you plz tell when we should avoid set( as u say it causes TLE ) and use some other option as I usually see 10^8 compution( if exceeding then TLE )?
•  » » » » » » 4 years ago, # ^ |   +5 Ummm... Just to understand using functions from STL may requires higher time as they are usually with larger constanst. For instance, writing binary search on your own is usually faster than using lower_bound from STL. Also, maintaining stacks or queues on your own are usually faster than using queue<> and stack<> from STL as well.You may try to have some experiments on performing million times of binary search written by yourself, and with the same case, test on performing million lower_bound.In cases that we can easily write functions on our own, and the problem TL is very tight, we should not rely on STL functions.
•  » » » » » » » 4 years ago, # ^ |   0 Thanks a lot!!
•  » » » » » 4 years ago, # ^ |   0 Can you tell me how to pass memory limit? I used up to 262000 kb and cannot pass the test zz
•  » » » » 4 years ago, # ^ |   +3 It is not well within 10^8 operations. If any of the cartons has size 10^7 then variable maa is also equal to 10^7.Before you begin calculating the answer you insert all integers from 0 up to maa into your set and this initialization itself takes around 2*10^8 operations.
•  » » » » » 4 years ago, # ^ |   0 10^7 * ( log(10^7) ) == 7 * log( 10^7 ) ( Base 10 )10^7 * ( log(10^7) ) is approx 2 * 10^8 ( Base e )Are STL operations base 10 or base e as both gives different results?Yeah I realised that earlier from comments above and made it AC after changing variable maa threshold.
•  » » » » » » 4 years ago, # ^ |   0 I think the most of the time we deal with base 2 logarithms. Nobody bothers to mention the base unless its different from 2 (Correct me if im wrong). Since sets are usually implemented as red-black trees (according to cpp reference) i believe the base is equal to 2.
•  » » » 4 years ago, # ^ |   0 I passed pretests in O((n+m)logM), but it was a tough battle. Input/Output took the most of time. TL was too strict imo.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +5 My solution passed pretest easilyUPD And it passed all tests in around ~1 sec
•  » » 4 years ago, # ^ |   0 Strange, my solution which is O(Xlog(N)) passed, where X = 1e7http://codeforces.com/contest/767/submission/24774891
•  » » » 4 years ago, # ^ | ← Rev. 3 →   -8 Maybe judge data was weak.. I don't see any number fi, si being 107 in the tests. I can see that there are maximum fi, si ≤ 9 × 105 :| Then O(x log n) passes simply. Also even if x = 1e7 then it can pass also :) O(1e7 log 1e7) O(2 * 1e8)
•  » » » 4 years ago, # ^ |   0 Lucky you optimizing I/O operations... cannot do this in C#... :P
•  » » 4 years ago, # ^ |   +1 Yeah, time limit in D was too strict. Submited using : Binary Search and Sorting : TLE on test 8 24776219 Binary Search and Two Pointer with cin/cout : TLE on test 9 24776253 used scanf/printf : AC 24775689
 » 4 years ago, # |   +1 Hard Problem set, but atleast now I learn how to use set :)
 » 4 years ago, # |   +28 When you find out your solution to B is wrong 1 minute before the contest ended... :( I have a feeling many B solutions will fail system testing...
 » 4 years ago, # |   0 Nice problemset. A-C were awesomem very good tasks
 » 4 years ago, # |   +8 B is hardest than DLogic R.I.P
•  » » 4 years ago, # ^ |   0 may be they confused Div2 B with Div1 B :D
•  » » 4 years ago, # ^ |   0 I'm sure you meant "harder" instead of "hardest" :)
 » 4 years ago, # |   0 Maybe it should be Div1 contest istead of Div2 ? :)
 » 4 years ago, # |   +14 Guys! English!! What the heck with problem C. I understood the problem from context, not from the description. Please don't use translators, ask someone who speaks English well to translate statements.
•  » » 4 years ago, # ^ |   0 I understood it from the picture :D :D Yeah, the statements suck a lot.
•  » » » 4 years ago, # ^ |   0 The worst was understanding the input. They interchanged lamps with wires throughout the statement.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +17 This sentence in problem D : "The main issue Olya has is the one of buying new cartons."
•  » » » 4 years ago, # ^ |   +2 RIP...English.
•  » » » 4 years ago, # ^ |   0 This sentence in problem B : "If the receptionist would stop working within t minutes, he stops serving visitors (other than the one he already serves)." I got 1 wrong answer before I realized, the receptionist leaves exactly at tf, even if somebody's request is partially completed.
 » 4 years ago, # |   0 Was problem C greedy tree dp? My approach was to find a subtree of weight of dp[root]/3 and remove the weight of that subtree from its ancestors' weights. Then I try to find another subtree that has weight of dp[root]/3 and we are done. Code: LinkIs this approach correct?
•  » » 4 years ago, # ^ |   0 Yes.
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 In addition, the height of the firstly found subtree should be highest possible, so that we can increase the chance finding the second one.
 » 4 years ago, # |   0 How to solve C? I am getting WA on pretest 8 and 10.My approach -> If totalheat is not divisible by 3 return -1. Check if we can find two subtree of totalheat/3 then return those 2 values. Check if we can find a subtree with heat totalheat/3 and and it's parent with heat 2*totalheat/3 then return parent and that node. Else return -1.
•  » » 4 years ago, # ^ | ← Rev. 4 →   +3
•  » » 4 years ago, # ^ |   +4 The general idea is correct but your solution fails at both cases. You need to check that two subtrees of weight totalheat / 3 do not intersect and checking that immediate parent has weight 2 * totalheat / 3 is not enough — it could be parent's parent that has the weight 2 * totalheat / 3.
•  » » 4 years ago, # ^ |   +1 While calculating weight of subtrees, whenever weight of a subtree equals totalheat/3 push it into ans vector and return 0, because it will not be contributing in it's parent. It will handle the removal of that subtree. 24775716
 » 4 years ago, # | ← Rev. 2 →   +12 The problem-set was nice, but I feel that the difficulty levels of the questions was jumbled up. I found A
 » 4 years ago, # |   0 Can someone tell me why printing 16 gets WA on problem B pretest 2? I think I miss something in the statement but it says: "If the receptionist would stop working within t minutes, he stops serving visitors (other than the one he already serves)."
 » 4 years ago, # |   +48 Now you know why there are 8 writers: we need people to draw the cartoon and to write stories. :P
•  » » 4 years ago, # ^ |   +21 Maybe next time we will need people to properly explain these stories in English :D
»
4 years ago, # |
+88

# 398 (Div.2̶ 1)

 » 4 years ago, # |   +12 i am not sure if this was a div2 round or div1 round sorry to say that but it was one of the worst rounds i have ever seen here
 » 4 years ago, # |   +4 good contest for DIV I contestants, Div II contestants RIP
 » 4 years ago, # |   +99 My first DIV1 contest.
 » 4 years ago, # |   -19 C was awesome...D was a little easy for a D problem (they should have been swapped)I didn't read B but judging of the number of people who have solved it it must be really hard for a B problemThe statements were rubbish..they were way longer than they needed to be (that's why I didn't solve B...skipped it after seeing the statements)But all in all the contest was great.(don't downvote me guys it's just my opinion):)
•  » » 4 years ago, # ^ |   +15 it was great because you didn't read problem B but who read problem B and tried to solve wasted too much time while problem D was easier to solve
 » 4 years ago, # | ← Rev. 2 →   +3 It so frustrating when you solve problem but can't pass tests because standard reading method, you used all the time, doesn't read fast enough for this input. I have linear time solution for C but probably reading method I use in my C# solution too slow. Now I think that string.Split() is just too slow for this problem. Don't enjoy such contests.
•  » » 4 years ago, # ^ |   +3 I have the same I/O timeout problem for problem D also for C#. Spent the entire contest time trying to figure out why I am getting timeout on test 9.I also don't welcome this situation. The official answer was that "It is not guaranteed that a solution exists for all languages". Well, c'on... I have seen some folks with solutions in C++ and still getting timeout on test 9, probably for the same reasons (since some are Div1).I would like to thanks the organizers for setting up the contest of course, really enjoyable, but cannot but feel disatisified with taking a big rating hit for trying to solve a problem which is unsovable given the time limits without optimizing I/O. Really, this is a known issue. My opinion is that the limits should have been increased to 3 or 3.5 seconds to allow for such reads. This will still not make an n^2 fit but will allow enough time to I/O...Didn't even have time to read the others except B (which also has a very long text...). My opinion is that weather this particular contest should be rated should come into question.
 » 4 years ago, # | ← Rev. 2 →   +5 Am I the only one who practice translating hardly?
 » 4 years ago, # |   0 Lowest solved, highest wrong answer :P "long live 398 Div#2"
 » 4 years ago, # |   +7 Be stucked in Problem B. RIP my rating. :<
 » 4 years ago, # |   -10 Contest should be unrated.Bad translations, long statements and very hard B.
 » 4 years ago, # |   +19 is it rated?!
•  » » 4 years ago, # ^ |   +28 only for Div.1 participants ;)
•  » » » 4 years ago, # ^ |   +10 No please:) I just resubmit without thinking when i stuck at some problems. Many pretests failed including failing pretest 2 :)
 » 4 years ago, # |   -23 Vote here. They can make contest unrated.
•  » » 4 years ago, # ^ |   0 I liked the problems. They were harder than usual, but they were harder for everybody, not just you. Why make it unrated?
•  » » » 4 years ago, # ^ |   +6 I would vote for unrated because there were several issues with timeouts due to I/O operations taking to long (for example in C# for problems D and I understand also C).I would really have enjoyed this contest especially due to the harder problems however if despite a sound solution I have to spend the entire contest time to figure out I get timeouts due to I/O, then.. I would go for unrated.
•  » » » » 4 years ago, # ^ |   0 Maybe you should avoid using slow languages in competitions.
•  » » » » » 4 years ago, # ^ |   +5 Thanks! Never encountered this problem until now though. Usually the limits are better thought to allow even C# and Java solutions to pass.
•  » » 4 years ago, # ^ |   +13 do not worry, your name will fit your new rank haha
•  » » » 4 years ago, # ^ |   0 I'm pupil now. LOL
 » 4 years ago, # |   +3 Fastest Systest ever... no wonder, since there was so low total number of submissions.
 » 4 years ago, # |   0 How to solve E?
 » 4 years ago, # | ← Rev. 2 →   +43 4 6 20 1 1 12 2 2 2 2 2Are cases like these not in system tests? At least two of my friends will output -1 for this test but I believe all the cartons of milk can be drank, right?In fact, my friend will fail if there is no 0 in the first line but a solution still exist. This apparently is not in the systests however ==
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Shouldn't the answer be -1? We can drink carton 1 and 2 that are inside fridge on day 1 but how can we drink carton 3 and 4 on day 2?
•  » » » 4 years ago, # ^ |   +10 You can just drink them lol. They are not expired yet.
 » 4 years ago, # | ← Rev. 2 →   0 A. Pretest 5 should be a systest! There should be more possibilities to hack.
 » 4 years ago, # | ← Rev. 2 →   0 A DIV2 guys can some one tell me why i got TLE on test 23 ? submission
 » 4 years ago, # | ← Rev. 3 →   +5 problem B test case 3 :input:7 14 321 2output:13answer:0statement says :The receptionist spends exactly t minutes on each person in the queue. If the receptionist would stop working within t minutes, he stops serving visitors (other than the one he already serves).my output should be correct
•  » » 4 years ago, # ^ |   0 Yes I have the same question too for my submission. Please someone to answer us.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +5 Your output is 13, while if Vasya visit t = 13, the receptionist would not serve Vasya as the reception cannot close before tf = 14 because it requires 3 minutes serving Vasya (from t = 13 to t = 15).
•  » » » 4 years ago, # ^ |   +5 Yea but the statement says "(other than the one he already serves)."
•  » » » » 4 years ago, # ^ |   0 Which means someone he is already serving, and not people who are in the queue waiting.
•  » » » » 4 years ago, # ^ |   0 I think the receptionist will choose to serve a new comer or not, based on whether if the receptionist can serve the new comer fully before the close of receptionSo for "the one he already serves", they mean those being fully served as the receptionist will choose not to serve the new comer if the new comer cannot be fully served.
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Please skip this comment
•  » » » » 4 years ago, # ^ |   0 Yeah, but the statement also says "(so that (tf - 1) is the last minute when the receptionist is still working)". So (I'm also not happy to admit), from the statement, the answer to case 3 is indeed 0. Dammit!
•  » » 4 years ago, # ^ |   0 same problem here i was stuck with that test case
•  » » 4 years ago, # ^ |   0 Let's rephrase the last sentence : "The receptionist will not accept new customers during last t minutes, but she will finish serving those who came until time t_f - t" I misunderstood this statement during contest as well, but fixed my code easily with this new insight (compare 24774069 and 24775470).IMO, pretest 3 should have simply been added to problem statement and all would be much better.
•  » » » 4 years ago, # ^ |   0 I see. Thanks for the answer. Personally I am not so good in english and I find the translation terrible. I suppose that many others feel the same and that this bad translation costed to us time and rating.
•  » » 4 years ago, # ^ |   0 I faced the same problem this system test is the worst of all
•  » » 4 years ago, # ^ | ← Rev. 4 →   0 My solution failed system tests just because of this 'error' in the problem statement. Maybe this is one of the reasons why B had so many successful submissions.
•  » » » 4 years ago, # ^ |   0 KAN MikeMirzayanov Could you please provide some clarification as to what that statement meant? Some other used asked during the contest and he was clarified what it meant. Should not that have been an announcement for everyone?
•  » » » » 4 years ago, # ^ |   +10 As others mentioned, the statement is: "When there is t minutes before tf, the receptionist stops serving new visitors, and only finishes serving the one which is already being served."
•  » » » » » 4 years ago, # ^ |   0 Unfortunately, I do not see that line in problem statement. All I see is "If the receptionist would stop working within t minutes, he stops serving visitors (other than the one he already serves)." And I do not think many people would agree that both the statements mean the same thing. The problem statement should have been more clear :)
•  » » 4 years ago, # ^ |   0 This part of the statement explains why the answer to case 3 is 0:"(so that (tf  -  1) is the last minute when the receptionist is still working)"
 » 4 years ago, # |   +5 System test gives WA for all submission for problems D &E
•  » » 4 years ago, # ^ |   0 I got AC for D...
•  » » » 4 years ago, # ^ |   -10
•  » » » » 4 years ago, # ^ |   +16 Don't worry, you still have your another Div.1 account : repeating
•  » » » » » 4 years ago, # ^ |   -12 Is it forbidden to have 2 accounts on CF !!
•  » » » » » » 4 years ago, # ^ |   +6 OMG, Question of the year!!!
 » 4 years ago, # | ← Rev. 2 →   +26 WTF is wrong here, it says my D is accepted but in standings it seems like it failed — http://store.picbg.net/pubpic/6A/71/96070172827f6a71.png?UPD: That's the case for everyone, now I see...
•  » » 4 years ago, # ^ |   0 Seems like it affected the Rating changes too.
 » 4 years ago, # |   0 I do not know why everyone says that problem B was difficult, it was just a simulation and greedy, for me it was more difficult to solve problem C
 » 4 years ago, # |   0 This was the worst contest for me — I began with C, did it. Then tried D, but failed on some pretest. At this point I had just 20 minutes left, so I went back to A and B. I got A, but with a very low score, then wrote B. I had a small bug, which I found. I was just about to click submit when the contest ended(I had already selected the file). In the end, my C fails system test. :(((
 » 4 years ago, # | ← Rev. 2 →   0 I've got a question. This is test 4 for B problem:30 70 10330 32 35Why is the answer 60? Isn't the queue supposed to close a tr — 1 = 69?
•  » » 4 years ago, # ^ |   +6 If Vasya visits at t = 60, Vasya is served from t = 60 to t = 69 which consists of 10 whole minutes. So the reception can close at tf = 70.so that (tf - 1) is the last minute when the receptionist is still workingBy this, the receptionist still works at t = tf - 1 = 70 - 1 = 69.
 » 4 years ago, # | ← Rev. 4 →   0 What's going on with the standing? They are giving fail in spite of passing? NVM, it got fixed
 » 4 years ago, # |   -40 What kind of time limit has been set for the 2nd problem ?What fool did it ? Who is this foolish person who set this problem ?Submissions : Java (During the contest), MLE : http://codeforces.com/contest/767/submission/24771836 C++ (After the contest), AC within 1310 ms : http://codeforces.com/contest/767/submission/24775207 Such a negligent attitude is rather bad, and I dont think deserves a place on CF. The two codes are 150 % identical, expect they differ only and only in language .
•  » » 4 years ago, # ^ |   +10 Dude think before calling the problem setters foolish. They are doing this voluntarily and you should be thankful to them instead. Sometimes there are some negligences, but you shouldn't call them foolish at least.
 » 4 years ago, # |   0 Is this proper test for B? Is only Vasya can come at midnight (at time 0) ? 0 7 2 4 0 0 0 6
•  » » 4 years ago, # ^ |   0 tgeed yahked bgan ci haha
 » 4 years ago, # |   0 I was deceived by the unusual input of C which is tree data
 » 4 years ago, # | ← Rev. 4 →   +5 In problem B, for the 3rd pretest: 7 14 3 2 1 2 My answer was 13. Why is it wrong? In the condition it states: If the receptionist would stop working within t minutes, he stops serving visitors (other than the one he already serves), so I assumed that means he should enter before tf but doesn't need to get out before tf. Either I'm missing something or the condition was wrong.Whoops, someone already posted the same question, sry.
•  » » 4 years ago, # ^ |   0 same problem here
•  » » 4 years ago, # ^ |   +2 MikeMirzayanov please look into this
•  » » 4 years ago, # ^ |   +5 If you go at time 13, the receptionist would stop working within 3 minutes(actually after 1 minute the person will stop working). So you can't get served.
•  » » » 4 years ago, # ^ |   +6 (other than the one he already serves), this means that he keeps serving the one she already servers.
•  » » » » 4 years ago, # ^ |   0 No, that means, say, assume you go at time 9 and start served. At time 11 the receptionist would stop working within 3 minutes, but the server continues to serve you.
•  » » » » 4 years ago, # ^ |   0 I think the receptionist will choose to serve a new comer or not, based on whether if the receptionist can serve the new comer fully before the close of reception.
•  » » 4 years ago, # ^ |   +2 You won't be served if you come at 13, because the queue closes T seconds before the end.
•  » » » 4 years ago, # ^ |   0 (other than the one he already serves), this means that he keeps serving the one she already servers.
•  » » » » 4 years ago, # ^ |   0 But he comes after than T seconds before the end, so the queue is already closed. He isn't even start getting the passport.The idea behind the phrase is the following one. Suppose T = 5, Tr = 20. If you come at 13 seconds, you will be served even if the queue is supposed to close at 15. If you come at 18, however, you aren't served.
•  » » 4 years ago, # ^ |   0 Oh yeah, I just read that wrong, my bad, missed the "within t minutes" part. I should buy new glasses xd.
 » 4 years ago, # |   0 In problem B This test case: 7 14 3 2 1 2The output of the judge is 0 however i am printing 13 and he tells me wrong why he can come at min. 13 noone is there so he can enter as the 2nd one finishes at min. 13
 » 4 years ago, # | ← Rev. 2 →   +11 I got 17th place, but it is showing that I got 49th place.
•  » » 4 years ago, # ^ |   +1 I finished 316 , but rating update says that I finished 2236... looks like "D" was not considered in rating update somehow
•  » » » 4 years ago, # ^ |   +1 same here I finished 263 but says that I finished 2017
•  » » 4 years ago, # ^ |   +1 Same problem here. It looks like the rating was calculated before system testing.
•  » » 4 years ago, # ^ |   +1 Same here. This shows I got 108th place while this shows I got 347th place.
•  » » 4 years ago, # ^ |   0 Looks like cf has broken.
•  » » 4 years ago, # ^ |   0 same here !
•  » » 4 years ago, # ^ |   0 17th div2 participants , 49th with div1+div2
 » 4 years ago, # |   +16 That moment when only A is accepted but I have new best rating lol.
 » 4 years ago, # | ← Rev. 2 →   +22 MikeMirzayanov Rating change is weird.
 » 4 years ago, # |   +3 Why does it say I am in position 656 or so if I'm in position 97? My rating went down when it should have gone up. Please help
 » 4 years ago, # |   0 Why is everyone's D on the scoreboard wrong?In status I see I have accepted it.But the rating have changed according to the scoreboard .
•  » » 4 years ago, # ^ |   +3 And also E!!!
 » 4 years ago, # |   0 MikeMirzayanov how come the same test case pass in the pre-test and fail in the system test, my solution is anyways has a bug but I'm just curious. http://codeforces.com/contest/767/submission/24762072
 » 4 years ago, # |   +43 Cheaters On Problem D: Hasan: Submission M.A.H.M.O.O.D: Submission
•  » » 4 years ago, # ^ |   -22 yeah but I got AC and Hassoony got TLE on test 9 Problem D is an easy binary search with greedy for a check function it's easy to have similar codes because the problem is easy I mean for problems like A and B in contests almost everyone submits a similar code.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +41 You got AC with 1996ms. He got TLE because he changed everything to long long, while you simply added unsigned in some places. Don't Try to be smart :)))).
•  » » » 4 years ago, # ^ |   -26
•  » » 4 years ago, # ^ |   +12
•  » » » 4 years ago, # ^ |   +11 Thanks for being very responsive.
•  » » » » 4 years ago, # ^ |   0 Be like CheaterKiller :D
•  » » 4 years ago, # ^ |   0 So, why have you created a fake account? I can't believe, that you are afraid of them.
•  » » 4 years ago, # ^ |   +3
 » 4 years ago, # |   +1 hi .. there is a problem in standing now .. my soultion for D is accepted and apper on my standing -1 !! and i haven't points and my rate is decrease !! how !!??
 » 4 years ago, # |   +1 on the contest standings it says that I ranked 103(without unofficial participates) but on my profile it shows that the last contest I did (#398) I ranked 289Can somebody look into this because it will effect my rate a lot ?
•  » » 4 years ago, # ^ |   +3 this might help http://codeforces.com/blog/entry/50469?#comment-343949
 » 4 years ago, # |   +15 Seems the problem with D&E standings display also affected the rating changes... Is there anyone fixing this?
 » 4 years ago, # |   +19 Ahhhhhh，What's the matter? I think my rating is too high.
 » 4 years ago, # |   +9 my submission of problem D showed accepted in "My submission",while the final score is calculated without the score of problem D. what is the problem?
•  » » 4 years ago, # ^ |   +1 same here !!
 » 4 years ago, # | ← Rev. 2 →   +3 Question C: That moment when you realize that abs(1/3 * total) < abs(total) doesn't hold if total = 0.EDIT: total -> abs(total)
•  » » 4 years ago, # ^ |   0 And it's even worse when total got negative.
•  » » » 4 years ago, # ^ |   0 Oops, I meant abs(1/3 * total) < abs(total).
•  » » 4 years ago, # ^ |   +8 Or when you realize there's no wire above the root.
•  » » » 4 years ago, # ^ |   0 Same...
 » 4 years ago, # |   +3 When you solved 1 problem but your rating still increases
•  » » 4 years ago, # ^ |   0 Same....
 » 4 years ago, # |   +12 I want to know why my rating -48,In this conteset my rank is 124, but the profile's rank is 980,why ? Sorry,my English isn't well
 » 4 years ago, # |   +60 this happened because you didn't say thanks to MikeMirzayanov
 » 4 years ago, # |   +31 Strange rating change. It seems like problem D is not considered.
•  » » 4 years ago, # ^ |   0 same here !
•  » » 4 years ago, # ^ |   +5 yes...but why?
•  » » » 4 years ago, # ^ |   +11 Hope it will be recovered. You can't lose the chance to be purple.
•  » » » » 4 years ago, # ^ |   +5 thank you~ and you can rise more :)
 » 4 years ago, # |   +5 Problem B statement is wrong. "If the receptionist would stop working within t minutes, he stops serving visitors (other than the one he already serves)." I submitted without considering above statement, my solution got accepted.
 » 4 years ago, # |   +10 More points but less rating increase Me
 » 4 years ago, # |   0 If I know about such complicate B task I would spend all time solving D, segment tree is much more attractive for me :)
 » 4 years ago, # | ← Rev. 2 →   -38 .
•  » » 4 years ago, # ^ |   +8 The contest is already unrated for you!
•  » » 4 years ago, # ^ |   +10 Which test is not correct? Easy to say sth. like this without mentioning a specific test
•  » » » 4 years ago, # ^ |   0 7 14 3 2 1 2 Answer should be 13 instead of 0. Problem is occuring because of wrong problem statement. "If the receptionist would stop working within t minutes, he stops serving visitors (other than the one he already serves)."
•  » » » » 4 years ago, # ^ |   0 even i had that confusion and had 4 WAs thanks to that. then i asked in the question section and got clarified.As codeforces's popularity is growing day by day, I think they should take an effort to provide better English statements.
•  » » » » » 4 years ago, # ^ |   -11 Either round should be unrated or submissions must be retested based on the problem statement.
•  » » » » » » 4 years ago, # ^ |   0 If it gets retested, a lot of AC ones will get WA. I don't think this happened for the first time in CF. It happened a lot in the past too and none of those round was declared unrated...
•  » » » » 4 years ago, # ^ |   0 I fail to understand why it should be 13? If you arrive at 13, you won't be served, because t_f is 14 and 13+3 is > 14?? This complies with the problem statement.
•  » » » » » 4 years ago, # ^ |   0 "If the receptionist would stop working within t minutes, he stops serving visitors (other than the one he already serves)." This implies that even if you arrive at 13 you will be served.
•  » » » » » » 4 years ago, # ^ | ← Rev. 4 →   0 No, he will already stop serving new visitors after 14-3 = 11 because then current time + t > 14! This is what it implies...
•  » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 "He already serves" not "he is serving". There is nothing wrong with the statement. Check your English.
•  » » » » » » » 4 years ago, # ^ |   0 Okay
 » 4 years ago, # | ← Rev. 2 →   +32 Please, next time spend your energy on writing more clear problem statements instead of drawing pictures to all questions.
 » 4 years ago, # |   0 well, feel lucky not to compete in this round- - seems easy but actually…er…you all know now.
•  » » 4 years ago, # ^ |   0 after read the problems carefully…regret? D & E seems extraordinarily easy……than B
 » 4 years ago, # |   +3 How is the rating calculated? I ranked 21st in the contest,but the rating dropped by 20! I'm the only one whose rating dropped among the top 88 people,including those whose ratings were initially higher or lower than me.In particular,there are many people whose initial ratings were higher than me,scored lower than me in this contest,but their ratings rose sharply!How could this happen?
•  » » 4 years ago, # ^ |   0 I hope my ratings won't get decreased now -_-
 » 4 years ago, # |   +65 We know about the issue with ratings, they will be rolled back and then updated properly. Don't worry.
 » 4 years ago, # |   0 I quit , i need my Rate back !
 » 4 years ago, # |   0 In pC, when I hacked others with 4 0 1 1 -1 2 1 3 -1 The verdict of the hack is an unexpected error...... Just wonder whether this kind of testdata are already in the system test or not...
 » 4 years ago, # |   +9 Why rating changes is not logical ....
 » 4 years ago, # |   0 why？ same original rating , higher rank,lower rating? feel sad QAQ!
 » 4 years ago, # | ← Rev. 2 →   0 LOL
 » 4 years ago, # |   +13 The problems D&E were even not considered in standings on my IE ,but fortunately now it has been fixed .Just waiting for the fixing of rating changes now .
 » 4 years ago, # |   0 Hard but interesting problem set. Thanks for your work and I also appreciate the strong pre-tests!
 » 4 years ago, # |   0 Can someone provide me some good questions for practice on DP on trees.?
•  » » 4 years ago, # ^ |   0
 » 4 years ago, # |   +22 KAN How this Code get AC ?!test: 3 1 2 1 1 1 2 Code Output : -1 Expected Output : 1 1
•  » » 4 years ago, # ^ |   0 LOL
•  » » 4 years ago, # ^ |   0 this code and this code have the same issue
 » 4 years ago, # |   +3 I think score distribution should be change
 » 4 years ago, # |   -13
 » 4 years ago, # |   +1 KAN How can this code http://codeforces.com/contest/767/submission/24788498 24788498 get AC test case 5 20 4 4 0 0 10 14
•  » » 4 years ago, # ^ |   +1 This is invalid test The third line contains positive integers in non-decreasing order the time of the visitors must be positive, it can't be 0
 » 4 years ago, # |   +23 Wow! I got three 98 in Codeforces Round #398!
 » 4 years ago, # |   0 i think the problem is good , not only degree of difficulty , but also the trick . forever , the difficulty classification is so bad , the D is easier than B and C i think A D B C is better than the round .
 » 4 years ago, # | ← Rev. 2 →   +1 Solution for B: ~~~~~ ~~~~~ long min = 0; long mins = ts+t; int pl = 0; for (; pl
 » 4 years ago, # | ← Rev. 3 →   0 I wonder why this 24795199 got WA. I need help.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 your code fails in this testcase:50 11 -12 13 14 1 I think you are marking more than 2 vertices, because you are cutting the tree more than 2 times. I added another condition (num != 2) to your if at the dfs and it passes test 9.http://codeforces.com/contest/767/submission/24806874
•  » » » 4 years ago, # ^ |   0 I got it.Thanks！
 » 4 years ago, # |   +3 I found a test case which is 6 2 -1 3 1 0 1 3 -1 4 1 5 -1 Both my friends passed the problem, but have different output, their submission are 24775420, 24775421 the first one output 2 5, which I think is correct, and the second one output -1 Do the sys test miss the test case like this?


text:
# Translation of \\foo\bar links into smb://foo/bar links

Tue Jan 18 14:30:26 GMT 2005

On Tuesday 18 January 2005 6:21 am, Thiago Macieira wrote:
> It makes sense for kfile too, but not in emails. KMail currently doesn't
> highlight \\server\share entries in emails.

While true, this is not the problem. The problem is that KIO does not
understand "file:///\\" as an smb share.

I work in a windows-centric office. People email links to SMB shares all the
time. They *never* have a working URL in KDE. This is because, I think, when

For example, just yesterday I got an email with a link that is supposed to
point at this (changed a bit for clarity):

\\server\share\path\Functional Spec.doc

This is the URL it gives me in the link:

file:///%5C%5Cserver%5Cshare%5Cpath%5CFunctional%20Spec.doc

Or, for those without URL decoder brains:

file:///\\server\share\path\Functional Spec.doc

When I click this, I get an error saying "The file or folder
file:///\\server\share\path\Application Installation Functional Spec.doc does
not exist".

I think KMail / KDE should be able to handle these URLs. A URL with
"file:///\\" or "file:/\\" should all be able to be handled as smb:// URLs.

--
If you wait by the river long enough, eventually
you will see the bodies of all your enemies float by.
- Sun Tzu

format: plain


text:
# Free monoid generated by

Jump to: navigation, search
Stub grade: A
This page is a stub
This page is a stub, so it contains little or minimal information and is on a to-do list for being expanded.The message provided is:
Demote once fleshed out and minimally complete
Be sure to check Discussion of the free monoid and free semigroup generated by a set, as there are some things to note

## Definition

Given a set, [ilmath]X[/ilmath], there is a free monoid, [ilmath](F,*)[/ilmath][1].

• The elements of [ilmath]F[/ilmath] are all the finite tuples, [ilmath](x_1,\ldots,x_n)[/ilmath] (where [ilmath]x_i\in X[/ilmath])
• The monoid operation ([ilmath]*:F\times F\rightarrow F[/ilmath]) is concatenation:
• [ilmath]*:((x_1,\ldots,x_n),(y_1,\ldots,y_n))\mapsto(x_1,\ldots,x_n,y_1,\ldots,y_n)[/ilmath]
• The identity element of the monoid is:
• [ilmath]e=()[/ilmath] - the "empty" tuple.

The proof that this is indeed a monoid is below

### Notation

• We often identify [ilmath]x\in X[/ilmath] with [ilmath](x)\in F[/ilmath], and singletons of [ilmath]F[/ilmath] (ie: [ilmath](y)\in F[/ilmath] with [ilmath]y\in X[/ilmath].
• This notation extends further, and (especially in the case of the free semigroup generated by [ilmath]X[/ilmath][Note 1]) we write [ilmath](x_1,x_2,\ldots,x_{n-1},x_n)[/ilmath] as a product or word, [ilmath]x_1x_2\ldots x_{n-1}x_n[/ilmath]

## Terminology

• The finite tuples of [ilmath]F[/ilmath] are sometimes called "words".
• Warning:The "word" terminology may be specific to the free group, however I wouldn't be surprised if word is used in this context too, so I deem it still worth mentioning
• Caution:Word may only be used for elements of [ilmath]F[/ilmath] written in the "product" notation, [ilmath]x_1\ldots x_n[/ilmath]. The reference[1] implies this.
Grade: D
This page requires references, it is on a to-do list for being expanded with them.
Please note that this does not mean the content is unreliable, it just means that the author of the page doesn't have a book to hand, or remember the book to find it, which would have been a suitable reference.
The message provided is:
While not explicitly said, the main reference doesn't deal with these objects in great detail, however usually such tuples are called words, at least with free groups (see warning)

## Examples

• This page can be considered an element of the monoid generated by the alphabet (union all the symbols too)

## Proof that this is indeed a monoid

1. Associativity is trivial
2. Identity element being an identity element is trivial

(These might be good "low hanging fruit" for any newcomers)

## Notes

1. We do this because the semigroup has no identity (in fact, is considered as the set of all tuples of length greater than or equal to one of elements of [ilmath]X[/ilmath]), it has no "empty tuple", writing an empty tuple as a "word" would be an empty word! You couldn't even tell it was there.


text:
# My Favorite One-Liners: Part 50

In this series, I’m compiling some of the quips and one-liners that I’ll use with my students to hopefully make my lessons more memorable for them.

Here’s today’s one-liner: “To prove that two things are equal, show that the difference is zero.” This principle is surprisingly handy in the secondary mathematics curriculum. For example, it is the basis for the proof of the Mean Value Theorem, one of the most important theorems in calculus that serves as the basis for curve sketching and the uniqueness of antiderivatives (up to a constant).

And I have a great story that goes along with this principle, from 30 years ago.

I forget the exact question out of Apostol’s calculus, but there was some equation that I had to prove on my weekly homework assignment that, for the life of me, I just couldn’t get. And for no good reason, I had a flash of insight: subtract the left- and right-hand sides. While it was very difficult to turn the left side into the right side, it turned out that, for this particular problem, was very easy to show that the difference was zero. (Again, I wish I could remember exactly which question this was so that I could show this technique and this particular example to my own students.)

So I finished my homework, and I went outside to a local basketball court and worked on my jump shot.

Later that week, I went to class, and there was a great buzz in the air. It took ten seconds to realize that everyone was up in arms about how to do this particular problem. Despite the intervening 30 years, I remember the scene as clear as a bell. I can still hear one of my classmates ask me, “Quintanilla, did you get that one?”

I said with great pride, “Yeah, I got it.” And I showed them my work.

And, either before then or since then, I’ve never heard the intensity of the cussing that followed.

Truth be told, probably the only reason that I remember this story from my adolescence is that I usually was the one who had to ask for help on the hardest homework problems in that Honors Calculus class. This may have been the one time in that entire two-year calculus sequence that I actually figured out a homework problem that had stumped everybody else.

# My Favorite One-Liners: Part 46

In this series, I’m compiling some of the quips and one-liners that I’ll use with my students to hopefully make my lessons more memorable for them. Today’s one-liner is something I’ll use after completing some monumental calculation. For example, if $z, w \in \mathbb{C}$, the proof of the triangle inequality is no joke, as it requires the following as lemmas:

• $\overline{z + w} = \overline{z} + \overline{w}$
• $\overline{zw} = \overline{z} \cdot \overline{w}$
• $z + \overline{z} = 2 \hbox{Re}(z)$
• $|\hbox{Re}(z)| \le |z|$
• $|z|^2 = z \cdot \overline{z}$
• $\overline{~\overline{z}~} = z$
• $|\overline{z}| = |z|$
• $|z \cdot w| = |z| \cdot |w|$

With all that as prelude, we have

$|z+w|^2 = (z + w) \cdot \overline{z+w}$

$= (z+w) (\overline{z} + \overline{w})$

$= z \cdot \overline{z} + z \cdot \overline{w} + \overline{z} \cdot w + w \cdot \overline{w}$

$= |z|^2 + z \cdot \overline{w} + \overline{z} \cdot w + |w|^2$

$= |z|^2 + z \cdot \overline{w} + \overline{z} \cdot \overline{~\overline{w}~} + |w|^2$

$= |z|^2 + z \cdot \overline{w} + \overline{z \cdot \overline{w}} + |w|^2$

$= |z|^2 + 2 \hbox{Re}(z \cdot \overline{w}) + |w|^2$

$\le |z|^2 + 2 |z \cdot \overline{w}| + |w|^2$

$= |z|^2 + 2 |z| \cdot |\overline{w}| + |w|^2$

$= |z|^2 + 2 |z| \cdot |w| + |w|^2$

$= (|z| + |w|)^2$

In other words,

$|z+w|^2 \le (|z| + |w|)^2$.

Since $|z+w|$ and $|z| + |w|$ are both positive, we can conclude that

$|z+w| \le |z| + |w|$.

QED

In my experience, that’s a lot for students to absorb all at once when seeing it for the first time. So I try to celebrate this accomplishment:

Anybody ever watch “Home Improvement”? This is a Binford 6100 “more power” mathematical proof. Grunt with me: RUH-RUH-RUH-RUH!!!

# My Favorite One-Liners: Part 43

In this series, I’m compiling some of the quips and one-liners that I’ll use with my students to hopefully make my lessons more memorable for them. q Q

Years ago, my first class of students decided to call me “Dr. Q” instead of “Dr. Quintanilla,” and the name has stuck ever since. And I’ll occasionally use this to my advantage when choosing names of variables. For example, here’s a typical proof by induction involving divisibility.

Theorem: If $n \ge 1$ is a positive integer, then $5^n - 1$ is a multiple of 4.

Proof. By induction on $n$.

$n = 1$: $5^1 - 1 = 4$, which is clearly a multiple of 4.

$n$: Assume that $5^n - 1$ is a multiple of 4.

At this point in the calculation, I ask how I can write this statement as an equation. Eventually, somebody will volunteer that if $5^n-1$ is a multiple of 4, then $5^n-1$ is equal to 4 times something. At which point, I’ll volunteer:

Yes, so let’s name that something with a variable. Naturally, we should choose something important, something regal, something majestic… so let’s choose the letter $q$. (Groans and laughter.) It’s good to be the king.

So the proof continues:

$n$: Assume that $5^n - 1 = 4q$, where $q$ is an integer.

$n+1$. We wish to show that $5^{n+1} - 1$ is also a multiple of 4.

At this point, I’ll ask my class how we should write this. Naturally, I give them no choice in the matter:

We wish to show that $5^{n+1} - 1 = 4Q$, where $Q$ is some (possibly different) integer.

Then we continue the proof:

$5^{n+1} - 1 = 5^n 5^1 - 1$

$= 5 \times 5^n - 1$

$= 5 \times (4q + 1) - 1$ by the induction hypothesis

$= 20q + 5 - 1$

$= 20q + 4$

$= 4(5q + 1)$.

So if we let $Q = 5q +1$, then $5^{n+1} - 1 = 4Q$, where $Q$ is an integer because $q$ is also an integer.

QED

On the flip side of braggadocio, the formula for the binomial distribution is

$P(X = k) = \displaystyle {n \choose k} p^k q^{n-k}$,

where $X$ is the number of successes in $n$ independent and identically distributed trials, where $p$ represents the probability of success on any one trial, and (to my shame) $q$ is the probability of failure.

# My Favorite One-Liners: Part 13

In this series, I’m compiling some of the quips and one-liners that I’ll use with my students to hopefully make my lessons more memorable for them.

Here’s a story that I’ll tell my students when, for the first time in a semester, I’m about to use a previous theorem to make a major step in proving a theorem. For example, I may have just finished the proof of

$\hbox{Var}(X+Y) = \hbox{Var}(X) + \hbox{Var}(Y)$,

where $X$ and $Y$ are independent random variables, and I’m about to prove that

$\hbox{Var}(X-Y) = \hbox{Var}(X) + \hbox{Var}(Y)$.

While this can be done by starting from scratch and using the definition of variance, the easiest thing to do is to write

$\hbox{Var}(X-Y) = \hbox{Var}(X+[-Y]) = \hbox{Var}(X) + \hbox{Var}(-Y)$,

thus using the result of the first theorem to prove the next theorem.

And so I have a little story that I tell students about this principle. I think I was 13 when I first heard this one, and obviously it’s stuck with me over the years.

At MIT, there’s a two-part entrance exam to determine who will be the engineers and who will be the mathematicians. For the first part of the exam, students are led one at a time into a kitchen. There’s an empty pot on the floor, a sink, and a stove. The assignment is to boil water. Everyone does exactly the same thing: they fill the pot with water, place it on the stove, and then turn the stove on. Everyone passes.

For the second part of the exam, students are led one at a time again into the kitchen. This time, there’s a pot full of water sitting on the stove. The assignment, once again, is to boil water. Nearly everyone simply turns on the stove. These students are led off to become engineers. The mathematicians are ones who take the pot off the stove, dump the water into the sink, and place the empty pot on the floor… thereby reducing to the original problem, which had already been solved.

# Engaging students: Completing the square

In my capstone class for future secondary math teachers, I ask my students to come up with ideas for engaging their students with different topics in the secondary mathematics curriculum. In other words, the point of the assignment was not to devise a full-blown lesson plan on this topic. Instead, I asked my students to think about three different ways of getting their students interested in the topic in the first place.

I plan to share some of the best of these ideas on this blog (after asking my students’ permission, of course).

This student submission comes from my former student Deborah Duddy. Her topic, from Algebra: completing the square.

What interesting word problems using this topic can your students do now?

Applying what is learned in the class is very vital in fact it is a process TEKS that teachers need to use to maximize student’s understanding. “When are we going to use this in real life?” and “Why do we need to know this?” are questions that students ask on a daily basis. Connecting material to the real world helps engage students and develops critical thinking. Describing a path of a ball, how far an item can be tossed in the air and how to maximize profits for a company are just some examples of how quadratics can be used in the real world.

One important event happens during high school; students receive their driver’s license. In their written driver’s test, students must know the distance needed to stop a car at certain speed limits. Using an example like the one below will be interesting for the students and help connect lesson material and real life.

How could you as a teacher create an activity or project that involves your topic?

To begin class and get students involved with their learning, the class will participate in an activity. Each pair of students will have two different cards such as (x+2)^2 and x^2+4x+4, and any variations of these problems. They can only look at the (x+2)^2 card. Students will work out the problem on paper. Students will be asked to remember how to find the area of a square and then set up a square with the dimensions matching the first card. From there, the pairs would use algebra tiles (after knowing what each tile stands for) and attempt to “complete the square”. This activity will be used as an engage and a beginning explore for the students. This activity will help students see completing a square geometrically.

How does this topic extend what your students should have learned in previous courses?

Completing the square is another way of solving/factoring the equation. The process of completing the square is to turn a basic quadratic   equation of ax^2 + bx + c = 0 into a(x-h)^2 + k = 0 where (h,k) is  the vertex of the parabola. Therefore this process is very beneficial because it helps students graph the quadratic equation given. In order to find h and k, students should be able to factor, square a term, find the square root and manipulate the equation.

In solving the equation by completing the square is to subtract the constant off the left side and onto the right side. Then students take the coefficient off the x-term divide it then square it. Students then add this number to both sides of the equations. By simplifying the right side of the equation, students give the perfect square. Then solve the equation left by taking the square root of both sides and determining x.

References:

http://www.classzone.com/eservices/home/pdf/student/LA205EBD.pdf

# What I Learned from Reading “Gamma: Exploring Euler’s Constant” by Julian Havil: Part 18

The Riemann Hypothesis (see here, here, and here) is perhaps the most famous (and also most important) unsolved problems in mathematics. Gamma (page 207) provides a way of writing down this conjecture in a form that only uses notation that is commonly taught in high school:

If $\displaystyle \sum_{r=1}^\infty \frac{(-1)^r}{r^a} \cos(b \ln r) = 0$ and $\displaystyle \sum_{r=1}^\infty \frac{(-1)^r}{r^a} \sin(b \ln r) = 0$ for some pair of real numbers $a$ and $b$, then $a = \frac{1}{2}$.

As noted in the book, “It seems extraordinary that the most famous unsolved problem in the whole of mathematics can be phrased so that it involves the simplest of mathematical ideas: summation, trigonometry, logarithms, and [square roots].”

When I researching for my series of posts on conditional convergence, especially examples related to the constant $\gamma$, the reference Gamma: Exploring Euler’s Constant by Julian Havil kept popping up. Finally, I decided to splurge for the book, expecting a decent popular account of this number. After all, I’m a professional mathematician, and I took a graduate level class in analytic number theory. In short, I don’t expect to learn a whole lot when reading a popular science book other than perhaps some new pedagogical insights.

Boy, was I wrong. As I turned every page, it seemed I hit a new factoid that I had not known before.

In this series, I’d like to compile some of my favorites — while giving the book a very high recommendation.

# What I Learned from Reading “Gamma: Exploring Euler’s Constant” by Julian Havil: Part 17

Let $\pi(n)$ denote the number of positive prime numbers that are less than or equal to $n$. The prime number theorem, one of the most celebrated results in analytic number theory, states that

$\pi(x) \approx \displaystyle \frac{x}{\ln x}$.

This is a very difficult result to prove. However, Gamma (page 172) provides a heuristic argument that suggests that this answer might be halfway reasonable.

Consider all of the integers between $1$ and $x$.

• About half of these numbers won’t be divisible by 2.
• Of those that aren’t divisible by 2, about two-thirds won’t be divisible by 3. (This isn’t exactly correct, but it’s good enough for heuristics.)
• Of those that aren’t divisible by 2 and 3, about four-fifths won’t be divisible by 5.
• And so on.

If we repeat for all primes less than or equal to $\sqrt{x}$, we can conclude that the number of prime numbers less than or equal to $x$ is approximately

$\pi(x) \approx \displaystyle x \prod_{p \le \sqrt{x}} \left(1 - \frac{1}{p} \right)$.

From this point, we can use Mertens product formula

$\displaystyle \lim_{n \to \infty} \frac{1}{\ln n} \prod_{p \le n} \left(1 - \frac{1}{p} \right)^{-1} = e^\gamma$

to conclude that

$\displaystyle \frac{1}{\ln n} \prod_{p \le n} \left(1 - \frac{1}{p} \right) \approx \displaystyle \frac{e^{-\gamma}}{\ln n}$

if $n$ is large. Therefore,

$\pi(x) \approx x \displaystyle \frac{e^{-\gamma}}{\ln \sqrt{x}} = 2 e^{-\gamma} \displaystyle \frac{x}{\ln x}$.

Though not a formal proof, it’s a fast way to convince students that the unusual fraction $\displaystyle \frac{x}{\ln x}$ ought to appear someplace in the prime number theorem.

When I researching for my series of posts on conditional convergence, especially examples related to the constant $\gamma$, the reference Gamma: Exploring Euler’s Constant by Julian Havil kept popping up. Finally, I decided to splurge for the book, expecting a decent popular account of this number. After all, I’m a professional mathematician, and I took a graduate level class in analytic number theory. In short, I don’t expect to learn a whole lot when reading a popular science book other than perhaps some new pedagogical insights.

Boy, was I wrong. As I turned every page, it seemed I hit a new factoid that I had not known before.

In this series, I’d like to compile some of my favorites — while giving the book a very high recommendation.

# What I Learned from Reading “Gamma: Exploring Euler’s Constant” by Julian Havil: Part 16

Let $\pi(n)$ denote the number of positive prime numbers that are less than or equal to $n$. The prime number theorem, one of the most celebrated results in analytic number theory, states that

$\pi(x) \approx \displaystyle \frac{x}{\ln x}$.

This is a very difficult result to prove. However, Gamma (page 172) provides a heuristic argument that suggests that this answer might be halfway reasonable.

Consider all of the integers between $1$ and $x$.

• About half of these numbers won’t be divisible by 2.
• Of those that aren’t divisible by 2, about two-thirds won’t be divisible by 3. (This isn’t exactly correct, but it’s good enough for heuristics.)
• Of those that aren’t divisible by 2 and 3, about four-fifths won’t be divisible by 5.
• And so on.

If we repeat for all primes less than or equal to $\sqrt{x}$, we can conclude that the number of prime numbers less than or equal to $x$ is approximately

$\pi(x) \approx \displaystyle x \prod_{p \le \sqrt{x}} \left(1 - \frac{1}{p} \right)$.

From this point, we can use Mertens product formula

$\displaystyle \lim_{n \to \infty} \frac{1}{\ln n} \prod_{p \le n} \left(1 - \frac{1}{p} \right)^{-1} = e^\gamma$

to conclude that

$\displaystyle \frac{1}{\ln n} \prod_{p \le n} \left(1 - \frac{1}{p} \right) \approx \displaystyle \frac{e^{-\gamma}}{\ln n}$

if $n$ is large. Therefore,

$\pi(x) \approx x \displaystyle \frac{e^{-\gamma}}{\ln \sqrt{x}} = 2 e^{-\gamma} \displaystyle \frac{x}{\ln x}$.

Though not a formal proof, it’s a fast way to convince students that the unusual fraction $\displaystyle \frac{x}{\ln x}$ ought to appear someplace in the prime number theorem.

When I researching for my series of posts on conditional convergence, especially examples related to the constant $\gamma$, the reference Gamma: Exploring Euler’s Constant by Julian Havil kept popping up. Finally, I decided to splurge for the book, expecting a decent popular account of this number. After all, I’m a professional mathematician, and I took a graduate level class in analytic number theory. In short, I don’t expect to learn a whole lot when reading a popular science book other than perhaps some new pedagogical insights.

Boy, was I wrong. As I turned every page, it seemed I hit a new factoid that I had not known before.

In this series, I’d like to compile some of my favorites — while giving the book a very high recommendation.

# Predicate Logic and Popular Culture: Index

I’m doing something that I should have done a long time ago: collecting a series of posts into one single post. The following links comprised my series on using examples from popular culture to illustrate principles of predicate logic. My experiences teaching these ideas to my discrete mathematics students led to my recent publication (John Quintanilla, “Name That Tune: Teaching Predicate Logic with Popular Culture,” MAA Focus, Vol. 36, No. 4, pp. 27-28, August/September 2016).

Unlike other series that I’ve made, this series didn’t have a natural chronological order. So I’ll list these by concept illustrated from popular logic.

Logical and $\land$:

• Part 1: “You Belong To Me,” by Taylor Swift
• Part 21: “Do You Hear What I Hear,” covered by Whitney Houston
• Part 31: The Godfather (1972)
• Part 45: The Blues Brothers (1980)
• Part 53: “What Does The Fox Say,” by Ylvis
• Part 54: “Billie Jean,” by Michael Jackson

Logical or $\lor$:

• Part 1: Shawshank Redemption (1994)

Logical negation $\lnot$:

• Part 1: Richard Nixon
• Part 32: “Satisfaction!”, by the Rolling Stones
• Part 39: “We Are Never Ever Getting Back Together,” by Taylor Swift

Logical implication $\Rightarrow$:

• Part 1: Field of Dreams (1989), and also “Roam,” by the B-52s
• Part 2: “Word Crimes,” by Weird Al Yankovic
• Part 7: “I’ll Be There For You,” by The Rembrandts (Theme Song from Friends)
• Part 43: “Kiss,” by Prince
• Part 50: “I’m Still A Guy,” by Brad Paisley
• Part 76: “You’re Never Fully Dressed Without A Smile,” from Annie.

For all $\forall$:

• Part 3: Casablanca (1942)
• Part 4: A Streetcar Named Desire (1951)
• Part 34: “California Girls,” by The Beach Boys
• Part 37: Fellowship of the Ring, by J. R. R. Tolkien
• Part 49: “Buy Me A Boat,” by Chris Janson
• Part 57: “Let It Go,” by Idina Menzel and from Frozen (2013)
• Part 65: “Stars and Stripes Forever,” by John Philip Sousa.
• Part 68: “Love Yourself,” by Justin Bieber.
• Part 69: “I Will Always Love You,” by Whitney Houston.
• Part 74: “Faithfully,” by Journey.
• Part 79: “We’re Not Gonna Take It Anymore,” by Twisted Sister.
• Part 87: “Hungry Heart,” by Bruce Springsteen.

For all and implication:

• Part 8 and Part 9: “What Makes You Beautiful,” by One Direction
• Part 13: “Safety Dance,” by Men Without Hats
• Part 16: The Fellowship of the Ring, by J. R. R. Tolkien
• Part 24 : “The Chipmunk Song,” by The Chipmunks
• Part 55: The Quiet Man (1952)
• Part 62: “All My Exes Live In Texas,” by George Strait.
• Part 70: “Wannabe,” by the Spice Girls.
• Part 72: “You Shook Me All Night Long,” by AC/DC.
• Part 81: “Ascot Gavotte,” from My Fair Lady
• Part 82: “Sharp Dressed Man,” by ZZ Top.
• Part 86: “I Could Have Danced All Night,” from My Fair Lady.

There exists $\exists$:

• Part 10: “Unanswered Prayers,” by Garth Brooks
• Part 15: “Stand by Your Man,” by Tammy Wynette (also from The Blues Brothers)
• Part 36: Hamlet, by William Shakespeare
• Part 57: “Let It Go,” by Idina Menzel and from Frozen (2013)

Existence and uniqueness:

• Part 14: “Girls Just Want To Have Fun,” by Cyndi Lauper
• Part 20: “All I Want for Christmas Is You,” by Mariah Carey
• Part 23: “All I Want for Christmas Is My Two Front Teeth,” covered by The Chipmunks
• Part 29: “You’re The One That I Want,” from Grease
• Part 30: “Only You,” by The Platters
• Part 35: “Hound Dog,” by Elvis Presley
• Part 73: “Dust In The Wind,” by Kansas.
• Part 75: “Happy Together,” by The Turtles.
• Part 77: “All She Wants To Do Is Dance,” by Don Henley.
• Part 90: “All You Need Is Love,” by The Beatles.

DeMorgan’s Laws:

• Part 5: “Never Gonna Give You Up,” by Rick Astley
• Part 28: “We’re Breaking Free,” from High School Musical (2006)

Simple nested predicates:

• Part 6: “Everybody Loves Somebody Sometime,” by Dean Martin
• Part 25: “Every Valley Shall Be Exalted,” from Handel’s Messiah
• Part 33: “Heartache Tonight,” by The Eagles
• Part 38: “Everybody Needs Somebody To Love,” by Wilson Pickett and covered in The Blues Brothers (1980)
• Part 46: “Mean,” by Taylor Swift
• Part 56: “Turn! Turn! Turn!” by The Byrds
• Part 63: P. T. Barnum.
• Part 64: Abraham Lincoln.
• Part 66: “Somewhere,” from West Side Story.
• Part 71: “Hold On,” by Wilson Philips.
• Part 80: Liverpool FC.
• Part 84: “If You Leave,” by OMD.

Maximum or minimum of a function:

• Part 12: “For the First Time in Forever,” by Kristen Bell and Idina Menzel and from Frozen (2013)
• Part 19: “Tennessee Christmas,” by Amy Grant
• Part 22: “The Most Wonderful Time of the Year,” by Andy Williams
• Part 48: “I Got The Boy,” by Jana Kramer
• Part 60: “I Loved Her First,” by Heartland
• Part 92: “Anything You Can Do,” from Annie Get Your Gun.

Somewhat complicated examples:

• Part 11 : “Friends in Low Places,” by Garth Brooks
• Part 27 : “There is a Castle on a Cloud,” from Les Miserables
• Part 41: Winston Churchill
• Part 44: Casablanca (1942)
• Part 51: “Everybody Wants to Rule the World,” by Tears For Fears
• Part 58: “Fifteen,” by Taylor Swift
• Part 59: “We Are Never Ever Getting Back Together,” by Taylor Swift
• Part 61: “Style,” by Taylor Swift
• Part 67: “When I Think Of You,” by Janet Jackson.
• Part 78: “Nothing’s Gonna Stop Us Now,” by Starship.
• Part 89: “No One Is Alone,” from Into The Woods.

Fairly complicated examples:

• Part 17 : Richard Nixon
• Part 47: “Homegrown,” by Zac Brown Band
• Part 52: “If Ever You’re In My Arms Again,” by Peabo Bryson
• Part 83: “Something Good,” from The Sound of Music.
• Part 85: “Joy To The World,” by Three Dog Night.
• Part 88: “Like A Rolling Stone,” by Bob Dylan.
• Part 91: “Into the Fire,” from The Scarlet Pimpernel.

Really complicated examples:

• Part 18: “Sleigh Ride,” covered by Pentatonix
• Part 26: “All the Gold in California,” by the Gatlin Brothers
• Part 40: “One of These Things Is Not Like the Others,” from Sesame Street
• Part 42: “Take It Easy,” by The Eagles

# Lessons from teaching gifted elementary school students (Part 8a)

Every so often, I’ll informally teach a class of gifted elementary-school students. I greatly enjoy interacting with them, and I especially enjoy the questions they pose. Often these children pose questions that no one else will think about, and answering these questions requires a surprisingly depth of mathematical knowledge.

Here’s a question I once received, in the students’ original handwriting:

Here’s the explanation that my students told me (but didn’t write down): they wanted me to add adjacent numbers on the bottom row to produce the number on the next row, building upward until I reached the apex of the triangle. For example, the lower-left portion of the triangle would build like this (since 1+4=5, 4+9=13, 9+16=25, etc.):

56

18   38

5    13    25

1     4     9     16

Then, after I reached the top number, they wanted me to take the square root of that number. (Originally, they wanted me to first multiply by 80 before taking the square root, but evidently they decided to take it easy on me.)

And, just to see if I could do it, they wanted me to do all of this without using a calculator. But they were nice and allowed me to use pencil and paper.

And I produced the answer in less than five minutes.

I’ll reveal how I got the answer so quickly in this series. In the meantime, I’ll leave a thought bubble if you’d like to think about it on your own.


text:
# Evaluating $\int_{-20}^{20}\sqrt{2+t^2}\,dt$

I have this integral: $$\int_{-20}^{20}\sqrt{2+t^2}\,dt$$

I tried solving it many times but without success.

The end result is this: $$2\left( 10\sqrt{402}+\mathop{\mathrm{arcsinh}}(10\sqrt{2})\right).$$

I can't seem to get this end result. I got a few wrong ones but cant find this one. Perhaps it's wrong? Could anyone confirm it?

I tried Sage, and it calculates it correctly, but not with steps.

-
You do not "solve" integrals, but rather "evaluate" them. –  Argon May 21 '12 at 16:49
Did you try the substitution $t= \sqrt{2} \sinh(x)$? –  Fabian May 21 '12 at 16:55
Have a look the example too .math.stackexchange.com/questions/120981/… –  Mathlover May 21 '12 at 18:01

Another way integrate $\sqrt{2 + t^2}$ is to use the Euler substitution $u = \sqrt{2+t^2} + t$. Subtracting $t$ and squaring gives $t = \frac{1}{2}(u - \frac{2}{u})$. This implies

$$\sqrt{2+t^2} = u - t = \frac{1}{2}(u + \frac{2}{u})$$

and

$$dt = \frac{1}{2}(1 + \frac{2}{u^2})\,du$$

Thus \begin{align*} \int \sqrt{2+t^2}\,dt &= \int \frac{1}{4}(u + \frac{4}{u} + \frac{4}{u^3})\,du \\ &= \frac{1}{8}u^2 - \frac{1}{2u^2} + \ln{|u|} + C \\ &= \frac{1}{8}(u - \frac{2}{u})(u + \frac{2}{u}) + \ln{|u|} + C \\ &= \frac{1}{2}t\sqrt{2 + t^2} + \ln(t + \sqrt{2 + t^2}) + C \end{align*}

Applying this antiderivative to your integral, you get $$20\sqrt{402} + \ln(20 + \sqrt{402}) - \ln(-20 + \sqrt{402}) = 2(10\sqrt{402} + \ln(10\sqrt{2} + \sqrt{201}))$$

You can check that $\ln(10\sqrt{2} + \sqrt{201}) = \operatorname{arcsinh}(10\sqrt{2})$ so that this solution is the same as the one in your question.

-

While I was writting this answer, Artem posted his. My answer is essentially his 1st one.

Let $f(t)=\sqrt{2+t^{2}}$. Since $f(-t)=$ $f(t)$, we have

$$\begin{equation*} I=\int_{-20}^{20}\sqrt{2+t^{2}}dt=2\int_{0}^{20}\sqrt{2+t^{2}}dt \end{equation*}$$

As the integrand $f(t)$ is a quadratic irrational we can also use the following Euler substitution $$\begin{eqnarray*} x &=&\sqrt{2+t^{2}}-t\Leftrightarrow t=\frac{2-x^{2}}{2x}\Leftrightarrow \sqrt{2+t^{2}}=\frac{2+x^{2}}{2x} \\ dt &=&-\frac{2+x^{2}}{2x^{2}}dx, \end{eqnarray*}$$ which transforms the integrand into a rational fraction in $x$ $$\begin{eqnarray*} \int \sqrt{2+t^{2}}dt &=&\int \frac{2+x^{2}}{2x}\left( -\frac{2+x^{2}}{2x^{2} }\right) dx \\ &=&-\int \frac{1}{x}+\frac{1}{x^{3}}+\frac{x}{4}dx \\ &=&-\left( \ln \left\vert x\right\vert -\frac{1}{2x^{2}}+\frac{x^{2}}{8} \right) +C. \end{eqnarray*}$$ The limits of integration of $I/2$ are $$\begin{eqnarray*} t &=&0,x=\sqrt{2} \\ t &=&20,x=\sqrt{2+20^{2}}-20=\sqrt{402}-20. \end{eqnarray*}$$ Thus $$\begin{eqnarray*} I &=&\left. -2\left( \ln \left\vert x\right\vert -\frac{1}{2x^{2}}+\frac{ x^{2}}{8}\right) \right\vert _{\sqrt{2}}^{\sqrt{402}-20} \\ &=&2\ln \left( \frac{\sqrt{2}}{\sqrt{402}-20}\right) +\frac{1}{\left( \sqrt{ 402}-20\right) ^{2}}-\frac{\left( \sqrt{402}-20\right) ^{2}}{4}+\frac{1}{2}. \end{eqnarray*}$$

-

The typical way to start dealing with an integral that has $\sqrt{a^2+t^2}$ (in your case, $a=\sqrt{2}$) is to use a trigonometric substitution or a hyperbolic substitution.

If we use hyperbolic substitution, we want to use the fact that $$1 + \sinh^2 z = \cosh^2 z.$$ Set $t=\sqrt{2}\sinh z$. Then $$\sqrt{2 + t^2} = \sqrt{2 + 2\sinh^2z} = \sqrt{2(1+\sinh^2 z)} = \sqrt{2\cosh^2 z} = \sqrt{2}\cosh z.$$ Also, if $t=\sqrt{2}\sinh z$, then $dt =\sqrt{2}\cosh z\,dz$. Therefore, $$\int\sqrt{2+t^2}\,dt = \int \sqrt{2}\cosh z \sqrt{2}\cosh z\,dz = 2\int\cosh^2 z\,dz.$$ Now we need to solve the integral of $\cosh^2 z$. We can do this by parts, similarly to how we solve the integral of $\cos^2t$. Let $u=\cosh z$, $dv=\cosh z\,dz$. Then $du=\sinh z\,dz$, $v=\sinh z$, so \begin{align*} \int\cosh^2 z\,dz &= \cosh z\sinh z - \int \sinh^2z\,dz\\ &= \cosh z \sinh z - \int(cosh^2z - 1)\,dz\\ &= \cosh z\sinh z +z - \int\cosh^2z\,dz. \end{align*} Hence \begin{align*} \int\cosh^2z\,dz &= z + \cosh z\sinh z - \int\cosh^2z\,dz\\ 2\int\cosh^2z\,dz &= z+ \cosh z\sinh z + C\\ \int\cosh^2 z\,dz &= \frac{1}{2}z + \frac{1}{2}\cosh z\sinh z + C. \end{align*} Then to get it back into a function of $t$ we remember that $t=\sqrt{2}\sinh z$, so $\sinh z = \frac{\sqrt{2}}{2}t$. Then $z= \mathop{\mathrm{arcsinh}}\left(\frac{\sqrt{2}}{2}t\right)$, and $$\sinh z\cosh z = \sinh z \sqrt{1+\sinh^2z} = \frac{\sqrt{2}}{2}t\sqrt{1 + \frac{1}{2}t^2} = \frac{1}{2}\sqrt{2+t^2}.$$ Therefore, $$\int\sqrt{2+t^2}\,dt = 2\int\cosh^2z\,dz = 2\mathop{\mathrm{arcsinh}}\left(\frac{\sqrt{2}}{2}t\right) + \sqrt{2+t^2}+C.$$ Now plugging into the definite integral gives you a solution.

If we use trigonometric substitutions, we want to use the fact that $$1 + \tan^2 \theta = \sec^2\theta$$ Set $t=\sqrt{2}\tan\theta$, with $-\frac{\pi}{2} \lt \theta\lt\frac{\pi}{2}$. Then $$\sqrt{2+t^2} = \sqrt{2+2\tan^2\theta} = \sqrt{2}\sqrt{1+\tan^2\theta} = \sqrt{2}\sqrt{\sec^2\theta} = \sqrt{2}|\sec\theta|.$$ Since $\sec\theta\gt 0$ on $-\frac{\pi}{2}\lt \theta\lt \frac{\pi}{2}$, we get that $\sqrt{2+t^2} = \sqrt{2}\sec\theta$.

Also, if $t=\sqrt{2}\tan\theta$, then $dt = \sqrt{2}\sec^2\theta\,d\theta$. Therefore, $$\int\sqrt{2+t^2}\,dt = \int \sqrt{2}\sec\theta\sqrt{2}\sec^2\theta\,d\theta = 2\int\sec^3\theta\,d\theta.$$

So we need to find $\int\sec^3\theta\,d\theta = \int\frac{1}{\cos^3\theta}\,d\theta$.

This can be done any number of ways. Using integration by parts, we get $$\int\frac{d\theta}{\cos^3\theta} = \frac{1}{2}\tan\theta + \frac{1}{2}\int\frac{d\theta}{\cos\theta}.$$ And $$\int\frac{d\theta}{\cos\theta} = \int\sec\theta\,d\theta = \ln|\sec\theta + \tan\theta|+C.$$ Thus, we get that $$\int\sqrt{2+t^2}\,dt = \tan\theta + \ln|\sec\theta+\tan\theta|+C.$$ To change it into a formula using $t$, we use the fact that $t=\sqrt{2}\tan\theta$. Therefore, $\tan\theta = \frac{\sqrt{2}}{2}t$; and $$\sec\theta = \sqrt{1 + \tan^2\theta} = \sqrt{1 + \frac{t^2}{2}} = \frac{\sqrt{2}}{2}\sqrt{2+t^2}.$$ Plugging in and evaluating gives the desired result.

-

Here are two more ways to calculate $\int \sqrt{a^2+x^2}\ dx$.

1. Let us make the substitution $\sqrt{a^2+x^2}=t-x$. After squaring, $a^2=t^2-2xt$, from which $$x=\frac{t^2-a^2}{2t}\,.$$ Using the last expression, one finds $$\sqrt{a^2+x^2}=t-x=\frac{t^2+a^2}{2t}\,,$$ and $$dx=\frac{t^2+a^2}{2t^2}dt.$$ Plugging everything into the integral, $$\frac 14\int\left(\frac{2a^2}{t}+t+\frac{a^4}{t^3}\right)dt=\frac{a^2}{2}\ln t+\frac{t^4-a^4}{8t^2}+C.$$ Note, that from the above $x\sqrt{a^2+x^2}=\frac{t^4-a^4}{4t^2}$, therefore we obtain finally $$\int\sqrt{a^2+x^2}\,dx=\frac{a^2}{2}\ln(x+\sqrt{a^2+x^2})+\frac{1}{2}x\sqrt{a^2+x^2}+C.$$
2. Consider the integration by parts: $$u=\sqrt{a^2+x^2},\quad v=x,\quad du=\frac{x}{\sqrt{x^2+a^2}}.$$ Therefore, $$\int\sqrt{x^2+a^2}\,dx=x\sqrt{a^2+x^2}-\int\frac{x^2dx}{\sqrt{a^2+x^2}}=\\ x\sqrt{a^2+x^2}-\int\frac{x^2+a^2-a^2 dx}{\sqrt{a^2+x^2}}=\\x\sqrt{a^2+x^2}-\int\sqrt{a^2+x^2}\,dx+\int\frac{a^2dx}{\sqrt{a^2+x^2}}.$$ It is known (and can easily be found with the variable change from my point 1) that $$\int\frac{dx}{\sqrt{a^2+x^2}}=\ln(x+\sqrt{a^2+x^2})+C,$$ hence, finally, $$\int\sqrt{a^2+x^2}\,dx=\frac{a^2}{2}\ln(x+\sqrt{a^2+x^2})+\frac{1}{2}x\sqrt{a^2+x^2}+C.$$
-