redocyz's blog

By redocyz, history, 6 years ago, In English

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

Let's discuss the problems here after the contest.

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

| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Reminder: 1 more hour

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

GL & HF!

»
6 years ago, # |
  Vote: I like it -26 Vote: I do not like it

ez

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

can't submit more and says it ended even though still 30 min

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Why can I sometimes see a "not solved" sign for a hidden test set in the scoreboard?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I am guessing that happens when you submit something that pass subtask 1, and then after that submit something that doesn't.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Shouldn't they took the last submission that passes the subtask one?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have it:) My actions was

    1) 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)

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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.

»
6 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe you needed to cout.flush()?

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      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.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I've downloaded your solution and run it locally. It works fine on my laptop:)

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      :( something wrong with my laptop. Do you use windows(like me) or linux?

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ubuntu 16.04
        gcc version 5.4.0 20160609

»
6 years ago, # |
  Vote: I like it +13 Vote: I do not like it

What's the proof for task B?

»
6 years ago, # |
  Vote: I like it -14 Vote: I do not like it

I hated all the problems in the 3 rounds xD.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In my opinion, the last one from round1B was the best and I still can't solve it.

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Anyone sees why this code gets RTE on problem 1 large? Thanks in advance.

Code
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I used LIS for third problem Test Set 1, but got WA. :(

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    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.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, I know and my code passes this case.

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        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.

»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

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.

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it +11 Vote: I do not like it

    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.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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)

»
6 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

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!

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    aaaa abaa baaa bbaa aaba abba aabb aaab

    Here at each position all pairs are possible. But e.g. you can choose bbbb.

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      Perhaps I didn't make my approach clear enough, here's the code which passed that testcase link

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        So your code returns "-" but there are many solutions, e.g. BBBB.

        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Oh! so there's a solution to that! I assumed you meant that BBBB is a wrong output!

          Thanks for your feedback.

»
6 years ago, # |
  Vote: I like it +25 Vote: I do not like it

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.

»
6 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it

Problem A passes with randomized solution. Hunch paid off My Code

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    you don't even need randomize, a complete search would pass too as long as you break.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Break where exactly? I got a TLE on the hidden set with my complete search solution.

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        see this. I suspect you repeat searching the same character many times.

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it
»
6 years ago, # |
Rev. 4   Vote: I like it +4 Vote: I do not like it

Thanks for participating Round 1C, and congratulation to those in the top-1500 and qualified to Round 2. See you in Round 2! :)

I am the author of the first problem. I still find it amazing that the last sample case fits into a testcase, and one of the valid output (presented in the sample output) is a valid English word :')

Context: "Help I'm Trapped in a Factory" is a meme, and of course it's only a joke. I am not really trapped in a Code Jam factory. (and no one is; Google does not enforce anyone to work in Code Jam)

»
4 years ago, # |
  Vote: I like it -8 Vote: I do not like it

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 <iostream>
#include <map>
#include <algorithm>
#include <queue>
#include <list>
#include <string>
#include <cmath>
#include <stack>
#include <cstdio>
#include <fstream>
#include <climits>
#include <set>
#include <vector>
#include <tuple>
#include <cstring>
#include <functional>
#include <utility>
#include <iomanip>

using namespace std;



#define endl '\n'
#define f(k,a,b) for(int k=(a);k<(b);k++)
#define vi vector <int>
#define vvi vector <vector <int> >
#define   vii vector <pair <int, int > >
#define int long long
#define pii pair <int,int>
#define piii pair< pair<ll int,ll int>, ll int >
#define fsd fflush(stdout);
#define tdef typedef
using namespace std;


 int po2(int a){f(i,1,63){if((1LL)<<i==a)return i;}return 0;}
void tc(int i){cout<<"Case #"<<i+1<<": ";}
void yes(){cout<<"YES"<<endl;}
void no(){cout<<"NO"<<endl;}
void impb(){cout<<"IMPOSSIBLE"<<endl;}
int modinv(int a, int m){
	int m0 = m;
	int y = 0, x = 1;

	    if (m == 1)
	      return 0;

	    while (a > 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<<ans<<endl;
	}


	return 0;
}

Please do let me know some test case where this fails ( for C-small it self ) and what is the logic error here. Thanks in advance!