King_George's blog

By King_George, history, 4 weeks ago, In English,

Just several hours ago, JSOI2017(the selection contest in my province) ended, and I ended up with rank 5. Finally, I could go to NOI(Chinese National Olympiad of Informatics, more details can be found here), which will be held in July. Although rank 5 is pretty good, there's still a wide gap between top 4 and me(congrats to the top 4 who may get a 5-point bonus in NOI). This means I have to learn more and train harder, so here comes the post. In this post, I'm gonna record my daily training and contests during the last two and a half months. I hope keeping updating will push me to train harder and also improve my English in the same time. The problems mentioned here may be easier than those mentioned in matthew99's and Petr's blog, but I'll do my best to make this post great. Hope you may like it. :)

Codeforces Round #411 will start in less than one hour. I'll make my first record after it. Wish everyone good luck.

My performance in the contest was a complete flop. I was too sleepy to code problem C and D, though they were not too difficult. I was exhausted after the two-day provincial-team-selecting contest. Maybe all I need now is just a good rest. I will solve the problems left in the contest after that and share with you later.

May 6th

I solved problem B of Petr Mitrichev Contest 1. The problem is not too difficult. The key is that if we know the value of A(1, j) and A(i, 1), then we can calculate all A(i, j). Then the problem becomes whether there exists some values of A(1, j) and A(i, 1) such that all A(i, j) is between 0 and 1. For two elements A(i, 1) and A(1, j), we have some limits that it's impossible for A(i, 1) = x and A(1, j) = y simultaneously. So the problem becomes a 2-SAT.

In the evening, I took part in Atcoder Grand Contest 014, which was another flop to me. The problems are a little bit easier than usual, and there was a data structure problem. However, I still just solved 4 problems. I couldn't focus when coding, and as a result I made some stupid mistakes when coding C and D. I tried to solve problem E after that, and my performance on E was just shit. After having an idea, I hurried to code. Still, I made a lot of mistakes when coding, and couldn't accept it in time. After the contest, I tried a lot of times before accepting it. I found that both my ideas and implementation were wrong. As a Chinese OIer, I couldn't solve this data structure problem. What a shame!

After JSOI and AGC014, I noticed that I'm now having a big problem of coding. I always made some small mistakes such as typo when coding, and often need a lot of debugging to get accept. I should try to focus on my code when coding, and train more problems which are difficult to implement. Have you once had the same problem? And how do you avoid making stupid mistakes when coding?

May 7th

I took part in topcoder SRM714 and codeforces #412, and plan to solve left problems several days later.

May 8th

May 9th

I solved problems from APIO2014. They are much easier than those of last year. 'Beads and wires' is the most interesting one I think. First, you need to find how the blue wires will be like. When choosing a root, all blue wires will consist of the parent of parent, the parent and the node. This can be done by dp. I spent some time on coding. My code was pretty long and ugly. Some part of my code is almost the same, and it appears again and again slightly different every time. I'm wondering if there's some efficient way to code tree-dp problems, where you need to store the maximum and second maximum of four or more dp values.

May 10th

I tried to solve UOJ204 Boat from APIO2016. It's a dp problem. First you need to discretize the number of boats, and then do a interval dp. My dp status is dp[i][j][k], which means till the i-th school, there're k schools sending x boats, where x lies in the j-th interval. I think it's a little bit tricky to use the status k, as there're C(B, k) / k! ways choosing k numbers from the j-th interval(B is the total number of numbers in the j-th interval). Using prefix sums, it can be done in O(N3). However it got time limited exceeded. I squeezed my code for some times, and it still couldn't pass the fourth subtask. I saw some other submissions with similar complexity passes, and matthew99 solved it with FFT. Maybe I'll think about it later.

APIO2017(China Region) event will begin tomorrow. I'll go to Beijing tomorrow morning. Wish everyone who is gonna to join it good luck.

May 11th

Arrived in Beijing. I solved UOJ110 Bali Sculptures and CF773D Perishable Roads, and thought about the other two problems from APIO2015. Among these problems, I thought UOJ111 Jakarta Skyscrapers is the most interesting one. First, you can come up with a pretty straightforward solution, dijkstra. Next, you need to use the small-big trick. For a doge with a large p value, just add edges to all skyscrapers it can reach, as the number of edges is n / p. For every skyscraper, build some new nodes v1, v2, ..., vp. Then, you just need to add edges between neighbouring skyscrapers for small p. Adding edges only between neighbouring vertexes, I pretty like this trick. Sometimes, changing your graph a little bit, maybe there comes a correct solution.

May 12th

Participated in Codeforces Round #413. My performance was good, but still not perfect. After solving the first four problems, I opened problem E. Came up with a straightforward solution which required treap. Then looked at standings, few people solved it, so just began to code immediately. Made some mistakes both in treap and main part, but avoided FST. I should think twice before coding next time. From this contest and AGC014, I found that I'm now having a big problem of coding. Spent too much time on data structures, and had some unsuccessful tries in both rounds. I should keep pressure on coding and keep solving data structures problems in my following training.

May 13th

Participated in APIO2017.

May 14th

Participated in THUPC(THU programming contest). It was a ACM contest hosted by THU. There were 11 problems. My team ranked 22. We didn't communicate too well, so we had a lot of penalty time. I'm gonna share with you the two problems I solved, H and G. I don't know if there is a place to submit and solve problems after the contest.

Problem H can be solved in either O(NlogN) or O(NlogNlogN). There was a method using persistent segment tree and binary search. However the constant was too big, after squeezing my code for a long time, I still couldn't pass it. Then I used divide and conquer and BIT. The constant decreased a lot. We finally passed it.

Problem D was easy but interesting. You're given a undirected graph, where the degree of each vertex is at most 7. You need colour it with four colours, so that there's at most one neighbouring vertex of the same colour for each vertex, or say it's impossible. Can you guys solve it?

May 15th

Back to Nanjing.

Solved Problem E of RCC Elimination Round with an O(N2) algorithm. Here's my method, which is different with the one mentioned in the editorial. When finding minSubsequence of an Array, we can iterate i from n(array length) to 1, and maintain the position of beginning elements of minSubsequence for every l(1 <  = l <  = K). For each i, we compare the two subsequences with length l starting at j(i < j <  = n) and i. The one starting from i consists of a[i] and the subsequence with length l - 1 starting at j(i < j <  = n). As this subsequence won't be larger than the one with length l starting at j(i < j <  = n), we just need to compare a[i] and a[j]. It works in O(N2). Then we join two subsequnces A and B. My way is to use two pointer i and j. If A[i]! = B[j], choose the smaller one. If A[i] = B[j], using some if-else to update the answer. Joining two subsequences costs O(N), and there'll be O(N) joins, so the total complexity is also O(N2).

Now let me share with you problem D I mentioned yesterday. In the contest, I tried to use some way to construct the answer but failed. Then I submitted a code with a little randomization, and it passed! Here is my solution. Colouring the vertexes in the order of decreasing of the degree of vertexes. For one vertex u, find a coluor c, which appears fewest times in the neighbouring vertexes of u. If there's more than one colour, random pick one. As the degree of a vertex is at most 7, there'll be at most one node v, which might become illegal after color u. If v is illegal, the we run this colouring method again to v. I was surprised that it accepted. After the contest, I knew why it works. As the degree of a vertex is at most 7, it can always be coloured by a colour c. So there's always a solution. For each vertex u, it will be recoloured limited times.

May 16th

May 17th

Solved B, C, G, H, I from Petr Mitrichev Contest 3. Problem B and C are easy. G requires some coding, and you need to squeeze your code a little bit. H requires both some thinking and coding. I like the trick to find the k-th minimal/maximal element. If we sort a in non increasing order. Let's say the maximum number you choose is product of a[p[1]], a[p[2]], ..., a[p[m]], the next number less than it will be one of a[p[1] + 1] * a[p[2]] * ... * a[p[n]], a[p[1]] * a[p[2] + 1] * ... * a[p[n]], ..., a[p[1]] * a[p[2]] * ... * a[p[n] + 1]. Similar problem can be also found here. For negative numbers, you just need to keep the maximum number for each amount of negative numbers.

I can be solved by dp. I stuck on it for a while. I first came up with a wrong dp solution, which may TLE if the output is correct. And then optimized if for a while, submitted and just got a WA. Here's my dp solution, can you see where's wrong? Using dp[l][r] presents the expected time needed to type correctly [l, r]. I transformed my dp like this, iterating the last time checked back, say k, dp[l][r] = dp[l][k] + r - k + t + sigma{(dp[i][r] + r - i + 1) * P}, where P is the probability making the first typo at position i(k < i <  = r). Almost every time, when there's a dp problem in the contest, I couldn't solve it. From NOIP2016 to JSOI2017, I only solved one dp problem where the main part is suffix array. I plan to solve more dp problems on topcoder to improve my dp skills.

When in contest, I had less time on dp problems. If you thought for a long time on a dp problem, and came up with nothing, you just wasted a lot of time. I'd fill pretty stressful in that situation and sometimes massed up everything. How do you guys balancing time, thinking full score solution of the dp problem, and coding partial score. I always couldn't find a good strategy.

Beside the gym, I solved CF794F and thought about E in the same contest. F is a nice problem for practising segment tree and lazy tags. Solved UOJ276. I made a mistake when coding. I forgot to update the answer from paths between the centroid and another vertex.

May 18th

Solved some problems from NOI2016D1, Yandex Round 1 and RCC Elimination Round.

For problem I I mentioned yesterday, the transformation of my dp function was wrong. When updating dp[l][r], after finding the first typo at position i, one might not check at position r again. So it's not dp[i][r]. The expected solution is to use dp[i] represents the minimum expected time to type all characters from [i, n].

May 19th

Learned some linear algebra. Math is always my weak point. Solved NEERC16 M.

Tomorrow I'll leave Nanjing to Beijing again for THUSC(THU Summer Camp).

May 20th

Arrived in Beijing. Solved UOJ207. Learned how to maintain sum of subtrees in LCT. For esch node, record one value for the sum of the subtree and another value for the sum of the light-children's subtrees.

Tomorrow is THUSC. Wish everyone good luck.

May 21th

Participated in THUSC2017 D1. My performance was shit. I underestimated the score most participants may get, and just coded some brute force and did nothing more. I wasn't in a good status in the whole contest after a long rest. There's little hope to be signed now. I should take this failure as a motivation. Train harder, and hope to be in best condition in NOI2017. If I fail in NOI again, I'll have no university to study in and have to be a farmer. GG.

Read more »

  • Vote: I like it  
  • +207
  • Vote: I do not like it  

By King_George, history, 8 months ago, In English,

Help! When using a lower_bound or upper_bound on a set say s lower_bound(s.begin(),s.end(),key); is much slower than s.lower_bound(key); Why does this happen?

20301681 gets a tle on 343D while after switching it into s.upper_bound(key) gets an ac 20661439

Can anyone tell me why?

Read more »

  • Vote: I like it  
  • -6
  • Vote: I do not like it