Hello world,codechef has judged the 5th problem(ALEXROSE) on DEC-16 long challenge,but nat yet published the Editorial,hoping they will publish soon
I respect your views, but I sincerely request to either mail codechef, or do something else. I don’t see anything positive coming out of posting it in discussion, and repeating it.
They will post it soon. I highly rebuke and disapprove the logic of “They are not posting the editorial = There is something malicious/dishonest which happened in it” . Problems are thoroughly tested and thought over. That’s why there are two codes, tester’s and setter’s code.
I know they may take some time to respond, but please refrain from posting and repeatedly posting such things on discuss forum. It does no good at all.
Hope I put across my views as gently and parliamentary as possible.
Hello Sir
in first case my Algo received 8 flowers with stems of 2 different heights 1 is 1000mm and 7 with 1000000000000000000mm
i need to prepare a bouquets of size 4 that means each bouquets should contains 4 flowers of same height
what the algorithm did is it creates one bouquet with 4 flowers with height 1000000000000000000mm for this no cut is required
now 3 flowers of height 1000000000000000000mm and one height 1000mm availabe
now to create second bouquet 3 cuts are required to form a bouquet with height 1000mm
therefore ANS=3
please correct me if iam wrong
@jawa2code Your solution is giving the wrong answer on test cases where all lengths are distinct.
**Input:
**
1
16 4
442 55 19 865 22 878 689 67 532 419 476 33 244 473 424 945
Correct Output: 12
And your solution’s output for this test case is 15 (link). The correct answer is 12, since we can form a bouquet of 4 roses by making the length of 3 roses equal to the 4th one.
Thanks a lot sir,for opening my Eyes
agreed but the delay in the editorial too unlikely
I am glad that things got sorted out. Special thanks to srd091
And jawa, editorials took long because (as many members suggested) of ACM ICPC contests going that time. Don’t worry, editorials should be out soon.
Hello srd091,please let me know test case to fail my code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
try {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
int n = 0, k = 0;
String key = null;
Integer value = 0, reqCnt = 0, demand = 0;
TreeMap<String, Integer> table = new TreeMap<String, Integer>();
HashMap<Integer, Integer> reqCntTable = new HashMap<Integer, Integer>();
String data[] = null;
for (int i = 0; i < t; i++) {
reqCntTable.clear();
table.clear();
data = br.readLine().split(" ");
n = Integer.parseInt(data[0]);
k = Integer.parseInt(data[1]);
data = br.readLine().split(" ");
if (k == 1) {
System.out.println(0);
continue;
}
for (int j = 0; j < n; j++) {
key = data[j].trim();
value = table.get(key);
if (value == null) {
value = 0;
}
value++;
value = value % k;
table.put(key, value);
}
Collection<Integer> boquey = table.values();
ArrayList<Integer> heights = new ArrayList<Integer>(boquey);
int hlen=heights.size();
Set keys=table.keySet();
Iterator iterator=keys.iterator();
String keyStr="";
while(iterator.hasNext()){
keyStr=(String) iterator.next();
demand = (k -table.get(keyStr));
reqCnt = reqCntTable.get(demand);
if (reqCnt == null) {
reqCnt = 1;
}else{
reqCnt++;
}
reqCntTable.put(demand, reqCnt);
}
long result = 0L;
int len = heights.size();
int freePool = 0, cpool = 0;
Integer available = 0;
int j = 0;
int bqCnt=0;
int reqAux = 0;
for (j = len - 1; j > 0; j--) {
cpool = heights.get(j);
reqAux = k - cpool;
available = reqCntTable.get(cpool);
if ((available != null) && (available >0)) {
int index=heights.indexOf(cpool);
heights.set(index, 0);
result+=cpool;
available--;
reqCntTable.put(cpool, available);
reqAux = k - cpool;
available = reqCntTable.get(reqAux);
available--;
reqCntTable.put(reqAux, available);
}else{
freePool += cpool;
bqCnt=freePool/k;
freePool=freePool%k;
result+=(k-1)*bqCnt;
}
}
bqCnt=freePool/k;
freePool=freePool%k;
result+=(k-1)*bqCnt;
result += freePool;
table.clear();
System.out.println(result);
}
} catch (IOException ex) {
}
}
}
=========================================================
@jawa2code Your code is still giving the wrong answer on this test case ([link][1]),
1
6 3
1 3 5 5 7 9
the correct answer is 3 as we can cut rose of length 9 to make it equal to 5 and cut roses of length 3 and 7 to 1, so the correct answer is 3.
[1]: wqXimZ - Online IDE & Debugging Tool - Ideone.com
Hello Soumya Raj Darbari,thanks a lot for helping me
I have made changes to solve different test cases but still failing
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
try {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
int n = 0, k = 0;
String key = null;
Integer value = 0, reqCnt = 0, demand = 0;
TreeMap<String, Integer> table = new TreeMap<String, Integer>();
HashMap<Integer, Integer> reqCntTable = new HashMap<Integer, Integer>();
String data[] = null;
for (int i = 0; i < t; i++) {
reqCntTable.clear();
table.clear();
data = br.readLine().split(" ");
n = Integer.parseInt(data[0]);
k = Integer.parseInt(data[1]);
data = br.readLine().split(" ");
if (k == 1) {
System.out.println(0);
continue;
}
for (int j = 0; j < n; j++) {
key = data[j].trim();
value = table.get(key);
if (value == null) {
value = 0;
}
value++;
value = value % k;
table.put(key, value);
}
Collection<Integer> boquey = table.values();
ArrayList<Integer> heights = new ArrayList<Integer>(boquey);
int hlen=heights.size();
Set keys=table.keySet();
Iterator iterator=keys.iterator();
String keyStr="";
while(iterator.hasNext()){
keyStr=(String) iterator.next();
demand = (k -table.get(keyStr));
reqCnt = reqCntTable.get(demand);
if (reqCnt == null) {
reqCnt = 1;
}else{
reqCnt++;
}
reqCntTable.put(demand, reqCnt);
}
long result = 0L;
int len = heights.size();
int freePool = 0, cpool = 0;
Integer available = 0;
int j = 0;
int bqCnt=0;
int reqAux = 0;
for (j = len - 1; j > 0; j--) {
cpool = heights.get(j);
reqAux = k - cpool;
available = reqCntTable.get(cpool);
if ((available != null) && (available >0)) {
int index=heights.indexOf(reqAux);
heights.set(index, 0);
result+=cpool;
available--;
reqCntTable.put(cpool, available);
reqAux = k - cpool;
available = reqCntTable.get(reqAux);
available--;
reqCntTable.put(reqAux, available);
}else{
freePool += cpool;
bqCnt=freePool/k;
freePool=freePool%k;
result+=(k-1)*bqCnt;
}
}
bqCnt=freePool/k;
freePool=freePool%k;
result+=(k-1)*bqCnt;
result += freePool;
table.clear();
System.out.println(result);
}
} catch (IOException ex) {
}
}
}
====================================================================
@jawa2code your code still fails where we can group roses of higher frequencies ([link][1]),
1
12 4
1 2 3 4 4 5 6 7 8 9 10 11
the correct answer for this test case is 8 while your solution is giving 9 as we can make the bouquet of 4 roses of the length of 4 (count=2), 4 roses of the length of 1 (count+=3) and 4 roses of length 8(count+=3), total count=8.
@jawa2code can you explain your approach.
[1]: ClX4Ql - Online Java Compiler & Debugging Tool - Ideone.com
Thanks a lot srd091,i have fixed that problem,but still it is giving WA,please help me
Hello srd091 this is the updates one
CodeChef: Practical coding for everyone
package practice;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
try {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
int n = 0, k = 0;
String key = null;
Integer value = 0, reqCnt = 0, demand = 0;
TreeMap<Integer, Integer> table = new TreeMap<Integer, Integer>();
HashMap<Integer, Integer> reqCntTable = new HashMap<Integer, Integer>();
String data[] = null;
for (int i = 0; i < t; i++) {
reqCntTable.clear();
table.clear();
data = br.readLine().split(" ");
n = Integer.parseInt(data[0]);
k = Integer.parseInt(data[1]);
data = br.readLine().split(" ");
if (k == 1) {
System.out.println(0);
continue;
}
for (int j = 0; j < n; j++) {
key = data[j].trim();
value = table.get(Integer.parseInt(key));
if (value == null) {
value = 0;
}
value++;
value = value % k;
table.put(Integer.parseInt(key), value);
}
Collection<Integer> boquey = table.values();
ArrayList<Integer> heights = new ArrayList<Integer>(boquey);
int hlen=heights.size();
Set keys=table.keySet();
Iterator iterator=keys.iterator();
Integer keyStr=0;
while(iterator.hasNext()){
keyStr=(Integer) iterator.next();
demand = (k -table.get(keyStr));
reqCnt = reqCntTable.get(demand);
if (reqCnt == null) {
reqCnt = 1;
}else{
reqCnt++;
}
reqCntTable.put(demand, reqCnt);
}
long result = 0L;
int len = heights.size();
int freePool = 0, cpool = 0;
Integer available = 0;
int j = 0;
int bqCnt=0;
int reqAux = 0,req=0;
for (j = len - 1; j > 0; j--) {
cpool = heights.get(j);
reqAux = k - cpool;
available = reqCntTable.get(cpool);
if((available != null)&&(available==1)){
available--;
reqCntTable.put(cpool, available);
req=k-cpool;
if(req<=freePool){
freePool-=req;
result += req;
continue;
}
}
if ((available != null) && (available >0)) {
int index=heights.indexOf(reqAux);
heights.set(index, 0);
result+=cpool;
available--;
reqCntTable.put(cpool, available);
reqAux = k - cpool;
available = reqCntTable.get(reqAux);
available--;
reqCntTable.put(reqAux, available);
}else{
freePool += cpool;
bqCnt=freePool/k;
freePool=freePool%k;
result+=(k-1)*bqCnt;
}
}
bqCnt=freePool/k;
freePool=freePool%k;
result+=(k-1)*bqCnt;
result += freePool;
table.clear();
System.out.println(result);
}
} catch (IOException ex) {
}
}
}
==================================================
Hello srd091,please test it,and let me know where it is failing
Hello Sir i am waiting for you response
Hello srd091 Please help me to know where it is failing
Hello srd091,please test my code
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
try {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
int n = 0, k = 0;
String key = null;
Integer value = 0, reqCnt = 0, demand = 0;
TreeMap<Integer, Integer> table = new TreeMap<Integer, Integer>();
HashMap<Integer, Integer> reqCntTable = new HashMap<Integer, Integer>();
String data[] = null;
for (int i = 0; i < t; i++) {
reqCntTable.clear();
table.clear();
data = br.readLine().split(" ");
n = Integer.parseInt(data[0]);
k = Integer.parseInt(data[1]);
data = br.readLine().split(" ");
if (k == 1) {
System.out.println(0);
continue;
}
for (int j = 0; j < n; j++) {
key = data[j].trim();
value = table.get(Integer.parseInt(key));
if (value == null) {
value = 0;
}
value++;
value = value % k;
table.put(Integer.parseInt(key), value);
}
Collection<Integer> boquey = table.values();
ArrayList<Integer> heights = new ArrayList<Integer>(boquey);
int hlen = heights.size();
Set keys = table.keySet();
Iterator iterator = keys.iterator();
Integer keyStr = 0;
while (iterator.hasNext()) {
keyStr = (Integer) iterator.next();
demand = (k - table.get(keyStr));
reqCnt = reqCntTable.get(demand);
if (reqCnt == null) {
reqCnt = 1;
} else {
reqCnt++;
}
reqCntTable.put(demand, reqCnt);
}
long result = 0L;
int len = heights.size();
int freePool = 0, cpool = 0;
Integer available = 0;
int j = 0;
int bqCnt = 0;
int reqAux = 0, req = 0;
for (j = len - 1; j > 0; j--) {
cpool = heights.get(j);
reqAux = k - cpool;
available = reqCntTable.get(cpool);
if ((available != null) && (available == 1)) {
available--;
reqCntTable.put(cpool, available);
req = k - cpool;
if (req <= freePool) {
freePool -= req;
result += req;
continue;
}
}
if ((available != null) && (available > 0)) {
int index = heights.indexOf(reqAux);
heights.set(index, 0);
result += cpool;
available--;
reqCntTable.put(cpool, available);
reqAux = k - cpool;
available = reqCntTable.get(reqAux);
available--;
reqCntTable.put(reqAux, available);
} else {
freePool += cpool;
bqCnt = freePool / k;
freePool = freePool % k;
result += (k - 1) * bqCnt;
}
}
bqCnt = freePool / k;
freePool = freePool % k;
result += (k - 1) * bqCnt;
result += freePool;
table.clear();
System.out.println(result);
}
} catch (IOException ex) {
}
}
}
Hello srd091,please let me know where it is failing
Sir, I would say that instead of posting code, if you can explain your approach/algo or include some comments in your code as such what that statement/variable/loop is doing, we will be able to help you better.
Because coding is quite weird in this sense. A programmer wouldn’t be able to understand HIS OWN code if he sees it after a month, (he wont be able to deduce what he did or thought while writing it if he includes no comment.)
Don’t take it in wrong sense, I admire your dedication to solving this problem alone for this long! Its really nice! But I would say, if you explain your approach, we might be able to give you the correct deductions/logic or even a correct code which will help you learn.
Cause if you get stuck with a problem, then its bad! It will take your time where you could solve many more problems which would make you learn many more things!
So, I will request, that if you find it agreeable, please explain how you are approaching the problem.
With Regards and Wishes.
Vijju/
Hello srd091 Thanks a lot
i have fixed that issues,it is working for some testcases tested,but still getting WA
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.Collection; import java.util.HashMap; import java.util.Iterator; import java.util.Set; import java.util.TreeMap;
public class Main {
public static void main(String[] args) {
try {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
int n = 0, k = 0;
String key = null;
Integer value = 0, reqCnt = 0, demand = 0;
TreeMap<Integer, Integer> table = new TreeMap<Integer, Integer>();
HashMap<Integer, Integer> reqCntTable = new HashMap<Integer, Integer>();
String data[] = null;
for (int i = 0; i < t; i++) {
reqCntTable.clear();
table.clear();
data = br.readLine().split(" ");
n = Integer.parseInt(data[0]);
k = Integer.parseInt(data[1]);
data = br.readLine().split(" ");
if (k == 1) {
System.out.println(0);
continue;
}
for (int j = 0; j < n; j++) {
key = data[j].trim();
value = table.get(Integer.parseInt(key));
if (value == null) {
value = 0;
}
value++;
value = value % k;
table.put(Integer.parseInt(key), value);
}
Collection<Integer> boquey = table.values();
ArrayList<Integer> heights = new ArrayList<Integer>(boquey);
int hlen = heights.size();
Set keys = table.keySet();
Iterator iterator = keys.iterator();
Integer keyStr = 0;
while (iterator.hasNext()) {
keyStr = (Integer) iterator.next();
demand = (k - table.get(keyStr));
reqCnt = reqCntTable.get(demand);
if (reqCnt == null) {
reqCnt = 1;
} else {
reqCnt++;
}
reqCntTable.put(demand, reqCnt);
}
long result = 0L;
int len = heights.size();
int freePool = 0, cpool = 0;
Integer available = 0;
int j = 0;
int bqCnt = 0;
int reqAux = 0, req = 0;
for (j = len - 1; j > 0; j--) {
cpool = heights.get(j);
reqAux = k - cpool;
available = reqCntTable.get(cpool);
int index = heights.indexOf(reqAux);
if ((available != null) && (available > 0)&&(index<j)) {
heights.set(index, 0);
result += cpool;
available--;
reqCntTable.put(cpool, available);
reqAux = k - cpool;
available = reqCntTable.get(reqAux);
available--;
reqCntTable.put(reqAux, available);
continue;
}
if(reqAux<=freePool){
freePool-=reqAux;
result += reqAux;
continue;
}
freePool += cpool;
bqCnt = freePool / k;
freePool = freePool % k;
result += (k - 1) * bqCnt;
}
bqCnt = freePool / k;
freePool = freePool % k;
result += (k - 1) * bqCnt;
result += freePool;
table.clear();
System.out.println(result);
}
} catch (IOException ex) {
}
}