Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

### redocyz's blog

By redocyz, history, 2 years ago, ,

Just a reminder that Code Jam Round 1C starts in under 7 hours.

Let's discuss the problems here after the contest.

• +53

 » 2 years ago, # |   0 Reminder: 1 more hour
 » 2 years ago, # |   0 GL & HF!
 » 2 years ago, # |   -26 ez
 » 2 years ago, # |   +5 can't submit more and says it ended even though still 30 min
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Maybe this will help, though you are out of time
 » 2 years ago, # |   +5 Why can I sometimes see a "not solved" sign for a hidden test set in the scoreboard?
•  » » 2 years ago, # ^ |   +8 I am guessing that happens when you submit something that pass subtask 1, and then after that submit something that doesn't.
•  » » » 2 years ago, # ^ |   0 Shouldn't they took the last submission that passes the subtask one?
•  » » 2 years ago, # ^ |   0 I have it:) My actions was1) Solve C-small & submit it (this automatically shows pending for C-large)2) Submit my new solution of C-large, but it fails on C-small (this makes "not solved" sign for a hidden test)
•  » » 2 years ago, # ^ |   +5 The rules are a little bit strange.If the last submission passed the visible tests, then this submission will be used in score, and the hidden test set gets a "?". If you submit an additional submission, that doesn't pass the visible tests, then you still get the points for the visible tests from the earlier submission, however you don't get the points from the previous hidden test (even if it would have been successful). Therefore the scoreboard shows a "-".This happened to me in 1B, because I accidentally submitted my solution of the third problem on the page of the first problem. To receive the points for the hidden test case, I had to resubmit my solution of the first problem.
•  » » » 2 years ago, # ^ |   0 Same with me !
 » 2 years ago, # | ← Rev. 2 →   +3 Only I had problem with solving second problem in C++?On local testing my solution didn't get score, because it didn't print the last line. But I printed and problem was in script. I decided to submit on server and got accepted.Solution
•  » » 2 years ago, # ^ |   0 Maybe you needed to cout.flush()?
•  » » » 2 years ago, # ^ |   +6 endl always flushes stream but as I said i had problem only with printing last query in last test. To ensure I added cout.flush in the end of code. But it didn't help.
•  » » 2 years ago, # ^ |   0 I've downloaded your solution and run it locally. It works fine on my laptop:)
•  » » » 2 years ago, # ^ |   0 :( something wrong with my laptop. Do you use windows(like me) or linux?
•  » » » » 2 years ago, # ^ |   0 Ubuntu 16.04 gcc version 5.4.0 20160609
 » 2 years ago, # |   +13 What's the proof for task B?
 » 2 years ago, # |   -14 I hated all the problems in the 3 rounds xD.
•  » » 2 years ago, # ^ |   0 In my opinion, the last one from round1B was the best and I still can't solve it.
 » 2 years ago, # | ← Rev. 2 →   0 Anyone sees why this code gets RTE on problem 1 large? Thanks in advance. Code#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define all(x) (x).begin(), (x).end() #define pb push_back #define xx first #define yy second #define sz(x) (int)(x).size() #define gc getchar #define IO ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define mp make_pair typedef long long ll; typedef unsigned long long ull; typedef long double ld; const double PI=acos(-1); template T getint() { T val=0; char c; bool neg=false; while((c=gc()) && !(c>='0' && c<='9')) { neg|=c=='-'; } do { val=(val*10)+c-'0'; } while((c=gc()) && (c>='0' && c<='9')); return val*(neg?-1:1); } const int MAXN=50001; const int SIGMA=26; struct trie { int id=1; int tree[MAXN][SIGMA]; bool ending[MAXN]; trie() { reset(); } void reset() { memset(tree,0,sizeof tree); memset(ending,0,sizeof ending); } #define HASH(x) ((x)-'A') void insert(string& t) { int akt=1; for(auto i:t) { if(tree[akt][HASH(i)]==0) { tree[akt][HASH(i)]=++id; } akt=tree[akt][HASH(i)]; } ending[akt]=true; } bool query(string &t) { int akt=1; for(auto i:t) { if(tree[akt][HASH(i)]==0) return false; akt=tree[akt][HASH(i)]; } return ending[akt]; } void remove(string& t) { int akt=1; for(auto i:t) { if(tree[akt][HASH(i)]==0) return ; //nincs benne akt=tree[akt][HASH(i)]; } ending[akt]=false; } }; trie ttt; int main() { IO; int T; cin>>T; int cs=1; while(T--) { int n,l; cin>>n>>l; vector t(n); ttt.reset(); for(int i=0;i>t[i]; ttt.insert(t[i]); } set Diff[l]; for(int i=0;i diff[l]; for(int i=0;i curr(l); string akt; for(int i=0;i<=n;++i) { akt.clear(); for(int j=0;j=0;j--) { if(curr[j]==sz(diff[j])) { if(j>0) curr[j-1]++; curr[j]=0; } } } cout<<"Case #"<<(cs++)<<": "<
 » 2 years ago, # |   0 I used LIS for third problem Test Set 1, but got WA. :(
•  » » 2 years ago, # ^ |   0 Same here.
•  » » 2 years ago, # ^ |   +2 Notice that the answer doesn't need to be monotonic. For example 3 10 5 10 Here the answer is to stack the 3 ants.
•  » » » 2 years ago, # ^ |   0 Yes, I know and my code passes this case.
•  » » » » 2 years ago, # ^ |   +5 Your program fails on this case 6 10 3 2 3 2 4 It reports 4 when the real answer is 5. I noticed that you are not covering all cases in your dp because the best answer up to the second number is take both the first and the second, so you will update that entry in the lis table as 2 and never will take into account discarding first number and taking second number onwards.My answer was indeed lis. The entry lis[i] stands for what is the sequence of size i with less weight. At first the table look like this: LIS = {0, oo, oo, oo, ...} Taking 0 elements has weight 0, and taking more than 0 elements has infinite(oo) weight (since we can't do that). I iterate through all numbers from the begining and update the entire table on each iteration. You don't need to store inifinite values explicitely. It works in time because the size this table will not grow over 139 elements. The answer is the size of the table. Watch my code for reference.
•  » » » » » 2 years ago, # ^ |   0 Thank you so much!
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   0 I also used LIS in an attempt to solve the third problem, but I failed.Could you please help debug my code? Thank youhttps://leetcode.com/playground/iu5EuzT3
 » 2 years ago, # |   +12 Wow, solution to C is very clever. It took just few character changes (few n's to 200) to get my solution to small test pass also large test, but I was completely unaware of this during contest.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +11 I decided to write solution for small and then think about large. My solution was basic n^2 LIS-like algorithm (dp[l] = min weight of correct subsequence of length l among current prefix of the array). After thinking I realized that I don't have to change it for large input!The sum of the top k ants' weights grows exponentially (with base 1 + 1/6) and thus the current bottom ant's weight too. Therefore, the maximum sequence length is around log(109, 1 + 1 / 6) ≈ 135. This is pretty ok for final complexity 6 * 10^5 * 135.
•  » » » 2 years ago, # ^ |   0 Solved it by accident as well and was disappointed about it. Task that can be solved by accident doesn't while trying to solve easy subtask doesn't seem a very good one.The concept of task where actual values are much smaller than quick worst case estimate isn't bad but it should have a way of exceeding time or memory limit if not noticed. Like multidimensional array, having interesting states non sequential or requiring some code to quickly handle non interesting cases. Programming language task in round 1B was better at this.I guess it was possible a write a DP with N*N array that wouldn't fit in memory.
•  » » » » 2 years ago, # ^ |   0 Yeah it feels the challenges are much more relaxed now.. and more participants pass than in previous years. Maybe they want to attract more new players.
•  » » » » » 2 years ago, # ^ |   +1 The last subround of round 1 is usually easier. I think it's because all the hard core ones already advanced, and the organizers want to make it more enjoyable for the less experienced crowd.
•  » » » 2 years ago, # ^ |   0 Why is the base is 1 + 1/6 ? I cannot quite understand the explanation of official editorial provided regarding to this problem (the large test)..especially when they said that the length is maximum 139. Any of your further explanation is appreciated :D..thanks in advance
•  » » » » 2 years ago, # ^ |   +1 When You have ants x1,...,xn then xn*6 > x1+...+x(n-1) -> xn > [x1+...+x(n-1)] / 6 -> x1 + ... + xn > x1 + ... + x(n-1) + (x1+...+x(n-1)) * 1/6 = [x1 + ... + x(n-1)] * (1+1/6)
•  » » » » » 2 years ago, # ^ |   0 Thank you for your explanation :D
 » 2 years ago, # | ← Rev. 2 →   +8 I wrote my solution for C small, and unexpectedly it passed C large. I used the approach described for C large in editorial, but I didn't realize that maximum stack height is so low (I stored state in map where keys are stack size and values are min weight for that size). If it was old Code Jam platform, maybe I would not even submit C large and would have lost more points!
 » 2 years ago, # |   0 What's wrong with this approach in A large?For every character at every index store those characters that appear at index + 1, also store all characters at a given index separately, now if there's a character at any given index that its possible subsequent doesn't cover all the possible characters at the index + 1 position, automatically say that any string is the answer with these two subsequent characters changed.
•  » » 2 years ago, # ^ |   +10 aaaa abaa baaa bbaa aaba abba aabb aaabHere at each position all pairs are possible. But e.g. you can choose bbbb.
•  » » » 2 years ago, # ^ | ← Rev. 3 →   0 Perhaps I didn't make my approach clear enough, here's the code which passed that testcase link
•  » » » » 2 years ago, # ^ |   +3 So your code returns "-" but there are many solutions, e.g. BBBB.
•  » » » » » 2 years ago, # ^ |   0 Oh! so there's a solution to that! I assumed you meant that BBBB is a wrong output!Thanks for your feedback.
 » 2 years ago, # |   +25 I get excited often with interactive problems but both interactive problems so far have been boring. This Lollipop problem is more interesting from Mathematical/Theoric point of view than from Algorithmic/Strategy Design point of view.I expect interesting interactive problems in next rounds.
 » 2 years ago, # | ← Rev. 2 →   +3 Problem A passes with randomized solution. Hunch paid off My Code
•  » » 2 years ago, # ^ |   +11 you don't even need randomize, a complete search would pass too as long as you break.
•  » » » 2 years ago, # ^ |   0 Break where exactly? I got a TLE on the hidden set with my complete search solution.
•  » » » » 2 years ago, # ^ |   0 see this. I suspect you repeat searching the same character many times.
•  » » » » » 2 years ago, # ^ |   0 Ah i understand now. I was repeating it for the same character. Thanks.
•  » » » » 2 years ago, # ^ |   0 i also got TLE but when i add one condition that if one solution is already found then we didn't need to call recursive function for any state and got AC.
»
2 years ago, # |
+15

### Scraped scoreboard for all rounds so far in GCJ 2018.

 » 9 days ago, # |   -8 Can someone help me in telling me what's wrong in my solution for C-small for problem 3 of this round ?Below is my solution:- //God's Grace #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define endl '\n' #define f(k,a,b) for(int k=(a);k<(b);k++) #define vi vector #define vvi vector > #define vii vector > #define int long long #define pii pair #define piii pair< pair, ll int > #define fsd fflush(stdout); #define tdef typedef using namespace std; int po2(int a){f(i,1,63){if((1LL)< 1) { // q is quotient int q = a / m; int t = m; // m is remainder now, process same as // Euclid's algo m = a % m, a = t; t = y; // Update y and x y = x - q * y; x = t; } // Make x positive if (x < 0) x += m0; return x; } int dp[(int)1e5+5][2]={}; int32_t main() { int t; cin>>t; f(ii,0,t) { int n; cin>>n; f(j,1,n+1){ cin>>arr[j]; } dp[n][0]=1; dp[n][1]=6*arr[n]; int ans=1; for(int j=n-1;j>=1;j--){ int ma = 1; for(int i=j+1;i<=n;i++){ if(arr[j]<=dp[i][1]){ ma=max(ma,dp[i][0]+1); } } if(ma!=1){ int am = INT_MIN; for(int i=j+1;i<=n;i++){ if(ma==dp[i][0]+1){ am = max(am,dp[i][1]-arr[j]); } } dp[j][0]=ma; dp[j][1] = min(am,6*arr[j]); }else{ dp[j][1] = 6*arr[j]; dp[j][0] = 1; } ans = max(ans,dp[j][0]); } tc(ii); cout<