Reminder: 1 more hour

GL & HF!

ez

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

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

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

What's the proof for task B?

I hated all the problems in the 3 rounds xD.

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

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<cassert>
#include<cassert>
#include<unordered_map>
#include<unordered_set>
#include<functional>
#include<queue>
#include<stack>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<sstream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<numeric>
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<typename T> 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<string> t(n);
		
		ttt.reset();
		
		for(int i=0;i<n;++i) {
			cin>>t[i];
			
			ttt.insert(t[i]);
		}
		
		set<char> Diff[l];
		for(int i=0;i<n;++i) {
			for(int j=0;j<l;++j) Diff[j].insert(t[i][j]);
		}
		
		vector<char> diff[l];
		for(int i=0;i<l;++i) for(auto j:Diff[i]) diff[i].pb(j);
		
		ll kulonbozo=1;
		for(auto i:diff) {
			kulonbozo*=sz(i);
		}
		
		if(kulonbozo==n) {
			cout<<"Case #"<<(cs++)<<": -\n";
			continue ;
		}
		
		vector<int> curr(l);
		
		string akt;
		for(int i=0;i<=n;++i) {
			akt.clear();
			for(int j=0;j<l;++j) akt.pb(diff[j][curr[j]]);
			
			if(!ttt.query(akt)) {
				break ;
			}
			
			curr[l-1]++;
			for(int j=l-1;j>=0;j--) {
				if(curr[j]==sz(diff[j])) {
					if(j>0) curr[j-1]++;
					curr[j]=0;
				}
			}
		}
		
		cout<<"Case #"<<(cs++)<<": "<<akt<<"\n";
	}
	
	return 0;
}

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

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.

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!

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.

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.

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

Scraped scoreboard for all rounds so far in GCJ 2018.

https://docs.google.com/spreadsheets/d/10q6bxqgnd0U9KNzGFvAl7Ik6kWZ8_wbfiUMRN-cJdXE/edit?usp=sharing

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)

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!