light42's blog

By light42, history, 9 years ago, In English

Can anyone give me recommendation of codeforces' past contest? What I need is some sort of contest where high mathematical analysis is required, even the easiest problem need some sort of understanding which people without higher mathematical experience will have a hard time to grasp it. Btw this is for my self-training.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By light42, history, 9 years ago, In English

Click here for the problem

At first sight, it seems that it can simply be solved using disjoint set ds. But the problem is more complicated because we handle two kinds of sets at once. Can anyone give a hint for this problem? (PS : I've already try to write and proof my solution for 3 days but still get WA. I suspect I didn't cover all the possible cases in the problem. And sorry if I'm not explaining my solution. It's too messed up I don't want to use it anymore.)

Full text and comments »

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

By light42, history, 9 years ago, In English

It's been roughly 2 years since I compete in Codeforces and even 4 years since I first dive into competitive programming. My problem solving skills indeed improved but not significantly. I tried my best to solve many problem as possible but those problems is quite hard to solve with my current skills right now. And yet there's 5 months left before next ICPC regional and there'll be new contestansts stronger than last year's from my country. I really want to go to WF even if it's only once before I quit and focus to became developer... But it's really hard. I'm tired...

Full text and comments »

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

By light42, 9 years ago, In English

Link to problem here

My method for solve this problem is to generate N^2 possible switch combination and from that combination we'll simply check if there's optimum solution. I pick this method because it's the most understandable way in the analysis and some coders use it and get acc. But my code still slow though (didn't pass 8 minute limit). I try to optimize the code but still too slow :(. Is there any way to optimize my code more?

PS: Sorry if this post is bad. This is the first time I'm posting codes(and sorry if my english is bad).

#include <cstdio>
#include <iostream>
#include <vector>
#include <climits>
#include <algorithm>
#include <set>

using namespace std;

#define LOOP(i,n) for(int i = 0; i < n; i++)

int T,N,Leng;
string outlet[200];
string devices[200];
int main()
{
	cin >> T;
	LOOP(i,T)
	{
		set<pair<string,int> > flipSwitch;
		set<string> dv;
		string dummy;
		int best = INT_MAX;
		cin >> N >> Leng;
		
		LOOP(j,N)
		{
			cin >> outlet[j];
		}
		
		LOOP(j,N)
		{
			cin >> devices[j];
			dv.insert(devices[j]);
		}

		LOOP(j,N)
		{
			LOOP(k,N)
			{
				string curr = "";
				int change = 0;
				LOOP(l,Leng)
				{
					if(outlet[j][l] == devices[k][l])curr += '0';
					else{curr += '1';change++;}
				}
				flipSwitch.insert(make_pair(curr, change));	
			}
		}
		
		for(set<pair<string,int> >::iterator it = flipSwitch.begin(); it != flipSwitch.end(); it++)
		{
			string flipIt = (*it).first;
			set<string> ot;
			LOOP(j,N)
			{
				string x = "";
				LOOP(k,Leng)
				{
					if(flipIt[k] == '0') x += outlet[j][k];
					else
					{
						if(outlet[j][k] == '1')x += '0';
						else x += '1';
					}
				}
				ot.insert(x);
			}
			if(ot == dv)best = min(best,(*it).second);
		}

		printf("Case #%d: ",i+1);
		if(best == INT_MAX)printf("Not Possible\n");
		else printf("%d\n",best);
	}

	return 0;
}

Full text and comments »

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

By light42, 9 years ago, In English

It's been roughly one week since two unusual rounds (round 294 and 295) been held. But no more round has been announced yet. Could anyone tell me what happened? I'm a little bit impatience about this XD.

Full text and comments »

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

By light42, 10 years ago, In English

Hi, I want to know how anyone feel right now about competitive programming. Are you feel lonely, happy, content, or desperate? Since I dive myself to the world of competitive programming the desperate feelings of not get any better always haunts me. I too sometimes feel lonely because I compete on my own. But despite of that, I really can't make myself quit. Because the competitive programming is so attractive. When I'm facing a problem there's a desire to solve it. And what a glad feeling when I already passed the problem. I want to be the very best in competitive programming, and I'll will not giving up on it. So what about you? Do you walk the same path as me? :)

Full text and comments »

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