### hanfei19910905's blog

By hanfei19910905, 10 years ago,

Qualification Round 1

Just sort. Notice 0 in the array.

Choose the 3 and 1 as much as possible. And let 2 combine with themselves. If there are more 1s and 2s, let two 1s combine with 2, and every four 1s take same taxi.

Implement with stack. If the string begin with '/', let top = 0, else remain the top; Then process the substring one by one, when meeting ".." , top--; else remain the top;

The number of new regular polygon's edges must be the factor of the given polygon. Listing all the factors take O(sqrt(n)) time. Then choose the best point take O(n). So the time complexity is O(n*sqrt(n)).

It's a classic DP problem. Array dp[i][j] stands for the min rightmost endpoint when choosing at most j segments from the first i segments . dp[i][j] =dp[i][j] = min(dp[i-1][j-1], max(dp[i-1][j],left[i])+length[i]). When the dp array is completed , find the max value of left[i+1]-dp[i][k] and rightmost point — dp[n][k]. Totally take O(n*n).

Qualification Round 2

Compare every two records and find the right friends. Give every name a unique number so as to avoid counting same friend twice. If a and b is friends, let friend[a][b] = true.

Establish two hash tables counting the number of the size (say 2) exiting in set makers and set caps. Obviously the sum of min number of every size in two sets is the first answer. Similarly establish two hash tables in order to count the number of the same size and same color. The hash function can be hash(color, size) = color*1000+size.

Because the length of string is at most 100*2000, so we can build 26 line-segment-trees to count the 26 Latin letters. The way to build tree and find the position of K-th letter is quite simple if you under stand line-segment-tree :)

A dp method is really great~ , sum[i] stands for the number of palindrome string in the first i letters. palindrome[i][j] judges weather the substring i...j is a palindrome string. dp[i] is the answer for the first i letters. dp[i] = dp[i-1]+Sum( palindrome[j][i]*sum[j-1] ) for all j<=i && j>0 . sum[i] = sum[i-1]+Sum(palindrome[j][i]) for all j<=i.

sort the array with compare condition (cube[i].color < cube[j].color ||(cube[i].color==cube[j].color && cube[i].size>cube[j].size)). Then for the first i cubes , there is a array Max_cube, Max_cube[j] records the max sum of j cubes' size with same color. To the cube i+1, if it's the k-th largest size of its color. Compare the answer with cube[i+1].size + max(Max_cube[k],Max_cube[k+1],Max_cube[k-1]). The time complexity is O(n*logn).

Forgive my poor English :)

gl and hf tonight!

• +39

 » 10 years ago, # |   +3 In 159D - Palindrome pairs, if you know a method to find all the subpalindromes fast, you can get a better than O(L^2) solution: Make two Segment Trees for counting the starts and the ends of palindromes. If a palindrome(for example, odd) has center at position K and maximum length 2 * D + 1, then: 1 palindrome starts in K and ends in K, 1 starts in K — 1 and ends in K + 1, ..., last starts in K — D and ends in K + D. So, for adding their ends and starts in O(log L), we use segment updating. What is the answer on the task? It's just a sum: for all K = 1, 2.., L — 1 we multiply the number of palindromes, that ended in K(exactly), and the number of palindromes starting later, i.e. st[K + 1] + st[K + 2] + ... + st[L]. Each number we can get in O(log L), using ST.
•  » » 10 years ago, # ^ |   0 Yeah, it's a better solution. And it seems that suffix array can work well in finding all palindromes , but i'm not good at it :( .
•  » » 10 years ago, # ^ | ← Rev. 2 →   0 There is O(n) solution. There is way to find palindromes is O(n) using Z-function-like algorithm. And we can to perform all queries to segment trees offline. First preprocess all Add queries for O(n), and then answer all Sum queries.
•  » » » 5 years ago, # ^ |   +1 can you please explain your approach how this Z-function works here? it will be really helpful !
•  » » » » 5 years ago, # ^ |   +1 I can't remember what talk about 6 years ago. There is original article in Russian http://e-maxx.ru/algo/palindromes_count You can translate it using machine translation, but I think this transation isn't good https://translate.google.ru/translate?sl=ru&tl=en&js=y&prev=_t&hl=ru&ie=UTF-8&u=http%3A%2F%2Fe-maxx.ru%2Falgo%2Fpalindromes_count&edit-text=&act=url There was project far transalting site "e-maxx.ru" in english try to google it
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 thanks a ton for this !!though it make little difference in this problem, but it is good!
 » 10 years ago, # | ← Rev. 2 →   0 I am quite new to sport programming so I have never implemented a segment tree. I heard about it, though, but thought it was complicated. Anyway, I think my solution to 159C - String Manipulation 1.0 is quite neat :)In short: binary search in a Fenwick tree.Slightly longer: we start out with 26 arrays, all filled with 1's and having a length of k*repeats[c], where repeats is an array containing the number of occurrences of each character in the initial string. Then, we build a Fenwick tree on top of each of these arrays. After that, we start processing the request. For each request p_i, c_i, we perform a binary search in the corresponding Fenwick tree in order to find the leftmost position with p_i 1's before it. Then, we replace the 1 in that position with a 0. Each search takes O(log(k*repeats[c_i])) queries to the Fenwick tree, each being of O(log(k*repeats[c_i])) complexity, which yields O(log^2(k*repeats[c_i])) per each request. The entire complexity of the algorithm is O(n*log^2(k*|s|)).After processing all requests, we extract the result by merely moving through the input string k times, each time either printing the corresponding character (if there's a 1 in its array) or omitting it.
•  » » 7 years ago, # ^ |   0 I also use this method. It really works. This is my code. 12708008
•  » » » 23 months ago, # ^ |   0 thank you for your source code, but could you please explain this part : (i dont really understand why you update the tree with 1)for ( int i = 0 ; i<26 ; ++i ) { int veSize = ve[i].size(); for ( int j = 1 ; j<=veSize ; ++j ) { tree[i].update(j,1); } } thanks :)
 » 10 years ago, # |   0 I was trying a tree solution for C, but was getting wrong answers and eventually decided to make a solution that supposedly took advantage of the fact that the string is cyclic. Yet in reality, I think it can easily become a solution that needs O(sqrt(|ss|)) time to process each command. (Where ss is s repeated k times) (Currently it is O(|s| + k ). There are initially k fragments of the ss string what you could do is for each of the k fragments, ad each letter, know the number of times the letter appears in the fragment and the positions of those appearances.Now, in order to delete the P-th instance of a letter in the overall string (ss), you can first do a O(|k|) loop to find the fragment that has the p-th instance (Use the sums for each fragment instead of going through the letters in the fragment manually). After you find the fragment, you can use a O(|s|) loop to naively remove the [p — (sum of the letter counts of previous fragments) ]-th instance of the letter in the fragment.This only looks like abusing the format of the string, because you can adapt it to work in O(sqrt(|s|)) time for any string (not just cyclic). So, let's say that ss has |ss| elements, you can always split it into O(sqrt|ss|) fragments of O(sqrt|ss|) letters each. The overall complexity would become O(sqrt|ss|) per step. The constraints make this good enough.
 » 10 years ago, # |   0 I am trying understand the 158E Phone calls solution but it seems a little complicated for me. In my little experience with dp I haven't found a problem like this. Could you explain the solution in more detail? Please!
•  » » 10 years ago, # ^ | ← Rev. 3 →   0 Suppose we processed the first i calls and j of those were ignored, the best way is to minimize the last minute of conversation (i.e. maximize the length of freetime until the current moment). It's the meaning of dp[i][j]. If you still can't get it, feel free to point out what you are confused :)
•  » » » 10 years ago, # ^ | ← Rev. 3 →   0 Problem is, topicstarter's formula for dp[i][j] is wrong. It should be:dp[i][j] = min(dp[i-1][j-1], max(dp[i-1][j],left[i])+length[i]), notdp[i][j] = min(dp[i-1][j], max(dp[i-1][j-1],left[i])+length[i])Here is my submission with this solution: 1355912.
•  » » » » 10 years ago, # ^ |   0 In my opinion, understanding its meaning is more important. If you know how it work, it isn't difficult to get the correct formula.
•  » » » » » 10 years ago, # ^ |   0 The meaning is pretty straightforward. Suppose that you know, for all previous i's and j's, the least time at which all calls end. You are currently considering whether it is a good idea to add the current call to the ones you omit, or not. This depends on the time all calls are going to end at. If you choose to omit it, you need to look at the time at which i-1 calls ended, and you dropped j-1 of them (because the newly dropped call is going to be the j-th). Otherwise, you're going to look at the time at which i-1 calls ended, out of which j were dropped (since it is always preferable to drop as many calls as possible). Then, you should find the time at which the i-th call is going to end. Since you already know when i-1 calls ended and when the i-th call is supposed to start, you should find the time at which it actually starts — by merely taking a maximum. After that, you just add its length to the time it starts. You are interested in minimizing the time, so you take the minimum.
•  » » » » » » 10 years ago, # ^ |   0 Thanks for your replies! I was out for a day and I was unable to reply. Already understand the solution.I am used to solve DP problems with top down strategy using recursion since it's easier to me to understand the solution.I know that recursion is expensive and it should be avoided when possible so I am trying to change my strategy.Thanks again!
•  » » » » » » 3 years ago, # ^ |   0 Thank you very much that made it very clear, just started learning dp, I would never have got it if you didn't posted this, it's been 7 years, since this post was made, but I wanted to ask a question, how do you form the base case that is what values must be stored initially in the two-d array dp[i][j]? is there a procedure you follow, what do you check or think before you form dp[][] for initial cases. thank you
•  » » » » 10 years ago, # ^ |   0 thx for correcting my mistake :)
• »
»
»
»
»
10 years ago, # ^ |
-18

if somebody can help me here in 158b, my test case 74 is wrong but my code seems to be okk. its in gnu c++ 4.6

# include

using namespace std; int main() { long n,ne,i,count=0,newe,fours=0,three=0,two=0,ones=0; cin>>n; short s[100005]; for(i=0;i<n;i++) { cin>>s[i]; if(s[i]==4) fours+=1; else if(s[i]==3) three+=1; else if(s[i]==2) two+=1; else ones+=1; } count=fours;

count+=three;
if(ones>=three)
ones-=three;
else
ones=0;
newe=two/2;
count+=newe;
two=two%2;
ne=ones/4;
count+=ne;
ones=ones%4;
if(ones==3&&two==1)
{
count+=2;
cout<<count;
}
else if(ones<=2&&two==1)
{
count+=1;
cout<<count;
}
else if(ones<=2&&ones>0&&two==0||(two==1&&ones==0))
{
count+=1;
cout<<count;
}
else
cout<<count;

return(0);
}
 » 9 years ago, # |   0 was somebody able to solve D using python? I implemented the DP solution above but I run out of time in test case 9 and the subsequent ones.On my machine python finds the solution in ~9 seconds (past the time limit).how can I find out if somebody ever solved this problem in Python?
 » 7 years ago, # |   0 This is not tutorial of VK 2015, can some body remove the tag?
 » 6 years ago, # |   0 Here is my Solution for 158D - Ice Sculptures: 15272199 My ans got WA in test case 39. Can anyone help finding my bug.Thanks in advance.
 » 6 years ago, # | ← Rev. 2 →   -15 Thanks for all!
•  » » 6 years ago, # ^ |   0 You output nothing on this test. What is your question?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Thanks for all!
 » 5 years ago, # | ← Rev. 2 →   0 B taxi. wrong answer on 67. can't even see inputs!http://ideone.com/cTEsEx
•  » » 5 years ago, # ^ |   0 Use ideone.com to share code.
•  » » » 5 years ago, # ^ |   0
 » 3 years ago, # |   0 Can someone help me with 158B - Taxi ? I did exactly as this editorial guides, I took the number of 4's and added them to the number of taxis, then I combined the 3's with 1's. Now, either (i) 3's are in excess or (ii) 1's are in excess or (iii) none of the 1's or 3's are left.I combined the 2's with themselves. Now, either (a) an extra 2 is left or (b) isn't. Taking these 6 cases:(i)(a) I added the number of 3's left to the answer and the 2 goes in a seperate taxi.(ii)(a) I added at max two 1's with the 2, and then combined the remaining 1's in groups of fours.(iii)(a) only that last 2 is left, which goes separately.(i)(b) I added the number of 3's left to the answer.(ii)(b) I combined the remaining 1's in groups of four.(iii)(b) nothing is left, everyone has been grouped.It seems to work, but I'm getting a wrong answer on test case 66. (49551813) The test case is too big and isn't shown fully. I can't find where it's wrong. Can someone help?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 I couldn't read the cases, but in a nutshell, all you have to do is this. 4 takes 1 taxi, 3 takes 1 taxi + it can give lift to 1. 2 takes 1 taxi + it can give lift to 2 as well as to 1, 1 can combine into groups of 4 to get taxi. If you want to take a look at my solution here it is : https://codeforces.com/contest/158/submission/50441428
•  » » » 3 years ago, # ^ |   0 Can I do this problem with dynamic programming?
 » 2 years ago, # |   0 Those who are stuck with Problem number 159D - Palindrome pairs  int n=s.length(); for (int i= 0; i< n; i++) palindrome[i][i] = 1; for (int i=0; i
 » 2 years ago, # | ← Rev. 2 →   0 A is definitely not worth being rated as 1800. [old comment, ignore]
•  » » 2 years ago, # ^ |   0 800 u mean?
•  » » » 2 years ago, # ^ |   0 Before rating changes recently, it was rated 1800.
 » 2 years ago, # |   0 158A - Next Roundwhy my code is getting a runtime error on test case 4? res = 0 n,k = map(int,input().split()) l = [int(i) for i in input().split()] kthScore = l[k] if kthScore <=0: print(0) else: for i in l: if i>=kthScore: res+=1 print(res) 
•  » » 21 month(s) ago, # ^ |   0 n, k = map(int, input().split())scores = list(map(int, input().split()))result = 0 max_score = scores[k-1]if max_score < 1: for score in scores: if score > max_score: result += 1 print(result)else: for score in scores: if score >= max_score: result += 1 print(result)
•  » » 20 months ago, # ^ |   0 Same here I think this is not the place for python programmer's This website is more biased on python
 » 23 months ago, # |   0 Hello @hanfei19910905,I see that your tip for problem 158A — Next Round, says Just Sort.But in problem statement it says that:The second line contains n space-separated integers a1, a2, ..., an (0 ≤ ai ≤ 100), where ai is the score earned by the participant who got the i-th place. The given sequence is non-increasing (that is, for all i from 1 to n - 1 the following condition is fulfilled: ai ≥ ai + 1).Since it clearly says that the array is already sorted in decreasing order. ai ≥ ai + 1
•  » » 18 months ago, # ^ |   0 Can you explain this question ..i am cofused
 » 23 months ago, # |   0 where can i get the code for these problems
 » 22 months ago, # |   0 My solution is giving wrong answer on test case 4 of B. Taxi .#include using namespace std; .#define LLI long long int .#define PB push_back .#define VI vector .#define REP(i, n) for(int i=0; i=0; i--) .#define sort(v) sort(v.begin(), v.end()) int main() { int n; cin >> n; VI v; REP (i, n) { int tmp; cin >> tmp; v.PB(tmp); } sort(v); int l = 0, r = n-1; int c = 0; while (l <= r) { if (v[l] + v[r] <= 4) { c++; l++; r--; } else { c++; r--; } } cout << c; return 0; } 
•  » » 19 months ago, # ^ |   0 https://leetcode.com/problems/boats-to-save-people/your soln is for this problem.. not for the problem asked in CF
 » 20 months ago, # |   0 Why there r no one one who uses python to solve problems????
 » 19 months ago, # |   0 I solved problem D using Manacher's Algo and prefix sums. 95691489
»
17 months ago, # |
0

# include

using namespace std;

int main() { int t,arr[100],count=0,k; cin >> t >> k; for(int i=0; i<t; i++) { cin >> arr[i]; if (arr[i] > 0) { if (arr[i] >= arr[k-1]) { count += 1; } }else { continue; } } cout << count; return 0; }

•  » » 13 months ago, # ^ |   0 for(int i=0;i=c && a[i]!=0) coount++; if(a[i]
»
11 months ago, # |
0

hey I don't know if someone will see this but can someone tell me why test case 3 doesn't work. This is the code.

# include

using namespace std;

int main() { int n, k, sum =0; std::cin >> n >> k; for (int i = 0; i < n; i++) { int a; std::cin >> a; if(a>k){ sum += 1; } } std::cout << sum; }

•  » » 11 months ago, # ^ |   0 int val=0; for (int i = 0; i < t; i++) { if (a[i] >= a[k-1] and a[i] != 0) { val++; } }take inputs in an array, a[i] >= a[k-1] and a[i]!=0 are the only 2 conditions reqd
 » 11 months ago, # |   0 It's possible to solve 158A — Next Round in linear time and constant space.My code in C++ is as follows: #include int main() { unsigned short n, k; std::cin >> n; std::cin >> k; unsigned short counter = 0, elementK; bool brokeCycle = false; // Cycle once through second line, up to k-th element for (int i=0; i> currentScore; // Check if i-th element is > 0 if (currentScore > 0) // If so, increment counter counter++; else { // If not, break from cycle brokeCycle = true; break; } // Keep track of k-th element if necessary if (i == k-1) elementK = currentScore; } // If first k-elements were positive if (!brokeCycle) { // Cycle through remainder of the second line for (int i=k; i> currentScore; // Check if i-th element is equal to or greater than k-th element if (currentScore > 0 && currentScore >= elementK) // If so, increment counter counter++; else // If not, break from cycle break; } } // Print counter std::cout << counter; } It may be a bit redundant, so feedback is welcome.
 » 10 months ago, # |   0 i = input() j = input() k = int(i[2]) total = 0 n = 1 x = 0 while (x!=1): if(int(j[2*n-2])>=int(j[k-1])): total += 1 n +=1 else: x = 1 print(total)why I receive error like : if(int(j[2*n-2])>=int(j[k-1])): ValueError: invalid literal for int() with base 10: ' 'please help me I want to solve in python programming
»
9 months ago, # |
0

** I'm constantly getting MLE on the following code for 158A; ** can anyone help me out please! I've tried different approaches , and even submitted some of the previous solution (which got accepted verdict) , but for those solutions also, I'm getting MLE; ~~~~~

# include <bits/stdc++.h>

using namespace std;

# define ll long long

int main() { ios_base::sync_with_stdio(false); cin.tie(NULL);

# ifndef ONLINE_JUDGE

freopen("inputf.in","r",stdin); freopen("outputf.out","w",stdout);

# endif //Online judge

//mycodehere! int n,k;cin>>n>>k; int arr[n]; for(int i=0;i<n;i++){ cin>>arr[i]; } int count=0; for(int i=0;i<n;i++){ if(arr[i]>=arr[k] && arr[i]>0){ count++; } } cout << count << "\n"; return 0; } ~~~~~

 » 3 months ago, # |   -9 this is shit in the first example 158A it says:: Input 8 5 10 9 8 7 7 7 5 5 and if the number >= k we add ++ to the counter. and in the main problem it says Contestant who earns a score ((equal to or greater)) than the k-th place finisher's score will advance to the next round. but in the first example the output is 6 not 8 as it should be because 5 >= 5 = true.
»
2 months ago, # |
-11

TAXI SOLUTION

# include <bits/stdc++.h>

using namespace std;

int main(){

int n,c=0,g1=0,g2=0,g3=0,g4=0; cin>>n; int t=n;

while(t--){

int x; cin>>x;

if(x==1)g1+=1; else if(x==2)g2+=1; else if(x==3)g3+=1; else if(x==4)g4+=1; } c+=g4;

c+=min(g1,g3); int cg1=g1,cg3=g3; g3-=min(cg1,cg3); g1=g1-min(cg1,cg3);

c+=g1/4; g1=g1-4*(g1/4);

c+=g2/2; g2=g2-2*(g2/2);

c+=g3;

if(g2==1 ){

if(g1>=2)

c+=g2,g1=g1-2*g2;

else if(g1==1||g1==0) c+=g2,g1=0;

} if(g1>0){ c+=1;

} cout<<c;

}