# Part of GCPC2017 Problem Solution

C joyride

It is another wonderful sunny day in July – and you decided to spend your day together with your little daughter Joy. Since she really likes the fairy-park in the next town, you decided to go there for the day. Your wife (unfortunately she has to work) agreed to drive you to the park and pick you up again. Alas, she is very picky about being on time, so she told you exactly when she will be at the park's front entrance to pick you up and you have to be there at exactly that time. You clearly also don't want to wait outside, since this would make your little daughter sad – she could have spent more time in the park! Now you have to plan your stay at the park. You know when you will arrive and when you will have to depart. The park consists of several rides, interconnected by small pavements. The entry into the park is free, but you have to pay for every use of every ride in the park. Since it is Joy's favorite park, you already know how long using each ride takes and how much each ride costs. When walking through the park, you obviously must not skip a ride when walking along it (even if Joy has already used it), or else Joy would be very sad. Since Joy likes the park very much, she will gladly use rides more than once. Walking between two rides takes a given amount of time. Since you are a provident parent you want to spend as little as possible when being at the park. Can you compute how much is absolutely necessary?

It's another sunny day in July. You decide to spend time with your daughter joy, because she likes fairy Park in the next town very much. You plan to stay there for one day. Your wife (unfortunately she has to work) agrees to drive you to the park and pick you up. Oh dear! She's very tight with time, so she tells you the exact time when she'll arrive at the entrance to the park, and you'll have to be right there at that point. You also know that you don't want to wait outside, because it will make your daughter sad: she could have stayed in the park more! Now you have to plan your trip to the park. You know when you're coming and when you have to leave. The park contains several recreational facilities, and there are some trails connecting them. There are no tickets in the park, but it costs money to play a project. Because this is joy's favorite park, you already know how long it will take for each amusement facility to finish and how many tickets it will take. When you walk through the park, it's obvious that you can't skip the rides you pass because it makes joy unhappy. Because joy likes the park very much, she is happy to play with an amusement facility many times. Traveling between two facilities can also take some time. Because you are a farsighted parent and you want to spend as little money as possible in the park, can you figure out how many tickets must be spent?

Through the analysis of the theme map, we can conclude that there are two different schemes for each kind of amusement facility: playing once to play next or playing multiple times. Then two schemes can be extended naturally: memory search and shortest path of hierarchical graph.

How to understand memory search to solve this problem?

It can be assumed that the first dimension of the dp array is the location, the second dimension is the time spent, and the final state is the location 1, and the time spent is remaining. Then the whole graph is traversed by dfs, and each node is divided into two different schemes.

- Continue to search along the graph
- Repeat recursion of the current point

Finally, the answer to this question is to add all the recursive sub-answers to the initial state.

import java.math.*; import java.io.*; import java.text.*; import java.util.*; public class Main { static int connections[][]=new int[3250][3250]; static int dp[][]=new int[3250][3250]; static int MoneyCost[]=new int[3250]; static int TimeCost[]=new int[3250]; static final int INF=1000000007; static int ride,pavement,cost; public static int dfs(int CurrentLoc,int CurrentTime,int Tlimit,int Rlimit) { if(CurrentTime>Tlimit) return INF; else if(CurrentLoc==1&&CurrentTime==Tlimit)This is the initial state. return 0; else if(dp[CurrentLoc][CurrentTime]!=-1) return dp[CurrentLoc][CurrentTime]; else { dp[CurrentLoc][CurrentTime]=INF; for(int i=1;i<=Rlimit;i++) { if(connections[CurrentLoc][i]>0) { dp[CurrentLoc][CurrentTime]= Math.min(dp[CurrentLoc][CurrentTime],dfs(i,CurrentTime+cost+TimeCost[i],Tlimit,Rlimit)+MoneyCost[i]); } } dp[CurrentLoc][CurrentTime]= Math.min(dp[CurrentLoc][CurrentTime],dfs(CurrentLoc, CurrentTime+TimeCost[CurrentLoc],Tlimit, Rlimit)+MoneyCost[CurrentLoc]); return dp[CurrentLoc][CurrentTime]; } } public static void main(String args[])throws IOException { BufferedReader bf=new BufferedReader(new InputStreamReader(System.in)); String tmp=bf.readLine(); int remaining=Integer.parseInt(tmp); tmp=bf.readLine(); String tmps[]=tmp.trim().split(" "); ride=Integer.parseInt(tmps[0]);pavement=Integer.parseInt(tmps[1]);cost=Integer.parseInt(tmps[2]); for(int i=1,tmp3,tmp4;i<=pavement+ride;i++) { tmp=bf.readLine(); String tmps2[]=tmp.trim().split(" "); tmp3=Integer.parseInt(tmps2[0]);tmp4=Integer.parseInt(tmps2[1]); if(i<=pavement) { connections[tmp3][tmp4]=1; connections[tmp4][tmp3]=1; } else { TimeCost[i-pavement]=tmp3; MoneyCost[i-pavement]=tmp4; } } for(int i=0;i<=1250;i++) for(int j=0;j<=1250;j++) dp[i][j]=-1; int ans=dfs(1,TimeCost[1],remaining,ride)+MoneyCost[1]; if(ans>=INF) System.out.println("It is a trap."); else System.out.println(ans); bf.close(); } }

If the shortest path of hierarchical graph is used, the idea is similar to the memory search mentioned above. A two-dimensional array is used to store the results of different locations and different times.

import java.math.*; import java.io.*; import java.text.*; import java.util.*; import sun.misc.ObjectInputFilter.Status; public class Main { public static class Node { int next,to; public Node(int a,int b) { this.next=a; this.to=b; } } public static class Status { int CurTime,CurLoc; public Status(int a,int b) { this.CurTime=b; this.CurLoc=a; } } static final int INF=1000000007; static Node nodes[]=new Node[25000]; static int heads[]=new int[25000]; static int MoneyCost[]=new int[25000]; static int TimeCost[]=new int[25000]; static int distances[][]=new int[2500][2500]; static boolean inquiry[][]=new boolean[2500][2500];//Markup arrays also need to be open in two dimensions static int cnt=0,remaining,ride,pavement,cross; public static void construction(int from,int to) { nodes[cnt]=new Node(heads[from],to); heads[from]=cnt++; } public static void spfa(int threshold) { for(int i=0;i<=1230;i++) for(int j=0;j<=1230;j++) { distances[i][j]=INF; inquiry[i][j]=false; } Queue<Status> q=new LinkedList<Status>(); inquiry[threshold][TimeCost[1]]=true; distances[threshold][TimeCost[threshold]]=MoneyCost[1]; Status tmp6=new Status(threshold,TimeCost[threshold]); q.add(tmp6); while(q.isEmpty()==false) { Status cur=q.poll(); //System.out.println(cur.CurTime); inquiry[cur.CurLoc][cur.CurTime]=false; int nxttime=(cur.CurTime+TimeCost[cur.CurLoc]); //System.out.println(cur.CurLoc+" "+nxttime+" "+remaining); if(nxttime<=remaining) { if(distances[cur.CurLoc][cur.CurTime]+MoneyCost[cur.CurLoc]<distances[cur.CurLoc][nxttime]) { distances[cur.CurLoc][nxttime]=distances[cur.CurLoc][cur.CurTime]+MoneyCost[cur.CurLoc]; if(inquiry[cur.CurLoc][nxttime]==false) { Status tmp7=new Status(cur.CurLoc,nxttime); q.add(tmp7); inquiry[cur.CurLoc][nxttime]=true; } } } for(int i=heads[cur.CurLoc];i!=-1;i=nodes[i].next) { int nxt=nodes[i].to; int nxtTime=cur.CurTime+cross+TimeCost[nxt]; if(nxtTime>remaining) continue; else { if(distances[nxt][nxtTime]>distances[cur.CurLoc][cur.CurTime]+MoneyCost[nxt]) { distances[nxt][nxtTime]=distances[cur.CurLoc][cur.CurTime]+MoneyCost[nxt]; if(!inquiry[nxt][nxtTime]) { Status tmp9=new Status(nxt,nxtTime); q.add(tmp9); inquiry[nxt][nxtTime]=true; } } } } } } public static void main(String args[])throws IOException { BufferedReader bf=new BufferedReader(new InputStreamReader(System.in)); String tmp=bf.readLine(); remaining=Integer.parseInt(tmp); tmp=bf.readLine(); String tmps[]=tmp.trim().split(" "); ride=Integer.parseInt(tmps[0]); pavement=Integer.parseInt(tmps[1]); cross=Integer.parseInt(tmps[2]); for(int i=1;i<=2500;i++) heads[i]=-1; for(int i=1,a,b;i<=pavement+ride;i++) { tmp=bf.readLine(); String tmps2[]=tmp.trim().split(" "); a=Integer.parseInt(tmps2[0]);b=Integer.parseInt(tmps2[1]); if(i>pavement) { TimeCost[i-pavement]=a; MoneyCost[i-pavement]=b; } else { construction(a,b); construction(b,a); } } spfa(1); // for(int i=1;i<=6;i++) // System.out.println(distances[1][i]); if(distances[1][remaining]>=INF) System.out.println("It is a trap."); else System.out.println(distances[1][remaining]); bf.close(); } }

E plug it in!

Adam just moved into his new apartment and simply placed everything into it at random. This means in particular that he did not put any effort into placing his electronics in a way that each one can have its own electric socket.

Since the cables of his devices have limited reach, not every device can be plugged into every socket without moving it first. As he wants to use as many electronic devices as possible right away without moving stuff around, he now tries to figure out which device to plug into which socket. Luckily the previous owner left behind a plugbar which turns one electric socket into 3.

Can you help Adam figure out how many devices he can power in total?

Adam has just moved into his new apartment and put everything in a mess. This especially means that it does not organize all electronic devices into the case that each electronic device has plugs. Because the cable of this electronic device has power limitation, not every device can find its own socket. In his unwilling to toss about and want to find as many sockets as possible, he tries to find a solution which plug matches which interface. Fortunately, the landlord gave him an outlet, which allowed him to use one plug as three. Can you help Adam find the most number of appliances that can be connected to the circuit?

Typical bipartite graph matching, but this one is enhanced to match three points, so it is slightly different. As for how to achieve such a point when the three-purpose settings? If we enumerate the case of enlarging the capacity of each point by three times, it is very likely that the time-out will occur.

So a different way of thinking is not device matching plug, but plug matching device. When a plug is matched to three devices, the so-called triple expansion can be accomplished. As for the realization, we can directly match two more bipartite graphs for a certain point. (Since there are no more than two additional additions, jump out of the loop when the answer is updated to 2)

import java.math.*; import java.io.*; import java.text.*; import java.util.*; public class Main { public static class Node { int next,to; public Node(int a,int b) { this.next=a; this.to=b; } } static Node nodes[]=new Node[125000]; static int cnt=0; static int heads[]=new int[15000]; static int socket,device,connection; public static void construction(int from,int to) { nodes[cnt]=new Node(heads[from],to); heads[from]=cnt++; } static int matches[]=new int[125000]; static int secmatches[]=new int[125000]; static boolean inquiry[]=new boolean[125000]; public static Boolean Matching(int current) { for(int i=heads[current];i!=-1;i=nodes[i].next) { int nxt=nodes[i].to; if(inquiry[nxt]==false) { inquiry[nxt]=true; if(matches[nxt]==0||Matching(matches[nxt])==true) { matches[nxt]=current; return true; } } } return false; } public static void main(String args[])throws IOException { BufferedReader bf=new BufferedReader(new InputStreamReader(System.in)); String tmp=bf.readLine(); String tmps[]=tmp.trim().split(" "); socket=Integer.parseInt(tmps[0]); device=Integer.parseInt(tmps[1]); connection=Integer.parseInt(tmps[2]); for(int i=1;i<=socket+device;i++) heads[i]=-1; for(int i=1,a,b;i<=connection;i++) { tmp=bf.readLine(); String tmps2[]=tmp.trim().split(" "); a=Integer.parseInt(tmps2[0]); b=Integer.parseInt(tmps2[1]); construction(a,b); } long ans=0; for(int i=1;i<=socket;i++)//One-to-one matching { for(int j=1;j<=device;j++) inquiry[j]=false; if(Matching(i)==true) ans++; } for(int y=1;y<=device;y++) secmatches[y]=matches[y];Duplicate matching results //System.out.println(ans); long finans=0,tmpans=0; for(int i=1;i<=socket;i++) { for(int y=1;y<=device;y++) matches[y]=secmatches[y]; tmpans=0; for(int j=1;j<=2;j++)//Two more matches are made for a point. { for(int k=1;k<=device;k++) inquiry[k]=false; if(Matching(i)==true) tmpans++; } finans=Math.max(finans,tmpans); if(finans==2) break; } System.out.println(finans+ans); bf.close(); } }

I uberwatch

The lectures are over, the assignments complete and even those pesky teaching assistants have nothing left to criticize about your coding project. Time to play some video games! As always, your procrastinating self has perfect timing: Cold Weather Entertainment just released Überwatch, a competitive first person video game! Sadly, you aren't very good at these kind of games. However, Überwatch offers more than just skill based gameplay. In Überwatch you can defeat all opponents in view with a single button press using your ultimate attack. The drawback of this attack is that it has to charge over time before it is ready to use. When it is fully charged you can use it at any time of your choosing. After its use it immediately begins to charge again. With this knowledge you quickly decide on a strategy: • Hide from your opponents and wait for your ultimate attack to charge. • Wait for the right moment. • Defeat all opponents in view with your ultimate attack. • Repeat. After the game your teammates congratulate you on your substantial contribution. But you wonder: How many opponents could you have defeated with optimal timing? The game is observed over n time slices. The ultimate attack is initially not charged and requires m time slices to charge. This first possible use of the ultimate attack is therefore in the (m+1)-th time slice. If the ultimate attack is used in the i-th time slice, it immediately begins charging again and is ready to be fired in the (i + m)-th time slice

The seminar was over and the mission was completed. Even the annoying TA has no problem with your programming project. It's time to play a game! As always, procrastination is a good time for you: Cold Air has just released Uberwatch, a challenging first-person game. Unfortunately, you are not very good at such games. But uberwatch offers more than one game-based trick. In uberwatch, you can destroy all enemies by pressing a key to launch an infinite attack, but the disadvantage of this attack is that it has CD time. At the end of CD time, you can start skills at any time. Cooling immediately after skill use. With this little bit of knowledge, you can quickly come up with a magic trick: hide from the enemy until infinite attacks can be used, wait for the right time, repeat the above.

At the end of the game, your teammates all come to appreciate your tremendous contribution to the game you just played. But you want to know how many enemies can you get rid of with the best timing? This game can be seen as N periods of time, infinite attack at the beginning did not cool well, it takes M period to cool. The end of the first CD time is M+1 time period. If the infinite attack is used in the first time period, it immediately starts entering CD time and removes the CD again at the time of I+M.

There are obviously two different ways to deal with this problem:

The first is macro enumeration. Through the analysis, we can find that although the status of this topic is intermittent, on the whole, every state of using skills is transferred from the I-m state, so we can directly get the equation: DP [i] = max(DP[i-m],DP[i]).

The second is micro enumeration. That is to analyze the cooling time one by one, which is more cumbersome.

Let the first dimension be the time and the second dimension the cooling time. If the cooling time is analyzed, then the state transition equation will be DP[i][j]=max(dp[i][j],dp[i-1][j-1]), because there may be many different schemes to reach the state of dp[i][j], so when transferring the directly related state (when cooling the previous second). Also check the optimality.

Then it is to analyze the development of skills: fired or not fired.

If you fire, there will be such a state transition mode: dp[i][1]=max(dp[i][1],dp[i-1][interval]+enemies[i]), which means that the current state of firing and getting the number of enemies killed and the existing state is better than which.

If you do not fire, then there will be such a state transition mode: dp[i][interval]=max(dp[i][interval],dp[i-1][interval]), which is still better than the directly related state and the existing state.

import java.math.*; import java.io.*; import java.text.*; import java.util.*; public class Main { static int enemies[]=new int[350000]; static int dp[][]=new int[300900][12]; public static void main(String args[])throws IOException { BufferedReader bf=new BufferedReader(new InputStreamReader(System.in)); String tmp=bf.readLine(); String tmps[]=tmp.trim().split(" "); int n=Integer.parseInt(tmps[0]),interval=Integer.parseInt(tmps[1]); tmp=bf.readLine(); String tmps2[]=tmp.trim().split(" "); for(int i=1;i<=n;i++) enemies[i]=Integer.parseInt(tmps2[i-1]); for(int i=interval+1;i<=n;i++) { for(int j=1;j<=interval;j++) dp[i][j]=Math.max(dp[i][j],dp[i-1][j-1]); dp[i][interval]=Math.max(dp[i][interval],dp[i-1][interval]); dp[i][1]=Math.max(dp[i][1],dp[i-1][interval]+enemies[i]); } int ans=0; for(int i=1;i<=n;i++) for(int j=1;j<=interval;j++) ans=Math.max(dp[i][j],ans); System.out.println(ans); bf.close(); } }

C pants on fire

This problem belongs to closure transfer, and can be solved directly by improved floyd algorithm.

import java.math.*; import java.io.*; import java.text.*; import java.util.*; public class Main { static int value[]=new int[20000000]; static int cnt=0; static boolean dis[][]=new boolean[500][500]; static final int mod=19991126; public static void floyd(int limit) { for(int k=1;k<=limit;k++) for(int i=1;i<=limit;i++) for(int j=1;j<=limit;j++) { dis[i][j]=(dis[i][j])||((dis[i][k])&&(dis[k][j])); } } public static void main(String args[])throws IOException { BufferedReader bf=new BufferedReader(new InputStreamReader(System.in)); String tmp=bf.readLine(); String tmps[]=tmp.trim().split(" "); int n=Integer.parseInt(tmps[0]),m=Integer.parseInt(tmps[1]); cnt=0; for(int i=1;i<=n;i++) { tmp=bf.readLine(); String tmps2[]=tmp.trim().split(" "); int res1=((tmps2[0].hashCode()%mod+mod)%mod),res2=(tmps2[4].hashCode()%mod+mod)%mod; if(value[res1]==0) value[res1]=++cnt; if(value[res2]==0) value[res2]=++cnt; dis[value[res1]][value[res2]]=true; } floyd(cnt); for(int i=1;i<=m;i++) { tmp=bf.readLine(); String tmps3[]=tmp.trim().split(" "); int res1=(tmps3[0].hashCode()%mod+mod)%mod,res2=(tmps3[4].hashCode()%mod+mod)%mod; if(dis[value[res1]][value[res2]]) System.out.println("Fact"); else if(dis[value[res2]][value[res1]]) System.out.println("Alternative Fact"); else System.out.println("Pants on Fire"); } bf.close(); } }